Categories
Programming What I’m Up To

My solution to Advent of Code 2020’s Day 5 challenge, in Python

Welcome to another installment in my Advent of Code 2020 series, where I present my solutions to this year’s Advent of Code challenges!

In this installment, I share my Python solution to Day 5 of Advent of Code, titled Binary Boarding.

Spoiler alert!

Please be warned: If you want to try solving the challenge on your own and without any help, stop reading now! The remainder of this post will be all about my solution to both parts of the Day 5 challenge.

The Day 5 challenge, part one

The challenge

Here’s the text from part one of the challenge:

You board your plane only to discover a new problem: you dropped your boarding pass! You aren’t sure which seat is yours, and all of the flight attendants are busy with the flood of people that suddenly made it through passport control.

You write a quick program to use your phone’s camera to scan all of the nearby boarding passes (your puzzle input); perhaps you can find your seat through process of elimination.

Instead of zones or groups, this airline uses binary space partitioning to seat people. A seat might be specified like FBFBBFFRLR, where F means “front”, B means “back”, L means “left”, and R means “right”.

The first 7 characters will either be F or B; these specify exactly one of the 128 rows on the plane (numbered 0 through 127). Each letter tells you which half of a region the given seat is in. Start with the whole list of rows; the first letter indicates whether the seat is in the front (0 through 63) or the back (64 through 127). The next letter indicates which half of that region the seat is in, and so on until you’re left with exactly one row.

For example, consider just the first seven characters of FBFBBFFRLR:

  • Start by considering the whole range, rows 0 through 127.
  • F means to take the lower half, keeping rows 0 through 63.
  • B means to take the upper half, keeping rows 32 through 63.
  • F means to take the lower half, keeping rows 32 through 47.
  • B means to take the upper half, keeping rows 40 through 47.
  • B keeps rows 44 through 47.
  • F keeps rows 44 through 45.
  • The final F keeps the lower of the two, row 44.

The last three characters will be either L or R; these specify exactly one of the 8 columns of seats on the plane (numbered 0 through 7). The same process as above proceeds again, this time with only three steps. L means to keep the lower half, while R means to keep the upper half.

For example, consider just the last 3 characters of FBFBBFFRLR:

  • Start by considering the whole range, columns 0 through 7.
  • R means to take the upper half, keeping columns 4 through 7.
  • L means to take the lower half, keeping columns 4 through 5.
  • The final R keeps the upper of the two, column 5.

So, decoding FBFBBFFRLR reveals that it is the seat at row 44, column 5.

Every seat also has a unique seat ID: multiply the row by 8, then add the column. In this example, the seat has ID 44 * 8 + 5 = 357.

Here are some other boarding passes:

  • BFFFBBFRRR: row 70, column 7, seat ID 567.
  • FFFBBBFRRR: row 14, column 7, seat ID 119.
  • BBFFBBFRLL: row 102, column 4, seat ID 820.

As a sanity check, look through your list of boarding passes. What is the highest seat ID on a boarding pass?

Importing the data

Every Advent of Code participant gets their own set of data. I copied my data and went through my usual process of bringing it into Python. This involves pasting it into a triple-quoted string and assigning it to the variable raw_input, and then splitting it using the newline character as a delimiter, producing a list named split_input:

