Skip to Content

Advent of Code 2018 - Day 12, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 12: 'Subterranean Sustainability'

Posted on

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 year 518 is significantly more underground than your history books implied. Either that, or you’ve arrived in a vast cavern network under the North Pole.

After exploring a little, you discover a long tunnel that contains a row of small pots as far as you can see to your left and right. A few of them contain plants - someone is trying to grow things in these geothermally-heated caves.

The pots are numbered, with 0 in front of you. To the left, the pots are numbered -1, -2, -3, and so on; to the right, 1, 2, 3…. Your puzzle input contains a list of pots from 0 to the right and whether they do (#) or do not (.) currently contain a plant, the initial state. (No other pots currently contain plants.) For example, an initial state of #..##…. indicates that pots 0, 3, and 4 currently contain plants.

Your puzzle input also contains some notes you find on a nearby table: someone has been trying to figure out how these plants spread to nearby pots. Based on the notes, for each generation of plants, a given pot has or does not have a plant based on whether that pot (and the two pots on either side of it) had a plant in the last generation. These are written as LLCRR => N, where L are pots to the left, C is the current pot being considered, R are the pots to the right, and N is whether the current pot will have a plant in the next generation. For example:

A note like ..#.. => . means that a pot that contains a plant but with no plants within two pots of it will not have a plant in it during the next generation. A note like ##.## => . means that an empty pot with two plants on each side of it will remain empty in the next generation. A note like .##.# => # means that a pot has a plant in a given generation if, in the previous generation, there were plants in that pot, the one immediately to the left, and the one two pots to the right, but not in the ones immediately to the right and two to the left. It’s not clear what these plants are for, but you’re sure it’s important, so you’d like to make sure the current configuration of plants is sustainable by determining what will happen after 20 generations.

For example, given the following input:

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

...## => #
..#.. => #
.#... => #
.#.#. => #
.#.## => #
.##.. => #
.#### => #
#.#.# => #
#.### => #
##.#. => #
##.## => #
###.. => #
###.# => #
####. => #

For brevity, in this example, only the combinations which do produce a plant are listed. (Your input includes all possible combinations.) Then, the next 20 generations will look like this:

                 1         2         3     
       0         0         0         0     
 0: ...#..#.#..##......###...###...........
 1: ...#...#....#.....#..#..#..#...........
 2: ...##..##...##....#..#..#..##..........
 3: ..#.#...#..#.#....#..#..#...#..........
 4: ...#.#..#...#.#...#..#..##..##.........
 5: ....#...##...#.#..#..#...#...#.........
 6: ....##.#.#....#...#..##..##..##........
 7: ...#..###.#...##..#...#...#...#........
 8: ...#....##.#.#.#..##..##..##..##.......
 9: ...##..#..#####....#...#...#...#.......
10: ..#.#..#...#.##....##..##..##..##......
11: ...#...##...#.#...#.#...#...#...#......
12: ...##.#.#....#.#...#.#..##..##..##.....
13: ..#..###.#....#.#...#....#...#...#.....
14: ..#....##.#....#.#..##...##..##..##....
15: ..##..#..#.#....#....#..#.#...#...#....
16: .#.#..#...#.#...##...#...#.#..##..##...
17: ..#...##...#.#.#.#...##...#....#...#...
18: ..##.#.#....#####.#.#.#...##...##..##..
19: .#..###.#..#.#.#######.#.#.#..#.#...#..
20: .#....##....#####...#######....#.#..##.

The generation is shown along the left, where 0 is the initial state. The pot numbers are shown along the top, where 0 labels the center pot, negative-numbered pots extend to the left, and positive pots extend toward the right. Remember, the initial state begins at pot 0, which is not the leftmost pot used in this example.

After one generation, only seven plants remain. The one in pot 0 matched the rule looking for ..#.., the one in pot 4 matched the rule looking for .#.#., pot 9 matched .##.., and so on.

In this example, after 20 generations, the pots shown as # contain plants, the furthest left of which is pot -2, and the furthest right of which is pot 34. Adding up all the numbers of plant-containing pots after the 20th generation produces 325.

After 20 generations, what is the sum of the numbers of all pots which contain a plant?

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

You realize that 20 generations aren’t enough. After all, these plants will need to last another 1500 years to even reach your timeline, not to mention your future.

After fifty billion (50000000000) generations, what is the sum of the numbers of all pots which contain a plant?

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!

Further Reading

  1. Index of All Solutions - All solutions for 2018, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 12
  4. Advent of Code - Come join in and do these challenges yourself!