Modern C++ in Advent of Code: Day 24

On day twenty-four of Advent of Code we are trying to navigate bad weather.

I do encourage you to try to solve it yourself first https://adventofcode.com.

Input

Today’s input is the starting state of our map with blizzard patterns. We will take the map as std::vector<std::string>.

Efficiency, Efficiency, Efficiency

Our main problem today is efficiency. How do we efficiently search through this ever-changing search space.

Using a simple search algorithm would be completely infeasible.

The first observation to make is that the behaviour of blizzards is circular. If we separate the blizzards by direction, we do not have to adjust their positions, and we can instead calculate their position in the future using modular arithmetic.

This turns complex updates into a computation that can be done for any position at any time.

We still have to find the shortest path from start to end. We could use a search algorithm, but because our map is relatively small, it is much simpler to remember all positions we can reach at each time. Starting with zero, when we can only reach the start point.

If we iterate over time and stop the first time when we can reach the end position, we know we have the shortest path.

Links

The repository with a complete solution (including input parsing) is available here: https://github.com/HappyCerberus/moderncpp-aoc-2022.

I post daily Modern C++ content on Twitter, LinkedIn, Mastodon, Medium and Substack.