Skip to Content

Advent of Code 2017 - Day 20, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 20: 'Particle Swarm'

Posted on

On Day 20 we will simulate a very small part of the universe. If you’d rather jump straight to the code, it’s right here.

I’ve challenged myself to post each day’s solution to Github and blog about it. Like last year, I’m going to be solving these problems in Kotlin. I might go back and revise solutions, but I’ll be sure to annotate that fact in these posts.

Problem Input

We are given a set of input for this problem. I’ve loaded this into a List<String> called input, which we will do some further parsing on later.

Day 20, Part 1

Suddenly, the GPU contacts you, asking for help. Someone has asked it to simulate too many particles, and it won’t be able to finish them all in time to render the next frame at this rate.

It transmits to you a buffer (your puzzle input) listing each particle in order (starting with particle 0, then particle 1, particle 2, and so on). For each particle, it provides the X, Y, and Z coordinates for the particle’s position (p), velocity (v), and acceleration (a), each in the format .

Each tick, all particles are updated simultaneously. A particle’s properties are updated in the following order:

  • Increase the X velocity by the X acceleration.
  • Increase the Y velocity by the Y acceleration.
  • Increase the Z velocity by the Z acceleration.
  • Increase the X position by the X velocity.
  • Increase the Y position by the Y velocity.
  • Increase the Z position by the Z velocity.

Because of seemingly tenuous rationale involving z-buffering, the GPU would like to know which particle will stay closest to position <0,0,0> in the long term. Measure this using the Manhattan distance, which in this situation is simply the sum of the absolute values of a particle’s X, Y, and Z position.

For example, suppose you are only given two particles, both of which stay entirely on the X-axis (for simplicity). Drawing the current states of particles 0 and 1 (in that order) with an adjacent a number line and diagram of current X positions (marked in parenthesis), the following would take place:

p=< 3,0,0>, v=< 2,0,0>, a=<-1,0,0>    -4 -3 -2 -1  0  1  2  3  4
p=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>                         (0)(1)

p=< 4,0,0>, v=< 1,0,0>, a=<-1,0,0>    -4 -3 -2 -1  0  1  2  3  4
p=< 2,0,0>, v=<-2,0,0>, a=<-2,0,0>                      (1)   (0)

p=< 4,0,0>, v=< 0,0,0>, a=<-1,0,0>    -4 -3 -2 -1  0  1  2  3  4
p=<-2,0,0>, v=<-4,0,0>, a=<-2,0,0>          (1)               (0)

p=< 3,0,0>, v=<-1,0,0>, a=<-1,0,0>    -4 -3 -2 -1  0  1  2  3  4
p=<-8,0,0>, v=<-6,0,0>, a=<-2,0,0>                         (0)   

At this point, particle 1 will never be closer to <0,0,0> than particle 0, and so, in the long run, particle 0 will stay closest.

Which particle will stay closest to position <0,0,0> in the long term?

First, let’s write a some data classes to help us simulate these particles.

data class Vec3D(val x: Long, val y: Long, val z: Long) {

    val distance: Long =
        x.absoluteValue + y.absoluteValue + z.absoluteValue

    operator fun plus(that: Vec3D): Vec3D =
        Vec3D(x = x + that.x, y = y + that.y, z = z + that.z)

}

This is just a 3D vector. You can calculate it’s absolute (Manhattan) distance, and add it to anther vector. And of course, we’ll define a Particle as well, which is just a numbered collection of these Vec3D objects:

data class Particle(val id: Int,
                    val position: Vec3D,
                    val velocity: Vec3D,
                    var acceleration: Vec3D) {

    fun move() =
        this.copy(
            velocity = velocity + acceleration,
            position = position + velocity + acceleration
        )
}

The move() method here calculates the next position and velocity of the given particle, and returns a copy. This will allow us to map over these values to implement our solution.

But first, some parsing of data, which is pretty straight forward so I’m not going to go into detail other than to say we loop through our input, assign an id to each particle starting from zero, and parse the string into Vec3D objects.

private val particles: List<Particle> = input.mapIndexed { idx, s -> parseParticle(idx, s) }

private fun parseParticle(id: Int, input: String): Particle =
    input.split("<", ">").let {
        Particle(
            id = id,
            position = parseVec(it[1]),
            velocity = parseVec(it[3]),
            acceleration = parseVec(it[5])
        )
    }

private fun parseVec(input: String): Vec3D =
    input.split(",").map { it.trim().toLong() }.let {
        Vec3D(it[0], it[1], it[2])
    }

Now, let’s talk about how to actually solve part 1. There are two ways to do this: the strictly correct way, and the way I’ve done it. Originally, I figured “oh, we can just take the particle with the lowest absolute acceleration and that’ll be it!”, and for my input I was actually correct. However after talking to a few people on the #AdventOfCode channel in KotlinSlack, it turns out that that doesn’t always work out.

