Advent of Code 2021 - Day 14, in Kotlin - Extended Polymerization • Todd Ginsberg

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 Longs, 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!

⭐ Day 14, Part 1

⭐ Day 14, Part 2

Further Reading