# 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!