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:
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:
Then I just remove those 3 edges and count up the size of each subgraph for the answer.