Advent of Code 2020 - Day 5, in Kotlin - Binary Boarding • Todd Ginsberg

Today’s main lesson for me was that while the puzzle descriptions are fun, they can hide a simple solution in plain sight. I started solving this one way, and then the actual way we solve it below struck me and I started over again. Judging by discussions I’ve seen, I’m not alone!

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

Problem Input

We’ll load the input into a List<String> and use it directly in our class today:

class Day05(private val input: List<String>) {

}

⭐ Day 5, Part 1

The puzzle text can be found here.

I will admit I got about half way though solving Part 1 “the long way” when I realized that instead of following the algorithm that the story sets out for us, we can take a short cut. The story essentially shows us how a binary search works. But what the story doesn’t directly say is that the input is actually a binary number, just encoded with different letters.

To show you what I mean, let’s take the worked example from today’s puzzle: FBFBBFFRLR == 357. For now, let’s just concentrate on the last part: RLR, to make things simpler. According to the example, RLR == 5. Because we’re dealing with only two symbols here (R and L), we can convert them into 1 and 0. Once we do that, we have 101 instead of RLR. And what do you think 101 in binary is in decimal ? 5!

Does this work for the first half? You bet it does. FBFBBFF == 44. Converting B to 1 and F to 0, we get 0101100. And what is that in binary ? You got it - 44!

But wait, it gets better. The instructions tell us to break up the input string and calculate these numbers, but for the row we have to multiply by 8 and add the seat number. Let’s see if we can shortcut that too. Remember our example: FBFBBFFRLR. Let’s convert that to binary using the same rules as above (R and B == 1, L and F == 0). This leaves us 0101100101. And I’ll give you one guess what that is in decimal - 357! Our answer!

What does this mean? We don’t have to do anything other than convert characters in the string to 1 and 0, and then convert that from binary to decimal!

private fun seatId(pattern: String): Int =
    pattern.map { if (it in setOf('B', 'R')) '1' else '0' }.joinToString("").toInt(2)

In this case, we’ll map over each character in our String. If we run into a B or an R, we convert it to a 1 character, otherwise we convert it to a 0. We take all of those and join them together into a String. Kotlin has a handy toInt() function in the standard library that allows us to specify the radix of the number we are converting. We’ll tell toInt() that we’re converting from binary (2) and that returns our seat number!

All that’s left is to map each of the inputs to their seat numbers and pick out the max value.

fun solvePart1(): Int =
    input.map { seatId(it) }.maxOrNull() ?: throw IllegalStateException("No answer")

The maxOrNull function is new to Kotlin 1.4 and is meant to replace the max function (there are corresponding minOrNull and min functions as well). This change was made to make this function behave more like the rest of the standard library. If you call max on an empty list, you’ll end up with an exception. Now, you’ll end up with null and will have to handle it. I’ve chosen to handle it by throwing an exception here.

Problem solved, onward!

⭐ Day 5, Part 2

The puzzle text can be found here.

There are quite a few ways to solve part 2, and I’ve gone around and around on this one. Of the six or so solutions I’ve tried, this one seems to be the nicest in terms of readability and performance.

fun solvePart2(): Int =
    input.map { seatId(it) }
        .sorted()
        .zipWithNext()
        .first { it.second - it.first != 1 }
        .first + 1

First, we calculate all of the seat IDs like we did in Part 1. Then we sort the list to make it sequential. The main part of this solution is to use the zipWithNext() function from the Kotlin standard library. The zipWithNext function turns a List<T> into a List<Pair<T,T>>. In more concrete terms, it turns listOf(1,2,3) into listOf(Pair(1,2), Pair(2,3)). So by using zipWithNext, we get a nice ordered list of pairs of numbers from the original list.

We can use those pairs to make sure they are adjacent numbers. We take the first pair that is not adjacent, because the first number in that pair comes directly before our answer. Take the first element of the pair and add 1 to it to get the missing element from the list.

Star earned! See you tomorrow!

⭐ Day 5, Part 1

⭐ Day 5, Part 2

Further Reading