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

On Day 16 we’ll revisit an past solution for inspiration and save ourselves 7 days of waiting. 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, which we will do some further parsing on later.

⭐ Day 16, Part 1

The puzzle text can be found here.

I’m going to implement our tiny set of instructions as a sealed class to make things easier on myself.

sealed class Dance
class Spin(val amount: Int) : Dance()
class Exchange(val left: Int, val right: Int) : Dance()
class Partner(val left: Char, val right: Char) : Dance()

And we’ll do the somewhat messy parsing of the giant input string into instructions:

class Day16(input: String, private val programNames: String = "abcdefghijklmnop") {

	private val instructions: List<Dance> = parseInput(input)

	private fun parseInput(input: String): List<Dance> =
	    input
	        .split(",")
	        .map { it.trim() }
	        .map {
	            when (it.first()) {
	                's' -> Spin(it.drop(1).toInt())
	                'x' -> {
	                    val (a, b) = it.drop(1).split("/").map { it.toInt() }
	                    Exchange(a, b)
	                }
	                'p' -> {
	                    Partner(it[1], it[3])
	                }
	                else -> throw IllegalArgumentException("Bad input: $it")
	            }
	        }
}

I’ll let you go through the nitty-gritty details on that, but essentially we split our input into individual strings, see what character they start with, and then rip the rest of the string apart and create a subclass of Dance.

And of course, we need to have our instructions evaluated against our programs, so I’ve written a function to evaluate a single instruction. In the case of a Spin instruction, a new CharArray is created and returned. In the case of Exchange and Partner it just returns the programs it was given because those are swapped in place. Also, I’ve written another swap extension function on CharArray, which just swaps two values in place (similar to the version we already have on IntArray).

private fun evaluate(programs: CharArray, instruction: Dance): CharArray =
    when (instruction) {
        is Spin -> {
            (programs.takeLast(instruction.amount) + programs.dropLast(instruction.amount)).toCharArray()
        }
        is Exchange ->
            programs.swap(instruction.left, instruction.right)
        is Partner ->
            programs.swap(programs.indexOf(instruction.left), programs.indexOf(instruction.right))
    }

Solving part one involves running through the instructions a single time and joining the resulting programs list into a string.

fun solvePart1(): String =
    executeInstructions()

private fun executeInstructions(startState: CharArray = initialState): String =
    instructions.fold(startState) { carry, next -> evaluate(carry, next) }.joinToString("")

I use a fold to iterate through the instructions, starting with the start state. Despite the amount of code we wrote to parse the input, I feel this part of the challenge was pretty easy. We’ve earned our star, let’s move on.

⭐ Day 16, Part 2

The puzzle text can be found here.

Let’s do some quick math. After parsing the instructions, the executeInstructions function takes just under 1 millisecond to run . Let’s round that up to 1ms to account for garbage collection and whatever other factors are at play in a longer run. Do that 1,000,000,000 times, and we have to wait for ALMOST 11 DAYS. Clearly, there has to be a better way to do this.

Let’s think back to the puzzles we’ve already solved. If you look at Day 6 we were asked to identify a cycle in our memory allocation algorithm. Could we use the same thing here? Given 1,000,000,000 runs with only 16 programs and the fact that the person who invented this puzzle clearly didn’t want us to wait a week to solve it, I bet we can.

My approach is going to be:

Create a map called memory to store the state of the programs (hash) after they are run, and the run number we found it in.
Keep executing the full set of instructions and record the hash and run number until we generate a duplicate.
Figure out the size of the cycle and calculate out how far from the end of 1,000,000,000 runs we will be if we eliminate redundant cycles.
Look in the memory for what the 1,000,000,000th record would be, had we run all the way to the end.

When I ran this on my input the cycle was fairly short - 48 runs long starting with the first run. I’m not sure, but it seems logical that the cycle might not always start at 1, so we have to account for that for a general solution.

I’ve decided to model this as a tail recursive function rather than iterate as a loop. Both work fine, both do the same work, I just think the recursive solution looks more elegant.

tailrec fun solvePart2(memory: Map<String, Int> = mapOf(), loopNumber: Int = 0, hash: String = programNames): String {
    return if (hash in memory) {
        // We found it!
        val cycleStart = memory.getValue(hash)
        val offset = (1_000_000_000 % (loopNumber - cycleStart)) - cycleStart
        memory.entries.first { it.value == offset }.key
    } else {
        solvePart2(memory + (hash to loopNumber), loopNumber.inc(), executeInstructions(hash.toCharArray()))
    }
}

Let’s go over it. The first time we call solvePart2, we initialize our memory (the hashes we’ve already seen), a loopNumber (how many times we’ve done this), and a hash (defaulting to the original alphabet). If we don’t find the hash in our memory, we add it to the memory, increment our loop number, execute the instructions against the hash we were given and pass that all, recursively, to ourselves.

Because this is recursive, we need a terminal condition. That is, of course, finding the hash in our memory. When that happens, we calculate our offset by dividing the cycle length into 1,000,000,000, and subtracting the loop number that started the cycle in case the cycle doesn’t start at zero (mine did). Remember: the offset represents how far along the cycle the 1,000,000,000th entry is. Finally, we search through the values in our memory until we find the offset, and there’s our end hash!

This implementation should be tail recursive or the stack will overflow if you have a long enough cycle. For me this runs in about 125ms! We could run that 8,000,000 times in the time it would take to do this without eliminating cycles! I’m sure there are plenty of optimizations that could be made to get this even quicker, if we were so inclined.

We either cheated time or broke the fabric of space (perhaps both?) but it earns us a star in either case, so that’s cool.

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

2^4 days and we’ve earned 2^5 stars with 18 left to go! Only 9 days left!

⭐ Day 16, Part 1

⭐ Day 16, Part 2

Further Reading