DEV Community

Cover image for Binary Boarding
Robert Mion
Robert Mion

Posted on

3 2

Binary Boarding

Advent of Code 2020 Day 5

Try the simulator!

Simulation of both parts of algorithm

Task: Solve for X where...

Part 1:

X = the highest boarding pass ID
Enter fullscreen mode Exit fullscreen mode

Part 2:

X = my boarding pass ID
Enter fullscreen mode Exit fullscreen mode

Example input

FBFBBFFRLR
BFFFBBFRRR
FFFBBBFRRR
BBFFBBFRLL
Enter fullscreen mode Exit fullscreen mode

It represents:

  • A list of encrypted boarding pass IDs

Part 1

  1. Using the title as a hint
  2. Writing a working algorithm
  3. Building the simulator

Using the title as a hint

  • The title is Binary Boarding
  • The instructions further suggest going one of two directions based on the character encountered
  • The solution seems clear

Given this boarding pass

FBFBBFFRLR
Enter fullscreen mode Exit fullscreen mode

Splitting FB from RL

FBFBBFF RLR
Enter fullscreen mode Exit fullscreen mode

Replacing Fs and Rs with 1s, Bs and Ls with 0s

1010011 101
Enter fullscreen mode Exit fullscreen mode

Parsing each one as a decimal

44       5
Enter fullscreen mode Exit fullscreen mode

Generating the ID

44 * 8 + 5 = 357
Enter fullscreen mode Exit fullscreen mode

Writing a working algorithm

Split the input at each new-line character into an array of strings

For each string
  Change the string according to the following instructions:
    Split the string into groups containing exclusively FBs and RLs
    Replace FBs with 1 and RLs with 0
    Parse the modified string as a decimal
    Calculate the sum of:
      The product of the first decimal and 8
      And the second decimal
  Return the sum

Return the highest number in the modified list of decimals
Enter fullscreen mode Exit fullscreen mode

Here's a visualization of my algorithm for Part 1

Visualization of my algorithm for Part 1

Building the simulator

  • Since these are boarding pass IDs, I wanted to simulate the population of a plane's seating chart
  • By the end of running Part 1, there should be one seat left unfilled: that's my seat!

Part 2

  1. Writing a slightly modified, working algorithm
  2. Finishing the simulator

Writing a slightly modified, working algorithm

  • I still need to generate the list of boarding pass IDs
  • But now I need to sort them in ascending order
  • And I need to find the only gap: where the number increments by 2 instead of 1
Split the input at each new-line character into an array of strings

For each string
  Change the string according to the following instructions:
    Split the string into groups containing exclusively FBs and RLs
    Replace FBs with 1 and RLs with 0
    Parse the modified string as a decimal
    Calculate the sum of:
      The product of the first decimal and 8
      And the second decimal
  Return the sum

Sort the list of decimals in ascending order

Filter the list to exclude all but one number:
  Find the number where the number at the very next location is not equal to this number plus one

Since the number found is the seat next to mine
  Return that number plus one
Enter fullscreen mode Exit fullscreen mode

Here's a visualization of my algorithm for Part 2

Visualization of my algorithm for Part 2

Finishing the simulator

As foreshadowed above, I wanted Part 2 to reveal the seat that in Part 1 was the only gap

Try the simulator!

Simulation of both parts of algorithm

This puzzle felt easy.

That made me feel great about my progress.

Bring on the next one!

Image of Datadog

Master Mobile Monitoring for iOS Apps

Monitor your app’s health with real-time insights into crash-free rates, start times, and more. Optimize performance and prevent user churn by addressing critical issues like app hangs, and ANRs. Learn how to keep your iOS app running smoothly across all devices by downloading this eBook.

Get The eBook

Top comments (0)

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more