Advent of Code 2020 - Day 9, in Kotlin - Encoding Error • Todd Ginsberg

We’re going to be doing a lot of list manipulation today. Thankfully, the Kotlin standard library has us covered. Today’s puzzles strike me as something you might see in a coding interview (with a more entertaining story).

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

Problem Input

Originally I had tried to use my existing helper function to load the input as a List<Int>, but some of the numbers overflowed an Int, so I wrote up a version that loads a file into a List<Long> and used that.

// In Resources

fun resourceAsListOfLong(fileName: String): List<Long> =
    resourceAsList(fileName).map { it.toLong() }

And for completeness, we’ll call it input, as usual.

class Day09(private val input: List<Long>)

Our input is already in a useful format, we don’t need to do any more parsing or manipulating (yay!).

⭐ Day 9, Part 1

The puzzle text can be found here.

The first thing we need to do is figure out a way to determine if a single given List<Long> is valid. This will be a minimal list of just the preamble and the next value (which we will call the target). We’ll worry about generating those later on.

Originally, I was going to write a function to generate Pair<Long,Long> in order to pair all of the numbers up. Given every possible pair, at least one must add up to the target or the preamble is wrong. But then I read this in the instructions:

“The two numbers will have different values…”

And it struck me that we could do this a different way. Since the numbers that add up to the target will be different, that means we don’t have to guard against the idea that two of the same number will add up to the target. At least that’s how I read it, and that’s how it worked out for my input. I’d be very interested to hear if this does not hold true for your input!

So given all that, we’ll turn our preamble into a Set<Long> and then come at this from the other way - given each member of the set, is there another member of the set that adds up to the target?

// In Day09

private fun List<Long>.preambleIsValid(): Boolean {
    val target = this.last()
    val subjects = this.dropLast(1).toSet()
    return subjects.any { target - it in subjects }
}

We’ll write our function as an extension function on List<Long>, because that seems like a nice way to clean up the code a bit for when we call this. We assume again that the List<Long> we are working on has the full preamble and the target at the end. So we take off the target, and create a Set<Long> called subjects from the rest of the list (remember to drop the target, although in practice I’m not sure that really matters). To be a valid preamble, any member of the set must combine with another member of the set to sum up to the target. We therefore test that target minus it is in the set. If that happens at least once, the preamble is valid.

Now that we have that, we can use the windowed function from the Kotlin standard library to solve part 1. The windowed function will generate sliding window representations of a List<T>. In our case we’re telling it we want windows that are the size of the preamble plus one (for the target), and to shift over only 1 element in the original list each time. We also tell it (false) that we don’t want partial windows. So if our preamble is 5, we will get a list of elements 0 through 5, and then 1 through 6, and then 2 through 7, and so on.

// In Day09

fun solvePart1(preamble: Int = 25): Long =
    input.windowed(preamble+1, 1, false).first { !it.preambleIsValid() }.last()

We take the first List<Long> that has a valid preamble. Since this is a full list, we take the last() value (the target) and return it as the answer to Part 1.

Note that our solvePart1 function allows us to set the size of the preamble. I used this for unit testing, and it defaults to 25 (the standard length).

Star earned, onward!

⭐ Day 9, Part 2

The puzzle text can be found here.

To solve part 2, we’ll have to write a function that given a List<Long>, find some sublist that adds up to the target. We’ll implement this as an extension on List<Long> again, because that feels natural here.

// In Day09

private fun List<Long>.findRangeSummingTo(target: Long): List<Long> =
    this.indices.mapNotNull { start ->
        this.indices.drop(start+1).reversed().mapNotNull { end ->
            this.subList(start, end).takeIf { it.sum() == target }
        }.firstOrNull()
    }.first()

Yikes! It’s not that bad, let me explain. In order to find a sublist that adds to the target, we’re going to assume that such a sublist actually exists, otherwise we’d have to write a lot more error handling code than we have here (which is none). What we’re attempting to do here is to use the list indices to generate smaller and smaller sublists and test them to see if they sum to the target.

We set up our outermost loop by indexing forward through our list, keeping only the non-null values that the inner loop will produce. The inner loop is set up to go backwards through our list, taking care not to overlap the start of the list. Again, the inner list only keeps non-null values. For the actual test, we get a sublist of our big list starting at start and ending at end. If that sublist adds up (sum()) to target, it is the list we’re looking for and we can return it via takeIf, otherwise that part of the loop will return null. Taking the very first value that the loops produce will be our value!

If you want to learn more about takeIf and its counterpart takeUnless, I have a blog post that goes into detail on them.

We could probably improve this function by making our inner loop work in the same direction as our outer loop, and then bailing out early when the sum is larger than the target, but I just found this more intuitive even if it is more work. I’m not doing the work, the computer is, so to some extent I don’t really care how many microseconds we might save with a solution that isn’t as easy to reason about.

Now we can solve part 2:

// In Day09

fun solvePart2(preamble: Int = 25): Long {
    val target = solvePart1(preamble)
    val range = input.takeWhile { it != target }.findRangeSummingTo(target)
    return range.minOrNull()!! + range.maxOrNull()!!
}

Sure we could have written this as a single expression, but I think it would have been rather messy so I opted for this. :)

To solve part 2 we grab the answer for Part 1 and call that our target. We then grab everything in the input list before the target using takeWhile. Once we have that, we can call our new findRangeSummingTo() function to find our answer. All that’s left is to sum up the min and max values in the resulting range. Since we know there are both a min and a max, we can use the completely dreadful “Hold My Beer” operator (!!) just this one time.

See you tomorrow!

⭐ Day 9, Part 1

⭐ Day 9, Part 2

Further Reading