Sat 05 December 2020
Day 5 of Advent of Code 2020 is a fun reference to the Binary Space Parititioning algorithm.
Here we are dealing with a particular case of partitioning, that can be summarized as "divide numbers by 2". The problem models a plane with 128 rows, and asks us to code up an heuristic to find our seat, given a list of seats represented by 9 characters long identifiers. The character at position i will tell use whether our seat is in the front or back portion of rows; the alogirthm discards rows recusrively until only our seat is left.
Coding up the logic verbatim would be cumbersome, with a few interval bound checks. The solution is much simpler once we recognize that an identifier is simply the binary representation of the (decimal) seat number.
In the reminder of this article we'll use binary arithmetics, and a bit of Python, to show that this is the case.
Let's look at the first 7 characters of the boarding pass. We know that [...] these specify exactly one of the 128 rows on the plane (numbered 0 through 127) [...].
The number of rows, 127, is represented in binary as 1111111.
int('1111111', base=2)
127
A right bit shift is equivalent to diving the number by 2:
int('1111111', base=2)
127
int('0111111', base=2)
63
int('0011111', base=2)
31
int('001111', base=2)
15
int('000111', base=2)
7
int('000011', base=2)
3
int('000001', base=2)
1
Now back to our problem. We are told that: [...] Each letter tells you which half of a region the given seat is in. Start with the whole list of rows; the first letter indicates whether the seat is in the front (0 through 63) or the back (64 through 127). The next letter indicates which half of that region the seat is in, and so on until you're left with exactly one row. [...]
This is equivalent to setting the leftmost bit to
0 (front: 0 through 64) or 1 (back: 64 to 127). In binary,
the front seats are rows in the range:
int('0000000', base=2)
0
to
int('0111111', base=2)
63
The back seats are rows in the range:
int('1000000', base=2)
64
to
int('1111111', base=2)
127
The problem statement continues with: [...] The next letter indicates which half of that region the seat is in, and so on until you're left with exactly one row [...].
It follows by the arithmetic we've just shown that selecting
the lower half (F) or upper half (B) of a region at
position i of the boarding pass, is
equivalent to setting the i-th bit of the binary row number to 0 or 1 respectively.
The same logic applies to the last 3 characters of the 9 character
boarding pass string. R sets the bit to 1, L to 0.
Below is a simple Python function to convert a boarding pass identifier to its decimal representation.
def to_binary(string: str):
string = (
string.replace("B", "1").replace("F", "0").replace("R", "1").replace("L", "0")
)
return int(string, base=2)
To convince ourselves this works, let's try it out on the problem base cases.
to_binary('FBFBBFFRLR')
357
to_binary('BFFFBBFRRR')
567
to_binary('FFFBBBFRRR')
119
to_binary('BBFFBBFRLL')
820
Once we obtain the seat numebrs in decimal, Part 1 and 2 of the problem
can be solved with a couple of lines of code.