Advent of Code 2024, Week 3

Advent of Code

Advent of Code is a yearly Advent calendar of programming puzzles that's run since 2015, with 25 two-part problems each year, each part rewarding one "star". For 2024, after completing every previous year, and even making the global leaderboard last year, I'm making a weekly blog post about that week's problems, containing my thoughts on them and how I solved them; these, of course, will contain spoilers. For the code, see:
2024 · personal library.

Day 12: Garden Groups (puzzle, code)

Solve Times: 10:10 / #735, 30:28 / #629

This problem is yet another grid-based problem. In this problem, the grid represents a garden, and each square in the grid is labeled with a letter representing the type of plant in that garden plot. Contiguous areas of the same letter represent a "region" of the garden, and the goal is to determine the cost of fencing required to surround each region. In part 1, this cost can be calculated by multiplying the area and the perimeter of a region to find the cost for that region. In part 2, the calculation is more complicated: instead of the total perimeter, the area is multiplied by the number of sides the region has.

The first step in this problem is dividing the grid into regions, and my first instinct when I saw it was to use a graph algorithm: connected components. By turning the grid into a graph, with edges between orthogonally adjacent tiles with the same plant in them, I could use my connected component finding algorithm to divide the grid into its regions. The area was a simple calculation, just requiring me to get the number of tiles in each region, but the perimeter was more complicated. In part 1, I accomplished this by looping through every tile in the region, getting its four neighbors, and incrementing the perimeter if the neighbor is either out of the grid or contains a different plant in it.

My logic for part 2, on the other hand, is a complete mess of spaghetti: the general concept is to get a list of all the edges of a region, and then inch along them in order to consolidate them into border segments. I stored each edge as a (position, direction) pair, representing the position inside the region and the direction from that position to the edge. Using this representation, I constructed a dictionary that mapped each edge to a list containing all the edges it is connected to. For every edge in the region, if it's already in this dictionary, skip it; otherwise, add a new entry to the dictionary. In the latter case, I move along the axis that is 90 degrees from the edge (both clockwise and counterclockwise), and see if each position also has an edge that is moving in the same direction as the original edge. If it does, it gets added to the dictionary; if it doesn't, the search in that direction ends. After this is done, the number of entries in the dictionary equals the number of unique segments in the region's boundary, which I can multiply by the area to calculate the answer for each region.

Day 13: Claw Contraption (puzzle, code)

Solve Times: 10:44 / #684, 01:19:41 / #3813

This is a very math-heavy puzzle, the first such puzzle this year, which was unfortunate for me because I'm rusty at math. Part 1, however, doesn't require that math: it presents a list of claw machines, each of which has two buttons that can be pressed to move the claw a specified distance on the X and Y axes, and a prize located at some (x, y) coordinate. The goal is to find how many presses of each button is required to reach the exact position of the prize, which is guaranteed to be at most 100 presses of each button. In part 2, the math comes in: the x and y positions of the prize are increased by 10e13, which effectively requires an algebraic solution to complete in any reasonable amount of time.

For part 1, I used a loop to check all possible counts of A presses (from 0 to 100), calculated how many B presses would be required after that many A presses to reach the goal, and if doing so was possible, used that number to update a "current best" variable, which I returned at the end. For the second part, my first idea was to try solving the algebra manually, but I don't remember linear algebra well at all, so I was unsuccessful.

The approach I ended up getting to work is based on the x-y delta, which is the difference between the x and y coordinates. I started by finding the delta between each button as well as the goal, and then took the LCM of the buttons' deltas. Using this LCM, I could figure out some number of presses of each button which leads to x and y being equal: the correct count of presses would have many multiples of these presses, plus some smaller number of presses of each button to align the total delta with the goal. To calculate this, I used a while loop to check every number of A presses, starting from zero, until I found a working one. I calculated the delta produced by the A presses, and then the delta that would be required from B presses to reach the goal's delta; if this yielded a positive (or zero) integer number of B presses, I subtracted the total effects of both buttons' presses from the goal, and then divided by the effect of the "delta-neutral" presses I calculated earlier. If this ultimately yielded a working solution, I converted it into the cost for that machine; if it didn't, I concluded that the machine is unsolvable and skipped it.

Day 14: Restroom Redoubt (puzzle, code)

Solve Times: 08:32 / #440, 44:12 / #1673

