Skip to Content

Advent of Code 2017 - Day 5, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 5: 'A Maze of Twisty Trampolines, All Alike'

Posted on

Day 5 is here, and presents us with another fairly straight-forward problem. We’re going to write our first recursive function of Advent of Code 2017 today. The problem description is quite lengthy, but the actual solution is short and simple.

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 jump offsets. I’ve parsed this into a List<Int> called input that each of my solutions will depend on.

Day 5, Part 1

I wish I always had requirements as thorough and well written as the ones that come with Advent of Code. This is quite lengthy, don’t get discouraged, it’s all useful.

An urgent interrupt arrives from the CPU: it’s trapped in a maze of jump instructions, and it would like assistance from any programs with spare cycles to help find the exit.

The message includes a list of the offsets for each jump. Jumps are relative: -1 moves to the previous instruction, and 2 skips the next one. Start at the first instruction in the list. The goal is to follow the jumps until one leads outside the list.

In addition, these instructions are a little strange; after each jump, the offset of that instruction increases by 1. So, if you come across an offset of 3, you would move three instructions forward, but change it to a 4 for the next time it is encountered.

For example, consider the following list of jump offsets:

0
3
0
1
-3

Positive jumps (“forward”) move downward; negative jumps move upward. For legibility in this example, these offset values will be written all on one line, with the current instruction marked in parentheses. The following steps would be taken before an exit is found:

  • (0) 3 0 1 -3 - before we have taken any steps.
  • (1) 3 0 1 -3 - jump with offset 0 (that is, don’t jump at all). Fortunately, the instruction is then incremented to 1.
  • 2 (3) 0 1 -3 - step forward because of the instruction we just modified. The first instruction is incremented again, now to 2.
  • 2 4 0 1 (-3) - jump all the way to the end; leave a 4 behind.
  • 2 (4) 0 1 -2 - go back to where we just were; increment -3 to -2.
  • 2 5 0 1 -2 - jump 4 steps forward, escaping the maze.

In this example, the exit is reached in 5 steps.

How many steps does it take to reach the exit?

My first thought is that we’re going to have an array of Ints (the offsets), a program counter (pc, indicating which element we are pointing at), and an Int to track the number of steps we’ve taken so far. We will keep jumping around and changing the offset until we produce a value outside of our offset array. We could easily write this as a while loop.

Now, we could do all that with a loop and it would work perfectly fine, and probably perform quickly. However loops are ugly, and this is a perfect opportunity to write a nice elegant recursive function. If you’re not familiar with recursion, it’s just a function that calls itself. On the surface that doesn’t sound all that useful, but it forces you to think about your problem in its most basic form.

In our problem, we’re trying to get the algorithm to produce a pc value that is outside of the offsets array. That’s our base case. If we detect that, we’re done. Otherwise, we just keep going.

fun solvePart1(): Int =
    jump(input)

tailrec private fun jump(offsets: IntArray, pc: Int = 0, steps: Int = 0): Int =
    if (pc < 0 || pc >= offsets.size) steps   // Base case
    else {
        val nextPc = pc + offsets[pc]
        offsets[pc] += 1
        jump(offsets, nextPc, steps.inc())    // Call to self, with new inputs
    }

What’s this tailrec keyword? If you aren’t used to writing a lot of recursive code, that might be new. This is a hint to the Kotlin compiler to unwind our recursive call into a loop so we don’t get a stack overflow. For a better description and some caveats to this, see the Kotlin tairec documentation

As you can see, I’m taking advantage of Kotlin’s default values for pc and steps, and since this is a private function I don’t have to worry about people passing nonsensical or bad values for those. I can control the inputs. And it’s pretty clear that the first thing our function does is to see if we’ve reached the end yet. If we are? Great, return the current step count and we’re done!

The else condition is also pretty straight forward, and exactly like the body of a loop we would have written (because a recursive function IS a loop if you think about it!). Store off the pc value, increment the offset that pc is pointing to, and call ourselves with our offsets, next pc value, and steps +1.

Running this is super quick: my answer took over 300,000 jumps and this code ran in under 35ms.

Gold star for us, let’s move on.

Day 5, Part 2

The twist today is rather simple, and gives us an opportunity to refactor what we’ve already done!

Now, the jumps are even stranger: after each jump, if the offset was three or more, instead decrease it by 1. Otherwise, increase it by 1 as before.

Using this rule with the above example, the process now takes 10 steps, and the offset values after finding the exit are left as 2 3 2 3 -1.

The jumping algorithm is almost the same, but in part two we mutate the current offset differently. This sounds like a job we could do by passing in a function to tell the jump function how to mutate the offset. In the case of part one, it always returns 1, and for part two it returns either -1 or 1.

So now our recursive jump function takes a new argument called mutator, which is a function that takes an Int (the current value of the offset), and returns an Int (the new value of the offset). This means jump now looks like this:

tailrec private fun jump(offsets: IntArray, mutator: (Int) -> Int, pc: Int = 0, steps: Int = 0): Int =
    if (pc < 0 || pc >= offsets.size) steps
    else {
        val nextPc = pc + offsets[pc]
        offsets[pc] += mutator(offsets[pc])
        jump(offsets, mutator, nextPc, steps.inc())
    }

Now we can use jump to satisfy both requirements. Instead of just adding 1 it adds whatever a call to the mutator function says to do.

And calling our new tail recursive jump function looks like this now:

fun solvePart1(): Int =
    jump(input, { 1 }) 

fun solvePart2(): Int =
    jump(input, { if (it >= 3) -1 else 1 })

Each part provides a mutator implementation, and the code works all the same way and just as fast. My answer to part two was around 30,000,000 jumps and only took around 100ms! The JVM is really very good at optimizing code in situations like this.

And with that, we’ve earned our second star of the day!

At the end of day 5, we’ve earned 10 stars with 40 left to go! 20% of the way there!

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 5
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Jump Around!