Skip to Content

Advent of Code 2019 - Day 12, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2019, Day 12: 'The N-Body Problem'

Posted on

Let’s simulate the universe! Unfortunately it’s just for a small part of it, not the entire thing. Simulating the entire universe faster than real-time sure would save us all from a bunch of stupid mistakes, wouldn’t it? But I’m sure simulating four fake moons is just as cool. Didn’t mean to get your hopes up. At least we’ll probably learn something this way! :)

Related but unrelated: I highly recommend reading The Three-Body Problem by Cixin Liu, if you are into Science Fiction.

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

Problem Input

In order to parse today’s input, we’ll be doing something a bit different. This code snippet refers to two classes (Moon and Vector3D) that we don’t know about yet. I’ll explain those in Part 1.

// In Day12

private fun parseInput(input: List<String>): List<Moon> =
    input.map { line ->
        line.replace("""[^-\d,]""".toRegex(), "")
            .split(",")
            .map { it.toInt() }
    }.map { Moon(Vector3D(it[0], it[1], it[2])) }

For each line of input, use a Regex to keep only the numbers, negative symbols, and commas. Split whatever is left by comma and convert each one to an Int. Map all of those into a Moon with a Vector3D. This might not be the most elegant way to do it, but I didn’t like how my Regex group capturing code looked.

Day 12, Part 1

The puzzle text can be found here.

Let’s write those two classes we learned about before.

First, our 3D vector:

// In Vector3D.kt

data class Vector3D(val x: Int, val y: Int, val z: Int) {
    operator fun plus(other: Vector3D): Vector3D =
        Vector3D(x + other.x, y + other.y, z + other.z)

    infix fun diff(other: Vector3D): Vector3D =
        Vector3D((other.x - this.x).sign, (other.y - this.y).sign, (other.z - this.z).sign)

    val abs: Int =
        x.absoluteValue + y.absoluteValue + z.absoluteValue

    companion object {
        val ZERO = Vector3D(0, 0, 0)
    }
}

We’ll define the Vector3D class in its own file because maybe we’ll reuse it. The vector has three values, x, y, and z and can be used to represent both the position and velocity of the moon. We’ll define the plus operator so we can add them together when we calculate the Moon’s new velocity. We’ll define the diff function so we can subtract one vector from another when we calculate the new velocity from our gravity. Remember when we do that, we only want to get -1, 0, or 1 to apply to velocity. Thankfully, the Kotlin Standard Library has a .sign function that does the work for us - no having to do a comparison here! I originally had that as the minus operator, but since it wasn’t the strict opposite of plus, it felt wrong so I changed it. I did make it infix so it would at least behave like an operator if we want.

We’ll also create an abs property to represent the absolute value of x, y, and z, which we use for the energy calculation. Finally, like with Point2D, we’ll define a starting point we’ll call ZERO.

Let’s define our Moon inside Day12, I don’t think we’ll reuse it (and can refactor if that changes).

// In Day12

data class Moon(var position: Vector3D, var velocity: Vector3D = Vector3D.ZERO) {

    fun applyGravity(other: Moon) {
        this.velocity += (this.position diff other.position)
    }

    fun applyVelocity() {
        position += velocity
    }

    fun energy(): Int =
        position.abs * velocity.abs
}

As you can see, Moon is comprised of two vectors - one for position and one for velocity. We have helper functions for applying the gravity and velocity calculations, and a function to calculate the energy level. What’s interesting to note here is that these are all vars, not vals. I opted to not re-create the Moon on each step, instead letting our logic maintain the state inside the Moon objects as a side-effect.

Next, let’s write another extension function. This will create every possible pair from a list of elements:

// In Extensions.kt

fun <T> List<T>.everyPair(): List<Pair<T, T>> =
    this.mapIndexed { idx, left ->
        this.drop(idx+1).map { right ->
            Pair(left, right)
        }
    }.flatten()

So if we have listOf(A, B, C), this will create a listOf(Pair(A, B), Pair(A, C), Pair(B, C)), and we’ll use this in our gravity calculation.

Since this won’t change, we can define all possible moon pairs as a property in Day12:

