Daily bit(e) of C++ | Advent of Code: Day 3
Daily bit(e) of C++ #336, Advent of Code 2023 using Modern C++: Day 3.
Welcome to day 3 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/3.
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 trying to decode an engine schematic.
Part one
Part one doesn’t require much thought. We can brute-force the problem by checking for adjacent special characters as we parse the input.
The only tricky part is that we have to take care of special characters that are one column ahead and after the parsed number. The first case can be addressed by remembering the presence of the previous step. The second case is naturally addressed when we finish parsing the number, which happens once we encounter a non-digit character (i.e. one column after the number).
Part two
The second part poses an interesting conundrum. We are explicitly looking for gears that have exactly two numbers next to them. Doing this type of check while parsing the input would be pretty cumbersome, as the numbers can be ahead and behind the gear.
One way to eliminate this complexity is to switch to a two-stage approach. First, we parse the input into a more helpful format, and only then do we try to analyze which gears have exactly two numbers next to them.
For gears, we care only about the position; for numbers, we also need the value. The position of a number is the row and the range of columns the number spans.
Once we finish parsing, all we have to do is iterate over all the gears and, for each, lookup the adjacent numbers. If there are exactly two of them, multiply and return the value.
We are missing functionality to get the numbers adjacent to a column from our NumStore. Fortunately, since we parsed left-to-right, the numbers are stored in each NumStore in sorted order. We can implement a lookup based on lower_bound as a method of the NumStore class.
Finally, we can put this together by introducing a lambda that will give us the gear ratio for a gear. Since we aim to return the total sum, we can return zero for any “improper” gear.
Conclusion
How did you do with today’s problems? Did you use a similar two-stage approach for 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.