Advent of Code 2017 - Day 20, in Kotlin • Todd Ginsberg

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

The puzzle text can be found here.

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:

Find the lowest absolute acceleration. If there’s only one choice, that’s it.

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.

Find the minimum absolute velocity at this point. If there’s only one, that’s the answer. (This is where I got my answer).

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

The puzzle text can be found here.

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!

⭐ Day 20, Part 1

⭐ Day 20, Part 2

Further Reading