Advent of Code 2024 - In Rust - Days 11-15

This is the third article in a series covering Advent of Code 2024 in Rust.

Day 11: Plutonian Pebbles

This puzzle presents some magic “pebbles” with rules governing how they multiply, asking to compute the total number of stones after applying the rules a certain number of times.

Of course a first idea here is the brute force approach where we recursively apply the rules to the input and count the number of stones in the end. But I wondered if we could do better, especially as the example (going from 2 to 55k “stones” in 25 iterations) makes it clear that things grow quickly. If we look at this as a search problem we would expect O(b^d) nodes, so if the example produces 55312 stones at a depth of 25, we can estimate a branching factor b of root(55312/2, 25) =~ 1.5, which also makes intuitive sense given we have one rule that produces 2 children (but that might apply multiple times in a row) and 2 that create one.

One association I had here was with grammars, where we could think of the rules as productions and the resulting set of stones as the “word” produced by that formal language. Not sure yet if that would prove helpful, but I remembered the MU puzzle from Gödel, Escher, Bach where observations external to the grammar could help us realize things we could not prove within the formal rules.

If we look at the rules (we apply the first one that fits):

0 => 1
NNN|MMM with an even number of digits => NNN MMM
N => N*2024

one interesting observation is that the stones do not interact. That is, each initial stone will create an independent tree of stones with no interaction between them, so one possible space optimization here would be to expand each stone in isolation and just sum up the count of leaves in the end.

                            125                       17
                            /                      /     \
                          /                     /           \
                    253000                   1                7
                   /   \                     |                 \
                253     0                   2024               14168
               /        |                 /      \               |
         512072         1             20          24          28676032
         /    \         |            /   \       /   \       /        \
     512       72      2024        2      0    2      4   2867       6032
      |       /  \     /  \        |      |    |      |    |  \      /   \
   1036288   7    2   20  24      4048    1   4048   8096  28  67   60   32
      |      |    |   |\  |\      | \     |    | \   | \   |\   |\   |\   |\ 
2097446912 14168 4048 2 0 2 4     40 48  2024 40 48  80 96 2 8  6 7  6 0  3 2

I began to wonder at this point if the second half of the puzzle might introduce some rule that would merge stones, which would require us to look at the whole tree…

Another observation we can make is that subtrees starting from single digits, like ‘0 -> 1 -> 2024 -> 20, 24 - …’ show up frequently, because apparently the splitting rule often ends up splitting numbers down to individual digits. So we can precompute lookup tables for these single digit trees, saying how many stones they will end up producing at different depths and use these the prune the search as soon as we hit a single digit.

We can extend that idea to a dynamic programming approach, by remembering results for arbitrary subtrees. To do this, we can turn the rules into a recursive function. If s(n,d) is the number of stones a number n produces at depth d (i.e., after blinking d times), we can rewrite the rules as:

s(_,0) = 1
s(0,d) = s(1,d-1)
s(NNN|MMM,d) = s(NNN,d-1) + s(MMM,d-1)
s(N,d) = s(N*2024,d-1)

We can then perform a depth-first search, memoizing the various values for s to help save work from sub(-tree)-problems we have solved before. It’s important that we use a depth-first search, as we’d otherwise revert to the naive algorithm by extending the whole tree before we hit the s(_,0) base case and can start memoizing values.

I ended up implemeting both the sequential naive algorithm and a recursive version of the dynamic programming approach. Turns out the runtime difference between them was negligible at 25 blinks (the variance between runs was greater than the actual value measured), but the memory usage was already showing some difference. And when I increased things to 35 blinks for testing, the differences became pronounced.

Approach	25 blinks	35 blinks
Naive	`~3 MB`	`~180.0 MB`
Dynamic	`~1.7 MB`	`~ 2.4 MB`

Somhow the dynamic solution ran much slower than the naive one at first, until I realized I had made a blunder where I was storing values but had forgotten to actually read them >.<

Turns out the second half of the puzzle ended up asking for 75 blinks, where the dynamic approach - once fixed - came in very handy.

Dynamic programming isn’t one of my strengths, so I felt rather proud of myself for seeing that approach and making it work :-)

Day 12: Garden Groups

This puzzle asks to delinate irregular shaped garden plots on a grid with fences, computing the area of each plot and the amound of fencing needed to surround it. Fences are not shared between plots, apparently.

Finding the area reminded me a little of ideas like flood filling from graphics. But I wondered how to handle the fencing outline, where a given square on the grid might have some edges that connect to the plot itself (so no fence was needed), while others connected to other plots (and thus needed a fence).

