This year’s Advent of Code is well past the half-way mark, and I’ve been reflecting on some of the harder or more interesting problems over the last few years, and the lessons learned about making code faster, or large problems tractable.

In case you haven’t encountered it, AoC is an annual coding competition, with a new problem every day, from December 1 through 25. Each day, there are two parts, and the second (usually harder) part unlocks after you solve the first part. You can use any programming language, and only need to submit the right answer (usually a number) to solve each part.

There is a global leaderboard, with amazingly short times for the top 100, and my company also has an internal leaderboard. We have a chat channel to share solutions and learnings, making it a very rich community experience.

The hardest problems for me have involved seeing things differently in order to solve them. In many cases, Part 2 requires a better algorithm, because while brute force may have sufficed for Part 1, the second part is 100 or a million times bigger.

I did these in a combination of Go, Julia, Rust, and Python. The code for all my solutions for 2020 through 2024 are in GitHub.

Here are some comments and observations about selected problems, with a perspective on techniques that made large problems computable in a reasonable amount of time.

2021

Day 15 (Go, Julia): Find the lowest cost path through a graph, starting at the top left, and ending up at the bottom right, adding up any cells you enter along the path that minimizes total cost. I did this in Go using graph library, Julia with Dijstra shortest-path algorithm (medium). A great learning experience for me, because it reinforced my application of when and how to use graph algorithms. In general, simple graphs are easy and quick to search using brute force, but larger graphs need algorithms to navigate quickly.

Day 19 (Go): Match up 3-dimensional cubes in space, adjusting x,y,z offset and also rotation along any 3 axes, so that at least 12 points in the each pair of cubes line up exactly. Then (Part 2), calculate the maximum distance between the cubes (hard). This problem required the right data structures to represent shapes in space, which made the searching and measurement feasible and quick.

Day 20 (Julia): Transform an image by successively replacing pixels with values looked up from a translation table, the index being the value of the 9 cells surrounding each pixel, converted from binary to decimal. Much complicated by the fact that the input data has a 1 in the first position of the translation table, meaning that empty areas are filled with 1s, which muck up the pixel count (hard).

Day 21 (Go): Simulate a game of rolling dice and moving round a board, trivial in Part 1. In Part 2, fork a set of parallel “universes” with identical state after every throw of a 3-sided die, and get the number of universes in which the winner won. This is one of the most head-breaking problems I’ve encountered, required thinking about state in a different way (hard).

Day 22 (Go): Turn on/off points in space, defined by 3-d ranges (like rectangular cubes). Part 1 quite easy (basically used brute force), but for Part 2 used recursive evaluation of volumes solution subtracting intersections. This required thinking about space in a more abstract way, and basically working backwards to get to an initial state (hard).

Day 23 (Go): Find the most economical solution to a board game, involving 4 (later 8) pieces from random starting tunnels to ordered destination tunnels via a corridor, sort of like the Towers of Hanoi. Solved the first part (8 pieces) on paper, second part using recursive depth-first search, eliminating branches that exceeded best solution found so far. This was a breakthrough for me in my understanding of Dynamic Programming (hard).

2022

Day 11 (Go, 100 lines): Simulate transfer of objects between a bunch of monkeys, with “worry levels” assigned to each object. Each monkey modifies the worry level according to some rules, then passes it to one of two monkeys, depending on whether the worry level is divisible by that monkey’s “test” number. Count up the number of inspections each monkey makes during the simulation. The answer is the product of the two highest inspection counts. Trivial (if tedious) for 20 iterations in Part 1, but integer values overflow for 10,000 iterations in Part 2, unless you apply an adjustment that preserves the decision outcomes while keeping the numbers fom getting too large. This was one of numerous problems in AoC that required finding a work-around for very large numbers (hard for Part 2).

Day 13 (Python, 49 lines): Given pairs of nested lists of numbers, count up how many are in the right order according to an arcane comparison function (Part 1), then combine all the pair elements into one big list, add a couple of marker elements, and sort the list according to the comparison function. For Part 2, report the product of the indices of the two marker elements. This was interesting because it’s quite easy in Python, due to its tolerance for mixed types, and illustrates how different languages are better for different things.

