Tumblr isn't the place where i usually post about programming stuff, but i'm quite proud of this: as is often the case i've attempted to solve some of the Advent of Code in Brainf*ck, a minimalistic esoteric language, and this time around i've gone out of my way to use somewhat complex data structures:
Contribute to nicuveo/advent-of-code development by creating an account on GitHub.
I've also written a detailed explanation of how this works on Reddit:
I love advent of code, but my body doesn't agree that it is a good ideer to wake up at 6 the first days of december without also going earlier to bed. It is 12 days and not 24 this year so i will at least be able to regain my sleep saturday.
So, here's a little peek at the bullshit I've been up to the last couple days:
It's Advent of Code time, which is a series of programming puzzles that Some Guy puts out every December. I've been back on a TIS-100 kick lately, so I decided to see if I could solve the first day in there.
For those unfamiliar, TIS-100 is a programming game. It is not intended as a general-purpose language or environment, it is itself a series of programming puzzles that you have to solve with an incredibly esoteric and limited environment. It's a bespoke assembly language (which is the least human-friendly class of languages*) where you can only use numbers from -999 to 999, the only math operations you have are add and subtract, you have very limited memory, and doing anything complex requires coordinating message-passing between 12 independent "nodes" that are running their own tiny programs, and are only connected to up to four neighbors.
It's an absurd thing to use when trying to solve a problem designed with general-purpose languages in mind, but, when has that ever stopped me?
Anyway, after much shenanigans, I solved both parts of Day 1, entirely in unmodified TIS-100. It did require some preprocessing of the input and summing of partial outputs, since the game only lets you can only run 39 numbers through the system at a time, and the input for the puzzle was over 4000 lines long, but all the actual logic happened in the game. The Part 2 took 20 minutes to run its 2.6 million in-game cycles. Or 200,000, depending on how you look at it. More on that in a minute.
I put all the code up on my Advent of Code repo on GitLab, and I'll go through some of the more interest details of how I managed to get there under the cut.
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.
* Programming languages vary a lot, but generally they fall on a spectrum from "easy for a computer to read" to "easy for a human to read" - the human-friendly ("high-level") languages abstract away more of the complexity of what's going on under the hood, and thus the computer has to do more to translate them into commands it can actually execute. The computer-friendly ("low-level") ones represent more directly what's going on under the hood, so the computer has to do less work to translate, with the tradeoff of being much harder to read and write for humans. Assembly is essentially the lowest-level language that humans can interact with, and requires knowing a lot about exactly what the processor is doing underneath all those layers.
This one wasn't as difficult as I expected, especially after doing Day 2 part 2. I expected some kind of curve ball thrown in, like the edge case I talked about in my post for Days 1/2 but one never showed up for my implementation.
That being said, I definitely could have made a simpler implementation by pulling in an external crate (I'm using rust) but I like to try to use just what the language gives me before I do that. Iterators helped a lot but having chains of methods that span 25 lines or more (including multi-line closures) can look quite complicated. I definitely could clean up my code if I tried but at the end of the day, if it works, it works.
i have just enough programming knowledge for advent of code to be possible but too little for me to know how to do any of it elegantly so I'm just bashing my head against a wall until it works and man I'm having so much fun
