Modern C++ in Advent of Code: Day 12

It is day twelve of Advent of Code and we looking for the shortest paths on a map. I do encourage you to try to solve it yourself first. https://adventofcode.com

Input

Today’s input is a map, with the elevation represented using lower-case letters. On top of that we have a start S and end E.

We will take the input as std::vector<std::string> and also detect the positions of S and E in the input.

The shortest path from start to end

For part one, we aim to find the shortest path from the start to the end. The main caveat is that we can only go up by one elevation level.

We can use a simple breadth-first search as the search algorithm, which only leaves the actual logic of determining whether we make a step from one position to another. We can wrap this logic in a lambda.

The shortest path from ground level to the end

For part two, we have a very similar problem, however, now the additional twist is that we want to find a path from any ground-level position a or S.

We can re-use most of our part one solution, however, to determine the shortest path, we need to find all of them, meaning that we need to start from the end, exploring backwards. Whenever we reach the ground level, we potentially update our best-known 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.