Modern C++ in Advent of Code: Day14
It is day fourteen of Advent of Code. Today, we will expand polymers using C++20 coroutines (and then the proper way using frequency counting).
As always, please try to solve the problem before looking at the solution. For all articles in this series, check out this list.
Day14: Part1
Our goal is to repeatedly expand a polymer represented by uppercase letters, using expansion rules that expand two-letter sequences by inserting a new letter in between the two existing two letters. For example: NNCB using the rules NN->C, NC->B, CB->H expands to NCNBCHB.
If each pair of letters maps to a rule, we end up doubling the polymer length in each step, so you might get a hint that simply expanding the polymer might not be the proper solution. However, this is such a great use case for applying C++20 coroutines that I had to solve Part1 using a lazy-brute-force approach, and we will discuss the proper solution in Part2.
So what even is a lazy-brute-force approach? Expanding the solution by 2x in each generation introduces two issues. The first one is computational (each step will run 2x longer than the previous one). The second problem is storage. With a typical machine with 32GB memory, we can only store the result for the first ~34 generations.
But what if we approached the problem lazily? We would only ever manifest a character when it is needed. Of course, this does not solve the computational problem, but we limit the required memory to be a small multiple of the number of generations.
We need a generator coroutine. This coroutine will yield characters that will then be consumed by the next generation or the main that will count the frequency of characters. First, however, we also need a baseline coroutine:
The first coroutine will serve as a base, generating characters from our initial input. The second coroutine is the actual expander, and it will read characters from the previous generation and then yield an extra character between each two read.
In our main function, we parse the input and then stack these coroutines as deep (number of generations) as needed:
This way, each generation consumes the characters generated by the previous generation, and finally main consumes the result, character by character.
With this, we need to implement our coroutines:
In our base coroutine, we read from the input and yield the characters one by one (lines 2–3). In the actual expander, we read the characters from the previous generation, which we receive as a parameter. We then check whether there is a matching expansion rule (line 12) and if there is, we yield the extra character (on top of yielding the characters read — lines 11 and 15).
And with that, we have a lazy-brute-force solution that will be slow but will use minimal memory. If you found this intriguing, check out my coroutine articles: Complete Guide, Practical Examples.
Day14: Part2
OK, it’s time to solve this problem properly now. The core observation here is that the expansions are independent. When we are expanding, for example AB using the rule AB->C, to ACB, the expansion is entirely local. It does not affect the characters A and B or any other part of the string.
To put this into explicit terms: when we apply an expansion rule, AB->C we are decreasing the number of AB, sequences, adding new AC and CB sequences, and adding the letter C.
Therefore, the optimal solution doesn’t need to expand the polymer. Instead, it can count the changing frequencies of sequences and characters.
So let’s go back to our typical structure and start with the declarations:
We introduce a custom pair to use it as a key in an unordered_map. It follows the same idea as Point from previous days. Finally, we wrap the intermittent frequencies in a struct, with a constructor initializer from the starting polymer and a tick method that takes the transformation rules and advances the generation one step.
To test, we use the inputs from AoC:
For input parsing, we rely on reading space-delimited strings, checking whether we don’t run into something unexpected:
Initializing, we record each character and each pair of characters:
Tick method implements the mentioned formula:
- we decrease the number of instances of the input pair (line19)
- we increase the frequency of the inserted character (line20)
- and then increase the frequencies of the two new pairs (lines 22–25)
Note that we can’t do this without temporary variables since the new pairs generated on lines 22–25 can be one of the pairs not yet processed in the loop.
In our main, we parse the input, create an instance of the counter, and tick the desired number of times. Finally, we pick the maximum and minimum (non-zero) frequencies and calculate the difference.
Links and technical notes
The repository with daily solutions is available at: https://github.com/HappyCerberus/moderncpp-aoc-2021.
Check out this list for articles about the other days in Advent of Code.
And please don’t forget to try Advent of Code for yourself.
Thank you for reading
Thank you for reading this article. Did you enjoy it?
I also publish videos on YouTube. Do you have questions? Hit me up on Twitter or LinkedIn.
