Advent of Code 2024, Week 2

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 5: Print Queue (puzzle, code)

Solve Times: 04:41 / #331, 17:11 / #1180

In this problem, the goal is to sort pages for a safety manual according to a list of rules. The input provided has two parts: the first lists page ordering rules, which each establish that one particular page must come before another particular page, and the second contains many lists of page numbers (called "updates"), some of which follow the rules and some of which don't. The goal of part 1 is to find which updates are correctly ordered, and add their middle pages' numbers; the goal of part 2 is to reorder all the updates according to the rules, and then add their middle pages' numbers again.

For part 1, my solution was very simple: loop through each update, and check if it's correct by looping through each rule and seeing if it either doesn't apply (one or both pages is missing) or is followed, then take the updates that are correct and add their middle values to the total. For part 2, I wrote an algorithm for reordering the updates that has some similarities to a topological sort, although I didn't think of it that way at the time: run a 2D loop through each pair of two values from the update, adding the value from the outer loop to a new list only if there are no rules which would be violated, and then remove all rules with the inserted value as their first value when adding it. By running this in a while loop until all items have been added to a new, reordered, list, I'm guaranteed to add at least one value every iteration until ultimately ordering the values correctly. Once the update is reordered, pulling the middle values and summing them is very simple.

Day 6: Guard Gallivant (puzzle, code)

Solve Times: 06:39 / #496, 14:19:32 / #33203

This problem wasn't too difficult inherently, but I did make some very stupid mistakes that meant I had to go to sleep without solving the problem. In this problem, there's a guard that moves in a 2D grid along a cardinal direction, and various obstacles scattered around; the guard moves forward until hitting an obstacle, at which point it turns right and tries to move again, which continues until it exits the grid. In part 1, the goal is to find how many spaces it travels to at any time before exiting the grid. In part 2, one obstacle can be inserted at any free space on the grid, and the goal is to find how many locations for the obstacle will cause the guard to get stuck in an infinite loop.

For part 1, I used the simple solution: simulate the guard's position and direction as it moves, keeping all visited positions in a set, and take the length of that set once done. For part 2, I had quite a bit more difficulty. I thought that keeping the runtime of my solution reasonable would be difficult to do, so my initial attempts were over-focused on runtime optimization at the cost of simplicity, which led them to be buggy in ways I couldn't diagnose. After a few failed attempts, such as a recursive pathing algorithm that split at every traveled location with a branch that places an obstacle there and one that doesn't, I settled on my ending algorithm. The approach of this solution is to loop through every empty position on the grid and try calculating the guard's path, from the start, with an obstacle added at that position only. If the guard leaves the grid, that position doesn't cause a loop; if the guard ever repeats a (position, direction) pair, it does. Although this logic works fine, my implementation of it was failing, and I spent hours trying to figure out the issue, including looking on the subreddit for potential issues my code could have. Eventually, I realized what my issue was: my input parsing was incorrectly not .strip()ping the whitespace from each line before getting its obstacles, and because I assumed every non-dot character was either an obstacle or a guard, it was placing obstacles at the end of every line due to the newlines located there, causing many inputs to loop when they shouldn't. After I finally realized the issue, fixing it was very simple, and my code finally produced the correct answer.

Day 7: Bridge Repair (puzzle, code)

Solve Times: 07:44 / #978, 09:48 / #712

This puzzle is another that is easiest to solve with a brute force approach, and that I therefore did solve with a brute force approach. In this problem, there is a list of "equations" with an answer followed by a list of numbers, but without any operations between them. The goal is to figure out which equations can be made to equal the answer by inserting some combination of the operators + and * in between each of the numbers, and add up the answers from those equations. In part 2, a third operation, concatenation (||) is added, which combines the string representations of the numbers together, but the problem is otherwise unchanged.

As I mentioned, I solved this problem with a brute force approach. Using Python's itertools.product, I generated all possible combinations of operators for a given equation length: itertools.product('*+', repeat = op_poses), and then ran through each combination, evaluated the equation with those operators, and checked if it produced the correct result. I was slowed down by using the wrong itertools function, as well as not noticing that the operators were always evaluated left-to-right rather than by precedence, but still solved the problem fairly quickly. For part 2, I used the same code, with only the addition of the '|' operator to the itertools.product call and the evaluation logic being required to make it work.

Day 8: Resonant Collinearity (puzzle, code)

Solve Times: 10:43 / #820, 14:06 / #554

This is another grid-based problem. Here, the grid contains a scattering of "antennas" represented by letters and numbers, with the particular letter or number representing each antenna's frequency. Every pair of antennas of the same frequency generates two "antinodes", one at each point whose distance is exactly twice as far from one antenna as it is from the other, and in part 1, the goal is to count how many locations within the grid contain an antinode. In part 2, antinodes are instead generated at any point that is in line with a pair of antennas, as long as it is within the grid.