Day 14's puzzle is quite unique because of its part 2, which is formulated very differently from a typical AoC problem; part 1, however, is another grid problem. The input is a list of "robots" which have a starting position and velocity, and every second, they move along a grid by that velocity, and wrap around when they cross the edges of the grid. In part 1, the task is to simulate the robots' motion for 100 seconds, then divide the grid into quadrants and multiply the number of robots in each quadrant. Part 2, however, is very unconventional: the problem statement simply says that the robots periodically form "a picture of a Christmas tree", and asks how many seconds it takes for this to occur, which is far vaguer than any other AoC problem has ever been. Because of this vagueness, part 2 became quite controversial; personally, I don't really like it, but I think it's a very interesting concept.

To solve part 1, my logic was quite straightforward. I maintained a list of each robot's position and velocity, and for 100 iterations, added the velocity to their position, using modulo to cover wrapping around. After the iterations were done, I used a list to count the number of robots in each quadrant, and checked each robot's position to assign it to a quadrant and increment the appropriate value in the list, then multiplied them all. For part 2, since I didn't have any idea what the Christmas tree might look like, my first thought was to use heuristics to search for it. I thought that, since a tree needs a trunk, a good way to start would be to try to find a trunk by looking for most of the center of the grid being filled. After this didn't work, I tweaked it to instead measure "column concentration": the percentage of the robots that are located in the N columns with the most robots, with a tree being assumed to be at a certain level of column concentration. Unfortunately, despite tweaking the threshold and the value of N repeatedly, I wasn't able to find the tree image, but I did notice a pattern in many of the images I created that they had a lot of robots in an area slightly to the right of the grid's center. From this, I thought to instead look for a large number of the pixels in those particular columns being filled in, and ended up with a heuristic that checks for at least ~23% of a three-column section of that region being filled in, which happened to work. I don't know if this works in general, but it does work for my input, which is the most I was willing to do.

Day 15: Warehouse Woes (puzzle, code)

Solve Times: 13:33 / #343, 35:05 / #163

This is a grid problem where the goal is to implement mechanics for a Sokoban-like game, featuring a grid filled with pushable boxes and static obstacles. The input for this problem is split into two parts: the grid itself, which contains a robot that represents the "player" alongside the aforementioned boxes and obstacles, and a series of directional movements. In part 1, the goal is to simulate all of the movements, and then calculate a number representing the position of every box at the end. Part 2 adds an interesting twist to the Sokoban concept by stretching the grid horizontally, which splits every box into a left and a right half that always move together, and therefore can push on many columns at once; other than this change, the problem is the same.

After parsing the input for part 1, I set up a loop to go through each of the robot's steps in order. The meat of the logic for Sokoban is getting pushing objects to work correctly, and the way I thought to do it here was to use a list to track every position that needs to move. This list starts with just the robot itself, and in a while True loop, I check the position given by adding the unit vector of the step's direction to the last position in the list. If that position is empty or an immobile obstacle, I break out of the loop and set a boolean flag to indicate whether movement is possible or not. If the position is a movable box, on the other hand, I add its position to the list, update the next position to check, and repeat until encountering a non-box. To accomplish the actual moving itself, I use the list to move every position forward by the direction's unit vector, and empty out its last occupied position. For part 2, after some thinking, I figured out a way to adapt my logic for the possibility of multiple columns being pushed on at once. Instead of a single list to track the current push, I created a list of lists, each representing one row or column of pushes (although only the column part is actually relevant), and when pushing a box vertically, added one list for each half of the box. If any of the lists encountered an obstacle, I aborted the entire attempted push, but I only did a successful push when all of the lists encountered empty space at the end. With these changes, I was able to correctly simulate the Sokoban logic for part 2, and then easily calculate the final answer.

Day 16: Reindeer Maze (puzzle, code)

Solve Times: 27:31 / #1909, 36:30 / #932

Day 16 presents yet another grid problem, although this time it's much more of a graph problem that's presented as a grid. The puzzle input is a two-dimensional maze with a start and end position, with a reindeer racing between them, and the goal is to find the lowest-score route from the start to the end. However, the reindeer starts out facing east, and turning (which can only be 90 degrees) incurs a score of 1000, compared to only 1 for moving forward 1 step. In part 2, the problem instead requires considering all of the possible shortest paths from the start to the end, and counting how many tiles appear on any of them.

