Advent of Code, day 23: The network is reliable

We’re almost there, just two more days to go. Yesterday’s puzzle was a difficult one. In fact, it is my first one I didn’t finish on the day I started it. Even worse, I have yet to get my second star. I guess my modular arithmetic needs some brushing up… So I was glad to see an easier puzzle today. And it was another IntCode one, the 11th time this year already.

After having repaired our ship, we now have to rebuild the network from scratch. There are 50 computers that are all running the IntCode program. They send each other packets using the output and input instructions. That sounds familiar, right? We’ve already connected 5 amps together. But the twist here is that any computer can send to any other computer, and more importantly, the in- and outputs are non-blocking. So how does my IntCode implementation hold up?

It’s all connected

As every year, I have chosen Python to implement my solutions. For me, the fun of Advent of Code is all about figuring out how to solve the puzzles, not to implement an efficient intersection of sets, or do yet another BFS search through a maze. So while my day job involves a lot of Go and Bash, for AoC I prefer something more expressive. And it’s very convenient to have libraries as networkx, numpy and itertools available.

My initial IntCode implementation for day 2 was quick and dirty, iterating over the integers and processing the opcodes as we go. That did the job nicely. Of course, I never expected I’d be needing this thing at least 10 more times.

Next up: day 5. That added some more opcodes, inputs, outputs and parameter modes (position vs immediate mode), explicitly stating that writes would never be in immediate mode. Of course my mind translated that into “writes will always be in position mode”. Inputs are static, so they can be hard-coded. And outputs can just be collected in a list, and be printed when the program completes. So far, so good.

Generators to the rescue

Then came day 7. Now we have five amplifiers running IntCode programs. The output of amp 1 needs to be connected to the input of amp 2, 2 to 3, etc. For part 1 that was no problem, since every amp waits for completion of the previous. Part 2 however, had a feedback loop. Computation was still sequentially, but the output of amp 5 had to be connected to amp 1. That means we have to pause computation of 4 out of 5 amps while we calculate the output of the fifth. My first reaction was, I should’ve done this in Go, then I just could’ve used channels and goroutines. Then I remembered Python also has a nice trick up it’s sleeve: generators.

Introduced in PEP 255, generators are a special type of function that return a lazy iterator. Meaning, you can iterate over the return values like you can with a list. But unlike lists, they do not store the entire contents in memory, only the state of the generator. And they also pause after getting the next() value, so they are ideal for our use case of the amps.

Writing generators is surprisingly easy. Just define a function like you would normally do, but instead of returning a value, you yield it. To give a simple example, this is an implementation of the Fibonacci sequence:

>>> def fib():
        a, b = 0, 1
        while True:
           yield b
           a, b = b, a+b
>>> f = fib()
>>> next(f)
1
>>> next(f)
1
>>> next(f)
2

This function will generate new Fibonacci number, every time next() is called.

So we can use generators for outputting the amps signal. So the outputs are provided using yield statements, while for the inputs we can still use a list, which is shared between amps. Problem solved!

6:00 AM

Day 9 introduced the last feature of our IntCode computer: relative mode. In relative mode, parameters behave similar to position mode, with one difference, the position they use is offset by an relative base. Easy peasy, right? Just add a relative base variable and use that when reading the parameters. Sure thing, the provided examples all checkout. All that’s left is to run it on my input, and submit the output: [203, 0].

Hmm… that doesn’t seem right, it should be a single value. Fast-forward 3 hours. After a discussion on Slack with several colleagues – who all seem to have run into the same issue – I’ve found the issue. Remember my brain stored “writes will always be in position mode”? Turns out relative mode also applies to writes… Just as the puzzle text clearly states. Reading is hard, especially at 6:00 in the morning. Even more so, because the text also says the IntCode program will output opcodes that seem to be functioning incorrectly. Completely missed that as well.

IntCode all the things

After day 9 the IntCode computer is now feature complete. That doesn’t mean it isn’t used in the following days. On the contrary, every other day we are presented with another IntCode program. In day 11 there’s a painting robot that will print the call sign of our ship. Day 13 has a fully functioning Arkanoid game (or Breakout, depending on your age apparently) game in just over 2000 instructions.

Day 15 has the input for a repair droid, that will eventually print a maze that we’ll need to traverse (yay networkx). Followed by a vacuum robot that takes and print ASCII characters as input and output in day 17. Two days later we get an IntCode program to control drones with which we can check if we’re in range of a tractor beam. And on day 21, there is another ASCII based program that shows the gaps a springdroid has to jump over. All those years of playing Super Mario finally pay off.

Don’t stop

Back to day 23. We have 50 IntCode computers, running in parallel, sending each other packets with non-blocking I/O. Turns out the 50 computers don’t really have to run in parallel, iterating over them will work just fine. The generator based implementation for the outputs is still working fine. But for the inputs we needed something else. Luckily Python has a counterpart to generators: coroutines.

Simple coroutines are introduced in PEP 342. They use the same yield keyword, but now on the right-hand side of an expression. When a coroutine encounters one of these yield statement, it will wait until it will receive a value via a send(value) call. To give a small example:

>>> def grep(pattern):
        print("Looking for", pattern)
        while True:
            line = (yield)
            if pattern in line:
                print(line)
>>> g = grep("python")
>>> g.send(None)  # Start he coroutine
Looking for python
>>> g.send("Yeah, but no, but yeah, but no")
>>> g.send("A series of tubes")
>>> g.send("python generators rock!")
python generators rock!

If you want to read more on generators and coroutines, read more in this excellent blog post.

So, my current (final?) IntCode implementation now uses both generators and coroutines to provide output and read input. So all that’s left, is to see what Eric Wastl has planned for us in days 24 and 25. Maybe one last addition to our IntCode computer? Don’t stop me now, ’cause I’m having a good time!