My solution for part 1 was to iterate through all the frequencies that appear in the input, and for each frequency, use a nested loop to check each pair of distinct antennas. To find the antinodes between a pair, I used the principle that, for an antinode to be twice as far from one antenna as the other, that means the distance between the two antennas needs to be the same as the distance between the antinode and one of the antennas. Therefore, to calculate the antinodes' positions, I took the vector from antenna 1 to antenna 2 and added it to antenna 2, and did the same for the other direction. With the antinodes' positions found, I checked that they were in bounds and then added them to a set to remove duplicates. For the second part, I used my lines library's lines_from_pos function to find all the antinodes from a specific starting position, using the distance between the two antennas as the step value. This also needed to be run twice, once from each node in the pair, but otherwise slot in perfectly into my code for part 1.

Day 9: Disk Fragmenter (puzzle, code)

Solve Times: 05:08 / #82, 01:24:14 / #4042

This is an interesting problem where the goal is to effectively defragment a disk by moving files around to optimize the available space on the disk, which I like both for the problem itself and for being my first (and hopefully not last) global leaderboard placement of the year. The input to this puzzle is a map of a disk, given in numbers of blocks that alternate between representing files and representing areas of free space. In the first part, the goal is to defragment the disk by moving individual file blocks, starting from the leftmost, into the rightmost free space until all blocks are moved, and then calculate a "checksum" on the finished disk. In part 2, after the defragmented disk is unsurprisingly extremely slow to use (according to the lore), whole files are instead moved at a time, but the goal is the same.

For part 1, I used a naive approach: represent the disk as a list, with elements being either " " for a free block or an integer for a block belonging to a file with that integer as its ID. After converting the input into this representation, I ran from the end of the disk until there was no free space left, removing the last block and, if it isn't empty, placing it at the earliest possible location. Although this is inefficient, being roughly O(n^2), I was able to code it fast enough to make the leaderboard.

Unfortunately, for part 2, I floundered for a while trying to figure out a good representation for the data and trying to debug it once I found one, making it much slower to complete. I ultimately settled on a list of pairs of (ID/" ", length) representing runs of either free space or a file, and looped through IDs from the last to the first, found the file with that ID, found the first area of free space that could accommodate it, and then stitched up the pairs representing free space near where the move occurred to avoid having multiple adjacent free areas. This approach works, but for a while I was struggling to figure out a bug in my implementation, which I was eventually able to determine. Somehow, the total size of the disk was decreasing after one particular move, throwing off the final checksum, and this move turned out to be when a file was moved exactly one space left in my representation, which had bugs with the free space stitching. After discovering this issue (through judicious use of print statements), I fixed it with a bandaid solution that just swapped the two pairs in that particular case, and got the right answer.

Day 10: Hoof It (puzzle, code)

Solve Times: 09:07 / #897, 24:46 / #2936

This is a grid-based problem again, although in this case it resembles a graph-based problem more than the earlier grid problems this year. The grid is divided into heights that range from 0 to 9, and the goal is to find "trails", which are paths starting at a location with height 0 (a "trailhead") and going to a location with height 9 by going up exactly 1 height at a time. Each trailhead has a score; in part 1, this score is the number of locations with height 9 that can be reached from it, and in part 2, this score is the number of distinct paths from it to a location with height 9. In both parts, the ultimate goal is to find the total score of all trailheads on the grid.

When I saw this problem, my first instinct was to try transforming it into a graph to make it easier to work with, which was easy to do thanks to my grid library's graph_from_grid utility function, which, as the name implies, converts a grid into a graph, with customizable logic for when to connect adjacent positions (although I was slowed down by not remembering exactly how it worked). With this graph, I iterated through every trailhead in the list of nodes, and ran a depth-first search (although a breadth-first search would have worked equally as well) from the trailhead to find all the reachable 9-height nodes from it. For the second part, in order to collect every path from a trailhead, I collected and stored a list of all the edges out of each trailhead, and then used another depth-first search, this time with entire paths as the positions rather than individual nodes; by doing so, I guaranteed that every path would be followed exactly once until reaching a 9-height node, at which point it could be tallied towards the result.

Day 11: Plutonian Pebbles (puzzle, code)

Solve Times: 03:04 / #234, 13:25 / #653

This is a nice, short problem to round out this post, and it also fits into a classic AoC problem mold, making it one of my favorite problems this year so far. In this problem, the input is a short list of "stones", represented by numbers, that transforms according to a few rules. At each transformation step, known as a "blink", stones with the number 0 change to a 1, stones with an even number of digits split into two stones (one with the first half of the digits, and the other with the second), and stones that are neither have their number multiplied by 2024. In part 1, the goal is to figure out how many stones exist after 25 blinks, and in part 2 the goal is instead to run 75 blinks.

This is a classic "scaling" type of problem which has made many appearances in AoC before, where part 1 is tractable with a naive approach, but part 2 requires a cleverer approach that abstracts out irrelevant parts of the data in order to reduce memory usage. In this case, the naive approach is to store the stones as an actual list, which was my approach for part 1: each blink creates a new list, then runs through the existing list and appends the transformation of each stone in the list to the new list. This is fast enough for the relatively small quantities required for 25 blinks, but for 75 blinks, it's totally inadequate. To solve this, I realized that the representation as a "list" was entirely a red herring, because the only thing that matters for a stone is its number, not its position or neighbors or anything else that requires a list to keep track of. This means that I could represent the stones as a dictionary mapping a stone's value to the quantity of stones that have that value, which I did with Python's collections.Counter. With this representation, the problem can be solved easily and quickly.