It doesn’t feel that long ago that I was writing my summary for last year’s Advent of Code, and yet, here we are again already.

For those unfamiliar, Advent of Code is an advent calendar where every day from December 1 to Christmas, you get a 2 part programming puzzle to solve. It’s essentially a bunch of Leetcode style interview puzzles, except they’re actually fun to do (usually) and with a competitive element too, as there’s a global leaderboard and you can create your own private ones too.

As with every year before, I used Swift. This year I set up my solutions as a Swift package instead of a playground. I didn’t do any setup in advance so I wasn’t able to have a reusable library in place with some common types and data structures as I was hoping to do, but it was still immensely helpful to be able to have third party dependencies including Apple’s swift-algorithms and swift-collections packages which are instant imports in much every Swift project I’m working on¹.

This post goes through some of the trickier puzzles this year. If you’d just like to look at the code, you can find all my solutions on my GitHub repo for Advent of Code.

Day 16

I encourage you to read the description of the problem before going ahead (part 1 is open to everyone even without an account, you need to complete it to unlock part 2), but here’s a quick summary of part 1: We have 30 minutes to traverse a graph of pipes, opening them to create the most optimal lava flow. Each move to a neighbour costs a minute, as does opening a valve.

Part 1 was fairly simple enough, I just set up a makeshift priority queue (swift-collections, alas, doesn’t ship with one) using a Dictionary<Int, Path>, where the key was the score for all the currently open valves. In every step I plucked out the path with the highest score, and visited all its neighbours. If the neighbour had a valve with a non-zero flow rate, I would also create another path that spent another minute opening it, and add it to the queue. Once I reached 30 minutes, I’d just update the maxScore.

While a bit wasteful, this worked in a pinch and wasn’t particularly slow. Advent of Code however has a knack for punishing you for inefficient yet workable part 1 solutions in part 2, and this was one of those days for me.

Part 2 now added a second player, and reduced the time to 26 minutes. While the time reduction certainly helped, the second player greatly expanded the number of possibilities for each step. If each node presented n possible next steps on average in part 1, the presence of two players means that goes up to n2 there. I needed a more efficient solution.

Looking at my input was a big clue here. Out of 54 valves, 39 had a flow rate of 0, meaning that opening them wouldn’t add to my score. They only existed as a step on a way to another valve, so I could cut them out entirely.

Taking this into account I created a reduced version of my graph with just the 15 valves with a non-zero flow rate. Each step would now take the minimum time for moving between the two valves, which further allowed me to eliminate the extra logic for 2 separate paths for valves with non-zero flow rates; since I could now jump straight to the next valve I wanted to, there was no need for travelling to a valve I didn’t need to open.

My solution still isn’t ideal here. While it converges to the correct answer very quickly (~10 seconds), it takes a long time to fully exhaust the whole search space (~15 minutes). I need to improve the heuristic here someday, but for now, it works.

You can read my full solution here.

Day 19

This is a problem where I would really recommend that you read the original text, but here’s a summary if you’d rather not: We’re given a bunch of blueprints, which define how we can construct various (ore, clay, obsidian, and geode) rock-extracting robots. Each robot can extract one rock of its type per minute, and requires some combination of the other rocks to build. Starting off with a single ore-collecting robot, and a machine that lets us construct one robot per minute, we have to maximise the number of geodes collected within 24 minutes.

Part 2 reduces the blueprints down to 3, but also increases the time limit to 30.

Like with day 16, this is not a particularly complex problem to write up a naive implementation for. The devil is in the details search space again.

The key insight here is that we need to only maximise the number of geodes, we only really need enough of the rest to construct our geode bots. Consider this sample blueprint:

Blueprint 1:
  Each ore robot costs 4 ore.
  Each clay robot costs 2 ore.
  Each obsidian robot costs 3 ore and 14 clay.
  Each geode robot costs 2 ore and 7 obsidian.

Remember that we can only construct one robot on any given step, so we can only really use 4 ores in any given step. If we have 4 ore robots, there’s no point in constructing any more of those, because we’re guaranteed to have enough ore to use at every step with just the ones we have already. And if we have more unused ore beyond 4 (while also having 4 bots; it’s possible that one bot created your 4 ores, and so if you use them up, you’ll only start the next step with 1), we can throw away the rest because it’s never gonna be used. This helps us treat two states where they only differ in having say 5 and 50 ores as identical, and thus ignore the one that we come across later.

This insight helps us tremendously narrow down our search space, by both restricting growth for bots that we don’t need more of, and also letting us ignore the quantities we don’t really care about.

You can find my full solution here.

Day 22

This was this year’s bastard puzzle™. Every once in a while we get a puzzle that can’t really be solved either generally or with just plain code, at least not easily or in a reasonable amount of time. It was day 24 last year, and this year it was day 22.

Part 1 started off fairly simply. We are given a grid of points as an input, with . symbolising empty space and # a wall, and a set of instructions for moving. Starting off at the leftmost pointing, we had to move around the board following the instructions, looping around the board when running out of space, and returning a combination of the final position and direction we were facing in as the output. Fairly straightforward then.

Part 2 tweaked the rules a tiny bit. The main goal remained the same, starting off from the same point and following the same instructions and returning the output in the same format. There was just one twist: The grid as it happens was divided into 6 squares of 50×50 points, which could be folded up into a cube. And so what we had to do for part 2 was move across the edge of this cube when running out of space.

Here’s what my input looked like, zoomed out to represent each 50×50 point block with a number for which face of the cube it was:

 12
 3
45
6

I spent a solid 30 seconds trying to solve this one programatically but gave up. There was just no way I was gonna be able to generalise the math to figure out how a cube folded, let alone then apply it to the problem at hand.

I ended up drawing out the cube on paper with all the connections labelled out, and then manually writing out the transition for each single outer edge. The infuriating thing about this puzzle was that the test input had a shape that didn’t match the puzzle input (which, as far as I can tell, had the same shape for everyone), which meant that there was no way to debug this except stepping through your code line by line.

I ended up having a off-by-one error for one single edge transition which cost me a good hour or so, and that I still could only figure out by going through the corresponding transitions generated by a someone else’s code for my input. All in all, this was a hassle. But still, a pretty fun one. At least it didn’t take anywhere near as much time as the other two.

You can read my full solution here.

---

As always, I really enjoyed this year’s Advent of Code. The difficulty level seemed a bit up and down, with no real trend day-to-day, which felt a bit strange. Overall I’d say it had some more difficult puzzles than last year did, but wasn’t a lot more difficult in totality.

I started off too late this year. In what is fast becoming an annual tradition now I’d even forgotten about day one once again despite setting multiple calendar alerts about it, so my setup wasn’t quite great. I had to repeat lots of bits of code across the project, and didn’t have any time to port over extensive library of extensions and data structures accumulated over the past years. I’m hoping to do all that before next year kicks off, unifying all my solutions into one single SPM package with a module for each year, and have a much more reliable base to start with. I’ve accumulated a pretty large library of extensions and common types across various projects, which I’m hoping to open source separately as well.