# Advent of Code 2017 - Day 10, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 10: 'Knot Hash'

Posted on

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!