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

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 `val`s, 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 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!