2019 was the fifth year of Advent of Code – and I consequently spent December waking up at 6AM and spending a lot of brain cycles solving puzzles to bring back Santa from the other side of the solar system, where he was stranded.

Let me quote myself to describe the whole thing to the people who are not familiar with it.  Advent of Code is an advent calendar with puzzles that can mostly be solved by programming: the input is a problem description and a user-specific input (as far as I know, there’s a set of a “few” pre-validated/pre-tested inputs), and you have to compute a number or a short string, and provide that as a result. If you have the correct result, you unlock a star and the second part of the puzzle, which allows to unlock a second star. Over the course of the 25 first days of December, you consequently get to collect 50 stars.

When I wrote my Advent of Code 2018 blog post last year, it was December 26th, and I had solved everything – this year it took me until yesterday (so, December 31th) before I got the 50th star. I don’t know if the problems were harder or if I got worse at solving them (maybe a mix of both?), but I still made it before the end of 2019, so I’ll count that as a win 🙂

This year, I worked in Kotlin, a JVM-based language designed by JetBrains, and that I enjoy quite a lot – it is fully compatible with Java, and allows for a much terser syntax, and requires to do things explicitly when it comes to mutability of variables and collections. I like it. My solution repository is on GitHub – beware, here be dragons… and spoilers!

And, like last year, let me give a few impressions of the different puzzles for this year. I WILL spoil the problems and at least hint at their solutions – if you want to start solving the problems with no preconception at all, you may want to stop reading here 🙂

Day 1 – as usual, pretty straightforward – you have a bunch of rocket modules with an associated weight, and you want to compute how much fuel you need, knowing the formula between the weight and the necessary fuel. Part 2 was slightly more interesting but still pretty straightforward – you realize you also need to account for the weight of the fuel of the modules, and for the weight of the fuel for the fuel, and and and. An easy start to start setting up the environment.

Day 2 – every year, there’s a problem that gets built on over and over again over the days – typically in the form of a small assembly language for which we build a small interpreter, and continue building on that. I think day 2 is the earliest it’s been introduced, and this year it was called Intcode; I will admit that I absolutely “played the meta” and made damn sure that the code I was writing would be reasonably easy to extend… and definitely took the time to write unit tests. Said unit tests had actually caught a few bugs before I ran my code on my input, so they allowed me to submit correctly on the first try – something I strive for 🙂

Day 3 – a problem about wires set on a grid, their crossings, and distances to these crossings. The first one where I read the problem, and felt the need to give it some thought – so I went to take my shower, thought of a first approach, dismissed it because of a corner case, re-read the problem, realized the corner case I was thinking about was not an issue. I wrote a few unit tests before leaving home, and solved the whole problem on my morning commute on the train.

Day 4 – a distinct disappointment. It was a small set of rules to implement on numbers – to be actually considered as strings – and it felt easy and not very interesting. On top of that, I was not working that day, so I would have had time for a more complex puzzle – hence, double disappointment!

Day 5 – as expected, the Intcode interpreter that we had started to implement on day 2 came back, with a couple more features. That’s where my relatively clean implementation of day 2 paid off – because I was able to finish both parts in the first 1000 people to finish. Very far from the leaderboard (it only considers the first 100 people), but still something I’m proud of (as of now, 44000 people have solved that day 🙂 ).

Day 6 – we get a set of objects in space that all orbit around exactly another object (except for one that doesn’t orbit around anything), and we’re asked a few questions about the system. To me, this was the first “somewhat algorithmic” problem of this year, in that knowing that the underlying structure was a tree and that I was consequently perfectly allowed to make some assumptions reduced my second-guessing to 0. Hence, I had solved the first part before leaving home, and had solved the second part halfway through my commute – and that felt pretty good.

Day 7 – that one was a “WELL THANK GOODNESS IT’S SATURDAY” because I had a bit more time. It was another Intcode problem – technically nothing new to implement, but needing to run a few interpreters in parallel and to feed the output of one to the input of another. Pretty fun, all in all, and I ended up looking into Kotlin’s coroutines and channels, which ended up being quite useful for the later days.