private val moonPairs: List<Pair<Moon, Moon>> = moons.everyPair()

Finally, we need to simulate one step of the simulation:

private fun step() {
    moonPairs.forEach {
        it.first.applyGravity(it.second)
        it.second.applyGravity(it.first)
    }
    moons.forEach { it.applyVelocity() }
}

This looks at each pair of moons and performs the gravity calculation between them (one from A to B and another from B to A). At the end, it evaluates all of the new velocity values. This is all done as side-effects on the Moon class.

Finally, we can solve our problem:

fun solvePart1(steps: Int): Int {
    repeat(steps) {
        step()
    }
    return moons.sumBy { it.energy() }
}

Simulate the universe for steps number of steps, and sum the energy levels at the end. Star earned!

Day 12, Part 2

The puzzle text can be found here.

I’m not going to lie to you - I needed help to figure out the trick to this one. The instructions are clear that we’re not supposed to calculate this for real because it would take an eternity. The trick is to realize that x, y, and z are independent. Meaning, we can wait for all of the position.x and velocity.x values to cycle. By doing that, we know the periodicity for x. Once we know the number of cycles it takes to repeat for x, y, and z, we can take the Least Common Multiple of all the cycle lengths and that’s how long it would take all three sets of values to line back up!

The other thing I learned is that we don’t have to keep a cache of all the states we’ve seen, hoping for a match. Because the transforms we do in a step can be undone, we can always get the previous state. And that means that the start of the cycle must be the initial state we have for our input. So when we try to detect the cycle, we can just compare our x, y, and z values with our starting values. We don’t have to store all the intermediate values as they will never match.

I was hoping to get away without any additional dependencies, but I’m breaking that today. We’ll be using Apache Commons Math in order to calculate the Least Common Multiple we’ll need. I didn’t feel like writing my own version was worth the time.

// In build.gradle.kts

dependencies {
    // Existing dependencies here
    implementation("org.apache.commons:commons-math3:3.5")
}

Solving part 2 involves:

fun solvePart2(): Long {
    val startingX: List<Pair<Int, Int>> = moons.map { it.position.x to it.velocity.x }
    val startingY: List<Pair<Int, Int>> = moons.map { it.position.y to it.velocity.y }
    val startingZ: List<Pair<Int, Int>> = moons.map { it.position.z to it.velocity.z }
    var foundX: Long? = null
    var foundY: Long? = null
    var foundZ: Long? = null
    var stepCount = 0L
    do {
        stepCount += 1
        step()
        foundX = if (foundX == null && startingX == moons.map { it.position.x to it.velocity.x }) stepCount else foundX
        foundY = if (foundY == null && startingY == moons.map { it.position.y to it.velocity.y }) stepCount else foundY
        foundZ = if (foundZ == null && startingZ == moons.map { it.position.z to it.velocity.z }) stepCount else foundZ

    } while (foundX == null || foundY == null || foundZ == null)
    return lcm(foundX, lcm(foundY, foundZ))
}

In this version, we store off our initial values for position.x and velocity.x (and y and z) for each moon. We’ll do this as a List<Pair<Int,Int>> because that’s easy to create. These are our initial states - startingX, startingY, and startingZ. We’ll also declare foundX, foundY and foundZ for when we detect the cycles. These are declared as Long? because we’ll overflow an Int when calculating the Least Common Multiple later, and it’s just easier to make them Longs now.

Next, we simulate the universe over and over until we find all three period values. We do this by re-creating the List<Pair<Int,Int>> for that step and comparing them to our initial states. If we find one, we set it, otherwise we keep going.

Finally, we use the lcm function from Apache Commons Math to solve our puzzle!

Star earned!

I found this really interesting. Initially I thought I had caught the right hints from the problem description, but my “solution” took a realy long time. That’s a good clue it’s wrong - Advent of Code solutions should be solvable in a couple of seconds at most. I hadn’t caught the clue that the x, y, and z values are not connected, and that was where I went wrong. I was trying to detect the cycles of each Moon and then take the Least Common Multiple.

The lesson for me is that there’s no shame in asking people who know more about math than I do for help!

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 12
  4. Advent of Code - Come join in and do these challenges yourself!