Advent of Code 2019 - Day 24, in Kotlin • Todd Ginsberg

Today’s puzzle introduces us to a modified version of Conway’s Game of Life.

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

My friend Mark Ducommun was featured on Talking Kotlin a few months ago! He spoke about this experiences with implementing Conway’s Game of Life in Kotlin for multiple platforms. Give it a listen!

Problem Input

We’re going to borrow the BitSet class from Java to represent our game board. I picked this over List<Boolean> or Map<Point2D,Char> because it just seemed more natural.

First, we’ll need some variables to help us describe the board:

class Day24(input: List<String>) {

    private val bounds: Point2D = Point2D(input.first().length - 1, input.size - 1)
    private val startGrid: BitSet = parseInput(input)
}

The bounds help us because we need to do a few calculations on how wide the board is. This is especially true because BitSet effectively implements our board as an array of booleans. In order to translate a Point2D into a place in the BitSet, we’ll need to define an extension function (local to our puzzle class today) to help us with this:

private fun Point2D.offset(): Int =
    this.x + (this.y * (bounds.y + 1))

We also need a way to iterate over all the points in the board. We will define another extension function on Point2D to do that:

private fun Point2D.upTo(): Sequence<Point2D> = sequence {
    (0..y).forEach { y ->
        (0..x).forEach { x ->
            yield(Point2D(x, y))
        }
    }
}

This defines a lazy sequence, although we could have just returned a List<Point2D> instead given the small number of points we ended up needing.

And now we can use these things to parse our input into a BitSet:

private fun parseInput(input: List<String>): BitSet =
    BitSet().also { bitSet ->
        bounds.upTo().forEach { at ->
            bitSet[at.offset()] = input[at.y][at.x] == '#'
        }
    }

⭐ Day 24, Part 1

The puzzle text can be found here.

Let’s start off by writing the code to turn our BitSet into another BitSet given the transform rules. This will be an extension function on BitSet.

private fun BitSet.next(): BitSet =
    BitSet().also { newBitSet ->
        bounds.upTo().forEach { point ->
            val neighbors = this.countNeighbors(point)
            val alive = this[point.offset()]
            newBitSet.setNextRound(point, alive, neighbors)
        }
    }

This function creates a new BitSet and iterates through each Point2D on our board. For every point, it calculates the number of neighbors in our old BitSet, figures out if that spot is currently alive in the old BitSet, and then determines what the same spot should be in the new BitSet.

We do this with a few helper functions:

private fun BitSet.at(point: Point2D): Boolean =
    this[point.offset()]

This at extension function on BitSet lets us determine what the value of a specific spot on our board is. It reuses Point2D.offset() to accomplish this.

Next, we need to count the number of neighbors our spot has:

private fun BitSet.countNeighbors(at: Point2D): Int =
    at.neighbors()
        .filter { it.x >= 0 && it.y >= 0 }
        .filter { it.x <= bounds.x && it.y <= bounds.y }
        .count { this.at(it) }

The countNeighbors function will exclude anything that falls into the negative range. The rules for part 2 get a lot more complicated.

I know this is a lot of functions to write to solve this, but let’s keep going. We need another one to set a spot in our BitSet based on whether the spot is considered “alive” and depending on how many neighbors it has. This is the implementation of the rules.

private fun BitSet.setNextRound(point: Point2D, alive: Boolean, neighbors: Int) {
    this[point.offset()] = when {
        alive -> neighbors == 1
        !alive && neighbors in setOf(1, 2) -> true
        else -> alive
    }
}

Now that we have the ability to turn a BitSet into a BitSet one minute into the future, we need to detect the first time the pattern repeats. We’ll write another function for this:

private fun firstDuplicate(start: BitSet): BitSet {
    val seen = mutableSetOf<BitSet>()
    var latest = start
    do {
        seen += latest
        latest = latest.next()
    } while (latest !in seen)
    return latest
}

This function maintains a list of the states that we’ve seen and only returns once it generates its first duplicate.

Finally, we can implement part 1!

fun solvePart1(): BigInteger =
    firstDuplicate(startGrid).toBigInteger()

OK, one more function. Because our BitSet conveniently implements a binary number, we can use it directly to calculate the final answer for Part 1. We need to convert it to something more useful, like a BigInteger:

fun BitSet.toBigInteger(): BigInteger =
    BigInteger(1, this.toByteArray().reversedArray())

Star earned!

⭐ Day 24, Part 2

The puzzle text can be found here.