I realized that we could treat this as a graph search with two different edge colors. If we connected each node with all of its neighbors and colored each edge connecting to the same node type black and edges connecting different nodes a different one red, we could do any graph traversal, and just add up the number of nodes we found (= area) and the number of red edges for each node (= fence segments).

Graph of the example, with "black" (-) and "red" (*) edges

  A - A - A - A
  *   *   *   *               *       This node needs two bits of
  B - B * C * D     =>      - B *     fencing (*) and is connected
  |   |   |   |               |       to its own plot on two sides (-)
  B - B * C - C
  *   *   *   |
  E - E - E * C

To make handling the outsides simpler, we could connect each node to a single “out of bounds” node there (with different letter to anything else) using red edges.

The second part of the puzzle asks to “collapse” straight runs of fencing, only counting them once. There is a challenging example provided of an area with two “holes”, where the fences connect, but should not be counted as one segment. The description mentions that fences have an in-side and an out-side (and there’s a nice joke about Möbius strips).

AAAAAA
AAABBA
AAABBA
ABBAAA
ABBAAA
AAAAAA

I figured that we maybe can borrow an idea from walking a maze, where we always keep one hand on the wall. If we could represent the fences as vectors with a direction, we could “walk” around each loop and essentially count how often we have to change direction. If we make each loop have the same direction (e.g., clockwise) we should be able to detect the edge case below, where two plots meet. If we find a point with two outgoing vectors, we must choose the one going straight or to the right. We can produce this view from the previous graph search by assuming a new grid of N+1 x N+1 coordinates “between” the plots for these fence vectors, which we can produce from taking each “edge” in our plot graph and turning that 90 degrees clockwise.

 +-------->----------+
 | A  A  A   A  A  A |
 |         +--->-+   |
 | A  A  A | B  B| A |  
 |         ^     v   |
 | A  A  A | B  B| A |
 ^   +-->- +---<--+  V
 | A |B  B | A  A  A |
 |   ^     v         |
 | A |B  B | A  A  A |
 |   +--<--+         |
 | A  A  A   A  A  A |
 +---------<---------+

I also thought about an alternative where we would try to use a kind of “scanlines” approach, remembering all the grid tiles of a single plot and then “scanning” across the rows from top to bottom, looking at how the letter boundaries shift between rows, but I couldn’t come up with a simple system of rules to cover holes, etc. that I could convince myself would handle all cases.

                 +1 for the overall top
|A AA AA A| |    +2 for the sides
|A AA|..|A| V    Outsides didn't move, but +3 (new run of B's)
|A AA|..|A|      Nothing moved, no changes.
|A|..|AA A|      +3 for new Bs, +1 for end of Bs
|A|..|AA A|      Nothing moved, no changes.
|A AA AA A|      +1 for end of Bs
                 +1 for bottom (end of input)

Day 13: Claw Contraption

In this puzzle, we’re asked to play a number of unusual claw machines that each have two buttons A & B that each move the claw by a particular positive vector on the X/Y plane, and a prize at a single point on the plane. We’re allowed to press each button up to 100 times. For a given claw machine, we’re asked to find out if we can win the prize at all, and, if so, what the cheapest sequence of button presses is to do so, given it will cost 3 tokens to push the A button and 1 token for B. The overall puzzle solution is the total cost for winning all possible prizes. Here are two claw machine examples:

Button A: X+94, Y+34
Button B: X+22, Y+67
Prize: X=8400, Y=5400

Button A: X+26, Y+66
Button B: X+67, Y+21
Prize: X=12748, Y=12176

I thought about treating each claw machine as a system of equations we could solve for A/B. For the first example, this would become something like the below. I was surprised that this would yield a single solution, given the puzzle had mentioned a “cheapest way to win”, which suggests there should be more than one.

X: 94a + 22b = 8400
Y: 34a + 67b = 5400

...

b = (34*8400 - 94*5400) / (22*34 - 67*94)
a = (67*8400 - 22*5400) / (67*94 - 22*34)

Translating this back to the inputs (where A and B are
how far the claw moves, and P is where the prize is) we
would get:

b = (A.y * P.x - A.x * P.y) / (B.x * A.y - B.y * A.x)
a = (B.y * P.x - B.x * P.y) / (B.y * A.x - B.x * A.y)

