Home Blog Index
Joseph Petitti —

Solving Advent of Code the lazy way

Advent of Code is an annual set of programming puzzles that I've written about previously. I've participated in AoC for several years, but 2023 was only the second time I've completed a full year as it came out. All my solutions are written in Haskell, but I had to use some "hacky" techniques to get some of the answers.

Day 21

This puzzle involved counting the number of points reachable in exactly n steps from some starting position in a 2D world with obstacles. Part 1 is easy enough to brute force; with a 131-by-131 grid and n=64 you can simply count ever possible 64-step walk from the origin while eliminating duplicates.

But part 2 of the puzzle instead gives you an infinite world (the original grid tiled infinitely in all directions) and an absurd n=26501365. A key insight here is that the start position (65, 65) and 26501365 % 131 is 65, so the map of reachable locations forms a diamond centered on the start location where the points are all in the center of one of the tiled grids.

I think the "correct" way to solve this is to figure out the 9 different ways a given tile might be filled, depending on whether it's inside the diamond, at a point, or on an edge, manually calculate the number of reachable points in that configuration, and multiply it by the number of tiles that meet that condition. This is not what I did.

Instead, I realized that the number of tiles on the points of the diamonds would always be constant 4. The number of tiles on the edges would grow linearly with the size of the diamond. And the number of tiles inside the diamond would grow quadratically. Therefore the equation for the answer would look something like this:

f(n) = (a * n) ^ 2 + (b * n) + c

Where a, a, and c are constants. Hey, that looks like a quadratic equation. So all I had to do was manually solve for the first few values where x % 131 == 65 and do a quadratic fit:

Quadratic-fit of 3 points using WolframAlpha

The data is fit perfectly by a 2nd degree polynomial, so my intuition was correct. Plugging x = 26501365 into that equation yielded the correct answer.

Day 23

Day 23 is simple to understand: just find the longest path through a 2D maze. But unlike the shortest path, finding the longest path is NP-hard, meaning there's probably no general polynomial-time solution.

Honestly I don't know what the "smart" way to solve this one is, I just let my brute-force solution run for 12 hours and it eventually found the right answer.

Day 24

I spent a long time thinking through part 2 of this problem. The gist is you have 300 hailstones with an initial 3D position and velocity vector. You need to find one position and velocity you can throw a stone from to have it eventually collide with every single hailstone.

After turning it over in my head a few times I ended up with a huge system of non-linear equations.

# for each hailstone i with # initial position (hpx_i, hpy_i, hpz_i) # velocity (hvx_i, hvy_i, hvz_i) (hvx_i * t_i) + hpx_i = (vx * t_i) + px (hvy_i * t_i) + hpy_i = (vy * t_i) + py (hvz_i * t_i) + hpz_i = (vz * t_i) + pz

Repeat this with a different time value t_i for all 300 different hailstones and you can theoretically solve for the stone's initial position (px, py, pz) and velocity (vx, vy, vz).

I don't know enough linear algebra to solve that by hand, so I just plugged the whole system of equations into Z3 theorem solver. After a few minutes it spit out the right answer.

One optimizing insight is that you don't actually need all 300 hailstones, after the first 3 there's only one line that satisfies the system so you only need to check for those 3.

Day 25

The final problem gives you a complex graph and asks you to find 3 edges to remove in order to cut the graph into two disjoint subgraphs.

You could implement a complicated algorithm based on the max-flow min-cut theorem to find the 3 edges to remove. But they also become extremely obvious if you just visualize the graph. I plugged the input into Graphviz with layout=neato and got this lovely visualization:

Graphviz visualization of AoC 2023 day 25

Then I just remove those 3 edges and count up the size of each subgraph for the answer.