Well, using BitSet doesn’t really help us much here. I was planning on the twist being something like “Great, now the board is 100,000 times larger!”, but was wrong. Anyway, we can use most of what we have to solve part 2. We’ll still represent each of our layers as a BitSet, but we’ll store them all in a Map<Int,BitSet> where the key is the layer number, and the value is the board on that level. I had briefly considered writing this part using one big BitSet and a 3D point object, but rejected it because it just felt too confusing.

We’ll start by declaring some shared state properties that we’ll end up using in Part 2:

private var layers = mutableMapOf(0 to startGrid)
private val midPoint = Point2D(bounds.x / 2, bounds.y / 2)

We initialize our layers with what we have already - the startGrid is layer zero. Since the middle of our grid is central to the logic for finding neighbors, we’ll record its location in midPoint. From here on out, we’ll follow more or less the same procedure we did with part 1, except in three dimensions. Our extension functions to do this will therefore be on MutableMap<Int, BitSet>.

private fun MutableMap<Int, BitSet>.next(): MutableMap<Int, BitSet> =
    this.addEmptyEdges()
        .map { (layer, board) ->
            layer to BitSet().also { newBitSet ->
                bounds.upTo().filterNot { it == midPoint }.forEach { point ->
                    val neighbors = this.countNeighbors(point, layer)
                    val alive = board[point.offset()]
                    newBitSet.setNextRound(point, alive, neighbors)
                }
            }
        }.toMap().toMutableMap()

This function should look very similar to Part 1 except for a couple of changes. First, we have an addEmptyEdges() function. Because the topmost and bottommost layers still have neighboring layers, we want to add them in so the current top and bottom layers can grow into them. This function adds a new layer to the top and bottom of the map if they aren’t already empty:

private fun MutableMap<Int, BitSet>.addEmptyEdges(): MutableMap<Int, BitSet> {
    val min = this.keys.min()!!
    if (!this[min]!!.isEmpty) {
        this[min - 1] = BitSet()
    }

    val max = this.keys.max()!!
    if (!this[max]!!.isEmpty) {
        this[max + 1] = BitSet()
    }
    return this
}

The other function we need is something to calculate the number of neighbors, because it is so different from Part 1:

private fun Map<Int, BitSet>.countNeighbors(at: Point2D, layer: Int = 0): Int =
    at.neighbors()
        .filterNot { it == midPoint }
        .filter { it.x >= 0 && it.y >= 0 }
        .filter { it.x <= bounds.x && it.y <= bounds.y }
        .count { this.getValue(layer).at(it) }
        .plus(counterOuterNeighbors(layer, at))
        .plus(this.countInnerNeighbors(layer, at))

The interesting part here is that we can’t count the middle of any board as a legitimate spot. That “spot” is always a recursive board. So we filter that out right at the start. We do bounds checking similar to part 1. Then we need to implement some logic for two situations: If we are neighboring an “outer” grid, or an “inner” grid:

private fun Map<Int, BitSet>.counterOuterNeighbors(layer: Int, at: Point2D): Int =
    this[layer - 1]?.let {
        listOf(
            if (at.x == 0) it.bitAt(midPoint.west()) else 0,
            if (at.x == bounds.x) it.bitAt(midPoint.east()) else 0,
            if (at.y == 0) it.bitAt(midPoint.north()) else 0,
            if (at.y == bounds.y) it.bitAt(midPoint.south()) else 0
        ).sum()
    } ?: 0

This one took me a while because I forgot that corners have two neighbors. This accounts for that by doing a series of if statements. And for inner layers…

private fun Map<Int, BitSet>.countInnerNeighbors(layer: Int, at: Point2D): Int =
    this[layer+1]?.let {
        when (at) {
            midPoint.north() -> it.rowCardinality(0)
            midPoint.south() -> it.rowCardinality(bounds.y)
            midPoint.east() -> it.columnCardinality(bounds.x)
            midPoint.west() -> it.columnCardinality(0)
            else -> 0
        }
    } ?: 0

This function checks to see if we are evaluating a spot right near the midpoint. If we are, we need to get either the start or end column or start or end row from the next layer:

private fun BitSet.columnCardinality(x: Int): Int =
    (0..bounds.y).map { y -> this[(y * bounds.y.inc()) + x] }.count { it }

private fun BitSet.rowCardinality(y: Int): Int {
    val start = y * (bounds.x.inc())
    return this[start, start + bounds.y + 1].cardinality()
}

Finally, finally, finally, we have enough code to run Part 2, which we’ll do as a fold:

fun solvePart2(minutes: Int): Int =
    (1..minutes).fold(layers) { carry, _ -> carry.next() }.values.sumBy { it.cardinality() }

At the end we can sum up the cardinality of each layer, which gives us our answer!

Star earned!

⭐ Day 24, Part 1

⭐ Day 24, Part 2

Further Reading