Advent Of Code 2020 – Day 5 – Binary Boarding

You’ve made it through the passport verification phase. Now, it’s time to board the plane. You board the plane but then you realize that you have dropped your boarding pass. So, how are you going to handle this situation. Well, you are a developer, you know only one thing and that is to write code. That is what you are going to do.

Somehow, you scanned all the nearby boarding passes using your mobile camera (Your Puzzle Input) ; next step is to find your seat through the process of elimination.

This airline uses binary partitioning to seat people. A seat is specified in the form FBFBBFFRLR, where F means “Front”, B means “Back”, L means “Left” and R means “Right”.

Here’s how the seating arrangements works.

Part One – Find Unique Seat Id

Always read the given problem carefully.

I don’t know if you have already seen it or not. The given seat number can be re-written in binary.

For example – this FBFBBFFRLR can be written as 0101100 and RLR can be written as 111. That’s the binary representation of rows and columns.

Now, the problem has become simple. All we have to do is to convert the binary number into their respective decimal form.

We know that the rows and columns are fixed and represented by 7 and 3 digits respectively. Therefore, we know that the maximum value of the rows can go up to about 64 and for columns it is 4. So, with this understanding, let’s write the code to identify the rows and columns.

Identify Rows

We start with 64 as the base value and with every iteration we half the value. And whenever we encounter B we add the value to the row variable.

Let me show you the code and then we will do a dry run.

   1 def find_row(seat = "FBFBBFFRLR"):
   2     a = 64
   3     row = 0
   4     for i in range(0, len(seat) - 3):
   5         if seat[i] == 'B':
   6             row += a
   7
   8         a = a//2
   9
  10     return row

Let’s create a table with all the changing variables,

i	row	a
0	0	32
1	32	16
2	32	8
3	40	4
4	44	2
5	44	1
6	44	0

As you can see at the end we get the correct row value and that is 44.

Great!!! so we have the correct row. Now, we have to find the correct column. And for that we have to do the exact same thing but for the last 3 characters of our seat number. The code will be almost identical.

  13 def find_col(seat = "FBFBBFFRLR"):
  14     b = 4
  15     col = 0
  16     for i in range(len(seat) - 3, len(seat)):
  17         if seat[i] == 'R':
  18             col += b
  19
  20         b = b // 2
  21
  22     return col

This code will give us the column value for the last 3 characters i.e. RLR.

Now, there is a straight formula to find the seat id if we have the row and col. We will write a one liner function for that as well.

  24 def get_seat_id(row, col):
  25     return (row * 8) + col

Cool!!!

With this in place, we are good to go.

But wait, we are yet to find our place in the airplane and that is the Part two of the problem.

Part Two – Find Your Seat

Out of hundreds of Id’s you know that your seat wasn’t at the very front or back, though; the seats with IDs +1 and -1 from yours will be in your list. So, we know its somewhere in between, so if I find two ids which when subtracted from each other gives the output as 2 then that’s my seat.

Let’s quickly code the same for all the ids and find out our seat.

  31 seats = []
  32 f = open("inputs/day5.txt")
  33 for line in f:
  34     line = line.strip()
  35     seat_id = get_seat_id(find_row(line), find_col(line))
  36     seats.append(seat_id)
  37
  38 
  39
  40 my_seat = None
  41 for id in sorted(seats):
  42     if  id+1 not in seats and id + 2 in seats:
  43         my_seat = id + 1
  44
  45 print(my_seat)

The seat id that I got is 548, that is correct.

Awesome. You have found the correct seat id, perhaps you won’t disturb anyone now.

See ya next day.