Advent of Code 2020: Day 5 reflection
str.translate()
and str.maketrans()
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 7bit 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 F
s and L
s with 0s, and all the B
s and R
s 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
simple as int(s, 2)
.)
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 lessverbose way to do this.
And sure enough, there is!
translate()
and maketrans()
The Python str.translate()
method does just this:
And from the description of str.maketrans()
:
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.
Addendum
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 oneliner 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
through bc
(the basic
calculator) to
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
sort
after converting from binary to decimal, we could run into problems like99
sorting after100
. But, we can use then
option to sort the input numerically, like so:↩︎$ <input05.txt tr FBLR 0101  echo "ibase=2; $(cat)"  bc  sort n  tail n1