Advent of Code 2018 - Day 10, in Kotlin • Todd Ginsberg

On day 10, we’ll have fun simulating the entire universe (well, perhaps just the part where moving lights are concerned).

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

Problem Input

We’ll handle parsing as part of the solution to part 1, but it is another list of Strings. If you follow my GitHub repo, you’ll also see I checked in files to represent the answers we’re expected to get for testing.

⭐ Day 10, Part 1

The puzzle text can be found here.

Don’t worry, the code we’ll write is going to be shorter than the description (I suspect that’s true in most of these, and most good software actaully). What we’re going to do is declare a class to represent each point Light and its velocity. Then we are going to keep moving them all step by step until the area they consume stops growing. We’re taking advantage of the fact that Eric Wastl is not a sadist and didn’t make the lights converge on a single point.

Let’s start by creating our Light class, and the function to parse the data. We could have gone with a regular expression, but splitting the string and picking through the debris works just as well:

private class Light(var x: Int, var y: Int, val dX: Int, val dY: Int) {

    companion object {

        fun of(input: String): Light =
            input.split(",", "<", ">").map { it.trim() }.run {
                Light(this[1].toInt(), this[2].toInt(), this[4].toInt(), this[5].toInt())
            }
    }

}

The first thing that might jump out is that this class defines x and y as var, not val. This is so we can change its location without having to allocate a new instance of Light. An alternate way would have been to make this a data class with vals, and copy the data to a new instance every time we move. I felt that wasn’t necessary, and that a little mutability is fine in this case.

Next, we’ll implement the function to move our Light object around.

private class Light(var x: Int, var y: Int, val dX: Int, val dY: Int) {

    fun move(forward: Boolean = true) {
        if (forward) {
            x += dX
            y += dY
        } else {
            x -= dX
            y -= dY
        }
    }

    ...
}

Why are we allowing our points to move backwards? Remember, we’re going to simulate the universe until it stops shrinking. We know it stops shrinking because it starts to expand again. That means our Light objects will be in a bad state, and we’ll have to back them up a bit. This is why we allow Light to move backwards - because we have to rewind the universe.

Next, we will implement a class called Message, to simulate the universe, given a List<Light>. In order to do this, we will need a few basic facts about the universe, namely how big it is. So we’ll create a few private functions as well:

private class Message(val lights: List<Light>) {

    private fun skyArea(): Long =
        rangeX().span * rangeY().span

    private fun rangeX(): IntRange =
        IntRange(lights.minBy { it.x }!!.x, lights.maxBy { it.x }!!.x)

    private fun rangeY(): IntRange =
        IntRange(lights.minBy { it.y }!!.y, lights.maxBy { it.y }!!.y)

}

I’ve also created this extension property to make life easier. I’ve wanted to know how wide an IntRange is a few times now, so it’s a good candidate for an extension property (because it doesn’t change, otherwise we would define it as a function):

val IntRange.span: Long get() =
    (this.last.toLong() - this.first.toLong()).absoluteValue

Now that we have the tools, we can implement our “simulate the universe” function:

// In Message

fun resolveMessage(): String {
    var lastArea = Long.MAX_VALUE
    var thisArea = skyArea()
    while (thisArea < lastArea) {
        moveLights()
        lastArea = thisArea
        thisArea = skyArea()
    }
    moveLights(false) // We've moved one too far, back everything up one.

    return this.toString()
}

As a reminder, we’re going to keep moving all of the stars step by step until they start to expand. Once we get to that point we can back the universe up one step and convert the Light objects into a diagram like in the example. In theory we could just print it out, but I write unit tests for all of my solutions so I know they don’t change as I edit them and I have tests to match exactly.

All that’s left is to implement toString(), which takes advantage of joinToString and its ability to set delimiters for us:

// In Message

override fun toString(): String {

    val lightSet = lights.map { Pair(it.x, it.y) }.toSet()

    return rangeY().joinToString(separator = "\n") { y ->
        rangeX().map { x ->
            if (Pair(x, y) in lightSet) '#' else '.'
        }.joinToString(separator = "")
    }
}

You’ll notice here that we iterate over y first, and then x. If we did it the opposite way, our picture would be rotated. Rows first (y) then columns (x). All that’s left is to parse the input and call our function! And to make life easier we put all of our locations into a set, so we can look them up faster. If we were going to use Light for more than just this, I probably would have added a toLocationPair() function there instead of doing the work here.

Calling this function gives us the answer to part 1:

class Day10(rawInput: List<String>) {

    private val message: Message = Message(rawInput.map { Light.of(it) })

    fun solvePart1(): String =
        message.resolveMessage()

}

Star earned! Onward!

⭐ Day 10, Part 2

The puzzle text can be found here.

We have just about everything we need for this. Let’s make a slight refactoring to our Message.resolveMessage() function to count the number of steps it takes and we will be done! We’ll save some time and effort by returning the answer for both parts at once in the form of a Pair<String, Int>, where the String a picture of the message, and the Int is the number of steps it took.

fun resolveMessage(): Pair<String, Int> {
    var lastArea = Long.MAX_VALUE
    var thisArea = skyArea()
    var timeToResolve = -1 // Account for extra step at the end
    while (thisArea < lastArea) {
        moveLights()
        lastArea = thisArea
        thisArea = skyArea()
        timeToResolve++
    }
    moveLights(false) // We've moved one too far, back everything up one.

    return Pair(this.toString(), timeToResolve)
}

In addition to the signature change, the highlighted lines are the only parts that change. We start our timeToResolve counter at -1 so we don’t have to subtract one from it at the end.

Calling this function gives us the answer to part 2:

fun solvePart1(): String =
    message.resolveMessage().first

fun solvePart2(): Int =
    message.resolveMessage().second

Star earned! That was fun! There are probably other ways to do this (I’ve seen people doing this with gradient descent calculations), but I can understand and explain this version and its tradeoffs. One trick that seems popular is to keep moving lights until the area is a specific height, but I felt that was cheating a bit because we would have to know the font size in advance. Anyway, there are a lot of ways to solve this, you should go experiment!

We’re now 2/5 of the way through Advent of Code 2018!

⭐ Day 10, Part 1

⭐ Day 10, Part 2

Further Reading