BasketMC

Sequence Indexer, Episode 15: TIS-100

  • Published on

Episode 15 opens the Sequence Indexer, a puzzle that asks for numbers looked up by position in a list. Basket pours the list into a stack memory node, writes a lookup that counts the index down, and finds out which order the stack gives numbers back in. It is not solved by the end.

A list and an index

The segment map shows Signal Window Filter and Signal Divider as nominal. The Sequence Indexer panel reads: "Sequences are zero-terminated. Read a sequence from IN.V. Read index values from IN.X. Look up index value in sequence. Write indexed value to OUT." The grid has two stack memory nodes in the second column, IN.V over the first column, IN.X and OUT on the third, and a red communication failure node in the top right.

The plan on the recording is to put the whole sequence into the stack first and wait, "because if I start doing stuff right away, I'm going to be indexing the wrong thing."

TIS-100 Sequence Indexer puzzle with every node empty: the task panel says sequences are zero-terminated, read a sequence from IN.V, read index values from IN.X, look up the index value in the sequence and write it to OUT. Two stack memory nodes sit in the second column and a red communication failure node in the top right corner.

Building the lookup

The top left node moves each value from IN.V into the stack with "MOV UP ACC" and "MOV ACC RIGHT", loops while the value is above zero, and sends a 0 down at the end. The node under IN.X starts with "MOV DOWN NIL", so it holds the index values back until that signal arrives. The center node does the lookup: it saves the index with SAV, takes a value off the stack and swaps. If the index is still above zero it jumps to DONTSEND, runs "SUB 1" and puts the value back on the stack. At zero it sends the value on toward OUT.

"We're going to run out of space pretty quick, aren't we?" A "MOV 0 RIGHT" goes in at the top of the first node to preload a zero, "so we have a zero on both sides."

TIS-100 editor in Sequence Indexer: the top left node starts with MOV 0 RIGHT and feeds the stack memory node beside it, and the center node holds a lookup loop with SAV, SWP, JGZ DONTSEND, MOV ACC RIGHT and DONTSEND:SUB 1.

Zeros in the wrong place

The first run locks up. The next gets through several index values, but the first answer on OUT is a red 0 where 860 is expected. Basket steps through one instruction at a time: the index goes to BAK, and the inner loop takes a zero off the stack. "For some reason I was thinking it was on the other side." The sequence's closing zero was going into the stack too. The top node gets "JEZ DONE", and "DONE:MOV 0 DOWN" sends the signal without pushing that zero.

TIS-100 running test 1 of Sequence Indexer: the top stack memory node lists the sequence from 860 down to 697 with a 0 at the end, and the OUT column shows a red 0 beside the expected 860.

Last in, first out

Before the next run, the commentary expects it to be wrong "because of the way these values are stored in here." Asked for index 0, the program sends 697, the last number of the sequence, where 860 should be. The commentary thinks about turning the list around through the other stack node, then settles what the stack is doing: "It's not first in first out. It seems like it's first in last out. Well that complicates things."

TIS-100 running test 1 of Sequence Indexer: the top left node now has JEZ DONE and DONE:MOV 0 DOWN, the stack memory node holds 0 and 860 through 432, and the OUT column shows a red 697 beside the expected 860.

Where it ends

"Let me ponder some more, and then I will return." The video fades to the end card at about 23 minutes, with the Sequence Indexer still unsolved.