SignalChapter 6: Trees

42HEAP CHECK

The task

X is the top of a heap with Y and Z under it, and W is under Y.

P must receive 1 when no value is larger than the one above it, else 0.

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

Values go down a tree on bi wires and 1 or 0 answers come up and combine.

Hints

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

Hint 1Show

Send each value down to the core below so it can compare.

Hint 2Show

Answer up the same wire with 0 for fine and a negative number for not.

Hint 3Show

Y passes on what W said only when Y itself is fine.

Solution

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

aSC-2 standard

IN P0
OUT P1
OUT P2
IN P1
MOV B, A
IN P2
ADD B
JZ U
MOV A, -1
U: ADD 1
OUT P3

bSC-2 standard

T: IN P0
OUT P2
MOV B, A
IN P1
SUB B
JL N
IN P2
OUT P1
JMP T
N: OUT P1
IN P2

cSC-2 standard

IN P0
MOV B, A
IN P1
SUB B
JL O
MOV A, 0
O: OUT P1

dSC-2 standard

IN P0
MOV B, A
IN P1
SUB B
JL O
MOV A, 0
O: OUT P1

CYCLES: 608; at par
ENERGY: 7722; at par
NODES: 4; at par
INSTRUCTIONS: 36; at par