Advent of Code 2022
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 problemsolving 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 builtins 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 stringparsing 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 patternmatchexhaustiveness 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 intervaloverlap logic memorized, so I had to rederive 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 Rustlike equivalents that generate
parsers for you, but that would violate my nolibraries 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 “followtheinstructions” 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 multicharacter 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 oneliner, and
part_2
requires only changing the constant.
Day 7:⌗
A filesystemesque problem! I could probably have solved this better if I actually looked at the problem input and realized that the initial root directory is traversedto 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
pseudotree 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:

Ignore the borrow checker, and create an arena with your own pointeranalogues. Then, the borrowchecker 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 
Use Rust’s standardlibrary 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 beOption<Weak<RefCell<DirEnt>>>
. Note that this solution also requiresRefCell
inside theRc
, 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 eightway 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 negativeindexing 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 singleregister 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:
 operate on the item the monkey is holding (i.e. add, multiply, or do nothing)
 reduce the size of the value
 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 bignumber 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 shortestpath 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 zerounderflow 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 allpairsshortestpath (FloydWarshall), 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 breadthfirst 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 statespace 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 Manhattandistance 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 Manhattandistance 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 areasearch 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 uncovered 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
Manhattandistance 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 valveconfiguration in order to find the best valveconfiguration, so we need to do a search (either breadthfirst or depthfirst). 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 valveopenings by computing the allpairs shortest path (via FloydWarshall) 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 valveopenings.
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 windsequence, and the current position in the rocksequence.
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 cycleperiod!
We then need to calculate the following:
 the offset within the period that the desired number of iterations is at
 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 offbyone 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 floodfill from some point which is known to be outside the object, and count the faces that are exposed to the floodfill.
......
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:
 If we can build a geode machine, build it – the quadratic growth in geodes will dominate all other behaviors.
 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)
 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
 Don’t try to build more of a bot than the maximum singleturn consumption of their resource – we can only build one bot per round anyways
 If we can build whatever we want, we can skip all of the waitingforresources 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 minuteorder 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: breadthfirst search is better for these weird search problems than depthfirst search, because it’s easier to see what solutionspaces 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 n1
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 computersimulation 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:
 Label all the faces with unique names. I used A, B, C, X, Y, Z
 Label all the “flat” transitions, i.e. ones which appear in the net because they do not require any directionchanges when crossing between faces.
 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.
 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.
 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
DOSresistent 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 changeofbase 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^{n1}, ..., 1)
, it’s actually equivalent and you can use
the same algorithm as usual basechange.
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.