Advent of Code 2024, Week 4

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 19: Linen Layout (puzzle, code)

Solve Times: 08:21 / #980, 11:44 / #815

This is another fairly easy dynamic programming problem, meaning a problem that is best solved by recursively breaking it into smaller problems. Here, the input is a list of "patterns" of colored "stripes" (strings made of lowercase letters), followed by a list of "designs" (longer strings made of those same letters), and the goal is to construct the designs by arranging some sequence of the patterns. In part 1, the goal is just to find how many designs are possible to make; in part 2, the goal is to count the total number of ways each design can be made with the provided patterns.

In Python, implementing caching at the function level is very easy thanks to functools: all it takes is @lru_cache(None) above the function definition, as long as the function's arguments are all immutable. As this is a dynamic programming problem, I used this to add caching (also known as memoization) to my solution for both parts in order to ensure they would finish reasonably quickly. In part 1, I wrote a simple recursive function to check whether a design is possible to make: if it is equal to any available pattern, return True; otherwise, for any pattern that it starts with, recur by removing that pattern from the beginning; if none of those match, return False. By applying this to all the designs in the input, I then count how many are possible to form. For part 2, I used a very similar recursive structure. Instead of returning True when a pattern is equal to the current design, I return 1, and instead of applying a logical OR across all the recursive calls, I take their sum; otherwise, the code looks the same.

Day 20: Race Condition (puzzle, code)

Solve Times: 10:49 / #151, 01:00:37 / #1398

In this problem, there's a winding racetrack that has only one path, and the goal is to reach the end as quickly as possible. Since there's only one path, to make the race more interesting, racers are allowed to "cheat" and pass through walls in accordance with a simple rule: the cheat can only last for two steps, and must end on a position that is within the track. A cheat is defined as a pair of a start and an end position, and the goal is to calculate how many of the possible cheats save at least 100 steps. In the second part, the rules for cheating are different, allowing cheats of up to 20 steps rather than just 2, but the goal remains the same.

The key insight in this problem is that the path is completely linear: there's only one path from the start to the end (which is stated in the problem, albeit not very loudly), and therefore, every position on the path can be simply mapped to the time time taken to reach it, which will always be unique. Further, by defining a cheat in the way the problem specifies, a pair of positions that are both on the track, it is very easy to calculate the time saved by a cheat: subtract the track times of the two points, then remove the time taken to do the cheat itself. My solution for part 1 used this in order to calculate the time saved by a cheat, and enumerated all cheats by following the path and, at each position, finding all the cheats that can start there. To do this, I found all of the position's neighbors that are walls, and then all of the neighbors of those positions that are non-walls, and those non-walls, paired with the starting position, defined a cheat. By using these pairs as a key, I made a dictionary of every possible cheat and the amount of time it saved, and then counted the number of values >=100 in that dictionary for the result.

The same idea as I used in part 1 works in part 2, just with a greater range of positions to search, but although that's the solution I ended up with, the path I took to get there was rockier. I began by writing a function to get every possible end point for a cheat with a given start point, by finding all in-bounds positions with a Manhattan distance of 19 or less (which isn't correct). By looping through all of those positions where the end of the cheat wasn't a wall, I could get every possible cheat on the track, and calculate the time saved by each one in the same way as part 1, and therefore the result as well. Unfortunately, because I used 19 instead of 20 for the search, I got the wrong answer, and tried looking in the wrong places for the issue: I reread the problem and (incorrectly) decided that what cheats could only reenter the track once, and so I would need to account for that in generating the possible cheats. I did this by creating a graph with connections between any adjacent cells in the grid where at least one was a wall, so that I could use a breadth-first search to find every possible cheat that only reentered the track once. This also didn't work, and so I reread the problem statement again and realized that my initial approach was correct, but that I needed to use a range of 20 instead of 19. After restoring that code and making the change, I had a working solution and was able to get the correct answer.

Day 21: Keypad Conundrum (puzzle, code)

Solve Times: 30:16 / #34, 02:21:26 / #844

This was a very difficult problem, as you can see from my part 2 time and the fact my 30 minute part 1 time was the 34th fastest solve in the world. This problem centers around entering codes into keypads like the ones on old phones as well as like the arrow keys on a keyboard. The goal is to enter five codes, given in the puzzle input, into a phone-style keypad with an extra "A" key on it, but the only way to do that is to have control a robot to enter the code using an arrow-style keypad that also has an extra "A", and the only way to control that robot is to use another arrow-style keypad, and so on. In part 1, this indirection contains two intermediate robots, and in part 2 that number increases to 25, but in both parts the goal is to find the shortest possible sequence of arrow keys to press to eventually get the innermost robot to enter the codes in the input.

