#advent of code

Getting the Input In

TIS-100 is of course a game, and not intended as a general programming environment. There are emulators that are more general-purpose, but for the challenge, I wanted to stay as close to stock as I could.

The key is that it does let you write your own specifications (puzzles) with arbitrary input and expected output, so there was a way in. It doesn't make the output from the runs programmatically available in any way, but...well, we'll get there.

First, to get all 4000-plus inputs into the 39-slot input buffer, I first had to break them into bite-sized chunks. The specs are Lua scripts, but seemed pretty sandboxed, so I couldn't just read the file in there. Instead, I wrote a python wrapper script that did the chunking, then edited the specification on disk to inject each chunk as a Lua variable. After a run, TIS-100 updates the save file with some stats, so the python script watches the save file for modifications, and when a run finished and updated the save file, it injects the next chunk.

TIS-100 does notice when a specification is edited on disk and reloads it, so with the above that made it possible to run the program, go back to the specification list which triggers reloading the spec with the new input chunk that had been injected in the background, and then go back to the program and run it with the new input.

Getting the Output Out

The remaining problem was that the chunks were not independent - there was a bit of state (a single integer from 0-99) that needed to be preserved from one run to the next. The game is about outputting values, but as mentioned above, there's no way to access those values from outside the game short of screen-scraping, which felt a little against the spirit of things. Was there another way??

I soon realized that there is a sidechannel: that save file that I was watching to trigger the next input injection has, among the stats, the number of cycles taken by the most recent run of a spec. Inspired by things like timing attacks, I wondered: could I manipulate the number of cycles the run took in order to smuggle data out?

It was a very small bit of data: just the one number from 0-99, plus a partial count to be summed at the end, somewhere around 50-100 per chunk. That could easily be encoded into a 4-5 digit number, and my runs were already taking a few thousand cycles...

...the answer, reader, is of course you can! Allow me to introduce you to...

The Cycle Smuggler

this is the funnest part imo

Using just two of my precious twelve nodes, I implemented a system that idles for a set number of cycles, long enough for the rest of the program to process the most complex input chunk.

After the base idle, it takes in the output, (a 3-digit integer `m`) and idles for `100*m` loops, then takes in the state (a 2-digit integer `n`), idles for `n` loops, and immediately terminates.

The result of all of this is that given the base idle cycles, you can extract a 5-digit number `mmmnn` by taking the number of cycles that the program ran and calculating `(cycles - base_count)/3`, where 3 is how many cycles each loop takes - it could be 2, but I left it at 3 for debugging reasons. That number will be something like 12355, which is a count of 123 and a state value of 55.

So that's exactly what my script did: when the save file updated, it extracted the number of cycles taken, extracted the output and state, injected the state back into the input for the next run, and then at the end summed together all the output values to get the final answer.

Actually Running the Thing

After all that nonsense, as well as, you know, writing the actual TIS-100 program (which used 8 more nodes and a total of 119 instructions), I also added mouse emulation to my python script to automate starting each program.

In the end, I started the python wrapper, switched over to TIS-100, loaded the spec, and hit "run" - after that, the python script took over, sending clicks to initiate the next 183 runs, extracting all the partial counts from the cycle counts in the save file after each.

After 20 minutes or so, the script had chunked up all the input, logged its progress, and added up all the counts to get the answer, that I could - finally - put into AoC and cross my fingers.

As happens with AoC, I originally misread the instructions for Part One and actually started implementing what ended up being the solution to Part Two. So I left that node there but unused, and once I retooled it for the simpler version, I ran it with the sample input, then three sample inputs concatenated to test the multi-chunk setup. That all went well so I ran the full input and much to my delight and surprise, got the right answer on the first go!

Part Two was, of course, more hairy - I did have the head start but still had much message-passing to figure. I ended up with one logic bug, and one bug in how I handled the state being passed forward, and a third bug in my chunking up of the input where I tried to give it too many values (and thus dropped some). I first guessed too high, then too low, so I had narrowed the range to about 500, but of course that doesn't help much.

The last bug was the most annoying - I eventually threw some basic checksum-ish checks in the wrapper script, which revealed the dropped inputs, which was then easy enough to fix.

Another fun detail: while TIS-100's integer range of -999 to 999 was a perfect match for the puzzle data, TIS-100's _inputs_ are limited to -99. I ended up encoding e.g. -999 as the pair of (-1, 999), and then reconstruct the original number in situ.

A Footnote on Cycles

Also, the cycle smuggler was originally designed to idle for `n` repeats of a known base count, so that it wouldn't impose a minimum runtime penalty on the main program. But to be able to extract the values, the base count has to be higher than the maximum output value. In my case that was theoretically over 100,000, although in my input it was an actual maximum of 7700.

And thus, since the actual program took comfortably less than 7700 cycles, it was easier to just make it a constant base. I have been scheming ways to make a variable base work, but there's not really a reason to at this point.

So while it took 2.6 million cycles to get the result, that's a bit of a misnomer - most of that time is just idling for very specific amounts of time to smuggle values out. I don't know what the actual runtime was, but base cycle count (and thus maximum runtime) was 3810 cycles, so 184 runs of that would be about 700,000 cycles.

It does look like I got my base time close: running some inputs without the cycle smuggler, it looks like it takes on average about 1100 cycles, with ~3000 cycles max, so it was probably more like 200,000 cycles of actual processing time.