# Advent of Code 2021 - Day 14, in Kotlin - Extended Polymerization

Kotlin solutions to parts 1 and 2 of Advent of Code 2021, Day 14: 'Extended Polymerization'

Posted on

This problem looks a lot like the Lanternfish problem we ran into on Day 6. For small inputs, a naive approach will work fine. But when we really get going and start asking for big numbers, we’ll have to get more sophisticated. So today we’ll write an algorithm to expand our polymers without having to actually figure out what the polymer looks like.

If you’d rather just view code, the GitHub Repository is here .

Problem Input

Our input today is another list of strings which comprises two main parts, separated by a blank line. We’ll write two parsing functions to handle each part of the input, and we’ll set aside the very last character of the `template` because of a peculiarity in our algorithm (we’ll discuss it in part one).

``````class Day14(input: List<String>) {

private val lastChar = input.first().last()
private val template: Map<String, Long> = parseTemplate(input.first())
private val rules: Map<String, Char> = parseRules(input)

private fun parseTemplate(input: String): Map<String, Long> =
input
.windowed(2)
.groupingBy { it }
.eachCount().mapValues { it.value.toLong() }

private fun parseRules(input: List<String>): Map<String, Char> =
input.drop(2).associate {
it.substring(0..1) to it[6]
}
}
``````

The `parseTemplate` function is responsible for the first row of input. For a naive approach we might parse this to a `List<Pair<Char,Char>>` in order to represent pairs of consecutive characters. However, since that won’t scale we will instead map our input to every pair of characters (as a `String`) to how many times we see it in the input. For the example input of `NNCB`, we’ll end up with a `Map<String,Long>` that looks like this: `["NN" -> 1, "NC" -> 1, "CB" -> 1]`. We’ll use the `windowed` function to slide a window along our input string and turn it into a `List<List<String>>`, then we’ll use `groupingBy` and `eachCount` to group them together and count up how many there are. We’ve used this construct a few times now, it’s very succinct and powerful! The last step is to convert the `Int` that the `eachCount` function returns into `Long`s, because part two will overflow an `Int`.

To parse the rules, we’ll define a `parseRules` function which will take a `substring` of the input rows and map the pair of characters to its expansion character. No need to write a regular expression here since the characters we care about are always in the same places.

#### ⭐ Day 14, Part 1

The puzzle text can be found here.

The good news for today is that we don’t actually care what the polymer we generate looks like. We only care how many of each character it has. Given our work with the Lanternfish problem on Day 6, we know we can just worry about the counts. This is why we’ve chosen to represent a polymer as a mapping of characters to frequency, rather than to model the entire polymer as a string or a list of pairs. Since we only care about counts, any transform of `AC` to `ABC` is identical to any other transform of `AC` to `ABC`. We only need to know we’ve done it twice, not actually do it.

To get started, we’ll need to turn one polymer as a `Map<String, Long>` into another `Map<String, Long>`, which represents the next generation. We’ll do that by adding an extension function to `Map<String,Long>` called `react`. Since we need to build a new `Map`, we can use the `buildMap` function which allows us to pretend like we’re building a `MutableMap`, but really return a `Map`. This is handy because now `react` can be written as a single expression. Otherwise, we’d have to declare a new `MutableMap`, work with it, and then return it. By using `buildMap` we just worry about what goes in the map, and we can treat it as mutable while we’re building it.

``````// In Day14

private fun Map<String, Long>.react(): Map<String, Long> =
buildMap {
this@react.forEach { (pair, count) ->
val inserted = rules.getValue(pair)
plus("\${pair.first()}\$inserted", count)
plus("\$inserted\${pair.last()}", count)
}
}
``````

Inside `buildMap`, we go through each of the elements in the `Map` we called `react` on. Because `this` could mean both the map we’ve called `react` on or the map we’re building (or, technically, the `Day14` class), we qualify our `this`. We go through each `pair` of characters and `count` in order to generate the next generation. We look up the `rule` that this `pair` refers to. Luckily, there always seems to be an answer, there are no pairs in the polymer that don’t have an expansion. We’ll set this expansion aside as `inserted`. Next, we’ll expand our polymer by adding both newly valid pairs.