My implementation for part 1 was fairly straightforward, although it took a while to write: have a function that can find the sequence of moves needed to produce a sequence of button presses on any keypad, then apply that three times to get the answer. I did this by tracking the current position (starting at the location of "A" on the keypad), finding the path to the next position in sequence and adding that to the running path, adding an "A" to actually press the desired button, and repeating until finishing the entire sequence. This approach mostly worked, but there was one issue with it: in some cases, there are two possible paths to the next position, roughly corresponding to going horizontally first or going vertically first, and I didn't know how to pick the more optimal one, because which one is better depends on what the rest of the path around it looks like, and requires extrapolating out to further layers of robots. To solve this, I tried a randomized approach: pick a random valid path when needed, and just run the code 10,000 times and take the best result from that. Shockingly, this actually worked, and I got 34th place on the global leaderboard, my best performance this year.

Part 2, unfortunately, did not go quite as smoothly. Because of how large the paths would grow to, my approach of keeping the entire path in memory wouldn't work at all. However, when looking at the way that the paths form, I noticed that they would always make zero or more moves, then press A, then repeat, which translates to "move somewhere, then move back to A, then repeat" for the next robot out. Because each of these sequences separated by A are entirely self-contained, I could just use a Counter to represent the number of times each such sequence appears. With this, the problem is reduced to finding the optimal sequence of key presses for robot N to produce a given sequence for robot N-1, but doing this was still not trivial. The main issue is the same issue as I had in part 1: sometimes there are multiple possible paths between two points, and deciding which to use is very difficult. I first tried to randomize it again, and use a cache to both speed up processing and ensure that the same random choice is made each time in a single solve, but the space of possible solutions ended up being too large anyways, and none of my answers were as low as they should've been. Ultimately, after over an hour of trying to find the issue, I added two lines to my path finding function on a whim:

This overrides the random selection to always go horizontal-first when going from the A key to the down key, and otherwise changes nothing. I was intending to just use this to better understand how the problem worked, but this change actually led my code to produce the same answer every random iteration, which turned out to be the correct answer as well once I submitted it, and so I stopped there and pushed the code up to Gitlab.

Day 22: Monkey Market (puzzle, code)

Solve Times: 03:03 / #156, 13:49 / #139

This is a fun short problem that combines a hash-like algorithm with a sliding window. In this problem, the goal is to buy bananas from various buyers in a monkey market in exchange for information. Each buyer starts with a "secret number", and calculates the next secret number in a sequence using bit shifts, up to a total of 2000 new secret numbers; the goal of part 1 is simply to calculate all of the last secret numbers. In part 2, the actual price calculation comes into play, as the ones digit of the current secret number. However, to choose when to buy the bananas, the monkey serving as a liaison to the buyers has to be given a sequence of four consecutive changes in price, and will only buy the first time it hears that sequence from a given buyer. The task is to find which sequence of 4 price changes will lwad to the greatest total number of bananas bought.

My part 1 solution was very straightforward: I wrote a function that produced the next secret number given the current one, then for each buyer in the input, applied that function to the starting secret number 2000 times and added the result to a running total. Part 2 was more interesting, and I started by copying my part 1 code and tweaking it to save all the prices into a list for each buyer, and then created a second list of the price changes for that buyer. I realized that trying to guess a sequence of price changes to search for wouldn't be scalable, so from here, I thought of a solution that would only require one pass over each price change list. I created a Counter to map every possible sequence of price changes to the total value of selling after those changes. Using this, I iterated over every buyer's list of price changes using a 4-long sliding window, and maintaned a set of all the price changes that already occurred for that buyer. Whenever the current window wasn't in that set, I added the current price to its entry in the Counter, and then added it to the set to avoid trying to sell again later on that sequence with the same buyer. Once I finished all of the buyers, getting the final answer was as simple as taking the maximum value across the Counter.

Day 23: LAN Party (puzzle, code)

Solve Times: 04:14 / #304, 26:57 / #1114

