Skip to Content

Advent of Code 2018 - Day 10, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 10: 'The Stars Align'

Posted on

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

It’s no use; your navigation system simply isn’t capable of providing walking directions in the arctic circle, and certainly not in 1018.

The Elves suggest an alternative. In times like these, North Pole rescue operations will arrange points of light in the sky to guide missing Elves back to base. Unfortunately, the message is easy to miss: the points move slowly enough that it takes hours to align them, but have so much momentum that they only stay aligned for a second. If you blink at the wrong time, it might be hours before another message appears.

You can see these points of light floating in the distance, and record their position in the sky and their velocity, the relative change in position per second (your puzzle input). The coordinates are all given from your perspective; given enough time, those positions and velocities will move the points into a cohesive message!

Rather than wait, you decide to fast-forward the process and calculate what the points will eventually spell.

For example, suppose you note the following points:

position=< 9,  1> velocity=< 0,  2>
position=< 7,  0> velocity=<-1,  0>
position=< 3, -2> velocity=<-1,  1>
position=< 6, 10> velocity=<-2, -1>
position=< 2, -4> velocity=< 2,  2>
position=<-6, 10> velocity=< 2, -2>
position=< 1,  8> velocity=< 1, -1>
position=< 1,  7> velocity=< 1,  0>
position=<-3, 11> velocity=< 1, -2>
position=< 7,  6> velocity=<-1, -1>
position=<-2,  3> velocity=< 1,  0>
position=<-4,  3> velocity=< 2,  0>
position=<10, -3> velocity=<-1,  1>
position=< 5, 11> velocity=< 1, -2>
position=< 4,  7> velocity=< 0, -1>
position=< 8, -2> velocity=< 0,  1>
position=<15,  0> velocity=<-2,  0>
position=< 1,  6> velocity=< 1,  0>
position=< 8,  9> velocity=< 0, -1>
position=< 3,  3> velocity=<-1,  1>
position=< 0,  5> velocity=< 0, -1>
position=<-2,  2> velocity=< 2,  0>
position=< 5, -2> velocity=< 1,  2>
position=< 1,  4> velocity=< 2,  1>
position=<-2,  7> velocity=< 2, -2>
position=< 3,  6> velocity=<-1, -1>
position=< 5,  0> velocity=< 1,  0>
position=<-6,  0> velocity=< 2,  0>
position=< 5,  9> velocity=< 1, -2>
position=<14,  7> velocity=<-2,  0>
position=<-3,  6> velocity=< 2, -1>

Each line represents one point. Positions are given as pairs: X represents how far left (negative) or right (positive) the point appears, while Y represents how far up (negative) or down (positive) the point appears.

At 0 seconds, each point has the position given. Each second, each point’s velocity is added to its position. So, a point with velocity <1, -2> is moving to the right, but is moving upward twice as quickly. If this point’s initial position were <3, 9>, after 3 seconds, its position would become <6, 3>.

Over time, the points listed above would move like this:

Initially:

........#.............
................#.....
.........#.#..#.......
......................
#..........#.#.......#
...............#......
....#.................
..#.#....#............
.......#..............
......#...............
...#...#.#...#........
....#..#..#.........#.
.......#..............
...........#..#.......
#...........#.........
...#.......#..........

After 1 second:

......................
......................
..........#....#......
........#.....#.......
..#.........#......#..
......................
......#...............
....##.........#......
......#.#.............
.....##.##..#.........
........#.#...........
........#...#.....#...
..#...........#.......
....#.....#.#.........
......................
......................

After 2 seconds:

......................
......................
......................
..............#.......
....#..#...####..#....
......................
........#....#........
......#.#.............
.......#...#..........
.......#..#..#.#......
....#....#.#..........
.....#...#...##.#.....
........#.............
......................
......................
......................

After 3 seconds:

......................
......................
......................
......................
......#...#..###......
......#...#...#.......
......#...#...#.......
......#####...#.......
......#...#...#.......
......#...#...#.......
......#...#...#.......
......#...#..###......
......................
......................
......................
......................

After 4 seconds:

......................
......................
......................
............#.........
........##...#.#......
......#.....#..#......
.....#..##.##.#.......
.......##.#....#......
...........#....#.....
..............#.......
....#......#...#......
.....#.....##.........
...............#......
...............#......
......................
......................

After 3 seconds, the message appeared briefly: HI. Of course, your message will be much longer and will take many more seconds to appear.

What message will eventually appear in the sky?

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

Good thing you didn’t have to wait, because that would have taken a long time - much longer than the 3 seconds in the example above.

Impressed by your sub-hour communication capabilities, the Elves are curious: exactly how many seconds would they have needed to wait for that message to appear?

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 25 of the way through Advent of Code 2018!

Further Reading

  1. Index of All Solutions - All solutions for 2018, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 10
  4. Advent of Code - Come join in and do these challenges yourself!