Skip to main content

C'est la Z

A teacher looks at Advent of Code 2020 - Day 5

Day five's problem is a nice one for an early CS class. It can be very much brute forced but it also touches on some nice concepts and can be solved pretty elegantly. I've embedded a walk through in Clojure at the end but a Python solution would be pretty similar.

Read the problem over if you haven't. At it's core you are taking a boarding pass representing a coded airplane seat number and you're converting it to a known seat (row and column). The encoding scheme uses binary space partitioning. The question statement goes over the details.

One of the first things to notice is that you should separate the pass into two parts - the row, which consists of the first seven characters each one being an F or a B and the last three which are the columns and they are marked with either a R or an L.

So, the sample pass FBFBBFFRLR separates into FBFBBFF for the row and RLR for the clumn.

There are 128 rows numbered 0 through 127 so you start with 127 (the back of the plane) and then depending on if the next character is an F or a B you either subtract out half the range size or you don't. If the character is an B you don't since you're at the back of the section and the back rows are higher. If it's a F you do since you're at the front and front rows have lower numbers.

So, the first F says you're at the front so you subtract half the range and now you're looking at 0-63. The next character is a B so you don't subtract anything but you'll be next looking at 32 through 63 etc. The question has a full walk through.

Looking at the row string, you have FBFBBFF. If we substitute the amount we subtract for the letters we get 64 0 16 0 0 2 1 or the place values of a binary number in reverse.

In my solution, I reversed the string and then converted each F or B into a number. A B became a 0 and an F became 2^i where i is the location (index) in the string. For the sample string, once reversed to FFBBFBF it gives 1 2 0 0 16 0 64. If we sum those up and subtract from 127 we get our row number.

We basically can do the same thing for the column but there you subtract from 7.

Part 1 of the question asks you to map the row and column to a final number by calcualing row*8+col and then find the highest seat number from a give list of boarding passes.

Part 2 requires you look through all the boarding passes to determine your actual seat - the one seat missing from the data set.

Lots of good stuff for a class in this question.

You've got the basic data parsing as usual but I love that this can be brute forced but by noticing the base 2 nature of the data you can write up a number of different elegant solutions.

Here's a complete solution coded up in Clojure. You can also check all my Advent of Code solutions up on GitHub

comments powered by Disqus