I just ‘finished’ the puzzle game TIS-100, meaning I wrote a code that solves the final task of the game and saw all of the plot (other than the hidden puzzle. I’m not ready to tackle that mentally), so please listen to me rant why this is probably my favorite puzzle game of the 2010s, if not of all time.
First of all: what is it? It’s a game that tells you that you inherited a weird old time-y computer from your missing uncle and are trying to run some debuggers on it to figure out what it is. It comes with an ancient looking manual and very little else. If it sounds like a mystery game, it’s cause it is.
(Throughout this post, feel free to click to embiggen the images)
The game is really about designing algorithms in the mathematical sense: converting inputs into outputs. To do so you’re given a pretty simple assembly language architecture with one feature, and one huge caveat. The feature is that you have access to multiple chips that all run in parallel and can talk to each other. The caveat is that each only has a single register that can do storage, math, and logic, and a second register that can only be used as long term storage.
Got it? Ok, so let’s go over a solution to a puzzle, or more precisely my thought process of solving one. Spoiler warning obviously, if you want to solve each one yourself, don’t read this.
The TIS-100 in later levels includes a ‘graphics’ module that allows you to display pixel data that is being sent to the output. The format is a string of integers formed as
( Starting X coordinate, Starting Y coordinate, <series of integers representing colors to draw 1 square of>, -1 )
In this task we are given a length of a line, then a color to use for it. We have to figure out how to wrap at the edge of the screen if the line is longer than the screen width. Here’s what the tasks look like, along with my initial solution:
So how does a guy who loves nothing more than clean logical order and Object Orientation handle this? Simple, by creating treating each node as a make-shift object. Let me walk you through the code above.
First, we got to keep track of where we are on the screen:
The upper circled node iterates from 0 to 30 (screen width), then sends that data to the right. It also sends either 0 or -1 down to the node that keeps track of rows. The row tracking node (circled below) returns it’s stored value, and whenever it receives a -1 it increments the stored value. So now we got a steady generator that spits out
(0,0), (0,1), (0,2) ... (29,0), (30,0), (0,1), (1,1) ...
Now we have to keep track of what color we’re on. We got a third node for that:
This one stores the length of a color and the value of the color, then by swapping those in and out of the long term register it decrements the length and constructs a little quad packet like (0, 0, 2, -1). That particular packet would draw a grey square in top left for instance. The node then passes this packet down into the chain of helper passing nodes and off they go to the output off the bottom row.
I make this sound trivial, but in reality it took the better part of an hour to come up with this solution, and then a better part of a second hour debugging a bunch of silly deadlocks and memory corruption mistakes (having two nodes get out of sync and wait for input from each other so that they hang indefinitely, forgetting to swap memory contents before displaying, stuff like that).
So what kind of performance do we get on that? Well, this:
Not great compared to the average other user. So now we get to the second part of TIS-100. Optimizing to compete with the ‘others’ of the internet. So how can we optimize this?
Well, first thing that jumps out at me is that the bottom right node seems to be sending stuff pointlessly far. Look:
It really doesn’t have to go that far. What if instead of going all the way around, it just goes right? Now the top right packet constructor will only do 3 of the numbers, and the node below him will just plug in the row number from the left as we go. That should skim off a cycle or two, no? And skim them off the innermost loops too. Always good.
So now we’re just going straight right, though we needed to add a tiny bit of logic to the right to build the packet. 3 cycles less per each loop. Nice.
We can do better though, can’t we. I mean, what if we reärrange the nodes so that instead of the top right node acting as a packet constructor the packet gets constructed “as needed” and only in the last moment. A Just-In-Time packet, if you forgive the borderline archaic term. It would require moving the two “storage” nodes to below the input and then setting up an assembly line to the right of them. And oh look, the output is already set up exactly in the perfect spot for it. Hm. It’s like the designers knew this.
So at time A the packet is (?, ?, Color, ?).
At B we get (X, ?, Color, ?)
And only at C do we get (X, Y, Color, -1)
Now, how much of an improvement do we get?
Down from 7684 to 4898, so 36%. Not too shabby considering all we did was move some nodes around. Now, if we really wanted to make this mother fly, we would use that feature that lets us create longer packets. I mean, why send
(0,0,1,-1), (1,0,1,-1), (2,0,1,-1), (3,0,1,-1), ...
When we can send
(0,0,1,1,1,1 ... 1,1,-1)
I mean, it can’t be that difficult can it?
And before you know it, you’ve sunk another few hours into TIS.