# 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, it, it)) }
``````

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 `var`s, not `val`s. 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 `Long`s 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!