raw_input = """BBFFFFBRLL
BFBBBBFLLL
FBBBFBFLLR
BFBBBFBLRR
FBBFFBFLRR
FFBFFBFRRR
FBFBBBBLLL
BFFBFFFRLR
BFFBFFFRLL
BFBBFBFRRL
FBFFFFBLRR
BBFFBFBLLR
BBFBFFBRLR
BFBFBFFRLR
FBFFBFBRRL
BFFFFBFRLR
FFBBBBBRLR
BFFFBFBLLR
FBBBBBBRLL
FBBFBFBRRL
FBFBFBFLRL
FFBFBBFRLL
BFBFFBFRRL
FBBBBFBLLR
FFBBFBFLRR
BFBFBBFRRL
FBFFFBBLLR
FBBFFBFRRR
FFFBFBBLRL
FBBBBFBRRL
BFBFBBFLRL
BBFFBFBLRL
BBFFFFFLRL
BBFBBFFRLR
FFBFBBBRRL
FBFFFFFRLR
FFFBBFFLRR
BFFFBFFLRL
BFBFFFBRLR
BBFBFBFLRR
FBBBBFFRRR
FBFFFBFRLL
FBFFFFFLRL
BFFFFFBLRR
FFFBBBFLRL
FBFBBBFRLL
FFBFBBBLRR
FBFFFFFRLL
FFBFFFFLRR
BBFBFBBRRL
FFFBFBBLRR
BFFBFBBRRR
FFBBFFBLRL
BFBBBFFRRL
FFBBFFFRLL
FBFFBFBLRR
FBBFBBBRLL
FBBFFFBRLR
FBFFBFFLRL
FFFBFBBRRR
BBFFFBBRLL
BFBFBBBRRR
BBFFBFFLRR
FFBFFBBLLL
FFFBBBFLLL
FBBFBBBRRL
BBFBFBFLLR
BFBFFFFRLL
BFFBBFFRLR
BFBBFFFRLR
BBFFFBBRRL
BFBFFBFLRR
FBBFFFBRRR
FFBFFFBLLR
BFFFFBBRLR
BBFFBBFRRR
BFBBBFBLLL
FFBBBFBLRR
FFBFFBFLRL
FFFBBBBRLR
BFBFFFBRRR
BBFFBFFRRL
BFFBBFFLRR
FFFBFBBLLL
FBBBBBFLLL
BFBFFBFLLR
BBFBFBBRRR
FBFBBFBRLR
FBBFFBFRLL
BFBBFFBLRL
BFBBFFFRRL
FBFFBBFRLR
FBBFBBBLRL
FBFFBFFLLR
FFFBBFBRLR
FBBFFBBLLR
FFFBBBFRRL
BBFBBFFRRL
FFBBBFFRLR
BFFFFBBRRR
FBBBBBFRLR
BBFBFFBRRR
BFFBFBFRLL
BFBFFFFLRL
FBBBFFBRRR
FBBFBBFLLL
BFFFFBFLLR
BBFFFFBLLR
FFBFBFFLRR
FBBBFBBRRL
BFFFBBFLRL
FBFFFBFLLL
BBFFFFFRLR
FFFBBBFRLL
FFBBBFBRLL
BFFBFFBRLR
BBFFBBFLRR
FBBBBFBLRR
BFFBFFBLRL
FFBFFFFRLR
FBBBBBBRRL
FBBFFFBLLR
FBFFFFFLLR
FBBFBBFRLL
BFFBFFFRRL
FBBFFBFLLR
FFBBFFBLLR
FBBBFBBRLR
BFFBBBFLLR
FFBBFBFRRR
FFFBFBBRLL
FBFFFBBRRL
BFFFBBBLRL
BBFFBBBLLL
FBFBBFBLRL
BBFFFBBLRL
FBBBBFBLRL
BBFFBBFLLL
FBFBBFFRRR
BFBBFBFLRL
FBFFBBFLRL
BFBFBFBLRL
BFBBFBBLRL
FFFBBFBLLR
FFFBFBFRRL
FBBBFBFRRR
FBBBFFBLLR
BFFFBBFLRR
BFFFBFFLRR
BBFFFBFRRR
FFFBBFBLRR
BFFFFFFRRL
FBBFFFFLLR
BBFBFFFRRR
FBBBFFFRRR
BFBFFFFRLR
BFBBFFFRLL
FFBBBFBLLR
BFFBBBFLLL
FBFFFBFRRL
FFBFFFFRRR
FFBBBBFRRL
FFBFFFBLRR
FBBBBFBRRR
BBFFBFFLLL
FBBBBFFLLR
FBFFBBFLLL
BFBBBFBRLL
FBBFFFFRLL
FBBFBFBRLR
BFFBBFBLRR
FFBFBFBRLL
BBFFBBFRLL
FFBFBBFLLL
BFFBBFBLLL
FBFFFFFRRL
FBFFBFBLRL
FFBFFBFRLL
BFBBBBBRRR
FBFFBFBLLR
FFBFFFBLRL
FFBFFBBLRR
BFBFFBBRRL
FFBFBFBRLR
FFBFBFFLRL
BBFBBFFLRL
FFBFFBFLLR
FFFBBBBLRR
BFFBFBBRRL
FFBBFBBRLR
BFFBFBFLLR
FFBBFBBRRR
BBFFBBBRRR
BFFFBFFLLR
BFBBBFFRRR
BFBBFBBLLL
FFBBFBBLLL
FBFBFBBLLR
FFBBBFFLRR
FFBFFBFLLL
BFFBFFBLLL
FBFBBBFLLL
BBFBFBBRLL
FBFFBFBRRR
BBFBFFFRLL
BBFBFFFRRL
BFFFFBBLRL
BFBFFFFRRL
FFBFFBFRRL
FBBFBBFLRR
BFFFBBBRRL
FFBFFFBLLL
FFBBBBBLLR
BFBFBFBLRR
FFBBFFFLRL
FBBBBBBRRR
FBFBFFBLLL
FBFFBBBRRL
BFFBFFFRRR
BFBBFFBRRR
BBFBBFFLRR
BBFBFFBRRL
BBFFBBBLLR
FBFFFFBRLR
BBFFFFFRRR
BFBFFBFRLL
FBBBFBBRLL
FFBBFBFRLR
BFBFBFBRLR
FFBBBFFLLR
FBFFFFFLRR
FBFFBFFRLR
BFBBBBFRLR
FBFBBFBLRR
FBBBBFBRLR
BFBFFBBRLL
FFBBFBFLLL
FFBFBFBLLL
FFBFBFBRRR
BFBFBFBLLR
BFBBBBBRRL
FBBBBBFRRR
BBFBFFBLRL
FBBBBFFRLR
BBFFFFFLLR
FBBFFBBLRR
FBFFFFBRRR
BFFFBBFRLL
FBFBFFBLRR
BFBBFBBRRL
BFFFFBFRRL
FFBFFFBRRR
FFBFBBBRLL
BBFFFFFRRL
BFBBFBBLRR
FBBFBFFRRR
BFFBFFBLRR
BFFFBBFLLL
BFBFFFBRLL
BBFBBFBLLL
BFBFBFFRLL
FFFBBBFLLR
FBBBFFFRLL
BFBFFBFRRR
FFBBFFFRRR
BBFFFBBRRR
BFFFFBFLRR
BFFFFFFRRR
BBFFBFBLRR
FBBBBBBRLR
BBFFBFFLLR
BFFBBBBLLR
FBBBBFFLRR
FFBBBFFRRL
FBFBBFFLLL
BBFFBBBRLL
FBFFBFBLLL
BFFBFBBRLR
FBBFFFBLRL
FFBFBFFLLL
FBBBFBFLRL
FFFBBFFLRL
FBBBBFFRRL
BFBFBBBRRL
BFFFBBBLLR
FBFBFBBLRL
BFBBFFBLRR
BBFBFFFLRR
FBFFBBBLRR
FFBFFBBRLL
BFBFFFFLRR
BBFBFFBRLL
FBBBFBFRLL
BFBBBFFLRL
BFFBBBBRRL
BFFBBBBLRR
FFBBFBFRLL
FBFBFFFLLL
BFFFFFFLRL
BFBBBFBRRL
FFFBBBBRRL
FBFFFFBLRL
FBBBBBFRLL
FFBBFFFLRR
FBBFBBFLLR
BFBFBBFRLL
BFBFFFBLLR
BFBFBBBLRL
FFBFFFBRLR
BFFBBBFRRL
BFBBBBBLRR
FBFFFBBRLL
FBFBFBBRRR
FFFBFBBRLR
BFBFBBFLRR
FBFBFBBLLL
FFBBFFBRLL
FBBFBFBRRR
BFFFFFBRRL
FBBBFBBLLL
BBFBFFBLLL
FFBFBFBLLR
FFBBBFBRRL
FBFBFBFLLL
BFBFBBFRLR
FBBFBFFRLR
FFBFFBBRRR
BFFBFFBLLR
FBFFFBFLRL
FBFFFFFRRR
FFBBFBBRLL
FBFFBFFRLL
BBFFFBFLRR
BFBBBFFRLL
FBFBBBBLRL
FFFBBBBLLL
BBFFFFBRRR
FBBBBBBLLL
FFBFBFBLRL
BFFBFFBRRL
FFBBFBBLRR
BFBFFBFLLL
FBBBBFFRLL
FFFBBFBRLL
BFFFBFBLLL
BBFBBFBRLL
FFBFFBBLLR
BBFFFFBLRL
BBFBBBFLLR
BFBBFFBRLR
BFFFFBFLLL
BBFFBBFLLR
BBFBFFFLLL
FBBBFFFLLL
BFBBFBBRRR
FFBBBBFRRR
BBFBBFBRLR
BFBBFFFLLL
FFBFFFFLLR
FBFBFFBLLR
FBBBFFFLLR
BFBBBBFLRR
FBBFBFFLRR
FBFBBFBRRL
BFFBFFFLLL
FBBFBBFRRR
FBFFBBBRLL
FBFBBBBRRL
FFFBBBFRRR
FBFBFFBRRL
FFBBFBFLLR
BFBFBBBLLL
FFBFFBFLRR
BFBFBBFRRR
FBBBBBBLLR
BFFBFBFRRR
FBFFFBFRRR
BBFFFBFLLL
FBBFFBBRRR
BFBFBFBLLL
BBFFBBBLRR
FFBFFFFRRL
FFBFBBFLLR
FFFBBBFRLR
FFFBBFBLLL
FBFBBFFLLR
FBFBFBFRRR
BFBBFFFRRR
BFBFFBBRRR
FBFBBFFRLR
FFBFBBFRLR
BFFBBFFRRR
BFBFBBFLLL
FFFBBFBRRR
BFFBBFFRLL
FFBFFFFLLL
FFBBBFFRLL
BBFBBFBRRL
BBFBFFBLRR
FFBFFBBRRL
FBBFBBFRRL
BBFFFFBLLL
BFBBFFBRLL
FFBFBFFRLL
BFBBFFFLLR
FBBFFBBRLR
BFBFFBFLRL
BFBBFBBRLL
FFBBBFFRRR
FBFBBFFLRL
BFBBFBFRLR
FFBBFFBRRL
FBFFBBFLLR
FBFBBBFLLR
BFFFBBFRRL
FFFBBBBRRR
BFFFBBBRRR
FBBFBFFRRL
BBFFFFBRRL
BBFFFBBLLR
BFBBFBFRRR
BFFFFBBRRL
FBBFBBFLRL
FBBFBBBRLR
FBFBFFFLRL
BFFBFBFRRL
FBFBBBFLRL
BFBBBBBLRL
FFBFFFBRLL
BFFBBFBLRL
FBFBFBFRLR
BFFBBFFLLL
BFBBBBBLLL
FFBFBBFLRR
BBFBFBFRRR
FFFBBFFRRR
BFFFBFFRRL
BBFBFFFRLR
BBFBFFFLLR
BFFFFFFLRR
FBBFBBFRLR
FFBBBFFLRL
FBFBFFFRLR
FFBFBFFLLR
BFBFFBBLRR
BFFBBBFRLL
FBBFFBBLRL
BFBBFFBLLR
FBFFBFFRRR
BFFBBBFRLR
BFBFBBBLLR
BFFFFBBLLR
BFFBFBFLLL
BFBBFFFLRR
BFFFFFFRLR
BBFFBFFLRL
BFBFBFFLLR
BBFFFFFLRR
FFBFBBFLRL
FBFBFFBRRR
FFBBBBFRLR
BBFBBBFLLL
BFFFFBBRLL
FBFBBBFRRR
BFFBFBFRLR
FFFBBFFLLR
FBBFBFFLLL
FFFBFBBRRL
BFBBBBFLRL
FFBFFBFRLR
FBFFBFBRLL
FBBBFBFLRR
BBFFBBFRLR
FBBBBBFLRR
FBFFFFBRLL
BFFBFFFLRL
BFBFFFFLLL
BBFFBFBRLR
BFBBBFBLLR
FBBFFBBRLL
FBFBFBFRLL
BBFBFBBLRL
BFFBFBBLRL
FFBBBFBLRL
FFBBFBBLLR
BFFBFBFLRR
FBBBFBFRRL
BFFBBBFLRL
BFBBFBBLLR
BFBFFFBLRR
FBFFBBBLRL
FBFFBFFLLL
BBFFBFFRRR
BFFBFBBRLL
BFFFBFFRRR
BFFBBBBLRL
FBBFFBFRLR
FBFFBFFRRL
FBFFFBBRRR
BBFFFFBLRR
FBBBFFFLRL
FFBBBBFLRL
BFFFBFFLLL
BFBBBFFRLR
FFBFBBFRRL
FBFBBBFLRR
FFFBBBFLRR
BFFFBFBRLR
FBBBFBBLRR
FFBBBFFLLL
FFFBFBFRLR
FBBFFFBRLL
FBBFBBBRRR
BFBFFFFRRR
BFBBBFBLRL
BBFFFBBLRR
BFBFFBBLLR
BFBBFBFLLR
BBFFBBBRRL
FBBFFFFLLL
BBFBFFBLLR
BFBBBBBLLR
FFBFFBBRLR
FFBBBFBRLR
FBFBBBBLRR
FBBFBFBLRR
BBFFBBFRRL
BBFFBFFRLL
FBBBFFBLRR
BFFFBFBRRR
BFFBFFFLRR
FFBBFBBRRL
FBFBBBBRRR
BBFBBFFLLL
FBFFBBBLLL
FBBFFFBLRR
BFBBFFBLLL
FBFFFFBLLL
BFBFBBBLRR
BFFFFFBLLR
BFFBBFBLLR
FBFFBFFLRR
FBBFBBBLLR
FFBBBBBRLL
BFFFBBFLLR
FFBFBBBLRL
FBFBBBFRRL
BFFFFBFLRL
FBBFFBFRRL
FFFBBFBRRL
FFBBBBBRRL
BBFFFBFLRL
FBBFFFFLRR
BFBBBBFRLL
BFFBFFBRRR
FFBBFFFLLL
BFFBBBBRLR
BFBBFFFLRL
BFBFFBBLRL
BBFFFBFRLR
FBFBFBFLLR
BBFFFBBRLR
FBBBFFBLLL
FBBBFFFRRL
BFFFFFFRLL
FFBFBFFRRR
BFFFBFBRLL
FBBBFFFRLR
BFBBBFFLLL
FBBFBFBLLL
FFBBFFFLLR
BFFFBBFRLR
BBFFFBFRLL
FBBBBBBLRL
BFBFBFBRLL
FBBBBBFRRL
BBFBFFFLRL
BFBBBBFRRR
BFBFFFBLRL
FFBFBFBRRL
BFBFBFBRRR
FFBFFFFRLL
BBFBBFFLLR
FFBFBBBLLR
BBFBBBFLRL
FBFBBBBRLL
FFBBBBFLRR
FFBFFBBLRL
BBFFBBBRLR
BFBBFBFLLL
FBFBFFBLRL
BFFFFFBLLL
FBFFBFBRLR
FBBBBFBLLL
FBBFFBFLRL
BFFFBBBLLL
FBBFBFFLRL
FFFBBFFLLL
BFBFBFFRRL
BFFFFFBRLL
BFFBFBFLRL
BFFBBFBRRL
BFBBFFBRRL
FFFBBBBLRL
FFBFBBBRRR
FBFBBFBRRR
FFBBBBFLLL
BBFFBFBRLL
FBFFBBFRLL
FBFBFFFLLR
BFFFFBFRRR
FFBBBFBLLL
FBBBFFBLRL
BFFFBBBLRR
FFFBFBFRRR
FBFFFBBRLR
FBFBFFFLRR
FBBBFBBLRL
FBBBFBBRRR
BBFBFBBLRR
BFFBBBFLRR
BFFFFFFLLR
BBFBFBFRLL
BFFBFBBLLL
FFBBBBFLLR
BFFFFBBLRR
FBFBFFFRLL
BFBFFFBRRL
BBFBFBBLLR
FFFBFBBLLR
FBFFBBBRRR
FBBFBFFLLR
FBFBFBBRLL
BFFBBBBRRR
BFFBFFFLLR
BFBFBFBRRL
BFBBBBFLLR
FBBFBFBLLR
BFFFFFBRLR
FBFFFBBLLL
BBFFFFFLLL
FFBBBBBLRR
FFBBFBBLRL
BBFFFFFRLL
FBFBBFFRRL
FFBFBBBLLL
BFFFBBBRLR
FBBBFBFRLR
FBBFFFFLRL
FFBBFFBRRR
FBFBFBFLRR
BFBFBBBRLL
BFBFBFFLLL
FBFFBBBLLR
BFFFBFBLRL
FBBFFFFRRR
FBBBBBFLLR
BFFFFBBLLL
FBBFBFBLRL
BFFFBBFRRR
BBFFBFBRRR
BBFFBFBRRL
FFFBBBBRLL
BBFFBBBLRL
BFBBFBBRLR
BBFBBFBLLR
BFBBFBFLRR
FBFFFFBRRL
BFFBFBBLRR
BBFFBFBLLL
FBBBFBBLLR
FBFBBFBLLL
BBFBFBFRLR
BFFBBBBLLL
BFFBFFBRLL
BBFBBFBLRR
FBFFBBFLRR
BBFFBFFRLR
BFFFBFFRLR
FBFBBFFRLL
BFFBBBFRRR
FBBBFBFLLL
BBFBBBFLRR
FBBFFBFLLL
BBFBBFBLRL
FBFFFBBLRL
FBFBBFBRLL
BFBBBBFRRL
BFFFBFFRLL
BFBFBBBRLR
FFBFFFFLRL
FFBFFFBRRL
FBFFBBFRRR
BBFFFFBRLR
BFFFBFBLRR
BBFFBBFLRL
FFBBFFFRRL
FBFBFBBRLR
FBBFBFFRLL
FBBBFFBRLL
FBBFBBBLLL
FBBFFBBRRL
BFBFBBFLLR
FFBBFFBLRR
FFBBBBBLLL
BBFFFBFLLR
FBFBBBBRLR
BFBFBFFLRL
FFBBBBBRRR
BFBFFBFRLR
FBBBBFBRLL
BFBBBBBRLL
BFBBBBBRLR
FBBBBFFLLL
FBBFFFBLLL
BBFBFBFLLL
BFFFFFBLRL
FBBFBFBRLL
BBFBFBBRLR
BFFBFBBLLR
FFBBFBFLRL
FBFBBBFRLR
FBBBFFBRLR
FBFFFBFLRR
BFBFBFFLRR
BFFFFFBRRR
BFFBBFBRLL
FBFBFBFRRL
BBFBBFFRRR
FBBFBBBLRR
FBFFBBBRLR
BBFBFBBLLL
FFBFBBFRRR
FBFBBFBLLR
BFBFBFFRRR
BBFBBFBRRR
FFBFBBBRLR
FBFBFBBRRL
BFBFFFBLLL
FBFBFFBRLL
FBFFFBFRLR
FBFFFBBLRR
FBBFFFFRLR
BFBBFBFRLL
FBFBFBBLRR
FFBBBFBRRR
FBBFFFFRRL
FBFBBFFLRR
FBBBFFBRRL
FBFFFBFLLR
FFBFBFFRLR
FBBFFBBLLL
FFFBBFFRLR
BFFFFFFLLL
FFFBBBBLLR
FFBFBFFRRL
BBFBBFFRLL
FFFBBFFRLL
BBFFFBFRRL
FFBBFFBLLL
FBFFBBFRRL
BFBBBFBRLR
BFBFFBBRLR
FBFBFFFRRR
BFBBBFFLLR
FBFBFFFRRL
BFFBBFFLLR
FBFBBBBLLR
FFBBFFBRLR
FBFFFFFLLL
BBFBFBFRRL
FBBBBFFLRL
BFBBBFBRRR
BFFBBFFLRL
BFFBBFFRRL
BBFBFBFLRL
FBBFFFBRRL
BFFFBFBRRL
FBFFFFBLLR
FFBBFBFRRL
BFFBBBBRLL
BFBFFFFLLR
FFBBFFFRLR
BFBFFBBLLL
BFFBBFBRRR
BFFFBBBRLL
FFFBBFBLRL
FFBFBFBLRR
FFFBBFFRRL
FFBBBBBLRL
BFBBBFFLRR
FBBBBBFLRL
FBBBFFFLRR
BFFBBFBRLR
BBFFFBBLLL
FBBBBBBLRR
FBFBFFBRLR
FFBBBBFRLL"""

