Advent of Code 2023, 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 2023, after completing every previous 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:
2023 · personal library.

This week was weaker than last for me; I only scored significantly on 1 problem, and marginally on a second, earning me a total of 119 points for the week. This boosted me up to 527 points, which is 92nd place on the global leaderboard as of December 18.

Day 12: Hot Springs (puzzle, code)

Solve Times: 10:44 / #194, 2:07:49 / #2365

This problem wasn't a great way to start out the week (from a literary perspective, not a temporal one). In this problem, you have a series of springs represented by . (working), # (broken), and ? (superposition between them), and a series of integer "runs". The problem then asks how many ways there are to set the unknown springs such that the runs of broken springs match the given ones; for example, for ???.### 1,1,3, there's only one: #.#.###, because it has a run of one broken spring, another run of one, then a run of three. Part 2 is just a scaling-up, which multiplies the length by 5 to make brute forces infeasible.

My first instinct with this problem was a simple brute force: there's 2 possibilities for each ? spring, so 2 to the power of (number of ? springs) gives the number of possibilities to try, and then it's just a matter of checking that against the given runs. This, of course, wasn't workable for part 2, which forced me to use a cleverer strategy, and I settled on dynamic programming using Python's functools.lru_cache to implement memoization in a recursive implementation. My DP solution uses a two-dimensional parametrization, the current index in the list of springs and in the list of runs, and takes in entire runs of broken springs at a time. In retrospect, it might've been better to use a solution feeding in single characters at a time, which would be much less vulnerable to edge cases that took me a while to handle.

Day 13: Point of Incidence (puzzle, code)

Solve Times: 20:41 / #1171, 29:58 / #980

This problem is a simpler one focused on finding symmetry, although unfortunately for me I made some missteps that slowed my solving down. For part 1, it gives a list of two-dimensional grids which have a horizontal or vertical line of symmetry somewhere, and asks where that line is. In part 2, there's exactly one cell in the grid that can be flipped to create a different line of symmetry, and finding that is the challenge.

