Advent of Code 2025, Week 2

Advent of Code

Advent of Code is a yearly Advent calendar of programming puzzles that's run since 2015, which as of 2025 has 12 two-part problems each year, each part rewarding one "star". For 2025, after completing every previous year, I'm continuing my pattern of 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. Although the global leaderboard is no more, I'm still starting each puzzle as soon as the clock strikes midnight, so I'll still be including my solve times for each problem. For the code, see:
2025 · personal library.

Day 6: Trash Compactor (puzzle, code)

Solve Times: 02:21, 14:19

This problem is pretty easy to write the logic for; its main challenge is in parsing the input correctly. The input is a long list of math problems, each containing up to four numbers and one operation (specifically the commutative operations, + and *), and the goal is just to solve all of them and calculate the sum of the results. In part 1, the numbers themselves read left-to-right and are separated vertically, meaning there are always exactly 4 numbers per problem. In part 2, the numbers are instead read top-to-bottom and are separated horizontally, which means the left- or right-alignment of the numbers has to be considered, and that there can be less than 4 numbers in a given problem.

Part 1 was very straightforward to write: I parsed the input into five lists using Python's split(), which were guaranteed to be equal length, and iterated over that length to solve each individual problem. For part 2, I initially tried to solve it by taking the same input and iterating over the longest number to "rotate" the numbers as needed, not realizing that my split() had eliminated information about the alignment of many of the numbers that I needed to correctly parse them. To fix this, I went back to my input parsing function and added a new part 2 mode that wouldn't ignore the length of the spacing between numbers. Instead, I used the positions of the operators (which are always in the first column of the problem) to find the start and end of each problem, and parsed the input into a list of problems where the numbers are strings, with the spacing maintained. From there, it was easy to "rotate" the numbers correctly and solve each problem.

Day 7: Laboratories (puzzle, code)

Solve Times: 04:01, 06:19

Day 7 brings another grid problem, as well as another scaling problem, although it's still fairly easy compared to what I'd expect to see in the second half of the month's problems. The problem presents a grid containing a start point and some scattered "splitters", in which a "tachyon beam" is emitted downwards from the start point. This beam travels straight downwards normally, but if it hits a splitter, it splits into two new beams on either side of the splitter; multiple beams in the same column merge. In part 1, the goal is to find how many beams eventually reach the bottom of the grid. In part 2, there is a twist: the beam is revealed to actually be a quantum tachyon beam, which splits into two separate timelines whenever it hits a splitter. The goal is now to find how many different possible timelines there are.

I started by parsing the input into a "sparse grid", where instead of modeling the entire grid as a 2D array, specific points of interest (splitters in this case) are stored in a set, and all other points are implied to be empty by not being in that set. In part 1, I tracked all the current beam positions on the x-axis in another set (which automatically handles removing duplicates), and went down one row at a time, creating the next row's beam set by checking whether a splitter was present or not. For part 2, I decided to use recursive dynamic programming, by writing a function to find the number of possible timelines from a given start position, and memoizing the results with Python's functools.lru_cache.

Day 8: Playground (puzzle, code)

Solve Times: 14:16, 17:48

This is the first graph problem of 2025, marking the appearance of another ubiquitous AoC problem type. The input is a list of points in 3D space, which start with no edges between them at all, and adding these edges correctly is the goal of the puzzle. In both parts, these edges are added in order of the shortest Euclidean distance between pairs of points, which connects the individual points into larger and larger groups. In part 1, only 1000 of these edges are added, and then the three largest connected groups need to be found; the answer is the product of their sizes. In part 2, edges are added until all of the points are connected, and the answer is then calculated from the pair of points in the final edge to be added.

The most natural approach to this problem is to use Kruskal's algorithm, which does exactly what this problem asks for (the animation on Wikipedia even shows the same scenario as part 2, albeit with 2D points). However, I didn't have a union-find data structure implementation handy, so I used more general graph algorithms instead, despite their slowness. I started by finding the distances between every pair of points in the input, and storing them for later. For part 1, I then iterated through the 1000 pairs with the shortest distances and added them as edges to my Graph data structure, and used the connected component algorithm to find the largest groups in this graph for the answer. For part 2, I used a brute force approach of calculating and checking the connected components after every single edge addition until there was only one component left. It ran surprisingly quickly, at only around 3.5 seconds, and I finished the problem.

Day 9: Movie Theater (puzzle, code)

Solve Times: 02:27, 03:14:48

Day 9 (specifically its Part 2) is a massive difficulty spike over every earlier problem, at least in my opinion. It's another grid problem, where the input is a list of points on the grid that are "red tiles"; each point is along a cardinal direction from the previous one, and connecting each point with a line in sequence yields a simple polygon. In both parts, the goal is to find the largest possible rectangle that has two opposite corners located on red tiles, but in part 2, there is an additional complication where the rectangle must only contain red tiles and "green tiles", which are the points on the grid that are within the previously mentioned simple polygon.

