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

The puzzle text can be found here.

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 puzzle text can be found here.

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!