Skip to Content

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 description below might look long, but again, the author is exceptionally thorough.

A debugger program here is having an issue: it is trying to repair a memory reallocation routine, but it keeps getting stuck in an infinite loop.

In this area, there are sixteen memory banks; each memory bank can hold any number of blocks. The goal of the reallocation routine is to balance the blocks between the memory banks.

The reallocation routine operates in cycles. In each cycle, it finds the memory bank with the most blocks (ties won by the lowest-numbered memory bank) and redistributes those blocks among the banks. To do this, it removes all of the blocks from the selected bank, then moves to the next (by index) memory bank and inserts one of the blocks. It continues doing this until it runs out of blocks; if it reaches the last memory bank, it wraps around to the first one.

The debugger would like to know how many redistributions can be done before a blocks-in-banks configuration is produced that has been seen before.

For example, imagine a scenario with only four memory banks:

  • The banks start with 0, 2, 7, and 0 blocks. The third bank has the most blocks, so it is chosen for redistribution.
  • Starting with the next bank (the fourth bank) and then continuing to the first bank, the second bank, and so on, the 7 blocks are spread out over the memory banks. The fourth, first, and second banks get two blocks each, and the third bank gets one back. The final result looks like this: 2 4 1 2.
  • Next, the second bank is chosen because it contains the most blocks (four). Because there are four memory banks, each gets one block. The result is: 3 1 2 3.
  • Now, there is a tie between the first and fourth memory banks, both of which have three blocks. The first bank wins the tie, and its three blocks are distributed evenly over the other three banks, leaving it with none: 0 2 3 4.
  • The fourth bank is chosen, and its four blocks are distributed such that each of the four banks receives one: 1 3 4 1.
  • The third bank is chosen, and the same thing happens: 2 4 1 2.
  • At this point, we’ve reached a state we’ve seen before: 2 4 1 2 was already seen. The infinite loop is detected after the fifth block redistribution cycle, and so the answer in this example is 5.

Given the initial block counts in your puzzle input, how many redistribution cycles must be completed before a configuration is produced that has been seen before?

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 twist today is rather simple, and gives us an opportunity to refactor what we’ve already done!

Out of curiosity, the debugger would also like to know the size of the loop: starting from a state that has already been seen, how many block redistribution cycles must be performed before that same state is seen again?

In the example above, 2 4 1 2 is seen again after four cycles, and so the answer in that example would be 4.

How many cycles are in the infinite loop that arises from the configuration in your puzzle input?

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!

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 6
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Sad Songs and Waltzes, by Cake.