Phew. Airport security has cleared all of the passengers, and we have emptied our wallet in duty-free. Unfortunately, we appear to have dropped our boarding pass. We have no idea which seat is ours, and the flight attendants are busy with the massive influx of passengers. Our bad!
Day 5: Binary Boarding
We decide to be a little cheeky and surreptitiously scan the boarding passes of our fellow passengers. On each boarding pass, the seat is encoded as a sequence of seven
B's, meaning front or back, followed by three
R's, for left and right. These characters tell us where the airline has situated the passenger: The first seven characters encode the row, and the last three the seat. The plane has
128 rows of seats, numbered from
127; and eight seats per row numbered
Here's an example of such a sequence.
The first character,
F, informs us that we are in the front half of the plane. The next letter,
B, indicates that we're in the rear half of that section. Another
F is another slice of the possible seats removed. Do you see the pattern yet?
It's binary. Each seat has a unique ID that can be calculated as
row * 8 + seat, confirming our suspicion. We'll parse each line of input as if it were a binary encoded integer, replacing
The first stage of this challenge asks us to find the highest seat ID on any of the boarding passes we see, which we can quickly ascertain is
Now that we know the highest taken seat ID, we can get to work reverse engineering where the airline sat us. We can see that, compared to the usual aircraft of this type, the front- and rear-most seats are out of use. The plane is quite packed, so we can also be confident that the airline has situated us between two other passengers.
Our existing list of occupied seats allows us to identify which seats are vacant, using sets. Set theory is a branch of mathematical logic concerned with the study of 'sets': Collections of arbitrary, but unique, objects. We can use the relative complement of two sets, perhaps better known as the difference, to find the values that exist in one set but not the other.
To solve the second stage, then, we can create a set of all possible seats we could occupy. Then we subtract the set of all occupied seats.
Set(stride(from: passes.min()!, to: passes.max()!, by: 1)).subtracting(Set(passes))
We know that the airline has sat us between two other passengers. Therefore, we can limit the potential seats to the range bounded by the lowest and highest occupied seat ID. Subtracting the set of all occupied seats, the single remaining value – and our solution – is
651. Let's get comfortable, shall we?
As usual, I've made the code available in my Github.