Advent of Code is a pretty fun December activity – an advent calendar of programming puzzles with a story tying them all together. The puzzles are released at midnight ET, which is conveniently 9 PM PT.

I did Advent of Code for the first time last year (2021), and really enjoyed it. Since I became a manager I rarely get to write code for work (and try to minimize it, even so), and especially don’t get to write the kind of code that exercises the problem-solving part of my brain.

There’s a global leaderboard, but mostly I ignore that one. Instead, I give myself the following restrictions:

  • The puzzle solution must be implemented in Rust, using only language built-ins and the standard library.
  • No code should be shared between days; each day is a standalone problem.
  • Overall runtime of each solution in release mode should be at most a few seconds (and ideally much less than one second.)

Most Advent of Code problems aren’t terribly nuanced from the algorithmic perspective, so these restrictions usually don’t get too much in the way. And it means that the resulting code is mostly readable, too!

My solutions for 2022 are available in GitHub, if you’re curious.

Day 1:⌗

Mostly a string-parsing exercise: part_1 is just to find the max, and part_2 involves sorting them.

One kind of interesting thing that they do in AOC is that the solutions usually require some kind of rudimentary hashing over the outputs, so as to make sure you really got the right answer.

Day 2:⌗

Kind of a classic “do what you’re told” problem, where the hardest part of the problem is reading comprehension. Rust match statements make pretty short work of the actual solution (part_1, part_2); there’s no real twist in part_2 that requires too much thinking.

Rust’s pattern-match-exhaustiveness checks (and its strong typing) actually get in the way a bit in competitive programming problems. They really shine in more complex programs, but I’m not optimizing for the global leaderboard (otherwise Python is the way to go!).

Day 3:⌗

The first problem this year with a nontrivial data structure! Rust’s HashSet implementation in the standard library makes short work of the requisite intersection and union operations. In part_1, we straightforwardly apply the HashSet. In part_2, the additional complication is the need to handle the groups in sets of three. Conveniently, Rust slices (&[T]) have a chunks function that does this for you (as well as a windows function, if you want overlapping scans).

Day 4:⌗

Mostly a logic problem - finding overlapping intervals. I honestly don’t have the interval-overlap logic memorized, so I had to re-derive it. It’s approximately a_min.max(b_min) <= a_max.min(b_max), for intervals (a_min, a_max) and (b_min, b_max). This makes sense, because the overlapping section is bounded below by the higher of the minima, and above by the lower of the maxima. part_1, part_2

By this point, we can also see that manual parsing in Rust isn’t the most fun. There are libraries like sscanf or its Rust-like equivalents that generate parsers for you, but that would violate my no-libraries rule. In the meanwhile, str::lines and str::split_once are my friends.

Day 5:⌗

Oof. Parsing sucked on this one. The actual algorithm is a “follow-the-instructions” thing, and it’s pretty straightforward, but building the initial set of stacks is more than a little annoying.

I also overengineered this a bit because I didn’t read the input, and thought that the stacks could have multi-character labels.

    [D]    
[N] [C]    
[Z] [M] [P]
 1   2   3

If I’d thought more about the problem, I would have realized that you can completely ignore the [] and parse just for alphanumeric characters, which gets you an appropriate grid.

part_1 and part_2 were effectively the same problem (again), with a minor modification in part 2.

Day 6:⌗

This type of streaming processing is perfect for Rust’s iterator and slice combinators. The &[T]::windows function makes it almost trivial – part_1 is almost a one-liner, and part_2 requires only changing the constant.

Day 7:⌗

A filesystem-esque problem! I could probably have solved this better if I actually looked at the problem input and realized that the initial root directory is traversed-to exactly once.

The problem is effectively a sequence of

$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d

which need to be parsed into the filesystem somehow. In the input, it turns out that any line which doesn’t start with a $ must be part of the ls output, which isn’t something I actually took advantage of.

Rust’s standard library includes the PathBuf struct, which is basically a mutable vector of path segments with path helpers. Vec<String> would also have been suitable here.

I took advantage of the fact that, in practice, there’s usually little cost to inflating the index of a filesystem from O(n) to O(nlogn), so I implemented my pseudo-tree as a HashMap<PathBuf, (bool, usize)>, identifying each node by its full path. This made actually implementing part_1 trivial, and then part_2 just needed some reading comprehension.

