Advent of Code 2020 - Day 17, in Kotlin - Conway Cubes • Todd Ginsberg

Today we’ll implement a variant of Conway’s Game of Life

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

Problem Input

Unlike yesterday , there is nothing complicated about today’s input, so we’ll read it in as a List<String>.

class Day17(private val input: List<String>) {

}

⭐ Day 17, Part 1

The puzzle text can be found here.

I’m about to spoil Part 2, so if you aren’t ready for that you might want to leave now.

Part 2 has the same input and end conditions as Part 1, except it uses a four-dimensional space instead of a three-dimensional space. Instead of writing Part 1 as if we didn’t know that, and then going off and refactoring things for Part 2, we’ll just start writing a solution that will work for both parts.

The first thing we’ll need is a class to represent our three-dimensional point, called Point3D:

// In Movement.kt

interface Point {
    val neighbors: List<Point>
}

data class Point3D(val x: Int, val y: Int, val z: Int) : Point {
    override val neighbors: List<Point3D> by lazy {
        (x - 1..x + 1).flatMap { dx ->
            (y - 1..y + 1).flatMap { dy ->
                (z - 1..z + 1).mapNotNull { dz ->
                    Point3D(dx, dy, dz).takeUnless { it == this }
                }
            }
        }
    }
}

As you can see, we are implementing a Point interface. This will come in handy when we have to define a Point4D and expect it to return its neighbors as well.

The only functionality in our Point3D class is to enumerate its neighbors. There are a couple of things to look for here. First, we’ll use the lazy delegate to define our property. Why? Well, if we don’t, we’ll have a property called neighbors that gets calculated when we create a Point3D. This will set up a stack overflow situation because if we define, say Point3D(0,0,0), we will need to eagerly define all of its neighbors, and so on. We could override get() on our property, but the lazy delegate will cache the results we create here, hopefully saving us a bit of time later on.

If you want to learn more about the difference between properties, overriding getters, and lazy, please see my post on them!

Now that we have a Point3D, we need a way to turn our input into a useful format. We’ll put everything in a Map<Point, Boolean> where Point is some point in space (a Point3D now, but a Point4D in part 2), and the Boolean is whether that point is active or not.

// In Day17

private fun parseInput(input: List<String>, pointFunction: (Int, Int) -> Point): Map<Point, Boolean> =
    input.flatMapIndexed { x, row ->
        row.mapIndexed { y, point ->
            pointFunction(x, y) to (point == '#')
        }
    }.toMap()

In order to avoid having two parseInput functions, we will pass a pointFunction to this function. The job of pointFunction is to create a Point object in the desired dimension, just from x and y. To use this, we’ll loop through our input and create a bunch of Pair<Point,Boolean>, and call toMap() on the resulting list. Note that we have to take care to set the map values properly here.

Next up is a function to perform one cycle on our Map<Point,Boolean>:

// In Day17

private fun Map<Point, Boolean>.nextCycle(): Map<Point, Boolean> {
    val nextMap = this.toMutableMap()
    keys.forEach { point ->
        point.neighbors.forEach { neighbor ->
            nextMap.putIfAbsent(neighbor, false)
        }
    }
    nextMap.entries.forEach { (point, active) ->
        val activeNeighbors = point.neighbors.count { this.getOrDefault(it, false) }
        nextMap[point] = when {
            active && activeNeighbors in setOf(2, 3) -> true
            !active && activeNeighbors == 3 -> true
            else -> false
        }
    }
    return nextMap
}

We implement our nextCycle() function as an extension function. First, we’ll create the new map we’ll end up populating. We’ll make it a MutableMap but return it as a Map so we can modify it internally but our callers can’t.

The very first thing to do (and this is what I did wrong for a good amount of time) is to go through and make sure that all possible neighbors are in the new map. This is because some of them can become populated because of our rules, and we need them because we want to enumerate them in the next step!

Next, we go through every point in our map and figure out what its new state should be. We do this by getting the neighbors for our point and counting how many of them are active in the map from the past cycle. We use that number to figure out what the new state (active = true, inactive = false) our point should have.

Next, we need a function to solve our puzzle, given a number of rounds (which turns out to always be 6), and a function to create a point, that we can pass to parseInput:

// In Day17

private fun solve(rounds: Int = 6, pointFunction: (Int, Int) -> Point): Int {
    var conwayGrid = parseInput(input, pointFunction)
    repeat(rounds) {
        conwayGrid = conwayGrid.nextCycle()
    }
    return conwayGrid.count { it.value }
}

And to solve part 1, we call this solve function, telling it how to create Point3D objects:

// In Day17

fun solvePart1() =
    solve { x, y ->
        Point3D(x, y, 0)
    }

One nice feature about Kotlin is that if you have a function that takes a lambda as its final argument, you can leave off the parens. That makes solve in this case look like a keyword, rather than a function. I think that makes situations like this look a lot cleaner.

Star earned! Onward!

⭐ Day 17, Part 2

The puzzle text can be found here.

Because we did so much work for Part 1, Part 2 is fairly straight forward: Define a four-dimensional Point, and tell our solve function how to create one.

We’ll start with the four-dimensional Point:

// In Movement.kt

data class Point4D(val x: Int, val y: Int, val z: Int, val w: Int) : Point {

    override val neighbors: List<Point4D> by lazy {
        (x - 1..x + 1).flatMap { dx ->
            (y - 1..y + 1).flatMap { dy ->
                (z - 1..z + 1).flatMap { dz ->
                    (w - 1..w + 1).mapNotNull { dw ->
                        Point4D(dx, dy, dz, dw).takeUnless { it == this }
                    }
                }
            }
        }
    }
}

The Point4D class looks a lot like the Point3D class except with one more dimension (w) to handle. It bothers me that we’re manually fiddling around with FOUR dimensions in our neighbors property. I might spend time and write a VariablePoint which takes some variable number of arguments and knows how to create all of its possible neighbors. But for a puzzle solution, this is probably fine as-is.

Now that we have that, we just need to tell our solve function how to create one in a lambda:

// In Day17

fun solvePart2(): Int =
    solve { x, y ->
        Point4D(x, y, 0, 0)
    }

Star earned! See you tomorrow!

⭐ Day 17, Part 1

⭐ Day 17, Part 2

Further Reading