Module advent_of_code_2021::day_14 [−][src]
Expand description
This is my solution for Advent of Code - Day 14 - Extended Polymerization
By the end of today I was thinking it was a lot like crate::day_6, but I missed how
exponential it was when first reading, so implemented the naive versions for part one, but that
did not complete before it ran out of memory for part two. I ended up noting that each pair
would become two new pairs each step (or stay as the same pair if there was no insertion mapping
for that pair). This meant I could just track the counts of each pair in a given iteration, and
work out the next step by walking through the current pair counts and adding its count to each
of the pairs it maps to in the counts map for the next iteration.
The types are pretty convoluted today, enough so that I aliased the Polymer as map of pairs ->
counts, and pair mapping of pair -> pairs when iterated into Polymer and PairMap
respectively. That said, whilst the types were complex, they were a great guide for what
transformations I needed to do at each step, and once I’d satisfied the type checker the
solutions just worked.
There’s quite a lot of moving parts today, mostly involved in building the internal
representation from the input, and converting the result into the required output.
parse_input takes the file, transforms the seed polymer into the required map of pair counts
using into_pair_counts, and then takes the remaining lines and creates the PairMap. i.e. a
mapping of AB -> C becomes ('A', 'B') => [('A', 'C'), ('C', 'B')] which means when there is
a pair AB the next iteration will instead have two pairs, AC and CB. intersperse
handles performing a single insertion cycle, and iterate recursively calls intersperse
for the required number of cycles. Finally summarise works out the counts of each of the
characters. With the current implementation we need to take the counts of both parts of each
pair to account for the first and last characters. This in itself involves some complex type
munging, so has been extracted to into_count_by. If I was building this again I’d consider
making a struct to hold the polymer, including caching the final character from the seed. This
would allow just counting the first character in each pair and adding 1 to the count that
matches the final character. As it is, this works and is quick enough that it’s not worth the
effort.
Functions
The name is a legacy from the naive solution where this was mapping each pair to the new pairs and building the full polymer in order which failed as the final polymer had ~21 trillion characters. This takes all the existing pairs and adds their counts to the pair(s) they map to when the mapped character is inserted.
Reduce the pair mapping into a count of characters. This needs to be called twice once for each element in the pair, to account for the first and last character that are each only in one pair. The mapping parameter is to capture this difference, and maps a pair count entry from the Polymer into the character this invocation cares about
Split a list of characters into the counts of all the consecutive pairs that exist. The hard
work is delegated to library functions slice::windows to give an iterator of the pairs
and Itertools::counts to reduce that to the required map.
Recursively apply intersperse the required number of times
The types required to make today’s solution work are pretty complex, so there is quite a lot of
work here to take a relatively simple input format into the complex format that makes the logic
efficient. A bunch of the tests need to convert intermediate polymer string representations into
the map of pair counts used internally, so this is delegated to into_pair_counts.
The entry point for running the solutions with the ‘real’ puzzle input.
This is responsible for converting the internal representation of a polymer into the data needed to provide the puzzle solution. It also returns the intermediary hashmap so that this can be verified in tests against the example provided in the specification.