To solve this, I wrote a helper function that tries first all horizontal lines of symmetry, and then all vertical ones, until finding one that works. I took a while to wrap my head around the exact conditions to check for symmetry (especially for vertical symmetry, where I probably should've just rotated 90 degrees instead), but once that was done, part 2 was fairly simple, just requiring me to loop through each position in the grid and flip it before checking its symmetry. I also had to ensure it wouldn't return the same line as previously, so I added an argument to the helper function to ignore that line, which was all I needed to finish the problem.

Day 14: Parabolic Reflector Dish (puzzle, code)

Solve Times: 04:26 / #126, 28:40 / #500

This day was a classic cycle detection problem, similar to 2022 day 17. This problem has a grid of rocks, some of which are cubes and remain stationary, and some of which are round and therefore roll downhill until encountering another stopped rock or the edge of the grid. Part 1 just asks for the positions of the rocks after tilting the platform so north is downhill, but in part 2, the platform is tilted north -> west -> south -> east in succession one billion times, and it asks for the rocks' final position after that.

For part 1 I implemented as simple a solution as possible: while loop that tries to move rocks up whenever possible, quitting when all the rocks are stationary. For part 2, I initially misread the problem and thought a "cycle" was one tilt, rather than the four tilts in four directions, which led to my code becoming awkward; once I fixed this, I set up a dict from (set of rock positions) to (cycle number). Once I found a repeat (where the set was already in the dict), I used some modular arithmetic to calculate where in the loop the billionth cycle would be, and then used the rock positions at that time to get the final result.

Day 15: Lens Library (puzzle, code)

Solve Times: 01:50 / #45, 09:17 / #46

This was the only major time I scored on the global leaderboard this week, securing 111 points. This problem involves implementing a custom hash function, and then using it to construct a custom hashmap. The input lists a series of "steps" to follow: in part 1, you're asked to find the sum of hashing each step to ensure the hash function is working correctly, and in part 2, the steps represent either "insert" or "remove" operations for the hashmap, and finding the correct answer requires both operations to be correctly implemented.

I solved this problem in the simplest way I could think of. For the hash function itself, all I needed was a for loop over each character in the string, updating the current value each time with help from Python's handy ord function. For part 2, the hashmap was represented with a defaultdict(list) in order to preserve the order of values, which is needed for the problem, because I didn't want to look up the ordered dict syntax (although, supposedly, Python's dict keeps its order anyways in recent versions). Keys to the defaultdict represented the 256 boxes or buckets (from hashing the labels) that the data structure is composed of, and the values represented the key-value pairs that the hashmap itself has. Insertions, mutations, and removals are accomplished by modifying those value lists.

Day 16: The Floor Will Be Lava (puzzle, code)

Solve Times: 01:09:01 / #4142, 01:13:53 / #3514

This day was, at least so far (hopefully it remains that way), my worst performance this year by far, because of a stupid mistake. In this problem, a beam of light is sent from the top left corner and bounced around a room by "mirrors" (/ and \), which rotate it 90 degrees, and "splitters" (- and |), which split it into two beams going at 90 degree angles if the beam enters them from the flat side. The goal is to find how many tiles the beam will eventually cover in its path, including all its child beams from splitting. In part 2, the goal is to find the maximum possible number of covered tiles with any starting position for the beam.

To solve this problem, I implemented a beam motion simulation by storing a list of beams, with a position and direction, and updating each one one tile at a time. I soon realized this would require loop detection, because the beams often loop infinitely, but once I added that by tracking and ignoring previously seen position/direction pairs, I had what I thought was a working implementation. Unfortunately, it suffered from every AoC player's worst nightmare: it worked perfectly on the given samples, but not on my actual input. I spent almost an hour trying to figure it out before finally realizing the issue: my code didn't check for mirrors or splitters on the beam's current position, but only its next position. Normally, this would work fine, but it failed on the specific scenario where there was a mirror or splitter on the very first tile the beam entered, which in my input included the top left corner. Once I finally realized this, the problem was simple from there.

Day 17: Clumsy Crucible (puzzle, code)

Solve Times: 19:20 / #204, 23:46 / #183

Although I did really well on this problem, I'm annoyed at myself for not making the global leaderboard, because I would've done it if not for making a very poor decision. In this problem, there's a grid of positions where each position has a "cost" of heat loss, represented with a number 1-9, and the goal is to find the route to move a crucible from the top left to bottom right with the minimum heat loss possible. However, the crucible can't move freely: it can only move in a straight line for at most 3 tiles, and it can only turn 90 degrees left or right; it can't turn 180 degrees, and turning is forced after moving 3 tiles in a line. In part 2, the crucible is an "ultra crucible" instead, which must move at least four tiles before turning or stopping, and must turn after moving ten tiles.

For some reason, I initially tried to write a bespoke recursive search function to solve this problem. This was a horrible idea plagued with bugs and infinite loops, and after about 10 minutes, I realized what I should've been doing the whole time was a trusty reduction to Dijkstra's algorithm, a classic AoC pattern. The nodes in this reduction are 3-tuples of (position, direction, consecutive moves in that direction), and edges exist between all nodes where the crucible can make those moves. After getting the distances from start, I loop through all nodes that have a position in the bottom right (and, for part 2, have a consecutive moves of at least 4), and take the smallest distance of any of them. I also erred on part 2 by forgetting that the crucible can start moving either right or down, before bandaid fixing it by first changing the start node to move down, and then adding a second Dijkstra's iteration with a different start node for cleanness.

Day 18: Lavaduct Lagoon (puzzle, code)

Solve Times: 08:16 / #93, 03:28:12 / #4039

This problem went from a strong performance in the first part (winning 8 points) to an almost-worse-than-day 16 one in the second. In this problem, you're given a series of instructions containing a cardinal direction and a distance, which form a loop when composed; the question is how many tiles are contained by the loop when complete (similar in a sense to Day 10). In part 2, the size is increased massively to make naive approaches infeasible.

My solution for part 1 was one of those naive solutions, drawing on my memories of day 10: trace the loop, then flood fill from every edge coordinate at once to calculate the number of positions outside the loop, then subtract to get those inside. Part 2 required more than that, and the solution I ended up remembering from the Reddit discussions of that day was the "scanlines" one: go line-by-line and calculate the interior area from that. This proved intractable, so I ended up making a modification to "batch" ranges of y-coordinates, splitting batches at every y-coordinate that was contained as the endpoint of a line. Even then, I still had issues with calculating the transitions between "inside" and "outside": I tracked the list of crossing points and used those, but it's difficult to correctly calculate them with horizontal lines. I ended up needing to track "maybe-crossings", where the crossing's location or presence depends on whether it's currently inside or outside, and then loop over the list of crossings in order to ensure these were correctly defined. All this complexity led part 2 to become by far my longest individual part, and hopefully this time it'll actually stay that way.