Advent of Code 2023, 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 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.

At the end of this week, and therefore at the end of AoC 2023 as a whole, I have 759 points, placing me at 80th on the final global leaderboard. This is the first time I've landed on the global leaderboard in my three years of doing AoC, and I'm very glad to have done so!

Day 19: Aplenty (puzzle, code)

Solve Times: 08:10 / #36, 36:15 / #295

This was a fairly easy problem with echoes of day 5 (though I did better on this one), and a good start to the week, which scored me 65 points. In this problem, there's a list of parts with four values: X, M, A, and S, and a list of rules with a label and a list of checks of the form [X/M/A/S] [>/<] [number] [destination], or sometimes just [destination]. The rules are used to route parts between them or to the special locations "A" and "R" based on their values, with A meaning Accept and R Reject. The first part simply asks for which of the given parts are accepted, but the second part asks for how many parts out of all possible parts (with X, M, A, and S all ranging from 1 to 4000) will be accepted by the ruleset.

For part 1, I implemented a simple simulation of the process of following the rules and ran each part through it, which was sufficient for 36th on the global leaderboard; I could've used eval to simplify some of the logic, like a lot of the solutions I saw did, but I didn't think to do that and instead checked for the "<" and ">" strings. For part 2, brute force is clearly intractable, so what I ended up doing instead was recursively slicing ranges down, starting with a range of (1, 4000) for all four variables, and following each rule to create branching paths until reaching an "A" or "R", with smaller ranges each time. This gave me a list of valid range sets, which I could turn into the number of valid combinations with a bit of multiplication and addition.

Day 20: Pulse Propagation (puzzle, code)

Solve Times: 15:49 / #20, 29:34 / #15

This day was my strongest performance in AoC, both this year and ever, earning me 167 points in total. In this problem, there's a list of modules that can communicate by sending "low" and "high" pulses to each other. There's three types of modules: a flip-flop, which stores its current state, and toggles that state and sends the new state upon receiving a low pulse, a conjunction, which stores the state it last received from each of its inputs and sends a low pulse if all of them are high, and otherwise a high pulse, and a broadcaster, which just sends the pulse it receives forwards. In part 1, there's a button that can send a low pulse to the broadcaster, and the question is how many pulses will be sent after 1000 button presses. In part 2, the problem asks how many button presses it takes before the module "rx" receives a low pulse.

For part 1 (after some initial confusion because my session token had expired sometime yesterday), I again just implemented the rules as quickly as I could, storing high/low pulses as booleans, using a queue to store the pulses, and using dicts to store the modules' state. I managed to do this extremely quickly relative to other solvers somehow, giving me 20th place. For part 2, after it ran for a few dozen seconds I could tell it wasn't brute force, so I looked at the input to see what fed into the rx module. When I noticed it was fed by a conjunction module with four inputs, I thought it might be another cycle detection problem, and tried recording the number of presses it took for each of the four inputs to pulse high. After some confusion, I realized it was another LCM problem like Day 8, and took the LCM of the cycle lengths to get my correct answer.

Day 21: Step Counter (puzzle, code)

Solve Times: 05:11 / #142, 2:16:01 / #850

Unfortunately, after day 20, my performance began to decline sharply. Day 21 is another problem requiring careful input inspection; in it, there's a grid of open tiles . and walls #, and an elf that starts in the center of it. In part 1, the puzzle asks how many positions on the grid can be reached from the start in exactly 64 steps allowing backtracking, but the second part ramps up sharply: it has the grid tile infinitely in all directions, and asks how many tiles are reachable in exactly 26501365 steps.

For the first part my first instinct was to use Dijkstra again, checking for the number of positions whose distance was both within 64 and even. For the second part, I was stumped for a while before realizing that the center rows and columns of the input grid were empty (a feature not present in the sample input), which meant the way to reach the center of a tile from another center was equal to the input grid's length of 131. It also happens that the number of steps needed is exactly 202300.5 * 131, which I also noticed. Because of the way the elf moves, the total shape of the elf is a diamond, so I modeled that with a for loop of increasingly large layers around the diamond. Because 131 is an odd number, at each layer I alternate whether the remaining step count is odd or even; inside each layer, I add a number of reachable tiles based on the number of grids at that layer. Once I reached the last 131 + 65 steps I knew I needed special handling for the outermost layer, so I calculated the distances of each tile from the bottom, left, right, and top centers, and calculated the outer layers using the number of tiles that are reachable from those. At first, I didn't realize that I was missing the even further-out layer which runs from the corners, which lost me over an hour; once I realized this, I ran a search from each corner as well to account for it, and finally was able to get the solution.

Day 22: Sand Slabs (puzzle, code)

Solve Times: 1:26:07 / #2042, 1:43:47 / #1721

This problem is an interesting hybrid of 3D Tetris and Jenga, albeit also a quite difficult one that continued my streak of terrible placements. In this problem, you're given a set of 3D "bricks" which begin in midair, as they fall to the ground. First, you need to find where all the bricks will settle when they finish falling; after this, the goal is to try removing one brick at a time and see how many other bricks will fall when that brick alone is removed, and then sum that value across every brick. For part 2, the goal is the same, but the bricks that fall when a brick is removed will cause the bricks above them to fall as well.

