Daily bit(e) of C++ | Advent of Code: Day 5
Daily bit(e) of C++ #338, Advent of Code using Modern C++: Day 5.
Welcome to day 5 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/5.
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 analyzing the requirements of seeds to plant one as close as possible.
Parsing
Parsing the input is fairly straightforward today. We can read integer triplets for the main part of the input (the mappings) until we fail and skip over the text's non-digit portion.
From the problem formulation, it is clear that we will need to look up a mapping based on a threshold value. This requires either an ordered associative container std::set (or std::map) or a sorted std::vector.
Part one
For part one, we are treating the seeds as singular values, and our goal is to find the closest (i.e. minimum) location after converting the seed through the entire chain of mappings.
The conversion step is generic. Our input is the current value and a map; the output is the converted (or potentially unconverted if none of the mappings applies) result.
Getting from the seed to the location is then a question of sequencing all the conversions.
Part two
In the second part, we have to treat the information about seeds as ranges of values.
Fortunately, this doesn’t fundamentally change our approach. However, instead of converting a single value into another value, we are now converting an array of ranges into another array of ranges (where a single range can potentially expand into multiple ranges in the output).
Alternatively, you could brute-force the problem and iterate over all ranges, one value at a time; however, that’s very slow, and, more importantly, where is the fun in that?
Our first step is to adjust the parsing to extract the pairs of integers representing the start and size of the range.
The only remaining work is to re-implement our conversion method. Working with intervals offers a lot of off-by-one error opportunities, but other than that, the implementation is fairly straightforward.
When we consider a concrete pair of a range of seed values and a mapping, we can be in one of four situations:
there are no more mappings, meaning that the current range will stay as it is
the current mapping is after the start of our current range, meaning again that the current range will stay as it is; however, note that this also applies if the current mapping overlaps the tail of our current range; in that case, only the prefix of the current range will stay as it is
the start of the current range is within the current mapping; then the range must be converted; however, note that this also applies if only the prefix of our current range is within the current mapping
and finally, we need to take care of advancing to the following mapping while remaining on the current range
Once we have implemented this conversion, we can sequence all the conversion steps.
Conclusion
How did you do with today’s problems? Did you brute-force the second part, or did you implement the range-based logic?
Share your solutions and insights. Check out the repository with solutions and links to all articles: https://github.com/HappyCerberus/aoc-2023-cpp-solutions.