# Advent of Code 2017 - Day 6, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 6: 'Memory Reallocation'

Posted on

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(),
...
}
``````

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!