Part 1 was very simple: I checked all pairs of points in the input, multiplied their distances on each axis, and took the largest one. Part 2 was much more difficult, partly because of the size of the polygon (approximately 100,000 units on each axis), which made many approaches intractable. My first idea was to find every green tile on the edge of the polygon and check it against the rectangles, but this failed because of that issue. I then tried a new approach, where I broke the polygon into each of its line segments, took the four line segments forming each rectangle, and compared each rectangle line segment with all of the polygon line segments; any rectangle where no intersections between these segments were found was valid, and from there it was the same as part 1. However, actually getting the logic for finding these intersections right was very difficult, since simply sharing points wasn't enough to prove anything: it would have to cross that line into the polygon's exterior, which required complex logic to disambiguate that from lines that crossed into the interior or ran parallel to the border segments. I also extended this by adding an indicator of which side of a border segment was the "inside", which didn't help much.

Finally, after taking a half-hour break and thinking about the problem further, I tried a new approach: finding a "tripwire", a list of all the grid positions directly outside of the polygon. Using this "tripwire", I could check the perimeter of every possible rectangle to ensure that none of the points intersected it, eliminating the need to code all the edge cases for line segment intersection. With a few optimizations to cull rectangles that were smaller than the current best known rectangle without checking the tripwire, it finished in a reasonable time of about 2.5 minutes.

Day 10: Factory (puzzle, code)

Solve Times: 28:33, 12:11:18

In my experience, this was by far the hardest problem of 2025; I had to both wait until the morning and use an external library to solve it, two things I'm almost always able to avoid doing. In this problem, the input is a list of "machines" with some number of lights and a series of buttons. Each button is a list of numbers corresponding to a subset of the lights on the machine, and pressing a button affects all of the lights in that list. Each machine also has two sets of targets: booleans for part 1, and integers for part 2. In part 1, pressing a button toggles all of its linked lights, and the goal is to find the minimum number of button presses needed to set each machine's lights to the target state. In part 2, pressing a button instead increments the value of each light, and the goal is still to find the minimum number of button presses needed.

My Part 1 solution is simple in concept, although it took me a while to get there. Because pressing a button twice is equivalent to not pressing it, there's no reason to consider any cases with more than one press of a given button. As a result, I was able to try every possible subset of buttons, use the bitwise XOR operation to check whether that subset actually produced the target sequence of lights, and take the shortest valid one.

What Part 2 would ask was obvious even from the start, since the input includes two targets per machine, and Part 1 specifically says to ignore one of them; it's not much of a leap to assume that the ignored targets will be used in the other part. However, this didn't help me actually solve it: the first things I noticed once I started looking seriously at part 2 were that part 1's approach wasn't viable, since I can't ignore all scenarios that press the same button multiple times, and that the numbers involved were far too big for a brute force approach to be viable. My first idea was a greedy approach, which always tries to press whichever button makes the most progress (based on the largest machine it affects and the number of machines it affects) as long as it's valid. This didn't work, since in many cases there are multiple "best" buttons, and only some can lead to an actual solution, so I tried branching into all of these possibilities, but this quickly became almost as intractable as plain brute force when I tried it on the real input. This was pretty finicky, so I spent a while getting it to work on the sample input (partly due to some stupid typos).

When it immediately became obvious it wouldn't work on the real input, I had no idea where to go next. I did realize that the problem could be modeled as a system of linear equations, with one variable per button representing the number of times that button is pressed, and one equation for each light. I knew that by solving this system I could find the minimum number of button presses required, but I had no idea how to actually do that, since writing a solver would be a huge undertaking and I didn't want to use an off-the-shelf one. I slept on it, and ultimately decided to use Z3, a very versatile theorem prover capable of solving or optimizing across almost any constraints. From there, it was easy enough to express each machine using the necessary linear equations for Z3 to solve it, yielding the correct answer, although this remains a pretty unsatisfying solution as a result.

Day 11: Reactor (puzzle, code)

Solve Times: 05:13, 34:50

Day 11 is another graph problem, and in my opinion is a notable step down in difficulty from the previous two problems. The input to the puzzle is a directed graph, represented with a list of nodes with all of their connections. The goal is to find the total number of distinct paths through the graph to the "out" node. In part 1, the paths simply need to start at the "you" node, but in part 2 they need to start at the "svr" node and pass through both the "dac" and "fft" nodes.