Let’s suppose our single expansion rule is `AC -> B`. If we were doing this all as a big String, we’d end up with `ABC`. What we want in our map is `[AB -> 1, BC -> 1]`. We have the value 1 in this case because we only have one expansion. As our input grows in complexity, so does the count of the number of times we’ve seen each pair. This is how we shortcut the polymer generation process. Since we don’t really care about the actual order of the polymer, just how many times we’ve used each letter, we only need to keep track of the counts.

One thing I don’t really like about this is the syntax needed to add the `count` to whatever the existing amount is in the Map. Because there might not be a value in there, we have to handle nulls. I think this code is kind of ugly, so I’m going to define an extension function to do the work for us:

``````// In Day14

private fun <T> MutableMap<T, Long>.plus(key: T, amount: Long) {
this[key] = this.getOrDefault(key, 0L) + amount
}
``````

Knowing how to generate an expanded polymer given an existing polymer, we’re most of the way to the goal.

Let’s go back to our example input of `NNCB`. After calling `react` one single time, we end up with `NCNBCHB`, or as a map: `["NC" -> 1, "CN" -> 1, "NB" -> 1, "BC" -> 1, "CH" -> 1, "HB" ->1]`.

What we need to do now is to turn that mapping of pairs of characters into a map of how many times we’ve seen each character. There are (at least) two approaches we could take here and I think the simplest is to reduce our map of Strings to just have the first character in the pair. Some of these will naturally double up, so we’ll have to account for that.

Continuing on with our example, what we want to end up with is: `["N" -> 2, "C" -> 2, "B" -> 1, "H" -> 1]`. The one problem with this is that `B` ends up being under counted by 1 because it is at the very end of our input string and doesn’t pair up every time. If instead we’d taken the last element of each String, we’d have the same problem but with the first character in the input template. So we have to account for this.

``````// In Day14

private fun Map<String, Long>.byCharFrequency(): Map<Char, Long> =
this
.map { it.key.first() to it.value }
.groupBy({ it.first }, { it.second })
.mapValues { it.value.sum() + if (it.key == lastChar) 1 else 0 }
``````

To get the counts, we’ll `map` the first character of the key to the `count` (its frequency) for each mapping. At this point we now have a `List<Pair<Char,Long>>` but we want a `Map<Char,Long>`. To get that, we’ll call `groupBy` and give it two lambdas: one to extract the keys of the `Map` we want (`it.first`) and one to extract the value of the `Map` we want (`it.second`). We now have a `Map<Char,List<Long>>`. Each value of that `Map` is a list of all the values, which need to be summed. We can do that with `mapValues`, taking care to add 1 if we’re summing the count for the last element in the template input.

Using these two functions (`react` and `byCharFrequency`), we can write a `solve` function to apply this logic:

``````// In Day14

private fun solve(iterations: Int): Long =
(0 until iterations)
.fold(template) { polymer, _ -> polymer.react() }
.byCharFrequency()
.values
.sorted()
.let { it.last() - it.first() }
``````

We iterate for the given number of iterations, using a `fold` to generate successive polymers and then get the final polymers character frequency. Since we only care about the `values` we grab them and then sort them using `sorted`. Our answer is the last element in the sorted list of values minus the first element in the list of sorted values (note: we could have done `sortedDescending` and `first() - last()`, it doesn’t matter which way you do it).

And now we can call `solve` to get the answer for part one.

``````// In Day14

fun solvePart1(): Long = solve(10)
``````

Star earned! Onward!

#### ⭐ Day 14, Part 2

The puzzle text can be found here.

There’s not much to say about part two because we did all the work in part one. Call `solve` with 40, and we’re done.

``````// In Day14

fun solvePart2(): Long = solve(40)
``````

Star earned!