Advent of Code 2020: Day 5 reflection
The day 5 puzzle from last year’s Advent of Code talks about airplane seat numbering using “binary space partitioning”.
From the puzzle description:
After absorbing all of that explanation, it turns out that parsing a “seat
specification” is way less complicated than it might appear. Converting to
row and column is just like parsing a binary number: the first character is
just like the most significant bit of a 7-bit binary number (the 64s place, if
you will). As the rows are numbered with 0 in the front and 127 in the back, an
F is like a 0 bit and a
B like a 1.
Similarly, the last three characters are the binary representation of the
column number, with
L like a 0 and
R like a 1.
Let’s take the example
FBFBBFFRLR. The row and column break down like so:
And then the final seat ID is 44 × 8 + 5 = 357.
But multiplying by 8 is the same as shifting the binary digits left by three places. (The 1s place turns into the 8s place, the 2s place into the 16s place, and so on.)
So there’s no need to distinguish between row and column at all! We can just
replace all the
Ls with 0s, and all the
Rs with 1s, and
then parse the whole thing as an 11 bit binary number.
(And in Python, parsing a string
s representation of a binary number is as
So my quick Python code to parse a list of seat descriptions looked something like this:
def parse(lines): return [int(l.replace('F', '0').replace('B', '1') .replace('L', '0').replace('R', '1'), 2) for l in lines]
This worked just fine, but all those
replace() calls feel a little silly.
I thought that there must be a less-verbose way to do this.
And sure enough, there is!
method does just this:
And from the description of
We can use these methods to simplify our
parse() method like so:
t = str.maketrans('FBLR', '0101') def parse(lines): return [int(l.translate(t), 2) for l in lines]
Then part 1 of the puzzle (finding the highest seat ID in the input file) is trivial:
def part1(ids): return max(ids)
But the puzzle isn’t really the point of this post.
It’s more that I hadn’t ever used Python’s
translate() method before, so I
wanted to share in case it’s new to others as well.
Fun tidbit: the Python
translate() method is basically what the Unix
tr command does. We can solve
part 1 of the puzzle (find the highest seat ID out of all the input seat
descriptions) in a one-liner like this:
$ <input05.txt tr FBLR 0101 | sort | tail -n1 | echo "ibase=2; $(cat)" | bc
Because all the seat descriptions are the same length, we can sort them as
text strings and we’ll get the same order as if we sorted as numbers.1 Then
we can use
tail -n1 to take just the last line (the maximum value), and run it
bc (the basic
convert from binary to decimal. (We just need to prepend an
ibase=2 to get
bc to parse its input as binary.)
If we tried to use plain
sortafter converting from binary to decimal, we could run into problems like
100. But, we can use the
-noption to sort the input numerically, like so:↩︎
$ <input05.txt tr FBLR 0101 | echo "ibase=2; $(cat)" | bc | sort -n | tail -n1