Advent of Code 2022 - Day 6, in Kotlin - Tuning Trouble • Todd Ginsberg

I enjoyed today’s puzzle mostly because I just sort of fell into the solution. I was tinkering with an idea for Part One and it worked, and was able to reuse it for Part Two. That almost never happens, and I was happy that today’s puzzle required no special input parsing after yesterday.

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

Puzzle Input

Unlike yesterday’s puzzle which was almost entirely about input parsing, today we have absolutely nothing to do. We will take our input today as a single String and not change it in any way.

class Day06(private val input: String) {

}

⭐ Day 6, Part 1

The puzzle text can be found here.

When I first read this problem, I immediately though of Kotlin’s windowed function. The windowed function works over a collection and creates windowed views over that collection. For example, if we have a list of numbers 1 through 10: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and wanted a window of length 4 to slide 1 element over each time (list.windowed(4,1)), it would give us: [[1,2,3,4], [2,3,4,5], [3,4,5,6]...] (etc). With windowed, we could change the window size from 4 to something else, or change how many elements we slide over on each step from 1 to something else (fun fact: chunked, which we’ve seen in previous days is implemented using windowed, it sets the window size and the slide size to the same values!).

But then I realized that by using windowed we wouldn’t have access to the index, which we need to calculate our answer. But then I remembered Kotlin has a withIndex function that turns a stream of values (like a String) into a stream of IndexedValue which contains both the index and the value at each position. Calling that function on a String will give us a List<IndexedValue<Char>>, which we can use to build our solution.

We’ll write this function as a private extension function on String.

// In Day06

private fun String.findStartMarker(startMarkerSize: Int): Int =
        withIndex()
        .windowed(startMarkerSize, 1)
        .first { window ->
            window.map { it.value }.toSet().size == startMarkerSize
        }
        .last().index +1

We’ve already covered the first few lines - we call withIndex on our input, and then call windowed on that. This results in a rather ugly type signature of List<List<IndexedValue<Char>>>. Thankfully we don’t have to actually look at that, we just need to realize that the inner List<IndexedValue> represents our windowed values.

Once we have our indexed windowed view of our input we need to find the first view of the window that has startMarkerSize (4 in this case) unique elements. To do that, we can map the values out of the IndexedValue elements in the window, call toSet on it, and take its size. This represents the total unique characters in the window, which we can then compare to startMarkerSize. By using first, we find the first IndexedValue that meets that condition.

Now that we’ve found the List<IndexedValue> we care about, we call last() on it to the the final IndexedValue out. This contains our answer, so we return the index, remembering to add 1 because the problem statement is one-indexed, and we are working with a zero-indexed list.

Running this with a startMarkerSize of 4 gets us our solution.

// In Day06

fun solvePart1(): Int =
    input.findStartMarker(4)

Star earned! Onward!

⭐ Day 6, Part 2

The puzzle text can be found here.

I know what you’re probably thinking. “Well, we wrote that function for start markers of length 4 and it ran fine, I bet it takes forever with 14”. I thought that too. And in the absence of an plan I ran it with 14 just to see what would happen and it finished in just a couple of milliseconds. So we’ll call that a victory.

// In Day06

fun solvePart2(): Int =
    input.findStartMarker(14)

Are there ways to make this faster or produce fewer objects on the heap? Almost certainly. But this works and since this is an Advent of Code puzzle we’re going to run once, I’ll take this as-is. If this were production code that ran many times per second, sure, we’d probably have to pick a different approach. But it is important to understand the context in which your code runs.

Note that I found that adding asSequence() as the first step in the expression did not make an appreciable difference in runtime. Perhaps if we ran this a lot of times we’d notice the difference as the JVM’s JIT optimized it, but over a single run I didn’t see a reason to keep it.

Star earned! See you tomorrow.

⭐ Day 6, Part 1

⭐ Day 6, Part 2

Further Reading