Daily bit(e) of C++ | Advent of Code: Day 22
Daily bit(e) of C++ #355, Advent of Code using Modern C++: Day 22.
Welcome to day 22 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/22.
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 stacking and vaporizing sand bricks.
Part one
Our goal is first to stack the bricks while keeping track of which bricks are supporting which. Once we have collected this information, we can count bricks that only support bricks with multiple supports (our result).
Parsing is refreshingly easy today; however, we still need a representation for a brick.
I got lost in the problem formulation and went on a detour to fix a non-existing bug. For clarity: our input is a snapshot of the positions of all bricks at one specific time. However, the bricks are out of order.
Fortunately, because bricks cannot go through other bricks, we can fix this by sorting the input based on the z-axis. We also need to add a floor for the bottom-most pieces to stack on top of.
To determine where exactly (and which other bricks on top of) each brick will land, we can translate the problem into a 2D x-y view. We can keep track of the highest brick at each coordinate (which is always the last dropped brick) in a 2D array.
When dropping a piece, we know it will land on the highest brick(s) within its 2D footprint.
At this point, we have information about each brick’s final position and which other bricks it rests on (is supported by). However, to determine our result, we also need the opposite direction.
Once computed, we can implement a predicate that returns true only if all other bricks supported by this brick have multiple supports (i.e. removing this brick wouldn’t cause any bricks to fall).
Part two
The only complication in part two is that bricks can fall even if they have multiple supports as long as all those supports are falling.
We can get around this using a BFS, starting from each brick that cannot be removed (from part one).
Conclusion
How did you do with today’s problems? Did you use a different approach for stacking the bricks?
Share your solutions and insights. Check out the repository with solutions and links to all articles: https://github.com/HappyCerberus/aoc-2023-cpp-solutions.