Advent of Code 2020 in Kotlin: Day 05

On Day 05 we need to find our seat on the airplane! We must go over and decode a list of boarding passes to find their seat IDs. A boarding pass is just a sequence of 10 characters.

The whole problem revolves around Binary Search. Decoding a boarding pass is composed of two parts: Initially we analyse the first 7 characters to find the correct row; then, we look at the last 3 characters to find the correct column.

When looking for a row or a column, we divide the search space in half after each inspected character.

Since we are not looking for a number specifically, we can use left-most binary search to get the correct index we are looking for.

Let’s dig into the code!

Data representation

I wanted to represent each line in the input file as a BoardingPassobject. The boarding pass would list its row, column, and seat ID:

data class BoardingPass(val row: Int, val column: Int) {
  val seatID: Int
    get() = row * 8 + column
}

Pretty straightforward, isn’t it?

Reading the data

Like on Day 04, I extended the File class to return me a list of BoardingPasses:

fun File.toListOfBoardingPassesOrNull() : List<BoardingPass>? {
  return readLines().map { it.toBoardingPass() }
}

And to convert a line (String) into a BoardingPass:

fun String.toBoardingPass(): BoardingPass {
    // Find the correct column
    var lo = 0
    var hi = 127
    for (i in 0..6) {
    val mid = lo + (hi - lo) / 2

    if (this[i] == 'F') {
        hi = mid
    } else {
        lo = mid + 1
    }
    }

    val row = lo

    // Find the correct row
    lo = 0
    hi = 7
    for (i in 7..9) {
    val mid = lo + (hi - lo) / 2
    if (this[i] == 'L') {
        hi = mid
    } else {
        lo = mid + 1
    }
    }

    val column = lo

    return BoardingPass(row, column)
}

I’m not gonna go over how the binary search above works (check the Wikipedia article for that). All we do here is iterate over the characters in the boarding pass and extract the row and column. We then return a BoardingPass object with those values.

Part 1: Get the max seat ID in the list of boarding passes

Pretty easy this one:

fun main() {
  print(File("input.txt").toListOfBoardingPassesOrNull()?.map { it.seatID }?.maxOrNull())
}

We read the boarding passes, get the seat ID for each one of them and then select the one with maximum value.

Part 2: Find our own seat ID

The question tells us that our boarding pass is the only one missing in the input, and that the seats immediately before and after ours are taken.

We just must find the empty seat.

One way to do this might be to sort the list of seatIDs and find where there’s a gap of 1. That would give us O(n * log(n)) runtime complexity.

Instead, I decided to use a variation of Counting Sort. We know there will be at most 128 * 8 seats (i.e., 128 rows and 8 columns per row). So I preallocated an array of that size, where each position denotes a seat. Each position in the array has value 0 or 1. Zero means that seat is empty, one means it is taken.

Now we just go over each seat ID we have and mark then as taken in the array. After that, we just iterate over the entire array and find an empty seat between two taken seats. That empty seat is ours.

Here’s what the code looks like:

fun main() {
    val totalSeats = 128 * 8
    val maxSeatID = totalSeats - 1

    // Preallocate array for seats. Zero indicates the seat is emtpy
    val seats = ByteArray(totalSeats) { 0 }

    File("input.txt").toListOfBoardingPassesOrNull()?.map { it.seatID }?.forEach {
    seats[it] = 1
    }

    for (i in 1..maxSeatID-1) {
    // The current seat is empty but the previous and next seats are taken,
    // so that's our seat.
    if (seats[i] == 0.toByte() && seats[i-1] == 1.toByte() && seats[i + 1] == 1.toByte()) {
        print(i)
    }
    }
}

You’ll notice that on the line highlighted I call the toByte method multiple times. That’s necessary due to Kotlin’s limitation. It cannot automatically detect that those literals are of type Byte and there’s no shorthand to cast them. There’s even a ticket on JetBrains’s issue tracker but it doesn’t seem to be going anywhere.

That’s all folks

Today’s puzzle was pretty straightforward. My only surprise was the weirdness about the implicit conversions in Kotlin. Still, I’m happy with my solution.

Let’s see what’s up with day 06 tomorrow!