Skip to Content

# Advent of Code 2019 - Day 24, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2019, Day 24: 'Planet of Discord'

Posted on

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!

#### Further Reading

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