split_input = raw_input.split("\n")

Strategy

They dropped a hint in the title of the challenge: Binary Boarding.

They dropped a hint by saying the airlines seats people using binary space partitioning instead of zones.

They dropped a hint when they said that the row numbers range from 0 to 127, and that a seven-character sequence determined your row. Only two characters could be used in that sequence, F and B.

(Additional hint for those of you who didn’t study binary numbers: The numbers 0 through 127 can be represented using seven bits.)

They dropped a hint when they said that the seat numbers (which they called column numbers) range from 0 to 7, and that a three-character sequence determined your seat. Only two characters could be used in that sequence, L and R.

(Additional hint for those of you who didn’t study binary numbers: The numbers 0 through 7 can be represented using three bits.)

The “FB” and “LR” sequences are just binary numbers in disguise.

Solving this challenge involves:

  • Converting the “FB” and “LR” strings into binary strings.
  • Converting those binary strings into decimal numbers.
  • Doing the math on those numbers to get the seat IDs.

Converting the “FB” and “LR” strings into binary strings and converting those binary strings into decimal numbers

For each “FB” string, I wanted to convert the Fs to 0s and Bs to 1s. In order to do this, I used Python’s string.maketrans() method to build a character translation table and its string.translate() method to make the translation using that table.

The result was this function:

