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

On Day 10, we will put our reading comprehension skills to the test, as well as writing a bit of Kotlin. 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.

⭐ Day 10, Part 1

The puzzle text can be found here.

Whew! Well, it looks like we’re going to be taking sections of a list of numbers and reversing them a bunch of times. If we were writing this in Python, I suspect this would be a lot easier because it supports negative array indexes. In order to compensate for out of range indexes, we’ll have to constantly check them.

I should write a small set of extension functions on List<T> in Kotlin, to allow negative indexing. That would be very handy.

Let’s dispense with parsing the input first. We are going to split our String into individual elements, turn those into Ints, and then convert the whole thing to an IntArray. I suppose with such a small set of input, we could use List<Int>, but I like to be in the habit of using IntArray when I can.

private val lengths = parsePart1Input(input)
private val ring = IntArray(256) { it }

private fun parsePart1Input(input: String): IntArray =
    input.split(",").map { it.toInt() }.toIntArray()

As you can see, we’ve created a list of lengths (our input) and a ring which we initialize with the index number, thanks to the lambda we pass to the constructor of IntArray. We’re ready to run the hashing algorithm over our lengths:

private fun runForLengths(iterations: Int = 1) {
    var position = 0
    var skip = 0
    repeat(iterations) {
        lengths.forEach { len ->
            reverseSection(position, len)
            position = (position + len + skip) % ring.size
            skip += 1
        }
    }
}

Hey Todd! Why are you passing in the number of iterations when we only need one? Shhhhh. I’ve ready ahead to part two! We’ll need it and it’s easier to write it this way and explain this now than to make a trivial edit and explain that later. Go with it, eh?

I’ve decided to mutate ring as a side effect here rather than recreate and reassign ring every iteration. For each length we reverse a section starting at the current position, and ending length elements away. We’ll write that code in a second. After the reversal happens we increase our position, being careful not to bust out of our range, and add one to skip.

And finally, given a starting position and length, we need to reverse all of these elements. There are a couple of ways to do this such as creating a few smaller IntArray objects, calling reverse() on one of them, and sewing it all back together. I just find that difficult to follow so I’ve taken an iterative approach:

private fun reverseSection(from: Int, length: Int) {
    var fromIdx = from % ring.size
    var toIdx = (fromIdx + length - 1) % ring.size
    repeat(length / 2) {
        ring.swap(fromIdx, toIdx)
        fromIdx = fromIdx.inc() % ring.size
        toIdx = toIdx.dec().takeIf { it >= 0 } ?: ring.size - 1
    }
}

What does this do? It figures out the start (fromIdx) and end (toIdx) of the section to be reversed. Then it goes through the range and swaps pairs. After every swap, fromIdx is increased and toIdx is decreased. We take care not to make either of those produce a value outside the ring’s total size.

I’ve also declared an extension function on IntArray, to make the swap look cleaner here. You could easily just do this in the repeat loop above if that’s your preference, but I suspect I’ll need this again in the next 15 days.

// In-place swap elements on an IntArray
fun IntArray.swap(a: Int, b: Int): IntArray {
    if(a !in (0 until size)) throw IllegalArgumentException("Swap value out of range")
    if(b !in (0 until size)) throw IllegalArgumentException("Swap value out of range")
    val tmp = this[a]
    this[a] = this[b]
    this[b] = tmp
    return this
}

Now that we have all this, our solution is simple:

fun solvePart1(): Int {
    runForLengths()
    return ring[0] * ring[1]
}

Tests passing, star collected, let’s move on.

⭐ Day 10, Part 2

The puzzle text can be found here.

Despite how long that is we are actually really close to a solution without much more code. First, let’s modify how we parse our input for part two:

private val lengths = if (part1) parsePart1Input(input) else parsePart2Input(input)
private val magicLengths = listOf(17, 31, 73, 47, 23)

private fun parsePart2Input(input: String): IntArray =
    (input.map { it.toInt() } + magicLength).toIntArray()

Each character is converted to an Int, which will generate its ASCII value. This might look the same as we did above, but that was calling String.toInt(), and it converts it to digits, not ASCII values like Char.toInt() does. And of course we have to tack our magicLengths on to the end as the problem description tells us to.

Now we jump right to our solution without much more code. Run the hashing algorithm 64 times, and hex-ify the results:

fun solvePart2(): String {
    runForLengths(64)
    return ring
        .toList()
        .chunked(16)
        .joinToString("") { it.xor().toHex(2) }
}

I’ve written two extension functions to make life easier. A way to XOR a list of numbers, and a way to convert an Int to a HEX String. I’ve made the toHex() function take a width because I might not always want a 2-width string. The XOR implementation is a simple reduction.

// Xor a List of Ints
fun List<Int>.xor(): Int = this.reduce { a, b -> a xor b }

// Int to HEX String with leading zeros...
fun Int.toHex(width: Int = 1): String = "%0${width}x".format(this)

The only other interesting part of that solution is the call to chunked, which breaks our 256 element list into 16 lists of 16 elements each. It’s a handy new function available in Kotlin 1.2 !

I feel that 90% of Day 10 was just trying to understand the problem. But we did it and earned our stars for the day. I hope you’ve learned something and as always, feedback is welcome!

10 days and we’ve earned 20 stars with 30 left to go!

⭐ Day 10, Part 1

⭐ Day 10, Part 2

Further Reading