Skip to Content

Advent of Code 2017 - Day 17, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 17: 'Spinlock'

Posted on

On Day 17 we will shortcut ourselves out of a brute force situation. 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 String called input, which we will do some further parsing on later.

Day 17, Part 1

Suddenly, whirling in the distance, you notice what looks like a massive, pixelated hurricane: a deadly spinlock. This spinlock isn’t just consuming computing power, but memory, too; vast, digital mountains are being ripped from the ground and consumed by the vortex.

If you don’t move quickly, fixing that printer will be the least of your problems.

This spinlock’s algorithm is simple but efficient, quickly consuming everything in its path. It starts with a circular buffer containing only the value 0, which it marks as the current position. It then steps forward through the circular buffer some number of steps (your puzzle input) before inserting the first new value, 1, after the value it stopped on. The inserted value becomes the current position. Then, it steps forward from there the same number of steps, and wherever it stops, inserts after it the second new value, 2, and uses that as the new current position again.

It repeats this process of stepping forward, inserting a new value, and using the location of the inserted value as the new current position a total of 2017 times, inserting 2017 as its final operation, and ending with a total of 2018 values (including 0) in the circular buffer.

For example, if the spinlock were to step 3 times per insert, the circular buffer would begin to evolve like this (using parentheses to mark the current position after each iteration of the algorithm):

  • (0), the initial state before any insertions.
  • 0 (1): the spinlock steps forward three times (0, 0, 0), and then inserts the first value, 1, after it. 1 becomes the current position.
  • 0 (2) 1: the spinlock steps forward three times (0, 1, 0), and then inserts the second value, 2, after it. 2 becomes the current position.
  • 0 2 (3) 1: the spinlock steps forward three times (1, 0, 2), and then inserts the third value, 3, after it. 3 becomes the current position. And so on:
0  2 (4) 3  1
0 (5) 2  4  3  1
0  5  2  4  3 (6) 1
0  5 (7) 2  4  3  6  1
0  5  7  2  4  3 (8) 6  1
0 (9) 5  7  2  4  3  8  6  1

Eventually, after 2017 insertions, the section of the circular buffer near the last insertion looks like this:

1512 1134 151 (2017) 638 1513 851

Perhaps, if you can identify the value that will ultimately be after the last value written (2017), you can short-circuit the spinlock. In this example, that would be 638.

What is the value after 2017 in your completed circular buffer?

There doesn’t seem much of a trick to this one except the fact that we need to pick a data structure we can resize easily. I’ve chosen to use a MutableList<Int> for this because IntArray, which I would prefer to use with Int, does not have an insert ability and I don’t want to go write a bunch of code to split things apart and resize them.

We can jump straight into a solution:

class Day17(input: String) {

    private val step = input.toInt()

    fun solvePart1(): Int {
        var current = 0
        val memory = mutableListOf(0)
        (1..2017).forEach {
            current = ((current + step) % it) + 1
            memory.add(current, it)
        }
        return memory[current.inc() % memory.size]
    }
}

We keep track of where our pointer is with current, and just loop through 1 to 2017 (inclusive!), updating the current value and inserting the value of the loop into our memory. In the end, we return the memory slot after current, taking care to not overflow in case it is the final element in the list.

Easy star: earned.

Day 17, Part 2

The spinlock does not short-circuit. Instead, it gets more angry. At least, you assume that’s what happened; it’s spinning significantly faster than it was a moment ago.

You have good news and bad news.

The good news is that you have improved calculations for how to stop the spinlock. They indicate that you actually need to identify the value after 0 in the current state of the circular buffer.

The bad news is that while you were determining this, the spinlock has just finished inserting its fifty millionth value (50000000).

What is the value after 0 the moment 50,000,000 is inserted?

In principle I suppose we could just brute force this, and that would probably work out fine. However let’s look at our data and see if there’s a shortcut. In part one, let’s suppose our current value points to the final element in the list. Were does the new element get inserted, at the beginning of the list (wrapping around), or at the end? At the end. That means our target, 0, doesn’t move.

Given that, we don’t really need to keep tack of 50,000,000 numbers, just the single number next to 0! Let’s cut to the chase:

fun solvePart2(): Int {
    var current = 0
    var oneSlot = 0
    (1..50_000_000).forEach {
        current = ((current + step) % it) + 1
        if (current == 1) oneSlot = it
    }
    return oneSlot
}

Same logic as above but our “memory” in this case is just what’s in slot one (memory[1] above). This performs quickly enough (~500ms) and earns us another easy star!

I hope you’ve learned something and as always, feedback is welcome!

17 days and we’ve earned 34 stars with 2^4 left to go! Only 2^3 days left!

Further Reading

  1. Index of All Solutions - All solutions for 2017, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 17.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - You Spin Me Round (Like a Record) chorus. On a loop. For 10 hours. By Dead or Alive.