I also explored treating this as a vector problem. If we consider each button as a vector, we can visualize the problem as a linear combination of two vectors: (8400, 5400) = a * (94, 34) + b * (67, 21). If we visualize this, we can see that, indeed, most claw machines will only have a single solution. Our only choice is in what order to press the buttons, but not how often. There is one interesting edge case that can arise if one (or both) of the vectors are collinear and point straight at the prize, which would collapse our parallelogram into a line. In that case, a or b in our equations may be zero, which would likely render the solution to the system of equations invalid, and we might have a choice of whether to use the A or the B button to reach the prize.

Drawing showing a parallelogram of vectors

This leaves us with the following possible solutions for a given claw machine with the Prize at point P and vectors A/B:

P = a * A (A points straight at the prize)
P = b * B (B points straight at the prize)
P = a * A + b * B (The parallelogram situation)

Given we are specifically looking for integer solutions (we can’t do fractional presses of a button) I thought using modulo would be a nice way to check using something like P.x mod A.x == 0 && P.y mod A.y == 0. But that ends up yielding false positives, e.g., for a case like A = (10, 100), P = (100, 100). So a better solution is to compute candidate scalars and then really verify that P = a * A.

The second part of the puzzle is almost the same, but moves the prizes much further away, which can be solved the same way. In my case, the change ended up exposing the issue with my modulo idea, which didn’t occur in the first part of the puzzle.

Day 14: Restroom Redoubt

This puzzle asks to predict the positions of robots after 100 turns. The robots have a starting position and velocity and move in straight lines on a grid with wraparound (i.e., a torus). At this point, I really felt I was getting a lot of mileage out of my simple geometry and grid types, which was very satisfying.

At least for the first part it seemed simple enough to just simulate the robots for 100 turns. I did suspect that some of them might end up repeating the same path after a while, but exploiting that fact seemed overkill when we were dealing with some simple math for 500 robots and 100 turns. I had a hunch that the second part of the problem would turn up the # of turns massively, at which point dumbly updating each robots' position might no longer work, but I for the first part simply updating each robots position and plotting them on my torus grid worked fine.

The second part of the puzzle came as a surprise. Instead of cranking up the difficulty, it asked for when the robots showed up in the shape of a Christmas tree, cute! Thankfully, I had already implemented the Display trait for the grid, so I could just bring the font size in the terminal waay down, run the program and observe. And lo and behold, after a couple of thousand “seconds”, there suddenly was a christmas tree!

Look ma, a tree in my terminal!

Day 15: Warehouse Woes

Oh look, it’s Sokoban! This puzzle asks to simulate a “robot” moving in a warehouse full of boxes and walls, pushing boxes out of its way as it moves. The grid I had built for Day 6’s Guard Gallivant came in very handy again here.

Most of the program was very straighforward, one challenge was how to handle cases where the robot would push a whole row of boxes. After I thought about this, I realized we didn’t have to move each box, but could instead scan ahead, looking what’s right behind the boxes, which produces a small number of cases we can solve. And because the row of boxes we scan is contiguous by construction, we can simply update the ends of the row instead of each box. Here is an example (we’ll just consider the robot moving to the right; other directions work the same way):

Robot is trying to move right >

  @#      =>  -       Can't move into a wall
  @.      =>  .@      Robot moves into empty space
  @OOOO#  => -        Can't move, boxes bump into a wall
  @OOOO.  => .@OOOO   Robot pushes the whole row of boxes
                      (note that the middle doesn't change)

I had expected that the second half of the puzzle might introdue some restrictions on how many boxes the robot can push, but it did something much more interesting, creating “large boxes” that can partially overlap, creating interesting situations where our previous row of boxes might now end up with a more complex geometry that’s moving. Note, though, that this can only happen in the vertical direction!

##############
##..........##
##..[][][]..##
##...[][]...##
##....[]....##
##.....@....##
##############

Move ^:
##############
##..[][][]..##
##...[][]...##
##....[]....##
##.....@....##
##..........##
##############

I chose to treat this as a mini search problem. We can imagine building up a set of “active” grid positions, by starting at the robot and building a small search graph from there. Whenever we expand a tile that’s being pushed, we add to the queue: the other half of the box, if any, and the tile being pushed straight ahead. If we encounter any box that is blocked by a wall, the whole push should fail. If all boxes only encounter space ahead of them, we can push things.

##############
##..........##
##..[][]#...##
##...[][]...##
##....[]....##
##.....@....##
##############

Actually moving the boxes also becomes more complex the second half of the puzzle, as the shape can be more irregular now. I chose a simple clear and redraw approach. Once the set of moving tiles was identified by the search, I simply cleared all the old positions (replacing them with the empty tile) and then re-drew things in their new positions. This worked out nicely, and lo and behold another 5 puzzles were solved.