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 Fs and Ls with 0s, and all the Bs and 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 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 less-verbose 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 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.¹ 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.)