Skip to Content

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

Sometimes if I wake up in the middle of the night, I’ll attempt to read the day’s problem on my phone. I’ve learned, after reading this and fending off crazy nightmares that this is ultimately not productive.

This hash function simulates tying a knot in a circle of string with 256 marks on it. Based on the input to be hashed, the function repeatedly selects a span of string, brings the ends together, and gives the span a half-twist to reverse the order of the marks within it. After doing this many times, the order of the marks is used to build the resulting hash.

  4--5   pinch   4  5           4   1
 /    \  5,0,1  / \/ \  twist  / \ / \
3      0  -->  3      0  -->  3   X   0
 \    /         \ /\ /         \ / \ /
  2--1           2  1           2   5

To achieve this, begin with a list of numbers from 0 to 255, a current position which begins at 0 (the first element in the list), a skip size (which starts at 0), and a sequence of lengths (your puzzle input). Then, for each length:

Reverse the order of that length of elements in the list, starting with the element at the current position. Move the current position forward by that length plus the skip size. Increase the skip size by one. The list is circular; if the current position and the length try to reverse elements beyond the end of the list, the operation reverses using as many extra elements as it needs from the front of the list. If the current position moves past the end of the list, it wraps around to the front. Lengths larger than the size of the list are invalid.

Here’s an example using a smaller list:

Suppose we instead only had a circular list containing five elements, 0, 1, 2, 3, 4, and were given input lengths of 3, 4, 1, 5.

  • The list begins as [0] 1 2 3 4 (where square brackets indicate the current position).
  • The first length, 3, selects ([0] 1 2) 3 4 (where parentheses indicate the sublist to be reversed).
  • After reversing that section (0 1 2 into 2 1 0), we get ([2] 1 0) 3 4.
  • Then, the current position moves forward by the length, 3, plus the skip size, 0: 2 1 0 [3] 4. Finally, the skip size increases to 1.
  • The second length, 4, selects a section which wraps: 2 1) 0 ([3] 4.
  • The sublist 3 4 2 1 is reversed to form 1 2 4 3: 4 3) 0 ([1] 2.
  • The current position moves forward by the length plus the skip size, a total of 5, causing it not to move because it wraps around: 4 3 0 [1] 2. The skip size increases to 2.
  • The third length, 1, selects a sublist of a single element, and so reversing it has no effect.
  • The current position moves forward by the length (1) plus the skip size (2): 4 [3] 0 1 2. The skip size increases to 3.

  • The fourth length, 5, selects every element starting with the second: 4) ([3] 0 1 2. Reversing this sublist (3 0 1 2 4 into 4 2 1 0 3) produces: 3) ([4] 2 1 0.

  • Finally, the current position moves forward by 8: 3 4 2 1 [0]. The skip size increases to 4.

In this example, the first two numbers in the list end up being 3 and 4; to check the process, you can multiply them together to produce 12.

However, you should instead use the standard list size of 256 (with values 0 to 255) and the sequence of lengths in your puzzle input. Once this process is complete, what is the result of multiplying the first two numbers in the list?

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

I’m going to admit to you that the next section confused the h*ck out of me and I had to read it a few times before truly understanding it. Thankfully, we mostly have our solution written already.

The logic you’ve constructed forms a single round of the Knot Hash algorithm; running the full thing requires many of these rounds. Some input and output processing is also required.

First, from now on, your input should be taken not as a list of numbers, but as a string of bytes instead. Unless otherwise specified, convert characters to bytes using their ASCII codes. This will allow you to handle arbitrary ASCII strings, and it also ensures that your input lengths are never larger than 255. For example, if you are given 1,2,3, you should convert it to the ASCII codes for each character: 49,44,50,44,51.

Once you have determined the sequence of lengths to use, add the following lengths to the end of the sequence: 17, 31, 73, 47, 23. For example, if you are given 1,2,3, your final sequence of lengths should be 49,44,50,44,51,17,31,73,47,23 (the ASCII codes from the input string combined with the standard length suffix values).

Second, instead of merely running one round like you did above, run a total of 64 rounds, using the same length sequence in each round. The current position and skip size should be preserved between rounds. For example, if the previous example was your first round, you would start your second round with the same length sequence (3, 4, 1, 5, 17, 31, 73, 47, 23, now assuming they came from ASCII codes and include the suffix), but start with the previous round’s current position (4) and skip size (4).

Once the rounds are complete, you will be left with the numbers from 0 to 255 in some order, called the sparse hash. Your next task is to reduce these to a list of only 16 numbers called the dense hash. To do this, use numeric bitwise XOR to combine each consecutive block of 16 numbers in the sparse hash (there are 16 such blocks in a list of 256 numbers). So, the first element in the dense hash is the first sixteen elements of the sparse hash XOR’d together, the second element in the dense hash is the second sixteen elements of the sparse hash XOR’d together, etc.

For example, if the first sixteen elements of your sparse hash are as shown below, and the XOR operator is ^, you would calculate the first output number like this:

65 ^ 27 ^ 9 ^ 1 ^ 4 ^ 3 ^ 40 ^ 50 ^ 91 ^ 7 ^ 6 ^ 0 ^ 2 ^ 5 ^ 68 ^ 22 = 64

Perform this operation on each of the sixteen blocks of sixteen numbers in your sparse hash to determine the sixteen numbers in your dense hash.

Finally, the standard way to represent a Knot Hash is as a single hexadecimal string; the final output is the dense hash in hexadecimal notation. Because each number in your dense hash will be between 0 and 255 (inclusive), always represent each number as two hexadecimal digits (including a leading zero as necessary). So, if your first three numbers are 64, 7, 255, they correspond to the hexadecimal numbers 40, 07, ff, and so the first six characters of the hash would be 4007ff. Because every Knot Hash is sixteen such numbers, the hexadecimal representation is always 32 hexadecimal digits (0-f) long.

Here are some example hashes:

  • The empty string becomes a2582a3a0e66e6e86e3812dcb672a272.
  • AoC 2017 becomes 33efeb34ea91902bb2f59c9920caa6cd.
  • 1,2,3 becomes 3efbe78a8d82f29979031a4aa0b16a9d.
  • 1,2,4 becomes 63960835bcdc130f0b66d7ff4f6a5a8e.

Treating your puzzle input as a string of ASCII characters, what is the Knot Hash of your puzzle input? Ignore any leading or trailing whitespace you might encounter.

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!

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 10.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Twist and Shout, by The Beatles.