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

Day 6 of Advent of Code provided us with another problem with a fairly straight forward solution. The twist that part two gives us an opportunity to do some slight refactoring to get the answer.

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 consisting of memory values. I’ve parsed this into an IntArray called input that each of my solutions will depend on.

⭐ Day 6, Part 1

The puzzle text can be found here.

Do you see what I see? To me, this looks like a job for another tail recursive function. We could write it as a loop, but I feel a recursive function is more elegant and just reads a lot easier. In order to determine if we’ve seen a specific memory arrangement before, we’ll need to keep track of them in a Set. I decided the best way to do that was to join all of the values in the IntArray representing the memory into a String. This just seemed easier to debug, and in practice worked a lot faster than storing a copy of the IntArray itself. So we’ll define a Set<String> to store all of the Stringified hashes of the memory after each step.

fun solvePart1(): Int =
    reallocate(input)

tailrec private fun reallocate(memory: IntArray,
                               seen: Set<String> = mutableSetOf()): Int {
    val hash = memory.joinToString()
    return if (hash in seen) seen.size
    else {
        val (index, amount) = memory.withIndex().maxBy { it.value }!!
        memory[index] = 0
        repeat(amount) { i ->
            val idx = (index + i + 1) % memory.size
            memory[idx] += 1
        }
        reallocate(memory, seen + hash)
    }
}

Let’s go over what’s happening in our function. We take the current view of the memory (which we’ll just keep overwriting with each pass), and a Set<String> called seen, representing all of the hashes of memory we’ve seen. This is defaulted to the empty set, so callers don’t have to bother setting that. Once we’re in the function, we create the hash and see if we’ve seen it already. If we’ve seen it, great! We return the size of the seen set, which indicates how many hashes we’ve run across so far. Problem solved.

If we haven’t seen that hash before, we’ll eventually add it to the seen Set, but for now just hold off on that. Since we’re writing a recursive function, we’ll add it to the set when we make that call. In order to perform the memory reallocation we need to know both the index and value of the largest value in memory. Kotlin lets us get both of these values at once, thanks to a combination of withIndex() and maxBy().

val (index, amount) = memory.withIndex().maxBy { it.value }!!

I don’t normally like using the hold my beer operator (!!), but since I know that memory will always contain values, we can get away with it here. The rest of the function clears out the high spot we found in the memory and reallocates its number across the rest of the buckets. I do this with repeat, but you could do it any number of ways.

Finally, we call ourselves again with the new version of memory, and our set of all hashes, with our previously calculated hash added in.

This passes test and gives us a star! It doesn’t perform terribly (< 1s for me) either.

⭐ Day 6, Part 2

The puzzle text can be found here.

Well, that’s not so bad since we have most of what we need for an answer. A quick change of data structure, some minor refactoring and we’re done. We’ll use the method we learned on Day 5 of passing in a function so the solution to parts one and two can share as much code as possible.

Right now, we store the memory hashes we’ve seen in a Set. If we change that to a Map and store the hash as the key and the cycle number as the value, we should be able to calculate answers to part one and two using the same data structure.

tailrec private fun reallocate(memory: IntArray,
                               seen: Map<String, Int> = mutableMapOf(),
                               answer: (Map<String, Int>, String) -> Int): Int {
    val hash = memory.joinToString()
    return if (hash in seen) answer(seen, hash)
    else {
        val (index, amount) = memory.withIndex().maxBy { it.value }!!
        memory[index] = 0
        repeat(amount) { i ->
            val idx = (index + i + 1) % memory.size
            memory[idx] += 1
        }
        reallocate(memory, seen + (hash to seen.size), answer)
    }
}

It looks almost the same, right? Instead of calculating an answer we delegate that to a function the caller provides (answer). Since the lambda for answer is the last argument, we can take advantage of some nice syntax in Kotlin when calling our reallocate function:

fun solvePart1(): Int =
    reallocate(input) { map, _ ->
        map.size
    }

fun solvePart2(): Int =
    reallocate(input) { map, key ->
        (map.size) - map.getValue(key)
    }

That’s kind of neat right? If we wanted to make our code a bit cleaner, we could even define our answer type signature using Kotlin’s typealias:

typealias AnswerFunction = (Map<String, Int>, String) -> Int

All that means is that whenever we want a function that takes a Map and a String and returns an Int, we could just use AnswerFunction instead, like this:

tailrec private fun reallocate(memory: IntArray,
                               seen: Map<String, Int> = mutableMapOf(),
                               answer: AnswerFunction): Int {
...
}

I don’t usually define a typealias unless they just look too complicated. It’s a subjective thing, and sometimes it just makes sense.

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

At the end of day 6, we’ve earned 12 stars with 38 left to go!

⭐ Day 6, Part 1

⭐ Day 6, Part 2

Further Reading