SignalChapter 11: Capstones

88FACTORS

The task

X is from 2 to 127. P must receive its prime factors from smallest to largest, then a 0.

So 12 sends 2, 2, 3, 0. t is an SC-4, with C and D, and h an SC-1, with only A.

o is an SC-2L: every instruction takes 2 cycles, for half the energy.

The board

The board as the puzzle screen lays it out. Cyan pins read, lemon pins write, violet pins go both ways. On a narrow screen, scroll the board sideways to see all of it.

Key idea

Trial division across three cores: a counter, a divider that keeps what is left, and a core that gets each factor back by dividing one remainder by the next.

Hints

Each hint goes a step further than the one before. Open them one at a time.

Hint 1Show

g can count from 2 up to X while t divides out each count that divides what is left.

Hint 2Show

t can tell o what is left after each division, and o divides one value by the next.

Hint 3Show

Once what is left is 1, t still has to read the counts g has not sent yet.

Solution

Reveal the Full SolutionThe complete program for FACTORS. Open it only when you want the answer.

The reference program

The game's own solution. It passes every test and scores exactly par on every benchmark.

hSC-1 lite

IN P0
OUT P1
OUT P2

tSC-4 quad

S: IN P0
MOV B, A
N: IN P1
MOV C, A
T: MOV A, B
MOD C
JNZ N
MOV A, B
DIV C
MOV B, A
OUT P2
SUB 1
JNZ T
W: IN P1
JNZ W

gSC-2 standard

S: IN P0
OUT P2
MOV B, A
MOV A, 1
L: ADD 1
OUT P1
SUB B
JZ E
ADD B
JMP L
E: OUT P1

oSC-2L low power

S: IN P1
L: MOV B, A
IN P0
XCH A, B
DIV B
OUT P2
MOV A, B
SUB 1
JNZ K
OUT P2
JMP S
K: ADD 1
JMP L

CYCLES: 3876; at par
ENERGY: 36141; at par
NODES: 4; at par
INSTRUCTIONS: 42; at par

Another way: Factors odd counts

A second program that also passes. It beats par on CYCLES and ENERGY and gives some back on INSTRUCTIONS.

Faster and less energy than par, for more instructions. g sends 2 and then only odd counts, and keeps the count less X in A so it never passes 999.