Advent of Code 2023 - Day 9, in Kotlin - Mirage Maintenance • Todd Ginsberg

Today we’ll write a recursive function (despite the many, many mentions of sequences in the puzzle description) to solve the puzzle and then go enjoy the rest of our Saturday. I hope it’s a nice one where you are.

If you’d rather just view the code, my GitHub Repository is here.

Puzzle Input

We can take our input in as a List<String> and parse it directly into a List<Int> for each row, storing them in another List.

class Day09(input: List<String>) {

    private val rows: List<List<Int>> = 
        input.map { it.split(" ").map { i -> i.toInt() } }
}

We map each row of input by splitting it on the space character and mapping each part toInt. I declared i as the inner/inner lambda variable rather than use it because IntelliJ (rightly) complained that I was shadowing the it I’d already used. Normally in a case like this where I’m not operating on both and the use of it is clear in context it probably doesn’t matter. But I feel that keeping IntelliJ happy is usually a good idea, so why not? But I can’t stop you from using it in two places, can I?

⭐ Day 9, Part 1

The puzzle text can be found here.

Despite the fact that the puzzle text MENTIONS THE WORD SEQUENCE 14 TIMES, I avoided using sequences entirely and used recursion instead. Those sequencing lobbyists will have to find a better way to get me next time! I spent about 4 seconds considering if there is a mathy way to solve this (and I suspect there is) but in the end I figured I’d just mimic what the picture is doing in code and see if that works (spoiler: it does).

In order to solve part 1, we’ll write a recursive function that basically does what the example picture shows us. Calculate differences between elements all the way down until we can’t any more, and then push an answer back up.

We’ll call our function extrapolate and it will take a single row of input and return the Int representing its next value.

// In Day09

private fun extrapolate(row: List<Int>): Int =
    if (row.all { it == 0 }) 0
    else {
        val differences = row.windowed(2, 1).map { it[1] - it[0] }
        row.last() + extrapolate(differences)
    }

The first thing to do with any recursive function is to make sure we handle our end condition or it will run until we run out of memory. In our case, we end recursion when all of the elements of the row are 0. We do that by using the all function from the Kotlin Standard Library. If all elements are 0, the extrapolated future value is also 0, so we return that.

Otherwise, we need to get the differences between each of the numbers in the row. For this we’ll use windowed over the row telling it we want a window size of 2 and to slide over 1 element each time. The windowed function is great - if we have a List<Int> of [1, 2, 3, 4] and call windowed(2, 1) on it, we will end up with a List<List<Int>> of [[1,2], [2,3], [3,4]] (where each window is 2 long, and each next window is 1 over from the previous one. The windowed function is very flexible in allowing us to pick the size of the window, how many we move over each time, and if we’re willing to accept partial windows or not.

Once we have the differences we can recurse by calling extrapolate with them and adding the eventual result to the last element of the row, before returning that result to our caller.

Note that unlike yesterday, we cannot make this a tail-recursive function because the recursive call, despite being physically last in the function description, is not the last thing we do (addition is). We don’t really need it here anyway, these call stacks won’t get that deep.

Once again we’re able to use sumOf from the Kotlin Standard Library to solve part 1 by summing the results of the extrapolatedFuture of each row.

// In Day09

fun solvePart1(): Int =
    rows.sumOf { extrapolate(it) }

Star earned! Onward!

⭐ Day 9, Part 2

The puzzle text can be found here.

My gut reaction upon reading part 2 was “just reverse everything and run it again” (which seems to be my answer for a lot of things ), and it turns out that works here to…

// In Day09

fun solvePart2(): Int =
    rows.map { it.reversed() }.sumOf { extrapolate(it) }

Get the reversed version of each row and get the sumOf their extrapolated values.

Star earned! See you tomorrow!

⭐ Day 9, Part 1

⭐ Day 9, Part 2

Further Reading