# Advent of Code 2021 - Day 14

By Eric Burden | December 15, 2021

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
len = length(templatestr)
template = map(i -> templatestr[i:i+1], 1:len-1)

# Parse the remaining lines
pairmap = Dict{String,NTuple{2,String}}()
(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!