Skip to Content

Advent of Code 2018 - Day 1, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 1: 'Chronal Calibration'

Posted on

It’s December 1st, and you know what that means - Advent of Code is back! I look forward to this every year, because I have so much fun with it. Like last year, I’m going to try and solve each puzzle on the day they are released, and write a blog post about it. This December is a busy month for me, so we’ll see how long I can keep that up!

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

Problem Input

Our input file has one integer (positive or negative) per row. I’m going to reuse my function from last year to load the file into a List<String> and pass that to the class that implements our solution. Because they are Ints, I may as well parse them while I’m at it…

class Day01(rawInput: List<String>) {

    private val input: List<Int> = rawInput.map { it.toInt() }

}

Day 1, Part 1

(Some of the wonderful story elided, go read it yourself, it’s part of the fun!)

“Error: Device must be calibrated before first use. Frequency drift detected. Cannot maintain destination lock.” Below the message, the device shows a sequence of changes in frequency (your puzzle input). A value like +6 means the current frequency increases by 6; a value like -3 means the current frequency decreases by 3.

For example, if the device displays frequency changes of +1, -2, +3, +1, then starting from a frequency of zero, the following changes would occur:

Current frequency  0, change of +1; resulting frequency  1.
Current frequency  1, change of -2; resulting frequency -1.
Current frequency -1, change of +3; resulting frequency  2.
Current frequency  2, change of +1; resulting frequency  3.
In this example, the resulting frequency is 3.

Here are other example situations:

  • +1, +1, +1 results in 3
  • +1, +1, -2 results in 0
  • -1, -2, -3 results in -6

Starting with a frequency of zero, what is the resulting frequency after all of the changes in frequency have been applied?

Part 1 looks pretty simple, thanks to the .sum() extension already provided by Kotlin.

fun solvePart1(): Int =
    input.sum()

That earns us our first star! Onward!

Day 1, Part 2

You notice that the device repeats the same frequency change list over and over. To calibrate the device, you need to find the first frequency it reaches twice.

For example, using the same list of changes above, the device would loop as follows:

Current frequency  0, change of +1; resulting frequency  1.
Current frequency  1, change of -2; resulting frequency -1.
Current frequency -1, change of +3; resulting frequency  2.
Current frequency  2, change of +1; resulting frequency  3.
(At this point, the device continues from the start of the list.)
Current frequency  3, change of +1; resulting frequency  4.
Current frequency  4, change of -2; resulting frequency  2, which has already been seen.

In this example, the first frequency reached twice is 2.

Note that your device might need to repeat its list of frequency changes many times before a duplicate frequency is found, and that duplicates might be found while in the middle of processing the list.

Here are other examples:

  • +1, -1 first reaches 0 twice.
  • +3, +3, +4, -2, -4 first reaches 10 twice.
  • -6, +3, +8, +5, -6 first reaches 5 twice.
  • +7, +7, -2, -7, -4 first reaches 14 twice.

What is the first frequency your device reaches twice?

By reading carefully we know that we may have to loop through our list of inputs multiple times. This sounds like we could use an infinite sequence here. Thankfully, creating these in Kotlin 1.3 is pretty simple, so I’ll write an extension function that we can use in later problems if we need to.

fun <T> List<T>.toInfiniteSequence(): Sequence<T> = sequence {
    if (this@toInfiniteSequence.isEmpty()) {
        return@sequence
    }
    while (true) {
        yieldAll(this@toInfiniteSequence)
    }
}

All this does is check that our list isn’t empty (in this case it’s not, but I wanted to be thorough), and if not, just keep yielding the entire list. Kotlin will turn this into a sequence for us. Easy, right? The only weird part is having to label this. That’s because we’re in a coroutine scope here and we have multiple concepts of this going on at once, so we have to be explicit.

Since the sequence does most of the work for us, we can move directly to our solution:

fun solvePart2(): Int {
    val frequencies = mutableSetOf(0)
    var sum = 0
    return input.toInfiniteSequence()
        .map {
            sum += it
            sum
        }
        .first { !frequencies.add(it) }
}

In this case, we have two side effects: maintenance of the set of frequencies we’ve already seen, and the latest sum. Normally, I try to avoid code like this but the alternatives (one with fold and one recursive solution) were either too complicated or too slow (or both). In this solution, we use our infinite sequence to provide values that we map to the existing sum. This turns our sequence of inputs into a sequence of sums. Then we just stop the first time we’ve seen the sum before, by testing against our frequencies set.

This earns us our second star of the day!

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 1
  4. Advent of Code - Come join in and do these challenges yourself!