Advent of Code 2017 - Day 17, in Kotlin • Todd Ginsberg

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

The puzzle text can be found here.

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 18, Part 1

The puzzle text can be found here.

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!

⭐ Day 17, Part 1

⭐ Day 18, Part 1

Further Reading