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'
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 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!
Further Reading
- Index of All Solutions - All posts and solutions for 2019, in Kotlin.
- My Github repo - Solutions and tests for each day.
- Solution - Full code for day 12
- Advent of Code - Come join in and do these challenges yourself!