Advent of Code 2020: "Binary Boarding" - Day 5

Pretty amazing the tasks they ask you to do “on the fly”: Yesterday we fixed the passport scanner, today you have to write a piece of code which scans all the boarding passes in your environment (no one said they all carry them in the hand, and show it to you), and while waiting in the gangway you also have to identify your designated seat. Because, you know, you are such a good hacker you lost your boarding pass on the way from the gate to the plane ;-)

Task 1: Scan all the boarding passes with your phone camera, extract the code, and apply binary pattern matching to identify which seats exist. The airline has a pretty complex scheme going on, which depends on binary space partitioning. Find the highest seat number on the plane.

Task 2: Use the scanned data and find your seat. Seat belts sign is already on and you are still hacking in the gangway, hurry up! The only information you have: your seat exists, it’s not the first and last one, and the seats next to yours (-1, +1) exist.

Preparation

Load the data into a table. I don’t need an identifier today:

1
2
3
4
5
DROP TABLE IF EXISTS day5;

CREATE TABLE day5 (
    value   TEXT
);

Actual data:

1
2
3
4
5
6
7
8
COPY day5 (value) FROM STDIN;
FBFBFFBLLR
FBBBFFBLLL
BFBFFFFRRR
BFBBBFBRLL
FBFBBFBLLL
...
\.

There’s no further cleaning or preparation required today, the calculation of the seat position is already part of the task.

Task 1

It’s pretty much: “extract the position” and “apply binary position based on the partition”. Couple of CASE WHEN solve this problem straightforward, together with a SUBSTRING().

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    SELECT CASE WHEN SUBSTRING(value FROM 1 FOR 1) = 'F' THEN 0 ELSE 512 END +
           CASE WHEN SUBSTRING(value FROM 2 FOR 1) = 'F' THEN 0 ELSE 256 END +
           CASE WHEN SUBSTRING(value FROM 3 FOR 1) = 'F' THEN 0 ELSE 128 END +
           CASE WHEN SUBSTRING(value FROM 4 FOR 1) = 'F' THEN 0 ELSE 64 END +
           CASE WHEN SUBSTRING(value FROM 5 FOR 1) = 'F' THEN 0 ELSE 32 END +
           CASE WHEN SUBSTRING(value FROM 6 FOR 1) = 'F' THEN 0 ELSE 16 END +
           CASE WHEN SUBSTRING(value FROM 7 FOR 1) = 'F' THEN 0 ELSE 8 END +
           CASE WHEN SUBSTRING(value FROM 8 FOR 1) = 'L' THEN 0 ELSE 4 END +
           CASE WHEN SUBSTRING(value FROM 9 FOR 1) = 'L' THEN 0 ELSE 2 END +
           CASE WHEN SUBSTRING(value FROM 10 FOR 1) = 'L' THEN 0 ELSE 1 END AS seat_num
      FROM day5

This goes into a CTE, to allow easier access to the data. Strictly speaking that’s not necessary for task 1, I can apply the MAX() right to the result and solve the problem. But I need better data access for task 2.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
WITH seat_nums AS (
    SELECT CASE WHEN SUBSTRING(value FROM 1 FOR 1) = 'F' THEN 0 ELSE 512 END +
           CASE WHEN SUBSTRING(value FROM 2 FOR 1) = 'F' THEN 0 ELSE 256 END +
           CASE WHEN SUBSTRING(value FROM 3 FOR 1) = 'F' THEN 0 ELSE 128 END +
           CASE WHEN SUBSTRING(value FROM 4 FOR 1) = 'F' THEN 0 ELSE 64 END +
           CASE WHEN SUBSTRING(value FROM 5 FOR 1) = 'F' THEN 0 ELSE 32 END +
           CASE WHEN SUBSTRING(value FROM 6 FOR 1) = 'F' THEN 0 ELSE 16 END +
           CASE WHEN SUBSTRING(value FROM 7 FOR 1) = 'F' THEN 0 ELSE 8 END +
           CASE WHEN SUBSTRING(value FROM 8 FOR 1) = 'L' THEN 0 ELSE 4 END +
           CASE WHEN SUBSTRING(value FROM 9 FOR 1) = 'L' THEN 0 ELSE 2 END +
           CASE WHEN SUBSTRING(value FROM 10 FOR 1) = 'L' THEN 0 ELSE 1 END AS seat_num
      FROM day5
)
SELECT MAX(seat_num) FROM seat_nums;

