In the past few years, December has been for me “the month of Advent of Code”. 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.

I like the puzzles, I like the fluff around it (typically a more-or-less-sensical story around the Christmas theme), I like the duration and effort involved, I like that I learn something every year – all in all, I’m a fan 🙂 There’s a “global leaderboard” that tracks all the users who are in the first 100 to solve each puzzle; although I’m on a “favorable” timezone for the puzzles (they come up at 6am for me), I have no hope of ever scoring points on the leaderboard; my claim to fate this year is that I was in the first 1000 players for 11 stars out of 50 🙂

This year, as last year, I solved the whole thing in Go; my Go is still quite bad, probably not-a-all Go-like, and I tend to try to avoid spending too much time second-guessing and refactoring my code in that kind of contexts (it’s good training against analysis paralysis 😉 ), and it’s available on my GitHub if you’re not afraid of bad code and spoilers 🙂 (Oh, and also: truly horrifying code organization.)

After this general introduction, I want to talk a bit about my experience of the individual problems, so beware: spoilers ahead!

Day 1 and 2 are, as often, the easiest problem of the month – barely a warm-up, and also an opportunity to check that the tools are installed and that you can actually solve them. As it happened, my IDE was not installed yet since I had changed my desktop (I use GoLand), so I did that 🙂

Day 3 – given rectangular pieces of fabric that can overlap on a 2D grid, find the single piece of fabric that’s not overlapped by any other. Still pretty straightforward. I did bruteforce it violently (by checking if every pair of fabric pieces intersect), and there’s probably faster/cleaner ways of doing that, but considering the size of the problem, I didn’t invest the time for it.

Day 4 – given a list of (unsorted) dated and timed events, find times at which some events have the most probability of happening, depending on two different criteria. It was the first one on which I spent a significant amount of time, trying to debug my code for a fairly long time before I realized I had misread the problem >_< I also made my life significantly harder by deciding to Not Sort The Data First – which meant I learnt how to parse dates in Go, mostly 😛

Day 5 was a matter of cancelling out elements in a string (two characters in a row are cancelled if and only if they are the same letter, but not the same case; if such a cancellation triggers a new cancellable pair, this one is cancelled as well). My solution was profoundly ugly and was basically bruteforcing the whole string until no modification was done on the string (which was … yeah, ugly); after discussing it with a colleague after the fact and trying to shave off time on the whole thing, I ended up re-implementing it with a stack representing the string, and popping elements as they cancelled out (which was DEFINITELY a better way to tackle the problem), and I’m consequently slightly less ashamed of my solution 😉

Day 6 was a geometrical one. Given a set of points, the goal was first to find the largest non-infinite area that was closest to a single of these points; the second part was to find the area that was “close” to a maximum number of points. I found it quite fun. For the first part, the key was to see that on a “large enough” grid, the set of “infinite” areas was exactly the set of elements on the border; and that still the “large enough” grid was small enough to brute-force in a reasonable amount of time. For the second part, I made the hypothesis (thinking, at the time, that if the hypothesis didn’t hold I could revisit it) that a/ the region I was looking for was a single connected component and that b/ it contained one of the initial points; from there I got a first point and explored around it, and it was apparently enough.

On Day 7, the concept was a series of tasks that all had dependencies against each other, and the goal was to find an ordering of the tasks. I felt quite smug, because I read the problem, went “okay, it’s just a topological sort“, implemented it, and that was it. Then I saw the second part of the problem – tasks now take time, and I have 5 elves that can work the tasks – and swore a bit 😛 I did have a bit of a fumble on the problem text again (I did go for “select task first, elf second” whereas it was a “select elf first, task second” process), but the whole thing was fun to work out 🙂

Day 8 had a recursive, flattened structure, and it required some computation over the integer values of said structure. I made my life quite difficult, because I worked out a recursive algorithm on the flattened structure, instead of handling the recursive data structure and be basically done. Still, in the “realizations that come during Advent of Code”, there’s the fact that I do tend to be far more “algorithm-biased” than “data structure-biased”, which probably makes my life harder more often than not. Which was an interesting realization and one that may become quite useful in a much more general context.

Day 9 was a matter of inserting elements in a ringed list and see what happens after some iterations. It was half-spoilt to me – my implementation the first part used an array list, and was running in O(n²)… which was not really an option in the second part of the problem. I thought I had found a closed form of the problem, but it failed (I’m not sure if there exists a reasonable closed form to that thing); a colleague mentioned “linked-list” to me, and that was actually enough to spoil it. A bit sad, and mostly I was VERY, VERY annoyed that I didn’t think of it myself faster than that, but that’s life 🙂

Day 10 started with positions and velocity vectors that would eventually draw words. It was in my opinion not very interesting – just a matter of running the pixels until you get the smallest height, read the characters, and you’re done. I could have made it more interesting (I guess) by reading the characters programatically as well, but oh well.

Day 11 was basically computing values on a grid and computing the sum of these values for smaller or larger parts of the grid (3×3 for part A, arbitrary from 3×3 to 300×300 for part B). Part B ended up being surprisingly interesting 🙂 The brute-force algorithm runs in O(n⁴) and you can get it down to O(n³) without too much effort (and that’s actually enough to a get reasonable running time). But then we had a fairly long discussion with a colleague about the exact running time of two ways of implementing that solution, and it was very nice to work out the exact time and space complexity of what we were thinking about. (For the record: both our solutions were running in similar time, but mine took twice as much memory. Damn!)