Day 15 (Go, 166 lines): Given a list of “sensors” and their distance to nearest “beacon”, find positions in a row that could not possibly have a beacon (Part 1), and the possible location of an undetected beacon (i.e., where there is in coverage by known beacons) for Part 2. I did this one by mapping every cell in the space, and it worked. But a colleague blew my mind with a very short solution, that used a geospatial library that instantly solves this sort of thing. Again, makes you reflect on which tool is best for every job (hard).

Day 16 (Go, also 166 lines): Given a network (graph) of closed “valves”, each with a certain flow rate, connected by “tunnels”, find the sequence of opening the valves (takes one minute, plus one minute per step to get there) that yields the highest possible total flow during a 30-minute period. For Part 2, same but try two decisions (one for you and one for the “elephant”) each time step, over 26 minutes. Used simple depth-first dynamic programming solution, recursively tries each feasible candidate unopened valve, excluding those for which we wouldn’t have enough time to get any flow. Same for Part 2, but tried all possible pairs of remaining valves, one for each actor (slow but works). Some colleagues did this using linear programming (DP solution very hard).

Day 17 (Go 123 lines + Python 87 lines): Simulate simple geometric shapes falling down a shaft, getting moved left and right by gusts of “gas”, and falling on top of each other. For Part 1, determine the total height of the shapes after 2022 have fallen. For Part 2, do the same for 1 000 000 000 000 shapes (infeasible to simulate, so looked for repeating pattern in height deltas, and applied simple math in separate Python script). This one was hard, but a breakthrough for me because it was infeasible to simulate, had to find a way around this, which turned out to be detecting repeating cycles in the output (which comes up regularly in AoC).

Day 18 (Go, 65 lines): Given a list of 1x1x1 cubes in 3-d space, count up surfaces that don’t touch another point (Part 1). For Part 2, only count surfaces that are outside the shape (may include some face inside of a “tunnel”, so can’t just look outward from surface). I rated this one as medium difficuly at the time (and my solution is quite short), but I remember being stretched by the need to think about space and anti-space.

Day 19 (Go, 152 lines): Basically a set of optimizations, to find the maximum number of “geodes” that can be produced over 24 periods from a set of four types of “robots”. Each robot can produce one mineral of its own kind each time period. There are 30 “blueprints” (cost schedules), each of which lists the number of each type of ingredient required to build a robot. So it’s a production plan optimization. Part 1 asks you to optimize all 30 schedules, Part 2 only the first 3 blueprints, but for 32 periods instead of 24 (hard, used dynamic programming but linear programming would have been possible). This one was a real breakthrough for me in the application of Dynamic Programming, including using recursion to break down a problem, and memoization to avoid recomputing values already encountered.

Day 20 (Go, 95 lines): Given a list of numbers (7 in sample, but 5000 in input), simulate moving each number forward or backward in the (circular) list, forward if positive or backward if negative. For Part 1, do this once, and report the sum of the values 1000, 2000, and 3000 after zero. For Part 2, multiply each number by a huge value, and do it 10 times, report same sum. Complicated by duplicate values in the main input, so you can’t just look for position of a value. Also, iterations in Part 2 are infeasible with large multiplier as well as 10 iterations (hard). This one was a breakthrough for me because it highlighted the importance of using the right data structure, in this case a circular queue.

Day 21 (Go, 72 lines): Given a list of variable names, each with either a numbers or a simple formula, recursively evaluate the root node (Part 1), and find the value for one cell that makes the two sides of the root node equal. This one was only medium difficulty for me, but I remember having the “aha” moment when I realized that it could be solved using gradient descent, which I have several times coded during my career.

Day 22 (Go, 374 lines): Simulate movement on a 2D map, according to a list of instructions, which can either be to move n steps, or to turn 90 degrees left or right. There are obstacles to avoid, and one wraps around to the other side when walking off and edge. For Part 1, the map is in 2D. For Part 3, the map gets folded into a cube. This one was very hard, because of the 2D movements on different contiguous surfaces of a 3D object. I created a very verbose solution that mapped each possible transition from one surface to another.

Day 24 (Go, 175 lines): Find shortest path from entry to exit of a rectangular field, avoiding “blizzards” that move every time step. For Part 2, also move back to entry then back to exit, and add up all the steps. Used dynamic programming, depth-first search with memoization of previously found best values for each position+time combination (medium). Again a problem that reinforced my understanding and appreciation of Dynamic Programming.