The highest seat number is 938, that’s quite large. A quick count over seat_nums shows that there are 868 entries in the list. Wow, that’s a large plane!

Got curious, so I checked the largest (to date) commercial aircraft which is the A380. And indeed, the A380-800 is certified for 868 passengers in a one-class configuration. Pretty sure that’s not a coincidence. Do you have other numbers in your list?

Task 2

Need to find my seat, the plane wants to depart! Based on the seat numbers on the seat_nums list I need to calculate the neighbour seat (+1 and -1) numbers. And then simply check if these seats exist in the list. For that I have to loop over all available seats on the plane - I have an extra CTE to figure out the maximum seat number, and use that in the generate_series() loop - and then check if the seats exist in the list. Here is the CTE for the max seat number:

1
2
3
4
max_seat AS (
    SELECT MAX(seat) AS max_seat_num
      FROM seats
)

And the CTE to calculate the neighbour seats:

1
2
3
4
5
6
seats_exist AS (
    SELECT seat AS seat,
           seat + 1 AS sp1,
           seat - 1 AS sm1
      FROM seats
),

Throw all of this together:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
WITH seats AS (
    SELECT CASE WHEN SUBSTRING(value FROM 1 FOR 1) = 'F' THEN 0 ELSE 512 END +
           CASE WHEN SUBSTRING(value FROM 2 FOR 1) = 'F' THEN 0 ELSE 256 END +
           CASE WHEN SUBSTRING(value FROM 3 FOR 1) = 'F' THEN 0 ELSE 128 END +
           CASE WHEN SUBSTRING(value FROM 4 FOR 1) = 'F' THEN 0 ELSE 64 END +
           CASE WHEN SUBSTRING(value FROM 5 FOR 1) = 'F' THEN 0 ELSE 32 END +
           CASE WHEN SUBSTRING(value FROM 6 FOR 1) = 'F' THEN 0 ELSE 16 END +
           CASE WHEN SUBSTRING(value FROM 7 FOR 1) = 'F' THEN 0 ELSE 8 END +
           CASE WHEN SUBSTRING(value FROM 8 FOR 1) = 'L' THEN 0 ELSE 4 END +
           CASE WHEN SUBSTRING(value FROM 9 FOR 1) = 'L' THEN 0 ELSE 2 END +
           CASE WHEN SUBSTRING(value FROM 10 FOR 1) = 'L' THEN 0 ELSE 1 END AS seat
      FROM day5
),
seats_exist AS (
    SELECT seat AS seat,
           seat + 1 AS sp1,
           seat - 1 AS sm1
      FROM seats
),
max_seat AS (
    SELECT MAX(seat) AS max_seat_num
      FROM seats
)
SELECT my_seat
  FROM generate_series(1, (SELECT max_seat_num FROM max_seat)) AS my_seat
 WHERE NOT EXISTS (SELECT FROM seats_exist WHERE seat = my_seat)
   AND EXISTS (SELECT FROM seats_exist WHERE sp1 = my_seat)
   AND EXISTS (SELECT FROM seats_exist WHERE sm1 = my_seat);

My seat number is:

1
2
3
4
 my_seat
---------
     696
(1 row)

Categories: [Sql]

Tags: [Advent] [Advent-of-Code] [Challenge] [Postgresql] [Psql] [Sql]

Preparation

Task 1

Task 2

Friends