Daily bit(e) of C++ | Advent of Code: Day 19
Daily bit(e) of C++ #352, Advent of Code using Modern C++: Day 19.
Welcome to day 19 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/19.
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 sorting machine parts.
Part one
Today is all about choosing the correct representation. Let’s start with the items we are sorting.
The second piece of the puzzle is the rules in a workflow. Each rule is a condition with an attached destination that we should jump to if the condition is true or just a destination label.
We can avoid one layer of complexity (which of the values the condition is referring to) by wrapping that logic into a projection, treating a member pointer as a function. This allows the condition to operate simply on an integer.
A workflow is a combination of a label and a list of rules. Processing the workflow means iterating over the rules until we encounter either one with no conditions or a rule where the condition evaluates to be true.
Our ultimate task is to calculate the sum of the values of all accepted items. We must first parse the workflows and store them in a container for easy lookup.
With that, we can fold over all items in the input, determine whether the item is accepted (by following the workflows) and adjust the accumulator accordingly.
Part two
It might not look like it, but we have actually done a lot of heavy lifting that can be applied to part two.
Instead of a condition returning a boolean, we now want the condition to split the possibility space of the values of an item based on the threshold. The “true” portion will follow the label for this condition, and the “false” portion will continue to the next rule.
To start, we need to adjust our representation of an item. An item now represents the possibility space of items (i.e. the valid ranges of values).
As mentioned, a condition needs to split the possibility space into two chunks, meaning it now takes a Range and produces a pair of Ranges. Also, note that the projection now doesn’t return a copy of the value but a reference to the original.
Workflows remain unchanged; however, we drop the process() method because instead of processing a workflow, we now need to explore the entire tree of workflows, starting with “in”.
To wrap this up, we invoke our search and fold over the resulting list of accepted items (ranges of accepted values).
Conclusion
How did you do with today’s problems? Did you also find part two straightforward?
Share your solutions and insights. Check out the repository with solutions and links to all articles: https://github.com/HappyCerberus/aoc-2023-cpp-solutions.