Let’s continue our journey of understanding what “idiomatic Kotlin” means and solve one more puzzle from the Advent of Code challenge. The puzzles are independent of each other, so you don’t need to check any of the previous ones we’ve already covered. Simply read through the following solution or watch the video. We hope you learn something new!
Day 5. Binary Boarding
We’re boarding the plane! We need to analyze the list of boarding passes and find the seat with the highest seat ID. Then we need to find the one seat missing from the list, which is ours. You can find the full task description at https://adventofcode.com/2020/day/5.*
A seat is specified as, for example, FBFBBFFRLR, where F means "front", B means "back", L means "left", and R means "right". The first 7 characters are either F or B and they specify exactly one of the 128 rows on the plane (numbered 0 through 127). The last three characters are either L or R; these specify exactly one of the 8 columns of seats on the plane (numbered 0 through 7). A more detailed encoding description is given on the puzzle page.
Every seat has a unique seat ID, calculated by multiplying the row by 8 and then adding the column.
The puzzle input is the list of boarding passes. The first task is to find the boarding pass in this list with the highest seat ID.
The second task is to find the missing boarding pass in the list. The flight is completely full, there’s only one missing boarding pass, and that’s our seat. However, some of the seats at the very front and back of the plane don't exist on this aircraft, so they are missing from the list as well.
As usual, we suggest that you try to solve the task on your own before reading the solution. Here’s how you can set up Kotlin for this purpose.
Solution
Let’s first discuss the encoding of the boarding passes. Note how it is a nicely “hidden” binary representation of natural numbers! Let’s take a closer look.
Boarding pass: binary representation
First, let’s look at the rows. There are 128 rows on the plane, which are encoded with 7 “bits”. These bits are called F and B in the puzzle, but they carry the same meaning as 0 and 1 do in the binary representation. To extend the analogy, the way to identify the exact row based on the boarding pass is reminiscent of the algorithm used to convert a binary representation of the number to a decimal.
Let’s consider the provided example – the first seven characters of FBFBBFFRLR that decode the “row”. F means to take the “front”, or the lower half, while B is to take the “back”, or the upper half on each iteration. Taking the lower half is equivalent to not adding the corresponding power of two to the result (or multiplying it by zero), while taking the upper half is equivalent to adding it to the result (or multiplying it by one).
F = 0; B = 1
FB notation F B F B B F F
Bit 0 1 0 1 1 0 0
Index 6 5 4 3 2 1 0
2^Index 64 32 16 8 4 2 1
Decimal:
0 * 2^6 + 1 * 2^5 + 0 * 2^4 + 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0 =
32 + 8 + 4 =
44
If this conversion is clear to you, you can skip the remaining explanations in this section and go directly to the Kotlin implementation. If not, please read the description of the conversion strategy on the task page and the following explanations carefully.
We start by considering the whole range, rows 0 through 127. The maximum value that can be decoded via 7 bits is 1111111, or 127 if converted to the decimal form: 27 - 1 = 26 + 25 + 24 + 23 + 22 + 21 + 20 = 127. Each bit is responsible for its part of the range: if it’s 1, we add the corresponding power of two to the result; if it’s 0, we skip it.
| Bit | Bit index | Description of the task | Reworded in ‘binary representation’ terms |
F = 0
|
6
|
F means to take the lower half, keeping rows 0 through 63.
|
We don’t add 26=64 to the result.
That keeps the result in the |
B = 1
|
5
|
B means to take the upper half, keeping rows 32 through 63.
|
We add 25=32 to the result. That keeps the result in the range 32..63.
|
F = 0
|
4
|
F means to take the lower half, keeping rows 32 through 47.
|
We don’t add 24=16 to the result. That makes the possible range 32..(63-16), or 32..47.
|
B = 1
|
3
|
B means to take the upper half, keeping rows 40 through 47.
|
We add 23=8 to the result. That keeps the result in the range (32+8)..47, or 40..47.
|
B = 1
|
2
|
B keeps rows 44 through 47.
|
We add 22=4 to the result. That keeps the result in the range (40+4)..47, or 44..47.
|
F = 0
|
1
|
F keeps rows 44 through 45.
|
We don’t add 21=2. That makes the possible range 44..(47-2), or 44..45.
|
F = 0
|
0
|
The final F keeps the lower of the two, row 44.
|
We don’t add 20=1. That makes the result 44..(45-1), or simply 44.
|
Decoding column
Decoding the column follows the same logic, but now R takes the upper half and corresponds to bit 1, while L takes the lower half and corresponds to bit 0.
Let's now consider the last 3 characters of FBFBBFFRLR.
L = 0; R = 1
RL notation R L R
Bit 1 0 1
Index 2 1 0
2^Index 4 2 1
Decimal:
1 * 2^2 + 0 * 2^1 + 1 * 2^0 =
4 + 1 =
5
The whole range represents columns 0 through 7. It’s the maximum value that can be encoded via three bits: 22 + 21 + 20 = 7.
-
Rmeans to take the upper half, keeping columns 4 through 7. In other words, take22=4with the multiplier"1". -
Lmeans to take the lower half, keeping columns 4 through 5. In other words, take21=2with the multiplier"0". - The final
Rkeeps the upper of the two, column 5. In other words, take20=1with the multiplier"1",making the result4+1=5.
The last part is converting the row and the column numbers to the seat ID by using the formula: multiply the row by 8 and then add the column. For the sample boarding pass, the row is 44 and the column is 5, so this calculation gives the seat ID as 44 * 8 + 5 = 357.
Combining row and column
But if we look closer at this formula, we’ll notice that we don’t need to find the row and column separately! We can simply add all the row bits with indexes increased by three to the result (note that 8 = 23). This bit operation is formally called “left-shift”.
FBRL notation F B F B B F F R L R
Bit 0 1 0 1 1 0 0 1 0 1
Index 9 8 7 6 5 4 3 2 1 0
Decimal:
[0 * 2^9 + 1 * 2^8 + 0 * 2^7 + 1 * 2^6 + 1 * 2^5 + 0 * 2^4 + 0 * 2^3] + [1 * 2^2 + 0 * 2^1 + 1 * 2^0] =
2^3 * [0 * 2^6 + 1 * 2^5 + 0 * 2^4 + 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0] + [1 * 2^2 + 0 * 2^1 + 1 * 2^0] =
8 * 44 + 5 =
357
With a little bit of math, a Kotlin solution can almost fit on a single line! Let’s see how.
Converting boarding pass to seat ID
We only need to replace B/F and R/L with 1/0 notation, and then convert the resulting binary representation to an integer. Each of these operations is one function call:
fun String.toSeatID(): Int = this
.replace('B', '1').replace('F', '0')
.replace('R', '1').replace('L', '0')
.toInt(radix = 2)
fun main() {
println("0101100101".toInt(radix = 2)) // 357
println("FBFBBFFRLR".toSeatID()) // 357
}
The String.replace(oldChar: Char, newChar: Char) function replaces all occurrences of the old character with the new character. There are two more similar functions. If you need to replace each substring with a new string, pass the strings as arguments:
String.replace(oldValue: String, newValue: String)
In order to replace each substring that matches the given regular expression, use another function taking Regex as an argument:
String.replace(regex: Regex, replacement: String)
The String.toInt(radix: Int) function parses the string receiver as an integer in the specified radix. In our case, we specify that the radix is two, so it parses the binary representation of the number.
There’s no need to reimplement the conversion algorithm from scratch when you can use the library functions – unless you specifically want to practice that, of course, but that’s not the goal of this puzzle.
We’ve got the seat ID from the boarding pass now and we can continue with the task.
Finding the maximum seat ID
As usual, we need to read the input first. After implementing the conversion function, it’s quite straightforward:
fun main() {
val seatIDs = File("src/day05/input.txt")
.readLines()
.map(String::toSeatID)
// ...
}
The seatIDs list is a list of integers, and the only thing left is finding the maximum in this list. There’s no need to implement it from scratch; we simply use the maxOrNull() library function:
fun main() {
val seatIDs = …
val maxID = seatIDs.maxOrNull()
println("Max seat ID: $maxID")
}
We’ve found the seat with the maximum seat ID.
Finding the vacant seat ID
The second part of the task is finding the vacant seat that is missing from the list. There’s guaranteed to be only one. However, we remember that some of the seats at the very front and back of the plane don't exist on this aircraft, so they are missing as well. And so, we can’t simply iterate through the range from 1 to maxID and check for missing seats, as we would also “find” those at the very front and back.
Note, however, that our required vacant seat is not on the edge. This means it’s the only missing seat whose neighbors are both present in the list. So, we can check for this condition: that the seat itself must be missing (in other words, not occupied), but both its neighbors must be occupied.
First, to make our code more expressive, let’s add a function that checks whether a given seat is occupied. It checks that the given seat index belongs to the list of seat IDs provided as the input for our challenge. To make this check quickly, we convert the given list to a set:
fun main() {
val seatIDs: List<Int> = …
val occupiedSeatsSet = seatIDs.toSet()
fun isOccupied(seat: Int) = seat in occupiedSeatsSet
}
Kotlin allows us to create local functions, that is, functions inside other functions. That’s really convenient for the kind of short and simple function we need to write here: the isOccupied() function will capture the outer variable, occupiedSeatsSet, and we don’t need to pass it explicitly as a parameter.
Now the only thing left to do is find the desired seat index, when the seat is not occupied but the neighboring seats (with indices -1 and +1) are both occupied:
val mySeat = (1..maxID).find { index ->
!isOccupied(index) && isOccupied(index - 1) && isOccupied(index + 1)
}
println("My seat ID: $mySeat")
That’s it!
The whole main function that solves both parts of the task looks as follows:
fun main() {
val seatIDs = File("src/day05/input.txt")
.readLines()
.map(String::toSeatID)
val maxID = seatIDs.maxOrNull()!!
println("Max seat ID: $maxID")
val occupiedSeatsSet = seatIDs.toSet()
fun isOccupied(seat: Int) = seat in occupiedSeatsSet
val mySeat = (1..maxID).find { index ->
!isOccupied(index) && isOccupied(index - 1) && isOccupied(index + 1)
}
println("My seat ID: $mySeat")
}
Note that in order to use maxID as the upper bound of the range, we call !!, since the maxOrNull() function returns a nullable value. Specifically, it returns null if the list is empty.
Following the Kotlin philosophy, you might expect to find the max() function, throwing an exception if the list is empty. And you’d be right! However, in Kotlin 1.5 the max() function is deprecated, and in future versions it will be totally removed and replaced with a function throwing an exception. The max() function was present in the standard library starting with Kotlin 1.0 but returned a nullable value, and now the Kotlin team is slowly fixing this small discrepancy. Until the max() function reappears in the standard library, it’s fine to write maxOrNull()!! to explicitly highlight that you need the non-null value as a result, and you prefer an exception if the list is empty. Alternatively, to avoid using !!, you can use maxOf { it } for now.
That’s it! We outlined the strategy for solving the puzzle, recognized the binary encoding for the numbers, discussed how it works, and presented the solution in Kotlin, which is quite simple thanks to the Kotlin standard library functions.
*Used with the permission of Advent of Code (Eric Wastl).
Top comments (0)