This problem is a graph problem, where the graph represents computers connected in a network, and the goal is to analyze the connections between said computers to find which ones are involved in a LAN party. In part 1, the task is to find all groups of three computers with a "triangular" connection, meaning that all three of the computers are directly connected to both of the other computers, and where at least one of the computers' IDs starts with a 't'. In part 2, the challenge is instead to solve a classic graph theory problem called the clique problem, which involves finding the largest subset of the graph where all computers in the subset are directly connected to all other computers in that subset.

The first thing I did to solve this problem was convert the input into a more useful form: I used a set to list the nodes and a defaultdict to track the edges, and built a Graph object from my personal library out of them. For part 1, I looped through every node in the graph that began with "t", then looped through each of that node's neighbors, and then looped through each of those neighbor nodes' neighbors. In the innermost loop, if that node bordered the outermost node that starts with "t", I knew that there was a "triangle" there (since the other two connections are implied by the loop), and so I added it to a set (to avoid duplicates), then returned the length of that set at the end. Part 2 was more complicated, but I began by copying the code from part 1 to create the graph from the input. After some thinking, I realized that I could loop through each node and take the powerset of its neighbors to find all possible cliques in the graph, and then write another function to check if a list of nodes is actually a clique. I used a variable to track the best clique found so far, updated it as I found better cliques, and used it at the end to get the answer. I later adjusted this to reduce the search space significantly (I noticed that every node was in a 12-clique except for the one 13-clique for the answer, and every node had exactly 13 edges, so I searched only for 13-cliques), but the general approach remained the same and I was able to solve the problem.

Day 24: Crossed Wires (puzzle, code)

Solve Times: 04:58 / #83, 01:41:57 / #434

This is another reverse engineering problem, and its part 2 is one of the hardest problems this year, only comparable to day 21 in difficulty. The input in this problem is a complex electronic circuit that uses AND, OR, and XOR logic gates, alongside with a list of 90 different input wires that are labeled with either "x" or "y" followed by a number. In part 1, the goal is to simulate the circuit with the provided inputs and find the output, which is a binary number on the wires labeled with "z" followed by a number. In part 2, it's revealed that the goal of the circuit is to add the two binary numbers given on the "x" and "y" wires and produce the sum, but there are four pairs of gates whose outputs are swapped, causing the circuit to fail. The goal is to find these four pairs and combine them in order to yield the answer.

For part 1, I started by setting up a dictionary to represent the value of each wire and adding the input wires' values to it. From there, in order to simulate the circuit, I used a while loop to repeatedly re-run a for loop over all of the gates that hadn't been resolved yet. I did this because I knew that the gates wouldn't necessarily be in order, and so trying to do a single for loop would result in many of the input wires for a gate not being set yet. For any gates where that isn't the case, meaning it's possible to calcluate their value, I add the output wire's value to the dictionary and remove the gate from the next iteration of the loop. Once every gate is processed, I use the dictionary to convert the output wires into a decimal number and return it.

For part 2, I started by analyzing the input to try to understand what the circuit is supposed to look like, and thereby spot the errors in the broken circuits. I expected it to look like a standard binary adder circuit, and after writing some code to print the evaluation path and drawing it out, my expectations were confirmed. Bit n in the output is calculated as the XOR of two bits: the n-th sum bit and the n-th carry bit. The n-th sum bit is calculated from the XOR of the n-th input bits, and the n-th carry bit is calculated from the OR of two previous bits. One of these bits is the previous bit's carry, calculated by taking the AND of the (n-1)-th input bits, and the other is the carry from the rest of the calculation, which is obtained from the same inputs as the (n-1)-th output bit, but using an AND operation instead of an XOR. Once I understood the circuit layout, I tried to write a solution that would try to match each bit's evaluation pattern to the expected pattern that I just outlined, but I couldn't get it to work. After various failed attempts, I decided to instead solve the problem manually, but with some code to assist in finding the issues and verifying my solutions. I started by writing the ability to swap pairs of output wires, so that I would be able to verify my solutions, and then added functionality to randomly generate numbers up to 2^n for some n and compare the result of running them through the circuit with the correct sum. By changing n, I could find which specific bits were broken, and then manually compare the actual circuit in the input with what it should look like. Once I figured out a potential swap, I had the code change the logic gates accordingly to see if it would fix that bit, and if it did, moved on to the next bit until I found all four swaps.

