Daily bit(e) of C++ | Advent of Code: Day 12
Daily bit(e) of C++ #345, Advent of Code using Modern C++: Day 12.
Welcome to day 12 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/12.
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 counting the possible arrangements of malfunctioning hot springs.
Part one
Parsing is straightforward. We can store the textual representation of the condition as std::string and the numeric representation as std::vector<int64_t>.
One way to simplify the problem is to pre-generate feasible positions for each given number/width in the sequence. We can even filter for the initial feasible position to limit the number of options.
A valid placement can only span ‘#’ and ‘?’ characters and must be surrounded by either ‘.’ or ‘?’ characters.
We can now compute the number of combinations for a suffix and the remainder of springs using the precalculated positions. We must not leave any ‘#’ uncovered, so we also pass in the information about their positions in the text encoding.
Finally, we can fold over all the lines in the input.
Part two
While the solution from part one works, it is also very inefficient. We keep re-computing the same information for the later springs since we keep revisiting them in our recursion.
A straightforward solution is to cache the computed results (this also ended up being the faster solution for me).
The alternative solution is to compute the results bottom up. Consider that to compute the count for the second to last spring; we only need the counts for the last spring.
We can iterate over the numeric representations in reverse, computing the values for all possible placements.
Conclusion
How did you do with today’s problems? Did you use a cache or the bottom up approach?
Share your solutions and insights. Check out the repository with solutions and links to all articles: https://github.com/HappyCerberus/aoc-2023-cpp-solutions.