Re-posted from: https://www.ericburden.work/blog/2021/12/15/advent-of-code-2021-day-14/
It’s that time of year again! Just like last year, I’ll be posting my solutions
to the Advent of Code puzzles. This year, I’ll be
solving the puzzles in Julia. I’ll post my solutions
and code to GitHub as well.
I had a blast with AoC last year, first in R, then as a set of exercises for
learning Rust, so I’m really excited to see what this year’s puzzles will bring.
If you haven’t given AoC a try, I encourage you to do so along with me!
Day 14 – Extended Polymerization
Find the problem description HERE.
The Input – Pairwise Interactions
Today’s puzzle has us calculating the length of “polymer” chains, strings of
characters where new characters are inserted between existing characters in the
string. Now, this might spoil the surprise, but we’re definitely not going to
be making an exponentially growing string. Instead, we’ll be doing another
frequency analysis (I see you, lanternfish…),
where we’ll keep up with counts of the unique pairs of the “elements” at
each round. For that, we need to modify the input slightly to produce a
dictionary that has a “pair => [pair, pair]” structure, as opposed to the
“pair => letter” structure given by the input file.
# Useful Data Structures ------------------------------------------------------
# Type alias for the `pairmap` generated in our input parser
const PairMap = Dict{String,NTuple{2,String}}
# Ingest the Data -------------------------------------------------------------
# Read and parse the first line into a vector of element pairs, such that "HNH"
# will yield a `template` of ["HN", "NH"].
# Read and parse the remaining lines into a `PairMap` , coercing a line "CH -> B"
# in the input into a "CH" => ["CB", "BH"] entry in the `PairMap`.
function ingest(path)
return open(path) do f
# Parse the first line
templatestr = readuntil(f, "\n\n")
len = length(templatestr)
template = map(i -> templatestr[i:i+1], 1:len-1)
# Parse the remaining lines
pairmap = Dict{String,NTuple{2,String}}()
for pairstr in readlines(f)
(pair, insert) = split(pairstr, " -> ")
newpairs = (pair[1] * insert, insert * pair[2])
pairmap[pair] = newpairs
end
# Return a tuple of the template and pairmap
(template, pairmap)
end
end
Now, each entry in our dictionary will give back the two pairs that result from
inserting that letter in the middle of the original pair. This will come in
handy for…
Part One – Organometallics, Probably
In today’s puzzle, we are set to scrounge up some raw materials so our submarine
can polymerize itself some additional hull integrity. Turns out, our small chain
polymer can be extended by inserting additional “elements” between each polymeric
unit. Sketchy organic chemistry or not, the key insight here is that it’s super
inefficient to keep track of a string directly. In fact, our output doesn’t care
anything about the arrangement of the elements in the final polymer, just their
individual counts. This means: frequency analysis! Each pair of elements can
produce two pairs each round, so “HH” becomes “HN” and “NH”, for example. Now,
you may have noticed that I’m counting “N” twice in this process, so we’ll need
to account for that in our code.
# Some Useful Data Structures --------------------------------------------------
# Type alias for keeping up with the count of pairs in our `Polymer`. Instead
# of keeping track of the full sequence of elements in order, we only need
# the counts. By keeping a dictionary of each element pair and their counts,
# we make each step of the analysis run in constant time and space.
const PairCounts = Dict{String,Int}
# A `Polymer` is really just a wrapper around a `PairCounts`
struct Polymer
paircounts::PairCounts
end
# Setup for Iterating Polymers -------------------------------------------------
# The iterator struct, holds the template and pairmap. The template is needed
# for the first iteration, and the pairmap is used to generate the subsequent
# `PairCounts` objects.
struct PolymerGenerator
template::Vector{String}
pairmap::PairMap
end
# First iteration, performs the first insertion and returns a `Polymer`
# representing the result. Note, again, we're not actually
# inserting letters into a string, just keeping up with a count of letter
# pairs. This means that, assuming a `PairMap` of {"CH" => ["CB", "BH"]}
# and a `PairCounts` of {"CH" => 1}, the resulting `PairCounts` will contain
# {"CH" => 0, "CB" => 1, "BH" => 1}.
function Base.iterate(pg::PolymerGenerator)
paircounts = Dict([(pair, 0) for pair in keys(pg.pairmap)])
for pair in pg.template
(first, second) = pg.pairmap[pair]
paircounts[first] += 1
paircounts[second] += 1
end
return (Polymer(paircounts), paircounts)
end
# Subsequent iterations, given a `PairCounts` as the state, performs another
# insertion operation and returns the result.
function Base.iterate(pg::PolymerGenerator, paircounts::PairCounts)
newpaircounts = Dict([(pair, 0) for pair in keys(pg.pairmap)])
for (pair, count) in paircounts
(first, second) = pg.pairmap[pair]
newpaircounts[first] += count
newpaircounts[second] += count
end
return (Polymer(newpaircounts), newpaircounts)
end
# Iterate the `PolymerGenerator` `i` times and return the result
function Base.getindex(pg::PolymerGenerator, i::Int)
for (iteration, polymer) in enumerate(pg)
iteration >= i && return polymer
end
end
# Count the number of elements in the given `Polymer`. Now, since we're keeping up
# with letter pairs instead of the actual string, we need to do a tiny bit of
# math. For example, the string "NNCB" would be represented by a `PairCounts` of
# {"NN" => 1, "NC" => 1, "CB" => 1}, and would yield a `lettercounts` below of
# {'N' => 3, 'C' => 2, 'B' => 1}. For letters in the middle, we can get the
# actual element count as `lettercounts['C'] / 2`. Since letters at the end
# aren't being counted twice like letters in the middle, just round up the
# result of `lettercounts['N'] / 2` to get the number of 'N's in the string "NNCB"
function countelements(polymer::Polymer)
lettercounts = Dict{Char,Int}()
for (pair, count) in polymer.paircounts
for letter in pair
if letter ∉ keys(lettercounts)
lettercounts[letter] = count
else
lettercounts[letter] += count
end
end
end
elementcounts = Dict{Char,Int}()
for (letter, count) in lettercounts
elementcounts[letter] = ceil(count/2)
end
return elementcounts
end
# Solve Part One ---------------------------------------------------------------
# With all that setup, this part is easy. Create a `PolymerGenerator` from the
# input, get the 10th generated polymer, take the minumum and maximum element
# counts, and return the difference.
function part1(input)
polymergenerator = PolymerGenerator(input...)
elementcount = countelements(polymergenerator[10])
(least, most) = extrema(values(elementcount))
return most - least
end
This is a bit of a convoluted approach, but the upside is that each generation,
no matter how many elements in the current string, runs in O(1) time and space
complexity. This becomes really important in the next part.
Part Two – That Old Chestnut
That’s right. Part one asked us to count the “elements” in an exponentially
growing “polymer”, so part two asks us to do it again, but bigger. Now we
need to count the elements after 40 rounds of growth instead of just 10. Lucky
for us we did all that work in part one, eh?
# Solve Part Two ---------------------------------------------------------------
# Exactly the same as Part One, just get the 40th generated Polymer
function part2(input)
polymergenerator = PolymerGenerator(input...)
elementcount = countelements(polymergenerator[40])
(least, most) = extrema(values(elementcount))
return most - least
end
Ta-da! We’re able to “do part one, just 40 times” without breaking a sweat.
Wrap Up
Today brought in enough familiar elements that it was a nice break from the
challenge of prior days, which is good because I’m still working on getting
caught up on my blog posts. I’m still tweaking how I implement iterators in
Julia, the whole separate iterator/state thing takes a bit of getting used
to, but I think I’m starting to get the hang of it.
If you found a different solution (or spotted a mistake in one of mine),
please drop me a line!