Day 8 – easy peasy, a very exotic (and profoundly inefficient) image format is described, and ends up describing an image that contains letters, that eventually are the solution for the puzzle. I would assume that, like every year, some people end up implementing an OCR to read the image – I’m waaaay to lazy for that 🙂

Day 9 – Intcode again, we start to see a pattern where we’ll get an Intcode-related problem every two days 🙂 It would have been straightforward if not for a mis-read of the problem, for which I lost quite a lot of time debugging code that was actually doing what I thought it was doing…. but what I thought it was doing was not what it should have been doing. But at the end of day 9, it’s official: we have a full Intcode interpreter. Also, note for next year: never ever use int where I can use long. Seriously.

Day 10 – geometry! I have a bit of a love-hate relationship with geometry – I think that I see and understand things pretty quickly, but that there’s a lot of fiddly bits that take me a shit-ton of time to get right. In this iteration, the first part of the problem was to find the point in a field of points from which most of the other points were visible; the second part gave a procedure to remove points and was asking which point was the 200th to be removed. The funny thing is that I got the first part fairly quickly (although with a disgusting n³ algorithm – I wonder if there’s a better way, and I would wager that there is), and fought quite a lot with the second part… until I realized I had a subtle bug in the first part that was counting the points correctly, but not the correct points. Once that one was solved, that gave me the second star – phew!

Day 11 – yet another Intcode problem, in which the input was an Intcode program yielding a pattern on a grid. That one made me grumble a lot at the beginning, because the input/output were not really compatible with what I was doing up until there; I finally realized I could make things work by inheriting my existing Intcode interpreter and modifying the input/output methods only. So in the end, everything went better than expected – and I ended up re-using that trick of inheriting the Intcode interpreter for specific purposes later during the month.

Day 12 – probably a few giggles at the title of the problem, “The N-Body Problem”. The input is a set of four moons, with associated positions and velocities, and a set of rules to explain how said positions and velocities evolve. So that was the first part, and that was pretty trivial. And then the second part… was more interesting 😛 The question becomes “okay, now, after how many cycles does this thing repeat? Oh by the way, for an example, this one takes 4 trillion steps before it repeats, so you may want to be a bit careful there”. That was the first time I picked my pen and paper, until I got the key insight; I think I almost had it a few minutes after arriving in the office, but had missed a small thing on the math involved, which made it a bit longer than it should have been.

Day 13 – odd day, Intcode day 🙂 This time the provided Intcode is… a Breakout game, for which the second part was “okay, it runs, now win the game and return the score”. Honestly pretty fun – I lost a bit of time with wrong assumptions, but otherwise I enjoyed it.

Day 14 – we get a set of “chemical reactions” for which a set of compounds (and their quantities) are combined to get another compound (and its quantity). In the first part, “how much of INITIAL COMPOUND do you need to produce one unit of FINAL COMPOUND”; in the second part, “now you have X INITIAL COMPOUND, how much FINAL COMPOUND can you produce?” (and obviously, left-overs of compounds don’t make it a matter of simply multiplying the result of the first part :p). Exactly my preferred type of puzzle, a bit of algorithmics that’s not too fiddly to implement, a part 1 that helps part 2 in an “easy but non trivial way”… I really enjoyed that one 🙂

Day 15 – up for Intcode? Well, that’s a good thing, then 🙂 The provided Intcode program allows to explore an unknown maze, by saying “in this direction, I hit a wall… or not” – with the objective of finding an item in the maze. I thought that it was neat, and it really felt like the Intcode was a cool way to provide inputs in ways that are not trivial to parse for a human (instead of just providing the maze as ASCII with walls, which would make the whole thing much easier!).

Day 16 – that one made me grumpy. The first part was trivial (get input, apply repeating pattern, get first digits of repeating pattern), and the second part was confusing, worked with a trick that was input-dependent, and generally speaking… yeah, the grumps.

Day 17 – Intcode again, and my best score overall on the leaderboard, since I was the 711th to get the second star! It was also a bit weird, because I ended up solving it mostly by hand – typically not something I’d consider, because it’s usually far more painful to solve things by hand than to program a solution, but in this case… The first part used the Intcode to provide map in which a robot had to move around. The second part needed us to program the robot under a set of constraints (which essentially required the program to be “small enough” to fit in the memory of the robot). The I/O were also somewhat confusing – but I did manage to build on previous “oh, I need to inherit my initial thing and handle I/O that way”, and to also see how I/O was done there (which was important for the following days as well).

