Advent of Code 2021 in Kotlin - Day 1

Publish date: Dec 2, 2021
Tags: kotlin aoc

Table of contents

  1. Part 1
  2. Part 2
  3. Update

Advent of Code seems to be very well put together, but I’ve never had a go before. I’ve also been meaning to learn a bit of Kotlin, so I figured I’ll put the two together. At least for one day, no promises on doing all 25.

Part 1

The first problem is here. We’re given a list of depth measurements and need to work out how many measurements increase from the day before.

My instinct was to fold over the list keeping the previous value and count in the accumulator.

fun increases(depths: List<Int>): Int {
    val head = depths.first()
    val tail = depths.drop(1)

    return tail.fold(Pair(0, head)) { acc, i ->
        if (acc.second < i) Pair(acc.first + 1, i)
        else Pair(acc.first, i)
    }.first
}

The syntax for a tuple (Pair) is what I’d expect. It would of course be nice to have some syntax built in, and this isn’t too bad, but it does make reading a simple fold difficult. It was at this point that I realised there is no linked list in Kotlin’s stdlib, which adds to the clunkiness. Copying the list to get the tail is less than ideal too.

I figured a recursive function wouldn’t really clean this up much, but I had a go none the less.

fun increases(depths: List<Int>): Int {
    tailrec fun loop (prev: Int, count: Int, list: List<Int>): Int {
        return if (list.isEmpty()) count
        else {
            val newCount =
                if (list.first() > prev) count + 1
                else count
            loop (list.first(), newCount, list.drop(1))
        }
    }

    return loop (depths.first(), 0, depths.drop(1))
}

It’s not too bad to read, and I really like that you can explicitly declare your intent of tail recursion. I need to read the docs on this to see if it’s just sending a hint, or if it will actually fail to build if it’s not able to tail call optimize.

So, as I expected, the simplest approach is going to be an imperative one:

fun increases(depths: List<Int>): Int {
    var count = 0
    for (i in 1 until depths.size) {
        if (depths[i] > depths[i - 1]) count++
    }
    return count
}

I don’t think there’s anything I can say here, so on to part 2!

Part 2

We’re now told to do the same thing, but with the sum of a sliding window of three measurements. One thing I had liked when I first starting looking at Kotlin was that the stdlib has plenty of stuff in it. I searched the docs for “window” and sure enough, there’s a tidy little function called windowed that made it very simple to implement.

fun windows(depths: List<Int>): Int {
    return depths
        .windowed(3)
        .map { it.sum() }
        .let { increasesImp(it) }
}

I was looking for a pipe of some sort so that I could compose the function calls and let appears to do the job quite nicely.

Update

After reading the solution to this problem on the Kotlin blog, I missed a very obvious pattern - that we don’t have to compare the sums of two windows as the middle numbers will always be the same and cancel each other out - we only have to compare the lowest and highest numbers. The blog post uses windowed() to do this, but we can actually make a small modification to our imperative solution to cover both parts of the problem like so:

fun increases(depths: List<Int>, windowSize: Int): Int {
    if (windowSize < 1) throw IllegalArgumentException("windowSize must be 1 or greater")

    var count = 0
    for (i in windowSize until depths.size) {
        if (depths[i] > depths[i - windowSize]) count++
    }
    return count
}

To solve the first part of the problem we set the window size to 1, and set it to 3 for the second part.


Thanks for reading! Please feel free to send me an email to talk more about this (or anything else for that matter).