SignalChapter 11: Capstones

85FRACTION

The task

X is from -30 to 30 and Y from 1 to 30. P over Q must be X over Y in lowest terms.

P keeps the sign of X and Q is never below 1, so 0 over Y is 0 over 1.

e is an SC-2D: 10 lines, 3 cycle jumps. qy is an SC-2L: 2 cycles a line, half 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

Euclid in a loop of XCH and MOD B finds the divisor X and Y share; the sign of X has to stay out of the loop.

Hints

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

Hint 1Show

Divide X and Y by the largest number that divides both. MOD finds it fast.

Hint 2Show

In a loop of XCH and MOD B, the last value that is not 0 is that number.

Hint 3Show

Work on X without its sign, or the divisor can come out below 0.

Solution

Reveal the Full SolutionThe complete program for FRACTION. 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.

pxSC-2 standard

IN P0
MOV B, A
JG K
NEG
K: OUT P1
IN P2
XCH A, B
DIV B
OUT P3

eSC-2D signal processor

IN P0
MOV B, A
IN P2
L: XCH A, B
MOD B
JNZ L
MOV A, B
OUT P1
OUT P3

qySC-2L low power

IN P0
OUT P1
MOV B, A
IN P2
XCH A, B
DIV B
OUT P3

CYCLES: 1302; at par
ENERGY: 6225; at par
NODES: 3; at par
INSTRUCTIONS: 25; at par

Another way: Loop on px

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

Px runs the loop, where a jump takes 1 cycle, and e only keeps X and divides it. Faster than par, for more energy and instructions.

pxSC-2 standard

IN P0
OUT P1
JG K
NEG
K: MOV B, A
IN P2
L: XCH A, B
MOD B
JNZ L
MOV A, B
OUT P1
IN P2
OUT P3

eSC-2D signal processor

IN P0
MOV B, A
IN P2
OUT P1
IN P0
OUT P3
XCH A, B
DIV B
OUT P1

qySC-2L low power

IN P0
OUT P1
MOV B, A
IN P2
XCH A, B
DIV B
OUT P3

CYCLES: 1123; under par
ENERGY: 7161; over par
NODES: 3; at par
INSTRUCTIONS: 29; over par

Another way: Loop on qy

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

The low power qy runs the loop at half the energy, and e keeps Y for it. Less energy than par, for more cycles and instructions.

pxSC-2 standard

IN P0
MOV B, A
JG K
NEG
K: OUT P1
IN P2
XCH A, B
DIV B
OUT P3

eSC-2D signal processor

IN P0
OUT P3
IN P2
MOV B, A
IN P2
OUT P1
XCH A, B
DIV B
OUT P3

qySC-2L low power

IN P2
MOV B, A
IN P0
OUT P1
L: XCH A, B
MOD B
JNZ L
MOV A, B
OUT P1
IN P2
OUT P3

CYCLES: 1762; over par
ENERGY: 6045; under par
NODES: 3; at par
INSTRUCTIONS: 29; over par