Advent of Code 2022 Day 24 Walk-Through

Please attempt the problem on your own before watching this video!

[hyper-neutrino]

Amendment: The blizzard position check needs to be removed for (-1, 0) otherwise this solution breaks on some inputs because the program may incorrectly think that you cannot stay on the starting square which will cause no valid solution to be found.

This is not a problem for Part 2 because I added that check, but for Part 1, I've edited my solution on GitHub.

[fredoverflow]

I brute-force a "wave front" of reachable positions without any caching (but eliminating duplicate positions in each step), and part 2 still finishes in under 1 second. The blizzard density probably constrains the exponential growth in my favor, I guess? 😁

[borkomne]

I have idea for optimizing part 2. First, cache positions of all blizzards for LCM minutes. Then, instead of calculating collision, just check frod calculated cache. At reaching any target from target list remember last minute it led to target. Now, you can discard all values from the queue and start with single value, the target itself. This will have an effect of restarting bfs search, which should lead to quicker reach of the next target. What do you think?

[LeandroCoutinho]

For part 2, I think it's faster the solve the problem 3 times with different initial and final positions, instead of increasing the state.