Advent of Code 2018 - Day 12, in Kotlin • Todd Ginsberg

Today we get to play with sequences and the windowed function! I had a lot of fun with this one.

Problem Input

There are two parts to the input, an initial state and some instructions. We can parse that here before we get into the problem. First, let’s get the initial state out of the way. Don’t worry too much about what it means right now, it is formally specified below, but it looks something like this:

initial state: #..#.#..##......###...###

We only care about the part with the hashes and dots, so we can just substring our way there.

class Day12(rawInput: List<String>) {

    private val initialState: String = rawInput.first().substring(15)
    private val rules: Set<String> = parseRules(rawInput)

}

The rules are two rows below the initial state, and have a format like this:

...## => #

Because these are all the same width, and we only care about ones that end with #, we can filter out what we don’t want and get substrings of the rest:

private fun parseRules(input: List<String>): Set<String> =
    input
        .drop(2)
        .filter { it.endsWith("#") }
        .map { it.take(5) }
        .toSet()

⭐ Day 12, Part 1

The puzzle text can be found here.

The way we’re going to solve part 1 is through a sequence. Each time you select an item from a sequence, it generates the data you want, lazily. The sequence generator can have its own state, which is nice for situations like ours where the input from the previous round influences the next round. The function we are going to write will take the previous (or initial) state of the plants, mutate it, calculate the value of the spots with plants, and return the data as a Pair<String, Long>. We’ll return what the plants look like in the String, and the calculated sum in the Long.

First, let’s write an extension to calculate the sum we need. We’ll have to tell it where our zero index is, because it can change:

private fun String.sumIndexesFrom(zero: Int): Long =
    this.mapIndexed { idx, c -> if (c == '#') idx.toLong() - zero else 0 }.sum()

Now that we have that, we can write our sequence generator:

private fun mutatePlants(state: String = initialState): Sequence<Pair<String, Long>> = sequence {
    var zeroIndex = 0
    var currentState = state
    while (true) {
        // Make sure we have something to match to the left of our first real center point.
        while (!currentState.startsWith(".....")) {
            currentState = ".$currentState"
            zeroIndex++
        }
        // Make sure we have something to match to the right of our last real center point.
        while (!currentState.endsWith(".....")) {
            currentState = "$currentState."
        }

        currentState = currentState
            .toList()
            .windowed(5, 1)
            .map { it.joinToString(separator = "") }
            .map { if (it in rules) '#' else '.' }
            .joinToString(separator = "")

        // Because there are two positions to the left of 
        // the first real center that were not directly evaluated
        zeroIndex -= 2 

        yield(Pair(currentState, currentState.sumIndexesFrom(zeroIndex)))
    }
}

Most of the complexity in this code is maintaining enough data for us to look at. Because for any spot n that we look at, we have to evaluate n-2 through n+2. That means we can’t just start at zero or we won’t calculate it properly. So we’ll add some filler . data to the start and end of the string. If we add any to the start, we have to account for the fact that our zero point just moved to the right.

In order to mutate the past generation, we’ll depend on a function that Kotlin provides called windowed. In our case we’re telling it to slide along the string one place at a time and generate substrings that are 5 characters long. This is the data we’re going to evaluate. Because windowed returns what we want as a List<Char>, we have to turn it back into a String by using joinToString. Now we have a 5-length String, and we can see if it is in the list of rules. If it is, we map it to a #, otherwise we map it to a .. Joining the results together gives us a String that represents the next generation of plants.

Before returning from there let’s consider where our zero index is. Remember, to evaluate n, we need to look back to n-2. And because n-2 and n-1 are never really evaluated, the resulting next generation will be 2 shorter than the input (after padding!). So we subtract 2 from our zeroIndex.

In a sequence generator when you want to return a value you yield it. This will effectively return information to the consumer and wait around for you to ask for more, at which point it will loop and start over, mutating the generation we just created into the next. So we yield the diagram of the plants, and what its value is.

Calling this function, telling it to drop the first 19 results we don’t really care about, and using the data from the 20th, gives us our answer!

fun solvePart1(): Long =
    mutatePlants().drop(19).first().second

Star earned! Onward!

⭐ Day 12, Part 2

The puzzle text can be found here.

Yeesh! 50,000,000,000 seems like a lot of work. Luckily we don’t have to do it. If you run the code above and print out each of the responses you’ll eventually get to a point where the picture looks the same, just shifted to the right. And the difference in values between generations stops changing. If we could just generate enough data to find the point where it stops changing, we can use that to determine what generation 50,000,000,000 would look like if we ran for that long.

To do this, we’ll use our sequence and drop the values we get until we find they stop changing. This means we’ll have some side-effecting code here, where we maintain values outside our lambda, but that’s alright because it is local to our function:

fun solvePart2(targetGeneration: Long = 50_000_000_000): Long {
    var previousDiff = 0L
    var previousSize = 0L
    var generationNumber = 0

    // Go through the sequence until we find one that grows the same one as its previous generation
    mutatePlants().dropWhile { thisGen ->
        val thisDiff = thisGen.second - previousSize // Our diff to last generation
        if (thisDiff != previousDiff) {
            // Still changing
            previousDiff = thisDiff
            previousSize = thisGen.second
            generationNumber += 1
            true
        } else {
            // We've found it, stop dropping.
            false
        }
    }.first() // Consume first because sequences are lazy and it won't start otherwise.

    return previousSize + (previousDiff * (targetGeneration - generationNumber))
}

In order to tell when things stop changing we need to know what the previous value was (previousSize), what the difference between the previous generation and its previous generation was (previousDiff), as well as how many generations we’ve gone through to get there (generationNumber). Our dropWhile code checks to see if we have the same difference between the generation we’re looking at now and our previous, as our previous had with its previous. If so, we’ve stopped changing and can exit the loop. Otherwise, we have to save off all our facts and wait for the next value to come in, where we can check again. This shouldn’t take long, perhaps 110-150 iterations.

Once we know where we stop changing the picture and instead start changing the values by a fixed number, we can calculate our answer! We multiply the difference in generations by how many generations we have left, and add that do the value we’ve already calculated.

And we’ve earned a second star!

⭐ Day 12, Part 1

⭐ Day 12, Part 2

Further Reading