Day 18 – MY NEMESIS. I did literally spend tens of hours on that problem, and it was the one that kept me occupied until yesterday evening. The problem is beautifully simple: you have a maze with keys, you want to collect all the keys in the least possible steps, and each key unlocks exactly one door that may or may not be on the path to other keys. I stopped the execution of my first attempt after a few minutes, I tried another approach that was even slower, and after a lot of sweat and tears finally arrived at something that ran the first part in ~90 seconds (a bit slower than I would have liked, but oh well), which ended up being fairly close to the first attempt, although slightly optimized. The second part started scarier, and for my first attempt at solving it, I played a whole Pandemic game with my family before I shut down the execution (that hadn’t returned yet); for the second attempt I went full YOLO, I’m 90% confident that some cases would NOT be covered by what I did, but it did work on my input, so….. (And I got the second star of day 25 in the following 20 seconds, with a large sigh of relief.)

Day 19 – after the blood, sweat and tears that was day 18, the relatively easier day 19 was somewhat of a relief. The Intcode program defines, for points in a 2D space, a continuous area; the first question was to know how many points were hit by that area in a small zone, the second question was to find the first point at which a larger square was fully contained in said area. A bit of geometry – the fairly easy kind – and/or search in a 2D grid – it would have been solved MUCH FASTER if not for a bloody stupid off-by-one that took me ages to debug.

Day 20 – the first part was a maze with a twist (namely, portals to go from one part of the maze to the other); the second part was a maze with a twist… and some recursive structures going on. Pretty straightforward, fiddlier than I like, but still pretty neat.

Day 21 – the Intcode of the day takes as input a small program that tells a small robot to either continue or jump, and that tries to navigate over a platform full of holes. It felt way more like a logic puzzle than a programming puzzle, but oh well, it was still pretty fun. Took a while to get part 2, though, because the logic puzzle was “same one, but harder” for part two 😛

Day 22 – another one of my nemesises. The first part was trivial – you get a deck of cards, a set of operations to shuffle them, and you’re asked where is the card 2019 at the end of the shuffle. The second part made me draw a blank for a long while, in terms of “…. okay, I have literally 0 idea how to handle that” – the deck is now several hundred trillions large, and the operations are also performed several hundred of trillions of times…. okaaaaaay! I ended up (re-)learning a lot of things about modular arithmetic, and finally solving it. That was… interesting 😛

Day 23 – okay, that one was lovely 🙂 The Intcode program is used handle little network adapters that send packets back and forth to each other, and you need to handle that properly, restart the network from time to time, and so on. I enjoyed it a lot, although my solution is PROBABLY way more hacky than it needs to be (and PROBABLY relies more on timings than it should).

Day 24 – the first part was a small finite automaton on a finite grid – Game of Life-like, and nothing too problematic. Part 2 was way more head-scratching, mostly because it took me a long time to ACTUALLY understand the text – I had made assumptions that were wrong and it took me a lot of time to get rid of them. I quite like it, though – although my final code could probably have done with a bit of refactoring to get rid of a lot of unnecessary computation.

Day 25 – that one literally made me squee 🙂 The provided Intcode is a small text adventure game (à la Zork) that you need to solve to get out. I could have handled keyboard input and solved it by hand, but I found it much more interesting to build a small solver for it. My solver had a couple of hard-coded things in it still (which is a bit sad, but I decided I could live with it), and it took me a long while to see that my code was actually spewing the answer at some point (but that I was missing it because I wasn’t looking for it at the right place…) – but that was absolutely lovely.

All in all, I enjoyed this iteration of Advent of Code – I think I got more frustrated by a couple of problems than I had in previous years, but I’m still super happy that I made it through the whole thing. I really liked the fact that Intcode was used as an input for many puzzles – I found that it was a nice touch, and that it possibly made for more interesting puzzles too, since it allowed for a bit of “exploring” puzzles.

And since I did finish before the end of 2019 – although barely – let me also use this blog post to wish you all a very happy new year!