Daily bit(e) of C++ | Advent of Code: Day 10
Daily bit(e) of C++ #343, Advent of Code using Modern C++: Day 10.
Welcome to day 10 of Advent of Code using Modern C++. Before you start reading, I highly encourage you to try to solve the two problems yourself: https://adventofcode.com/2023/day/10.
If you missed it, I have prepared a template repository for C++, with a development environment (through a devcontainer) with a bleeding edge version of the C++ toolchain: https://github.com/HappyCerberus/aoc-2023-cpp.
Today, we are searching through a pipe maze.
Part one
We can use breadth-first search to find the most distant point in a loop. Applying the breadth-first search to a loop means that the two search directions will eventually meet.
When this happens, we will encounter an already visited space that was visited with the same distance. Note that we don’t have to handle the case when this space doesn’t exist because of the problem formulation.
Part two
For part two, we must count the number of spaces encircled by the loop.
The big complication is that we should only count the spaces where we would have to cross the loop to reach them from the outside. A space still counts as reachable if we can reach the space by walking along the loop (in the same spaces).
Introducing fake spaces is an easy trick to solve a problem of this type. Notably, we can shift all proper coordinates to {coord.row*2+1,coord.col*2+1} and consider the newly created coordinates empty.
With this translation, we can start at {0,0}, and using a BFS, mark all spaces that are reachable from the outside. When we are on a coordinate that neighbours two pieces of the loop, we must ensure the loop doesn’t connect through this coordinate.
However, for this to work properly, we have to handle the starting space. In part one, we would never revisit it, so starting the exploration in all four directions was sufficient. For part two, we must know the underlying pipe shape to detect that we are crossing the loop.
With the start space translated into the proper shape, we can start our second BFS at {0,0} in the newly translated coordinates.
At this point, we have “visited”, which contains all spaces that are part of the loop and “expanded_visited”, which contains all spaces that are reachable from the outside (in the converted coordinates).
The spaces encircled by the loop are those not in “visited” or “expanded_visited”.
Conclusion
How did you do with today’s problems? Did you manage to navigate the maze?
Share your solutions and insights. Check out the repository with solutions and links to all articles: https://github.com/HappyCerberus/aoc-2023-cpp-solutions.