Day 12 was a 1D infinite cellular automaton simulation, where the rules for the automaton were the input. The first part was easy (what’s the result after 20 iterations); the second part was a bit more challenging – simulating things for 50 billion iterations is PROBABLY not something one would want to brute-force. I must admit I always have a twinge of disappointment when the solution of the problem highly depends on the input data (the input data yields a pattern, recognizing the pattern and getting the closed form was the point there) – but it’s definitely part of the game, and should be expected.

Day 13 gave circuits (crossing rectangles) as an input, on which carts were moving, and the idea was to look at the collisions between these carts. I hated it with a passion – kidding, almost: I’m REALLY BAD at differentiating left and right, and I’m not too good with 2D grids either (although I’m getting better thanks to AoC) (no, really), and it took me much more time than I think it should have to find how much the carts were colliding with each other. That’s the first problem that took me more than 24h to solve.

Day 14 was far more straightforward – string generation according to certain rules, get the last elements after X iterations, get the N iterations after which a given substring is in the generated string. I’m quite ashamed at the time it took me to actually get the correct stop condition for part B (grmbl grmbl off by ones and not thinking clearly) – it shows by the fact that I had solved part A in less than 75 minutes after the publication of the problem, but part B took me until the next day.

Day 15 made us implement a small simulation of fights between elves and goblins, giving rules for movement and fight and looking at what was the outcome of a large fight. I believe that it was quite controversial – for sure it was one of the longest to implement, there was a lot of rules and a lots of moving parts to get correctly before arriving at the solution. I still enjoyed it, because I quite liked the idea that, at the end of the problem, I had the very basic blocks of a small game, which was fun 🙂

Day 16 gave us a small assembly language, and asked us to deduct the instruction codes for each instruction, given inputs, outputs and instructions. It was another take on “here’s a small assembly language, Do Stuff with it” (if I remember correctly, it was more of a thing last year); this time it was a fun exercise in reverse-engineering, and I enjoyed that a lot.

Day 17 was one of my favorites this year – the point was to fill 2D buckets with water falling from the top. It felt elegant and nice and it was pretty easy to represent things graphically; if anything, I’m a bit disappointed that Part B was basically given when you had implemented Part A with the full information without taking shortcuts.

Day 18 was another cellular automaton, but on a finite grid this time. The rules were fixed, but the input was user-dependent. Very similar concept to day 12, and same slight twinge of disappointment that the feasibility of the puzzle depends so highly on the initial data.

Day 19 went back to the assembly language, adding a small subtlety to it (the handling of the instruction pointer – I can’t remember how that one was handled last year). Part B was essentially “finding out what that code was actually doing in a fairly inefficient way” in order to either give the answer directly (which I did) or to re-code a better version of it for arbitrary inputs (which would have been better, but oh well 🙂 ).

Day 20 gave us a regexp describing possible paths in a labyrinth; the point was to re-create the labyrinth and then see which spots of the labyrinth were far away from the start. I found this one super-fun : the basic concept made me smile, and it was also pretty fun to implement and generally speaking a fun puzzle. Part B was straightforward, given the graph built in Part A.

Day 21 was further reverse engineering of some assembly code doing SOME operation, and trying to make things work; this was pretty fun to hack in my opinion 🙂

Day 22 was a maze in which your state (handling a torch, climbing equipment, or nothing) impacted the rooms you can enter/be in, and changing equipment took some time (and wanting to reach some point fast). All in all, pretty straightforward, just create the correct graph, run Dijkstra on it, be done.

Day 23 had a set of 1000 “balls in Manhattan distance” (so, generally speaking, octahedrons) in a large 3D grid, and the goal was to find the point hit by the majority of these balls. It has definitely been the problem which made me sweat the most. I first vaguely tried to bruteforce it (not a good idea, problem too large) – and then I also had a moment of brain fart by considering “cuboids” instead of “octahedrons” (oops). I tried to sample it regularly, and I couldn’t get the right spot between “reasonable sampling” and “reasonable performance”. I did a first attempt at splitting my space in octrees, and it ended up being still slow as hell. I tried to sample it at random, and I hit a local max that was probably larger than my area. I went back to the octrees, thought a bit more about the exact conditions of the problem and how to do things fast (in particular, checking if my octree parts and my octahedrons intersected), and I was finally able to give the answer. That one did take me a large part of four days before I was finally able to solve it.

Day 24 was back to “somewhat straightforward”: two sides of a battle choosing targets and trying to kill them, with a well-defined set of rules, and seeing what is the outcome of the fight. Somewhat similar conceptually to Day 15, but the rule set was much easier to implement.

Day 25 had a bunch of points, a definition of “two points are in the same constellation if they are at a distance 3 or less away, how many constellations do you have in your input?”. I kind of brute-forced it, I think, by creating the graph, getting all n² distances, and running a connected components on it, and there might have been a faster solution by considering the space itself and the neighborhood of the elements; it might have been faster with the provided input, but probably not in the general case, so eh. And I still had Day 23 to finish, so: low-hanging fruit on that one.

All in all, I thoroughly enjoyed this year’s problems, and if you have any interest in that kind of challenge, I highly recommend the whole thing. This year’s problems and the previous years’ problems are all available on the Advent of Code website. It must also be said that the Advent of Code subreddit is full of fascinating content, going from solutions in many languages to graphical representations of the problems via “here’s a way to make that problem more challenging, how would you then solve it?”.

Now I’m looking forward to December 1st, 2019 🙂