The version I settled on was to simulate the universe long enough for the particles to spread out and pick the one closest to the origin. I arbitrarily chose to simulate 1000 movements of each particle, and this seemed to work on a variety of inputs. To do this, we’ll execute this code:

fun solvePart1(): Int =
    (1..1000).fold(particles) { acc, _ ->
        acc.map { it.move() }
    }.minBy { it.position.distance }?.id ?: throw IllegalArgumentException("Wat")

Every iteration, the fold will produce a new list of particles that are one movement away from the old list. At the end of that, find the one with the minimum absolute distance and get its id. Freak out if there isn’t one, because that wouldn’t make sense but I can’t explain that to Kotlin’s type checker.

While this will earn us a star it should be noted that there is another solution that doesn’t depend on an arbitrary 1,000 simulations. After wrote my solution, I found this post on Reddit by MikeyJ231 which describes how to calculate this with far fewer simulations:

The approach I used was:

  1. Find the lowest absolute acceleration. If there’s only one choice, that’s it.
  2. In case of ties, step forward through time until the velocity of each particle has the same signs as its acceleration (in other words, the absolute value of each component of each velocity will increase from now on.
  3. Find the minimum absolute velocity at this point. If there’s only one, that’s the answer. (This is where I got my answer).
  4. In case of ties, repeat step 2 but with positions instead and compare those.

That’s some sound reasoning there, but I’m going to leave the solution as I have it. It runs quickly (~90ms) on the inputs provided and is fairly straight forward to understand. On to part two!

Day 20, Part 2

To simplify the problem further, the GPU would like to remove any particles that collide. Particles collide if their positions ever exactly match. Because particles are updated simultaneously, more than two particles can collide at the same time and place. Once particles collide, they are removed and cannot collide with anything else after that tick.

For example:

p=<-6,0,0>, v=< 3,0,0>, a=< 0,0,0>    
p=<-4,0,0>, v=< 2,0,0>, a=< 0,0,0>    -6 -5 -4 -3 -2 -1  0  1  2  3
p=<-2,0,0>, v=< 1,0,0>, a=< 0,0,0>    (0)   (1)   (2)            (3)
p=< 3,0,0>, v=<-1,0,0>, a=< 0,0,0>

p=<-3,0,0>, v=< 3,0,0>, a=< 0,0,0>    
p=<-2,0,0>, v=< 2,0,0>, a=< 0,0,0>    -6 -5 -4 -3 -2 -1  0  1  2  3
p=<-1,0,0>, v=< 1,0,0>, a=< 0,0,0>             (0)(1)(2)      (3)   
p=< 2,0,0>, v=<-1,0,0>, a=< 0,0,0>

p=< 0,0,0>, v=< 3,0,0>, a=< 0,0,0>    
p=< 0,0,0>, v=< 2,0,0>, a=< 0,0,0>    -6 -5 -4 -3 -2 -1  0  1  2  3
p=< 0,0,0>, v=< 1,0,0>, a=< 0,0,0>                       X (3)      
p=< 1,0,0>, v=<-1,0,0>, a=< 0,0,0>

------destroyed by collision------    
------destroyed by collision------    -6 -5 -4 -3 -2 -1  0  1  2  3
------destroyed by collision------                      (3)         
p=< 0,0,0>, v=<-1,0,0>, a=< 0,0,0>

In this example, particles 0, 1, and 2 are simultaneously destroyed at the time and place marked X. On the next tick, particle 3 passes through unharmed.

How many particles are left after all collisions are resolved?

Lucky us, we have everything we need to solve this pretty quickly. The approach I’m going to take is very similar to part 1. Simulate movement a bunch of times but eliminate any collisions between each step. To eliminate collisions, I group the particles by location and remove any that have more than one particle in the bucket. Flatmap them all back together, and we have a list of non-colliding particles. Do that 1,000 or so times and we can safely assume that the particles will no longer interact.

fun solvePart2(): Int =
    (1..1000).fold(particles) { acc, _ ->
        acc.map { it.move() }
            .groupBy { it.position }
            .filterValues { it.size == 1 }
            .flatMap { it.value }
    }.size

As with part 1, there is a more accurate way to calculate part 2. The collision detection logic above is fine and that doesn’t change. However we really only need to keep simulating if any particles are getting closer together. If they are all moving away from one another, we’re done. Since I feel that code is going to get messy and complicated, I’m going to stick with this solution for the same reason as above - it’s fast and easy to follow.

However you earned your two stars today, I hope you had fun.

That makes 20 days and 40 stars with only 10 left to go! Only 5 days remaining!

Further Reading

  1. Index of All Solutions - All solutions for 2017, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 20.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Particle Man, by They Might Be Giants.