Some folks at work were also curious about versions which actually try to construct proper trees in Rust. This is one of the harder things to do, because the Rust borrow checker doesn’t make it easy to have multiple references to the same node, and we had to support cd .. in the sequence.

The two straightforward ways to do this are:

  1. Ignore the borrow checker, and create an arena with your own pointer-analogues. Then, the borrow-checker doesn’t care, and if you’re using safe code the underlying libraries (e.g. Vec) will check bounds for you and preserve memory safety. Most graph libraries do this because it’s fairly cheap; it’s also very similar to writing a bump allocator. implementation

  2. Use Rust’s standard-library support for runtime garbage collection via Rc, which supports both strong and weak references. The parent reference of the root node isn’t defined, so we need the parent to be Option<Weak<RefCell<DirEnt>>>. Note that this solution also requires RefCell inside the Rc, so as to allow runtime interior mutability to go with the runtime garbage collection. implementation

But, similar to in other languages, if you’re reinventing a tree or graph data structure by hand rather than using a library, and it’s not an intrusive data structure, you might want to think about whether that’s worth the effort.

Day 8⌗

Advent of Code likes its grid problems and its search problems. The actual implementation for this one is mostly a “do what you’re told” thing, especially in part_1. I just wrote it exactly as described in the problem text.

In part_2 I struggled for a while because I thought that take_while would just solve the problem for me. Alas, it turns out take_while is exclusive, and the inclusive version has been an open feature request in the Rust standard library and the itertools crate for a while. For this problem, I wrote my own version.

Day 9⌗

Despite a relatively simple set of instructions, I ran into a bunch of implementation issues with this one. It turns out that the ~best way to represent points on an infinite 2D grid in Rust is probably some wrapper around (isize, isize) (or some other appropriate signed integer type). I wasn’t that smart, and defaulted to unsigned values at first, resulting in a bunch of overflow errors.

Once I got that figured out, the follow function was relatively straightforward. It’s notable that the two axes are actually fully independent by the specification, since we’re using eight-way connectivity (so dist(a, b) = max(x_dist, y_dist))).

part_1 was the direct simulation, and part_2 just ran it more times in a row.

Unfortunately Rust doesn’t have Python’s nice negative-indexing to index from the end of an array, since array indices are unsigned integers… bleh.

Day 10⌗

This was a really cool problem. I always enjoy the problems where you get to simulate some weird CPU architecture, and this one was no exception.

Essentially we have a single-register computer which supports waiting (noop) and changing the value of the register (addx). The input’s pretty small, so we can afford to keep the entire history of the value of the register at every cycle.

part_1 is really just checking that the simulation is working, and then in part_2 we have to scan through the history and draw a picture!

The puzzle output requires some careful staring at the picture, though, I mistyped it more than once.

#### #### ###  #### #  #  ##  #  # ###  
   # #    #  # #    #  # #  # #  # #  # 
  #  ###  ###  ###  #### #    #  # #  # 
 #   #    #  # #    #  # # ## #  # ###  
#    #    #  # #    #  # #  # #  # #    
#### #    ###  #    #  #  ###  ##  #

Day 11⌗

Another CPU simulation, but with dependent operations this time. Essentially each monkey implements the following short program:

  1. operate on the item the monkey is holding (i.e. add, multiply, or do nothing)
  2. reduce the size of the value
  3. send the item to one of two destinations depending on whether it’s divisible by the monkey’s divisor

In part_1, we’re given step 2 as x / 3.

In part_2, we need to come up with something ourselves, otherwise the values grow unboundedly large. Rust doesn’t have a stdlib big-number library, so I wasted some time implementing one before I realized that, since I had to support the modulus operation, necessarily all of the operations that the monkeys are doing must operate within a modular group. After all, the output is based on the number of times each monkey ran their program, not based on the items being thrown around.

The easiest modular group which supports accurate modular arithmetic for divisors m_1, m_2, …, m_n is, of course, the product of all of those divisors.

As it happens, the input only has prime divisors, so that’s also the best modular group. Not that I knew that when I implemented it…

Day 12⌗

The first search problem of 2022! This one looked like a shortest-path algorithm, so I figured that we’d have to use Dijkstra’s algorithm, which requires:

  • a definition of the outbound edges for a given position, and
  • a cost for each outbound edge