def convert_FB_to_01(string):
    translation_table = string.maketrans("FB", "01")
    return string.translate(translation_table)

The first line in the function uses string.maketrans() to define a translation table. string.maketrans() takes two arguments:

  1. The characters to be translated.
  2. The corresponding resulting characters.

In this case, I only want F to be translated into 0 and B to be translated into 1. All other characters translated using this table will remain unchanged.

The second line does the actual translating, using the translation table as its guide.

With the function defined, I could then use it to create a list of all the rows, expressed as binary strings:

binary_rows = [convert_FB_to_01(line[:7]) for line in split_input]

This line of code creates a new list, binary_rows, by taking the first seven characters of each line of input data — the “FB” string — and converting it to binary.

Here’s a sample of the result:

['1100001', '1011110', '0111010', '1011101', '0110010', 
'0010010', '0101111', '1001000', '1001000', '1011010', ...]

The next step was to convert binary_rows into a list of its numeric equivalents:

decimal_rows = [int(binary_row, 2) for binary_row in binary_rows]

This line of code, creates a new list, decimal_rows, by converting each binary string into its decimal numeric equivalent. It does this by using the int() function to convert strings to integers, and the extra argument specifies that value represented in the string is in base 2, a.k.a. binary.

Here’s a sample of the result:

[97, 94, 58, 93, 50, 
18, 47, 72, 72, 90, ...

It was time to do the same thing with the “LR” strings. This was pretty much the same operation as with the “FB” strings.

First, an LR-to-01 converter:

def convert_LR_to_01(string):
    translation_table = string.maketrans("LR", "01")
    return string.translate(translation_table)

Then, a list comprehension to use that converter:

binary_columns = [convert_LR_to_01(line[-3:]) for line in split_input]

This line of code creates a new list, binary_columns, by taking the last three characters of each line of input data — the “LR” string — and converting it to binary.

Finally, convert these numbers into decimal:

decimal_columns = [int(binary_column, 2) for binary_column in binary_columns]

I now had two lists that I could use to do the math:

  • decimal_rows: The “FB” sequences, converted into decimal numbers.
  • decimal_columns: The “LR” sequences, converted into decimal numbers.

Doing the math to get the seat IDs

As stated in the problem definition, the ID for any given seat is (its row number * 8) + (its seat number). I needed to build a list of seat IDs using decimal_rows and decimal_columns.

Here’s the code I used to do it:

decimal_rows_and_columns = zip(decimal_rows, decimal_columns)
seat_ids = [item[0] * 8 + item[1] for item in decimal_rows_and_columns]

The first line uses zip() to take two lists to make a single list filled with tuples. Each tuple has an item from the first list and a corresponding item from the second list. Here’s an example of zip() in action:

>>> list(zip(['a', 'b', 'c'], [1, 2, 3]))
[('a', 1), ('b', 2), ('c', 3)]

The second line uses the newly-created decimal_rows_and_columns as a basis for creating a new list of seat IDs.

Once the seat_ids list was created, it was a matter of using the max() function to get the highest ID value, which was the solution for part one. In my case, the value was 883.

The Day 5 challenge, part two

The challenge

Here’s the text of part two:

Ding! The “fasten seat belt” signs have turned on. Time to find your seat.

It’s a completely full flight, so your seat should be the only missing boarding pass in your list. However, there’s a catch: some of the seats at the very front and back of the plane don’t exist on this aircraft, so they’ll be missing from your list as well.

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.

What is the ID of your seat?

Strategy

It’s a full flight, so my seat should be the only one missing from the list. I could find this seat by doing the following:

  • Sorting the seats in ascending order.
  • Iterating through the seats, while keeping an eye out for a “gap”. That gap is my seat.

Solution

Here’s the code I used to solve part two:

sorted_seat_ids = sorted(seat_ids)

last_seat_ids_index = len(sorted_seat_ids) - 1
current_index = 0
my_seat_id = None

while current_index < last_seat_ids_index - 1:
    if sorted_seat_ids[current_index + 1] - sorted_seat_ids[current_index] == 2:
        my_seat_id = sorted_seat_ids[current_index] + 1
        break
        
    current_index += 1
    
if my_seat_id:
    print(f"My seat is {my_seat_id}.")
else:
    print("Better check that algorithm!")

It creates a list of sorted seat IDs, which it then loops through. While looping through it, it checks to see if the ID of the seat immediately after the current one is 2 higher than the current ID. If it is, we’ve found the gap, and the ID of my seat is the ID of the current seat plus one.

In my case, the seat ID was 532. I entered that value and solved part two.

One reply on “My solution to Advent of Code 2020’s Day 5 challenge, in Python”

seats = list(seat_ids)
for seat in seats :
if (seat+2 in seats) and not(seat+1 in seats):
print(seat+1)

Leave a Reply

Your email address will not be published. Required fields are marked *