Daily bit(e) of C++ | Advent of Code: Day 18
Daily bit(e) of C++ #351, Advent of Code using Modern C++: Day 18.
Welcome to day 18 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/18.
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 digging out a lava duct.
Part one
Because we are working with a reasonably small size of a lava pool, we can expand all walls into coordinates, create an implicit bounding box, determine the number of spaces reachable from the outside and then the size of the lava pool is size(bounding box) - size(reachable spaces).
As usual, we start with parsing.
Then, we dig out all the walls, keeping track of all spaces occupied by the walls and the bounding box.
With the walls finished, we can run our BFS search for spaces reachable from the outside.
Part two
The change in part two forces us to switch the domain. We can no longer enumerate the spaces; therefore, we need a solution that scales with the number of walls (instead of spaces).
One possible approach is to consider whether a space is inside the walls based on the number of lines to its left.
Unfortunately, while this idea looks very simple, the reality is a bit more complex, notably because we have to consider horizontal walls.
If we implement this logic, we can then work in the domain of walls, calculating the number of spaces inside the walls from the wall positions. We can also scan the walls in row order, processing the input in chunks, since the number of spaces between walls will remain the same until one of the walls ends or a new horizontal wall starts.
We can start with the parsing. The only tricky part is the comparator for a wall. In our processing order, we want to keep the horizontal walls between the two vertical walls.
Our first step is to parse out all walls and store them in an ordered data structure. We also use this opportunity to calculate the size of the perimeter (since our inside space logic will explicitly count only spaces inside the walls.
Now for the main complicated scan. We always grab the walls that start on the current row. Then we scan over them (the walls are sorted by their column position), keeping track of the inside spaces on this row using the “odd number of lines” logic.
After we have computed the number of inside spaces, we must determine which row we can advance to. This is either a row where one of our current walls ends or the next wall in our sorted data structure if it starts before that.
Conclusion
How did you do with today’s problems? Did you manage part two?
Share your solutions and insights. Check out the repository with solutions and links to all articles: https://github.com/HappyCerberus/aoc-2023-cpp-solutions.