However, even though this process did get me the answer, I wasn't fully satisfied with a manual solution, so later in the day I decided to write an automatic solver instead, using my knowledge of the correct solution and the circuit layout. I ended up with a fairly primitive solution, which understands the intended structure of the adder for each bit, and when that structure isn't found, can look at the other parts of the circuit to find the error. I started by identifying three gates for the current bit: the gate for the n-th sum bit, the gate for the (n-1)th carry bit, and the gate for the n-th output bit. If the latter gate didn't use an XOR to calculate its output, I knew there was an issue, so I searched for the gate to swap it with. Since the former gate (the n-th sum bit) should output directly into the output bit gate, and nowhere else, I used that to find the wire that needed to be swapped with the broken output wire. This was enough for most of the broken wires in the circuit, but one swap required a slightly different approach. For that one, I checked for whether the output gate was correctly linked to the sum bit or not. If it wasn't, I found the incorrect input to that gate by looking for an AND gate, since the inputs should be a XOR and an OR, and then swapped that wire with the output wire from the sum bit's gate. With these search criteria, I looped through all the bits in the circuit (except for bits 0, 1, and 45, since those have slightly different logic) and was able to produce the correct answer. In developing this automated solution, having the manually calculated answer available to reference was crucial, as was being able to use my scaffolding code for verifying the manual solution; it's a great example of how manual and automatic solutions can work together in AoC.

Day 25: Code Chronicle (puzzle, code)

Solve Times: 08:02 / #442, 08:05 / #375

Like most day 25 problems, today's was quite simple, to avoid taking too much time on Christmas Day itself. In this problem, the input is a list of shapes for keys and locks, represented as an image, where the height of the pixels in each column of the image defines the shape of that key or lock. Any key-lock pair where the key and lock would overlap is considered impossible to fit, and all other pairs (no matter the shape of the key and lock) are considered possible; the answer is the number of key-lock pairs that are possible. Part 2, as is traditional for AoC, isn't actually a puzzle to solve: it's just a button to press to get the star, but it requires getting all 49 other stars in the year to be available.

I wrote a very simple and straightforward solution that, as a consequence, took somehwat longer to code than it might've taken to think longer and write a cleverer solution, though it doesn't matter very much. Following the ideas in the problem description, I started by taking every image and converting it into a list of heights for either the lock pins or the key segments, depending on which type it is. Once I did that, I took every lock-key pair and compared their heights in each column: if any column's heights summed to more than 5, that meant they overlapped, and if none did then they didn't. With this, I could count the number of non-overlapping lock-key pairs, and obtain the final answer of Advent of Code this year. For part 2, I pressed the button and then went back to read the lore.

Advent of Code 2024 Retrospective

I don't have a whole lot to say about this year that I haven't already said about one of the individual problems, so this will be pretty short. First, my performance on the global leaderboard was much worse than 2023: that year, I placed 14 times for a total of 759 points, which landed me at 80th place on the global leaderboard; this year, I only managed to place three times and score 104 points. The elephant in the room here is the much greater levels of AI cheating this year when compared with previous years: for any simple enough problem (which makes up the majority of problems), the top of the global leaderboard is filled with times that are clearly impossible for even the fastest humans, and can only have been achieved by LLMs being fed the problem as soon as it opens. Although this isn't not a factor in my worse placements this year, the factor I find more worthwihle to consider is my own skill issues: quite a few problems this year were well within my ability to leaderboard on, but I failed to do so due to one stupid mistake or another. Examples include Day 22, where I confused the different sample inputs and went searching for a nonexistent bug, Day 17 part 2, where I forgot to use mod 8 for the output instruction, and Day 15 part 2, where I was only a few minutes off the leaderboard and could've reached it by being just slightly faster.

As for the year's AoC itself, rather than my skill at it, it was another great year, with some amazing problems and some fun but forgettable ones. Some of my favorite problems this year included days 9, 15, 17, 22, and 24, which I've written about further in this series of posts, but I liked for the interesting challenges they presented as well as the success I had in solving them. Some of the grids wore out their welcome a bit, but most of the grid problems were unique enough from each other that I didn't really mind them using a similar input structure. The only problem I particularly didn't like was day 14 part 2, owing to how vague the requirements are, but it is a fair problem with an interesting premise. I liked the theme of trying to find the Chief Historian (which you can read about in the problem descriptions; I didn't mention it, since I focused on the problems themselves, but it's fun to read), and the lore was well-written with the classic AoC absurdism. This was a great year of AoC, and I'm excited for the next one!