Advent of Code 2023 Day 24: Choking a 4th place finish on part 1

Показать описание

Advent of Code 2023, Day 24. Finished 4th (!) for part 1, but then struggled on part 2, finishing 244th and missing leaderboard.

Today's part 2 took me the longest of any day so far (excluding a day I missed because of a flight) at 1:19:31, but thanks to the good part 1 I was able to keep my 7th place on the global leaderboard. On part 2 I was really stumped for a while: in case the video is too long and watching me think quietly is boring, here's some a text description (which in hindsight now that I've written it is also quite long)

I tried solving some non-linear equations with SageMath (although I struggled for a while to tell it to solve over integers, I ended up using assume(var, "integer"), which I'm still not sure is right), but never got any results - I was trying to solve all 900 equations though, which in hindsight was a mistake.

Eventually I realized that if you fix the velocity, then what you have left is a linear equation, and the velocity is probably small in magnitude (all the hailstones have small-magnitude velocities, and we were asked for the sum of position coordinates, not velocity coordinates), so I thought about brute forcing over {-200, 200}3, but realized this was probably not feasible to solve a system of 900 equations that many times - at the time I didn't realize I didn't need all the equations (I really wanted to do -1000 to +1000, but this was just way too large).

Then I decided to try using least squares instead and just evaluate at a subset of the brute force range and look for spots where the OLS answer had relatively low squared error - from there I guessed that maybe the function f(velocity) = squared_error(OLS solution given velocity) was convex, so I tried doing "gradient descent" by numerically approximating the gradient with respect to velocity. I had to play with the learning rate a lot (and had a "bug" where my step size for the approximation was way too big), but eventually it got to a point that had ~integer coordinates. The error was still 1e18, but when I reevaluated with the rounded coordinates the error fell to ~200, which seemed likely to be just rounding noise.

From there I did an exact solve using only the first 5 equations (we have 3 unknowns + 1 new unknown for every 3 equations, so ceil(4.5) = 5 is the right number to use) and got my answer. In hindsight it probably would've been a lot faster if I OLS'd with fewer equations, or even just did the brute force using 5 equations.

0:00 - Intro
0:10 - Part 1
7:10 - Part 2 (confusion)
46:11 - Part 2 (good approach)
1:19:40 - Discussion
1:19:56 - "Brief" Explanation