Although this is a graph problem, I didn't actually use my graph library to solve it. Part 1 was easy to solve with a recursive search function, keeping track of the already-used nodes to avoid loops. My first idea for part 2 was to store the current path as part of this recursive search, and check at the end to ensure both "dac" and "fft" are included in it, but that turned out to be impossible due to how much larger the graph is when starting at "svr" instead of "you". (I didn't visualize the graph myself while solving, but this Reddit post illustrates the structure well). My next attempts involved trying to use a cache on the search function, which didn't help due to the fact that each call had a different set of already-used nodes, as well as trying to break up the path into three separate "legs" between the four required nodes and filter out obviously-unusable nodes beforehand, which didn't work either. However, the latter did involve me running Dijkstra's algorithm on the graph, which gave me a better understanding of the structure of the graph, which was useful despite not making it into the final code. I then decided to try removing the check for already visited nodes from the search, expecting it to fail (since I didn't know that the graph was acyclic), but to my surprise it actually worked. I then separated the graph into six segments (three on each possible path) and multiplied and added them to get the answer.

Day 12: Christmas Tree Farm (puzzle, code)

Solve Times: 14:37, 15:12

The final problem of 2025 looks very intimidating at first, but is actually among the year's easiest problems thanks to the convenient properties of its input. This input has two parts: the first part is a list of six shapes, formed from a 3x3 grid of pixels, that represent different types of presents, and the second is a list of two-dimensional regions, with a size and six quantities. Each of these quantities corresponds to one of the six types of presents, in order, and the goal is to determine whether there is any way to fit the requested quantities of presents into the region's total available space. Part 1's answer is the number of regions where this is possible. Part 2, following the AoC tradition, isn't a puzzle at all, and is instead a button that is only clickable if all 23 other stars have already been collected.

When I first saw the problem description, I had no idea how I could possibly solve it; my input was clearly too large to brute force, and I was skeptical that a greedy approach would work. My only rough idea was to find patterns of shapes that fit evenly into rectangles, and try to cover the area using them, but even this would probably have been very difficult to implement correctly, and I thought it wouldn't work in all cases. In order to get a better sense of the problem before trying to code something like that, I decided to print the size of each region alongside the total size of all shapes expected by that region, to see how much "slack" I would have when trying to fit all the shapes in. When I did this, I noticed that the regions appeared to fit into two categories: some regions' total shape area exceeded the available area by low single digits, while others had a total available area that exceeded the total shape area by 400 or more. For a few minutes I debated whether to just count the number of regions in the latter category and submit that, or whether to assume that would merely be an upper bound; I ultimately decided to submit it, and was somewhat surprised to see it was actually correct. Part 2, of course, did not present any difficulties.

Advent of Code 2025 Retrospective

The biggest changes in 2025 are the removal of the global leaderboard and the shortening of AoC from 25 days to 12. While I understand why Eric Wastl and the rest of the team decided to make both of these changes, I still do think they're both negative overall. The removal of global leaderboards is less of a concern for me, since private leaderboards still exist and the amount of AI solutions made the global leaderboards unusable for human competitors on many problems in 2024 anyways. However, I do think their removal has led to less competition even in private leaderboards, and not having a definitive global rank makes it hard to judge how well I actually did on a given problem (this could be alleviated by checking the Stats page upon submitting an answer, but it's hard to remember to do that, and I don't know how frequently it updates). The reduction from 25 to 12 days is also unfortunate, since I enjoy solving AoC problems and this change means there's only half as many of these problems to solve, but it's understandable that the team isn't able to maintain the 25-problem pace indefinitely.

As for the problems themselves, they were good overall but had some awkwardness, largely due to having to adjust to the shortened schedule. The difficulty curve was a particularly notable casualty of this: it's hard to smoothly increase the difficulty the same amount over half the time, and only having 12 days means weekend difficulty bumps are usually impossible to fit. In this case, I'd say the jump from day 8 to days 9-10 was much harsher than it should've been, while day 11 would've been better placed before those two. Day 12 was an outlier as well, and since it's not on Christmas Day anymore it's not as necessary to make it easier than its place in the calendar implies. As a minor nitpick, the names of the puzzles are less interesting: they're just a description of the location of the puzzle, as opposed to the puns, alliteration, or references used in previous years. Despite these minor issues, however, I do think this was another good year of AoC, with fun problems that felt like AoC problems and included most of the big categories (except for reverse engineering, sadly). There weren't any standout problems, but I did like Days 8 and 11, partly because I like working with graphs. Regarding my performance on this year's problems, with the exception of Day 10 (which I would have much preferred to solve without Z3), I'm reasonably happy with it. I didn't do as well as I did in 2023, but I think I largely did on par with 2024, which is to be expected since I'm pretty out of practice with AoC due to not having done anything with it since last December.