Dijkstra’s actually gives you the shortest path to every reachable position, so oddly enough you don’t actually need the end position!

I made the mistake here of using a bounded grid (i.e. Vec<Vec<char>>) as my grid representation rather than a bag of points, which meant that I kept running into zero-underflow on the usize for the indices.

In part_1 you run Dijkstra’s forward. In part_2 I initially thought that you’d have to compute all-pairs-shortest-path (Floyd-Warshall), but it turns out it’s sufficient (and faster) to compute Dijkstra’s backward, using an inverted edge definition.

I also realized after the fact that, since the cost is the same for every edge, Dijkstra’s reduces to a straight breadth-first search. Oh well.

Day 13⌗

This one was very annoying. The input values are nested brackets, for which an endless number of libraries exist to parse:

[1,1,3,1,1]
[1,1,5,1,1]

[[1],[2,3,4]]
[[1],4]

In fact, they’re even valid JSON! But, if you can’t use a library, you have to write a recursive descent parser by hand…

I (re-)discovered the amazing thing which is Rust’s Peekable iterator, which allows you to look at the next value to be consumed without consuming it out of the iterator itself. This means that you don’t have to keep track of any fancy indices; you just need to remember when to stop pulling out of the iterator.

The actual part_1 and part_2 also require implementing a comparator on the resulting parsed type. Since I implemented the type as

enum Val {
    L(Vec<Val>),
    V(usize),
}

this was pretty easy; just write a recursive function and use std::cmp::Ordering as per usual.

Day 14⌗

This one is a falling sand simulation. I learned from the previous days and represented my state-space as a HashMap<(isize, isize), V>, which made it a lot easier. Otherwise, follow the instructions and simulate the path of each unit of sand until the end condition is met.

part_1 was actually harder than part_2, I think – the latter’s end condition is simpler.

Day 15⌗

This one was very interesting. When I first read the problem, it was not at all obvious to me that the input must define a space where the beacons' positions and distances cover all but a single point… so I implemented things pretty naively.

In part_1 it suffices to parse out all the relevant intervals that come from the Manhattan-distance circle definition, and then merge them. The only twist is that the beacons on that row are (definitionally) not spaces where beacons can’t be.

part_2 was quite a bit more challenging. My initial solution was to merge the overlapping intervals across the entire grid, and then find the one row with two intervals (since there’s only one open spot). This worked, but it was pretty slow…

In chatting with a few other folks, I realized that:

  • a Manhattan-distance circle is actually an equilateral diamond (my monospace font is taller than it is wide, so this wasn’t immediately obvious to me)
  • You can transform the grid by rotating it 45 degrees, at which point the circles are now squares

And, it turns out, a recursive area-search of a grid is a pretty straightforward problem! My version does a quadtree search, subdividing the space into 4 equally sized rectangles each time, and recursing into the rectangle where the un-covered point can still be. Note that the rectangle is viable if, for all sensors, the distance to at least one corner is greater than the sensor range.

Then I figured out the even more convenient solution: since there’s exactly one point which isn’t covered by a sensor, and we know that it’s at sensor_dist + 1 Manhattan-distance away from a sensor… it suffices to look at all points which sit on the intersection of at least two sensors with their distance extended by 1.

This reduces the search space to something fairly trivial, and it’s pretty clean! Plus, it runs in O(sensors^2) time, rather than in some function of the overall search space. implementation

Day 16⌗

Another search problem! I ran into so many implementation issues on this one, but the core concept is pretty reasonable. I also made reading comprehension mistakes, e.g. assuming that opening a valve increased the flow to its downstreams; assuming that you could move to any valve immediately, etc. Bleh.

The key points:

We know that we need to visit every valve-configuration in order to find the best valve-configuration, so we need to do a search (either breadth-first or depth-first). However, naively doing that explodes the state space absurdly, since you can choose to move, wait, or open a valve in any given step.

Optimizations:

  • Pressure is released over time, so there’s no reason to wait to open a valve. That is, if a valve can be opened at T, the path where you wait one minute and then open it at T+1 is never optimal.

  • The problem can be transformed into a choice of a sequence of valve-openings by computing the all-pairs shortest path (via Floyd-Warshall) and using the resulting lookup table as the cost of traversing an edge, in minutes. The outcome is the maximum pressure release for a given set of valve-openings.

