RogerBW's Blog

I did last year's Advent of Code, and had a lot of fun working on it. Spoilers.

In 2018 I started it in Rust to try to learn that, but it soon got beyond my ability to wrestle the language into doing what I wanted, so this time I went for Perl5.

The early problems were pretty straightforward, like taking a series of numbers, doing operations on them and then producing a total. Day 2 introduced "Intcode", a simple computer architecture, with (at this point) just add and multiply instructions, though it soon got more complicated.

Day 3 gave two views onto the same puzzle: given two wires starting from the same point and traversing a rectilinear grid, find (a) the crossing point closest to the start and (b) the crossing point with the lowest total length of wire. I particularly like puzzles like this which require multiple approaches to a broadly similar data set.

Day 5 was more Intcode, adding several more instructions to the specification, and introducing addressing modes (a parameter can now be a literal number, or the address of a memory cell from which the number should be fetched).

Day 6 was a tree puzzle, and it started to look familiar; I suspect one might be able to solve this with sufficiently clever use of git branches. But at least it wasn't full routefinding optimisation.

Day 7 required multiple Intcode machines talking to each other, and I brute-forced this by making them save their state to a file and calling them as independent programs. This was really the day on which I should have converted the Intcode interpreter into a module; as it was the solution took longer to calculate than it might have.

Day 8 was unexpectedly trivial: decoding an image format (multiple layers in which each pixel could be black, white or transparent, but since the layers are given top to bottom transparent is the same as "not yet defined"). I ended up using the Imager module to plot this, just for fun.

Day 9 finalised the Intcode specification with a "relative base" parameter mode (using a register as an offset), and this is the day I did set up an Intcode module rather than running it as a separate program.

Day 10 was fiddly; it involved working out whether entities offset on a rectilinear grid were at the same angle as each other. Given how finicky floating-point comparisons are, I ended up storing each angle as its two-dimensional tangent (x,y) – and then using the actual angular value only for sorting the distinct pairs into order.

Day 11 was another Intcode program used to draw a series of letters; this was mostly just a matter of interpreting the output, though an obvious error that cut off the bottom line of the result led to my wasting far too much time trying to guess answers.

Day 12 had an enjoyable mental transformation. In a system of N moons, each one accelerates towards each of the others, in a deterministic way (just +1, 0 or -1 to its velocity in each axis). The meat of this problem was determining when the cycle of positions/velocities would repeat – which would take far too long if one treated the cycle as a complete thing. However, if one broke it down into x/y/z cycles and took the lowest common multiple…

Day 13 was one of the more popular problems judging by other people's comments, but I found it oddly unsatisfying. Basically it's an Intcode Breakout game, with a complicated scoring system; but it's easy to write code to follow the ball with the bat and thus, eventually, clear the field. (My Intcode module halts with a status flag when it's waiting for input, which makes this kind of interaction quite simple.)

Day 14 was a problem of a sort I hadn't met before: given a system of processes of the form x A + y B → z C, determine how much of the ultimate input you need. I found this one of the most satisfying problems of the whole series, simply because I had never previously encountered anything of this type. (Having found how much input was needed to produce one output, the second part was to see how much output could be made from a set amount of input – not a question of simple scaling, because some of the stages produced an excess of intermediate product that could be used without consuming more of the input.)

Day 15 was therefore a slight let-down, because it rapidly became clear that what was needed was a breadth-first search of a maze. (And there weren't even any loops in the maze, which was disappointing.) This ended up taking advantage of my Intcode module by forking it: if I've arrived at a space in the maze from the east, I need to look north, south and west to continue the search, so each direction gets its own copy of the Intcode machine that got me this far (which is then thrown away once it's finished with). Getting a complete map of the maze, necessary for part 2, was just a matter of removing the terminating condition from part 1. Still fun, but more straightforward than 14 because the problem was of a more familiar type.

Day 16 is just sneaky. It starts off with a fairly straightforward calculation… but part 2 then increases the complexity to the level that no current machine will run it in anything like reasonable time. Of course, you can cheat (if the solution is in the second half of the sequence, which you know at the start it is, the factors are 1 1 1 1…, 0 1 1 1…, 0 0 1 1…). It's interesting as a challenge, and sometimes even a well-specified problem turns out to be susceptible to this kind of optimisation, but I found it frustrating in a way I don't usually associate with programming.

Day 17 was definitely getting into assumptions and short-cuts. Can I get away with a crude path traversal, assuming there are no T-junctions (thus "keep going straight forward if you can, otherwise it's a right-angle bend and you should turn in the direction that is open")? Yes I can. Given the set of movement instructions, can I reduce it to the necessary components by visual inspection rather than by writing an algorithm? Yes, that too.

Day 18 was just a slog. The method of solution was obvious, but the constraints meant lots of niggling optimisations to reduce memory use. The least fun so far.

Day 19 was a bit of a relief after that. Some functions wrapped round the intcode gave me an insideness check for any set of coordinates, and then it was just a matter of a stepped search (since we assume the function is well-behaved, i.e. always increases for increasing inputs) to avoid having to check too many of them.

Day 20: argh, yet another breadth-first search in yet another maze! But this one was a bit more interesting; the parsing of the labels was a very minor challenge in itself, part 1 meant adding a clause to the neighbour generation routine, and part 2 meant effectively moving into three dimensions.

Day 21: find the patterns, then write very limited code to match the patterns. Yeah, doable, but surprisingly lacking in fun.

Day 22: do the problem the simple way, then realise that this will absolutely not work then scaled up. (This is something of a recurring theme.) Which is fine, but I had enjoyed doing it the simple way; the second part is basically a number theory problem with an incidental computing implementation and I ended up throwing it at libgmp.

Day 23: a relatively easy one! My Intcode system already blocks while awaiting input, but can have input stacked up while it's idle, so I just loop over the list of machines dropping each output packet where it ought to go. Part 2 was barely harder than part 1.

Day 24 was day 20 all over again, except with not-Life. Part 1 was easy; part 2 was another slog.

Day 25 was a satisfying conclusion, though. An old-school (not going to spoil this), granted in simplified form but given what it's running on this is hugely impressive anyway, with a programming component used to solve the puzzle. (Could have done it by hand, but boring repetitive work is what computers are for.) And going back to read the comments now revealed for previous puzzles was fun too.

I've had a great time doing this, and I'll probably be back next year. Definitely recommended if you enjoy programming. (I never got onto the leaderboard, since the puzzles are released at 5am UK time every day, and lots of people are waiting for them; the best I did was on day 11 when I happened to be awake, and got the 171st answer.)