For the first part, my main difficulty was finding a way to to get the bricks' final positions in a reasonable amount of time. After some false starts with intractable solution attempts, what I ended up with was storing the current target z-position for the bricks, starting at 1. I then loop through every brick that hasn't already fallen to a settled position and calculate how far it's able to fall, and store all bricks that can fall to the ideal z-position; I then drop all of them, and repeat until no bricks can fall to the ideal z, at which point the ideal z is increased until every brick has settled. Once this is done, I loop through every brick again to see if removing it leaves any other bricks unsupported, and if so how many, to solve part 1. It would've been much smarter and more efficient to just sort the bricks by starting z-position and drop them in that order, but I didn't realize that until looking at other peoples' solutions. For part 2, I kept the bricks' state from part 1 to avoid needing to re-find it, then converted it into a tree of bricks that support other bricks and a tree of bricks that are supported by other bricks, which I then walked to calculate the answer for each brick, looping through them again, and got the final answer.

Day 23: A Long Walk (puzzle, code)

Solve Times: 29:16 / #1151, 1:29:19 / #974

This problem presents a form of the longest path problem. In this problem, there's a forest (represented by a grid) and the goal is to find the longest valid path from the start to the end that doesn't use any tile twice. In part 1, the path is constrained by "slopes" that form intersections with exactly one entrance and two exits, and in part 2 these slopes are removed, making the problem space much larger.

For part 1, I used my graph_from_grid utility function to turn the input into a graph, following the slope rules. To find the longest path, I maintained a list of running paths, forked it at each intersection, and checked the longest length at the end, though this was only after some false starts with Dijkstra's. For part 2, the problem space is too large for that to work, so I had to find a better solution. I started by simplifying the graph: the only nodes that mattered were the start, end, and intersections, and everything between them can be reduced to the length of the edges between intersections (though I had to be careful to instead take the longest path between the intersections instead of the shortest like usual). I then used the same logic as part 1, but with aggressive heuristics to trim down the amount of paths under consideration: I stored the best distance for every pair of (current node, all seen nodes), and trimmed any paths that had the same current and seen but a lower distance, and I trimmed all paths whose current distance was less than 1/1.4 of the best distance so far. The 1.4 was derived empirically, by starting from 1.1 and increasing it until the output stopped changing; I didn't really like this problem because it fits into that "find a heuristic" mold.

Day 24: Never Tell Me The Odds (puzzle, code)

Solve Times: 1:14:16 / #1885, 13:15:13 / #4598

This problem is probably the hardest one this year, which led me to both use a third-party library and look at others' solutions for ideas before actually solving the puzzle for the first time this year, as well as being the first and only problem I couldn't finish before going to bed. In this problem, you're given a long list of hailstones, which are particles in 3D space, that have an integer starting position and constant velocity. The first part is relatively simple: it asks whether the hailstones' paths (not the hailstones themselves!) will intersect at some point in the future inside of a given x and y range. The second part is not at all: it asks for a position and velocity for a rock such that the rock will exactly intersect every hailstone at some integer time.

For the first part, it's a relatively simple matter of using algebra to find the intersection between the two lines, which is what I did, and checking if its (x, y) position is within the target area and if the intersection was actually in the future (easily checked by looking at the signs of delta-x versus x velocity). For the second part, it's a far less simple matter of algebra. My first idea was to again solve it algebraically by writing a system of equations using three hailstones and the rock, which contains nine equations (the rock's x, y, and z position at some time equals each hailstone's at that time) and nine unknowns (the rock's x, y, and z position and velocity, and the three times). Unfortunately, because it contains a nonlinear term (unknown velocity times time), solving this system manually is near-impossible and I gave up on it. I then tried installing the Z3 library and having it solve the system for me, which it did trivially, but I wasn't satisfied and avoided submitting until I got an answer that didn't use any external libraries. Looking on Reddit, I saw that it was feasible to run a brute force (with some preprocessing) to find the velocity vector by changing every hailstone to move in the rock's frame of reference and negating it, and looking for an intersection between every hailstone's trajectory. I found this intersection by running part 1's code on the first two hailstones, checking if it was an integer, and if so finding the z-coordinate of the intersection and checking that it was also an integer. From there, I did a sanity check that all other hailstones also hit this point, and if so I know it's the right answer, and can just return the sum of the coordinates of the intersection position.

Day 25: Snowverload (puzzle, code)

Solve Times: 3:24:14 / #3359, 3:24:18 / #2784

This problem was easily my least favorite this year, for a couple reasons: its difficulty is far harder than normal for a Day 25 problem (which are normally easy since they're on Christmas itself), and it's much easier to solve with a third party library or external tool as opposed to without them. In this problem, you're given an undirected graph which can be partitioned into two disconnected regions by removing exactly three edges, and the goal is to find the number of nodes in each disconnected region.

I quickly recognized this problem as a min cut problem, but actually solving it was a more difficult task. I tried a litany of different failed approaches, including the max flow-min cut theorem, Karger's algorithm, plain brute forces, and trying to find the most commonly used edges and assuming they're the three connecting ones. When all of these failed, I again looked to Reddit for ideas, and saw a Monte Carlo solution that I'd had similar ideas to before, but none working. In this solution, which I subsequently implemented, I run a DFS between randomly selected pairs of nodes and store the number of times each edge is used in the paths, then assume the top three used edges are the ones to remove. I then modify the graph to remove them, and find the number of nodes in one of the two disconnected components; the number in the other is found by subtracting from the total number. Part 2, as is traditional, doesn't have a puzzle to solve: it just asks whether the previous 49 stars were all collected first.