I actually initially implemented part_1 via bitset dynamic programming, but this was both slow and made part_2 challenging. I probably would have been better off not knowing about bitset DP at all.

In part 2, the key realization was that the optimal path never has you and the elephant open the same valve, and a single run of the initial search will find the maximum release for any set of opened valves. It suffices then to search through every pair of possible disjoint openings and compute the max.

Day 17⌗

This one was pretty interesting – in part_1, you bascially build a Tetris simulator. And then, in part_2, you notice that because the input sequence of new tetrominoes is deterministic and repeating, and the input sequence of movements is deterministic and repeating, then so too is the rate at which the total number of lines increases!

In part 2, we need to simulate things for so many blocks that we can’t afford to keep the entire game board in RAM. But, since it’s cyclic, we don’t need to – we only need to compute how long the cycle is.

There are a bunch of fancy ways to do this, but the “easy” way is to recognize that the jagged edge at the top of a tetris sequence is the only part that matters for the next block (i.e. the highest block in every column). Then, the two other inputs to the cycle are the current position in the wind-sequence, and the current position in the rock-sequence.

Suffice then to make a cache of the top of the game board and the two offsets, and just wait until we get our first cache hit. This is our cycle-period!

We then need to calculate the following:

  1. the offset within the period that the desired number of iterations is at
  2. the number of remaining full cycles until that point

and then the total number of lines at the desired number of iterations can be computed by assuming each cycle the number goes up by a fixed amount.

I did have a funny off-by-one bug where my math actually computed things for the 1,000,000,000,000th index, which is the 1,000,000,000,001th block. But it so happens that each rock adds, on average, one in the height, so the arbitrary -1 worked until I was able to figure it out with the help of a friend.

Day 18⌗

This was my highest placement in the worldwide ranking, though not high enough to actually get any points. Oh well.

It’s kind of a cute problem: in part_1, you walk through all the points, look at the points next to them, and check if they’re occupied. If so, the face in between must be interior to the object, and so not part of the surface area.

In part_2, you realize that the object isn’t convex, so you should also exclude all faces which are encapsulated by the object on all sides… but by far the easiest way to solve the problem is just to flood-fill from some point which is known to be outside the object, and count the faces that are exposed to the flood-fill.

            ......
  OOO       .OOO..
  O O   ->  .O O..
   OOO      ..OOO.
            ......

Day 19⌗

Another search problem! This one was, again, an exercise in optimization. I actually had a lot of trouble getting part_1 to work in the first place, and my solution was enormously inefficient – to the point that I needed to optimize for part 1, and so part_2 was fairly trivial afterwards.

Optimizations I used:

  1. If we can build a geode machine, build it – the quadratic growth in geodes will dominate all other behaviors.
  2. If the best case of the current branch is worse than the current max, we can prune the entire branch (we can compute the best case if we assume we make a geode machine every minute)
  3. If we waited a cycle where we could have built something, there’s no point building that same thing – in the previous minute we would have explored the better version of that path
  4. Don’t try to build more of a bot than the maximum single-turn consumption of their resource – we can only build one bot per round anyways
  5. If we can build whatever we want, we can skip all of the waiting-for-resources states, and also truncate the overall number of resources to the minimum mecessary to build everything in the blueprint

The actual runtime is also related to the size of the visited set, so I removed minute from the visited set (in the minute-order traversal, we never visit the same minute twice), and I packed the values into a smaller representation when I could.

I did take the time in this problem to actually write a wrapper struct rather than just using a tuple, which paid off.

Notably, I also tried an optimization which worked on my input, but which doesn’t generally work: preferring to build obsidian bots rather than clay or ore bots at all times, if it is possible.

A learning: breadth-first search is better for these weird search problems than depth-first search, because it’s easier to see what solution-spaces you’re pruning out before expanding them into the queue at all.

Day 20⌗

I had a really hard time with this one because I didn’t quite realize that the Rust % (rem) operator and rem_euclid operator are not the same – the former may give you a negative remainder. Once I fixed that, I noticed that my debug prints would be the same as the example, but shifted over by one. It turns out that doesn’t matter, because it’s a circular buffer. Oops.

