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

Kotlin solutions to parts 1 and 2 of Advent of Code 2020, Day 9: 'Encoding Error'

Posted on

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!