Day 05: Binary Boarding

Once past the turnstiles, you dash towards the cluster to take the retake exam. But to stop students from sitting next to their friends to cheat, Le Bocal implemented an unusual seating system.

Instead of directly telling you your station, the terminal prints a ticket with a code based on Binary Space Partitioning (BSP).

A code is exactly 10 characters: the first 7 denote the row and the last 3 denote the column of the station.

The cluster has 128 rows of desks, numbered from 0 to 127. Each letter divides the remaining range into halves: F means the front half (Front), and B means the back half (Back).

Consider, for example, the first 7 characters of FBFBBFFRLR :

• Start by considering the entire room: rows 0 through 127.
• F takes the lower half: rows 0 through 63.
• B takes the upper half: rows 32 through 63.
• F takes the lower half: rows 32 through 47.
• B takes the upper half: rows 40 through 47.
• B takes the upper half: rows 44 through 47.
• F takes the lower half: rows 44 through 45.
• The final F takes the lower half, giving row 44.

The last 3 characters work under the same principle across 8 columns (numbered 0 through 7). This time, L selects the left half (Left) and R selects the right half (Right):

• Start with columns 0 through 7.
• R keeps columns 4 through 7.
• L keeps columns 4 through 5.
• The final R selects column 5.

The ticket FBFBBFFRLR therefore corresponds to row 44 and column 5.

Every station has a unique Seat ID obtained by multiplying the row by 8 and adding the column: 44 * 8 + 5 = 357.

Part 1

Here are examples of decoding other exam tickets:

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

You obtain the file containing the list of all tickets assigned to the students present.

Analyzing every ticket in your list, what is the highest seat ID (Seat ID)?