My immediate instinct when seeing this problem was to use Dijkstra's algorithm to handle the pathfinding. Because both the position and direction of the reindeer are relevant, the nodes in the graph needed to include both, so I constructed the graph with a triple-nested loop: first the y coordinate, then the x coordinate, then the reindeer's direction. After skipping the (y, x) pairs that represented an impassable position, each of these became a node, and had edges added for turning left and right (with a cost of 1000, moving to the node with the same position but a different direction) and any applicable edges for moving to a new position (with a cost of 1). I also recorded the reindeer's starting position to use as the start point for the Dijkstra's search, and added zero-cost edges from the four nodes representing the end position to a node labeled "Target". After setting up the graph, I ran my implementation of Dijkstra's from the start position, and grabbed the resulting minimum cost for the "Target" node. For part 2, I knew I'd need to change my logic somehow to be capable of tracking multiple paths at once. My first instinct was to copy and slightly modify my Dijkstra's implementation, shifting the way I tracked paths: instead of mapping each node to a single prev node, representing the single shortest path to it, each node is instead mapped to a list of nodes that are part of shortest paths. Somewhat surprisingly, this actually worked, and all I needed to do afterwards was add the ability to follow multiple paths back to the start to find each position that's in any path, which I did with a list of running positions that ended up similar to my logic for Day 15's part 2.

Day 17: Chronospatial Computer (puzzle, code)

Solve Times: 11:25 / #386, 48:02 / #123

This day presented 2024's first reverse engineering problem, something I tend to enjoy, and today's was no exception. Reverse engineering puzzles, an AoC mainstay, usually give an input that's a program in some sort of assembly language, where part 1 can be solved simply by implementing the provided spec accurately, but part 2 requires manual analysis of the input code in order to understand what it does, and thereby solve it in a higher level language. Today's problem fit that mold: the problem describes a 3-bit assembly language with 8 instructions, one of which is an "output", and part 1 asks for the sequence of outputs produced by a given input program and starting register values. Part 2, on the other hand, asks for a value that can be set in the first register so that the program becomes a quine, a program that produces itself as its output.

There's not much to say about part 1: all I did was implement the provided spec, and run my interpreter on the input. For part 2, my first reaction was to take apart the program and write a Python equivalent to the code, which ended up looking something like this:

From looking at this, I noticed that it was effectively taking a digit of the base 8 representation of reg_a, converting that into an output number through some complicated formula, and repeating until it ran out of digits. Because, after outputting the last value, reg_a has to equal zero, its value in the last cycle has to be in the range [1, 7], since anything else would either already have exited or would be >0 after dividing by 8. Because I wasn't sure how exactly to calculate which of those numbers it could be, I looped through all of them until finding one that worked. From here, I multiplied that output by 8 to "undo" the truncation and repeated the process in order to get the next to last output digit, and went from there until all the digits were found. Unfortunately, i had an issue with this code where it would get stuck after a few cycles; I found and fixed a bug where I wasn't taking the output modulo 8, but it still didn't work. I eventually realized the issue: like in the previous two part 2s, I needed to use a list rather than a single value so that I could track multiple paths in parallel, which in this case means using multiple "previous values of reg_a" so that I could avoid picking a value that isn't actually possible to reach from any starting reg_a given the previous digits. To finish the search, I took the minimum of all the reg_a values stored at the end. Although I definitely could have placed on the leaderboard here with a few less mistakes, such as not forgetting the mod 8 for the output, I'm still happy with my solution for this problem.

Day 18: RAM Run (puzzle, code)

Solve Times: 06:13 / #285, 13:06 / #539

This puzzle is simpler than a lot of the other recent ones, and it's also yet another 2D grid puzzle. The grid, in this case, represents a region of memory, and the input gives coordinates on the grid where the memory becomes corrupted. The goal is to navigate from one corner of the grid to the other with some amount of the memory being corrupted, and therefore impassable; in part 1, the question is how long the shortest path is after exactly 1024 cells become corrupted, and in part 2, the question is which coordinate becoming blocked makes it impossible to reach the ending position.

Since this is another grid search problem, I used the same techniques as I did for previous grid searches this year: Dijkstra's algorithm (I could have used a simpler algorithm, but Dijkstra's was easier to reach). In part 1, I read in the list of blocked coordinates, and then converted the grid into a graph with those coordinates as missing nodes; running a simple Dijkstra's on this graph produced the answer. For part 2, my idea was to use my remove_node helper function to remove each node from the graph, one at a time, until the distance to the end as calculated by Dijkstra's becomes infinity (meaning it is unreachable); this is quite slow, taking around 2.5 minutes on my machine because of the need to repeatedly run Dijkstra's and construct new graphs, but it does work well.