The final remaining bit was that you need to remember to implement the circular array correctly, i.e. after you remove a value from the array, you take everything mod n-1 and not mod n, until you insert the value back in.

But, presuming that you did that, part_1 and part_2 were the same.

Day 21⌗

Another computer-simulation one! This one felt quite similar to 2021’s day 24, so I had an idea of what I needed to do already.

part_1 is just to parse the expression tree and evaluate it. Easy enough.

In part_2, you actually need to solve the equation for a value. On the actual day, I just printed out the equation (as it would be written mathematically, and expanded), and plugged it into online sympy. However, that solution doesn’t meet my constraints, so I figured I should actually solve it, too.

A number of my friends used numerical approximation solvers for this problem, but it turns out that’s not necessary: the construction of the input is that the variable to be solved for appears exactly once in the expression, which means that you can solve the equation by applying the inverse operation on a literal value:

a + b = v
    a = v - b
...
a * b = v
    a = v / b

until you get an equation of the form x = v, and then you can return v.

This problem was way easier if you used Python, though, because sympy is free and easy to use.

Day 22⌗

This problem gave me headaches, because coming up with the traversal instructions for an unfolded cube (a cube net) requires 3D visualization that I didn’t quite have worked out in my head.

Anyhow, part_1 felt almost reasonable, you just need to wrap around the map until you get to the other side.

part_2 is where things got hard, since you need to come up with the appropriate lookup table that connects the edges of the cube together. On the day of, I actually just hardcoded it, but essentially you are trying to fill out the following table:

      L     R     U    D
A
B    C,L
C          B,R
X
Y
Z

translating from a given face and a direction off of that face, to the new face, and the direction relative to that new face.

This can actually be computed deterministically! The algorithm goes as follows:

  1. Label all the faces with unique names. I used A, B, C, X, Y, Z
  2. Label all the “flat” transitions, i.e. ones which appear in the net because they do not require any direction-changes when crossing between faces.
  3. Since this folds up into a cube, there must be at least one “corner” – a face which is adjacent to two faces which are not yet connected.
  4. Connect those two faces. In order for this to work right, we need to make sure that we draw the outbound and inbound arrows correctly (i.e. A->B and B->C resulting in A->C with a turn). You can compute the correct angle by inverting and “following” the A->B->C arrow visually.
  5. Repeat steps 3 and 4 until the traversal table is fully computed.

Pretty cool problem, even if it gave me a lot of pain.

Day 23⌗

Another “do what you’re told” problem. As per usual, I ran into a bunch of implementation bugs in part_1, before realizing that my reading comprehension was bad. This problem runs on an unbounded grid, not a bounded one! I’d actually implemented the logic with explicit bounds checks, so I deleted those and everything worked. part_2 was a simple extension of part 1.

Day 24⌗

Another search problem, though this one was kind of unique in that the obstacles (blizzards) is completely independent of the position, and also cyclic! The cyclic bit turned out to be not useful in my input, but some friends were able to use that to run faster.

My implementation is effectively dominated by the speed of the Rust standard library HashSet, which is unfortunatelly not that fast because it uses a DOS-resistent hash function. FxHashSet runs a lot faster, but it’s an import… oh well.

Anyways, the core idea of part_1 is to keep track of (for each step) every possible candidate location, and then expand it to every possible new location. When we get to the end, we’re done!

And in part_2 we just run part 1 three times. Merp.

Day 25⌗

This was the last day of Advent of Code, so I was pretty excited! Also, day 25 has only one problem, with no real part 2, so that was exciting also.

Fortunately or unfortunately, this part_1 was way easier than it looked. The idea is that you’re doing a change-of-base from base 10 to base 5, but with a twist – the actual coefficients can only be (-2, -1, 0, 1, 2), rather than the usual (0, 1, 2, 3, 4). Since the basis is the same, i.e. (5^n, 5^{n-1}, ..., 1), it’s actually equivalent and you can use the same algorithm as usual base-change.

Final thoughts⌗

I really enjoyed Advent of Code this year, even with my (admittedly strange) restrictions. I do think that I could have done much better in the global leaderboard if I let myself use libraries and wrote some helpers for manipulating grids and 2D/3D coordinates, but I’m not sure that would have made it more fun.