Hello! Let’s continue with our advent of code 2020 streak. We’re now at Day 05.
Spoilers Ahead! The full solution for the problem is available here.
Given a string input referring to a seat in an airline, where in each character is one of (F, B, L, R) a seat might be specified like “FBFBBFFRLR”, where F means “front”, B means “back”, L means “left”, and R means “right”. Every character in the string, denotes a way of finding the right row and column in which your seat is present.
This involves binary partitioning > which just means that given a range of numbers, partition that into two (0..middle, middle..end). Read through the examples in the problem statement linked above, to get a better idea and be back here for how we can solve this problem.
The core idea required to solve this problem is to parse the seat input, and return a row and a column. The algorithm for that would look like:

Split the input into first 7 characters that represent the row, and the last 3 that represent the column (using a regex / the usual string indexing).

Initialize a range, from 0 > 128 for rows, and 0 > 7 for the columns. Iterate through the characters in the string.

If the current character is
B
orR
, partition the range and use the upper partition. This is can be done by moving the range start to the middle of the partition:range.start = range.start + (range.end  range.start) / 2
. 
Similarly if the current character is
F
orL
partition the range, and use the lower partition. This can be done by reducing the range end towards the middle of:range.end = (range.start + range.end) / 2;
Alright! Now that we have the algorithm in place, let’s define some structs to hold the Seat, Range.
Let’s also define some constants denoting the total number of possible rows and columns in the airline.
Now let’s create a function to parse the seat string, and return the row and column.
Since we need to partition the range for both rows, and columns we have abstracted out that logic into a separate function get_range_from_seat
, which looks like:
Now that we have a row, column pair the conversion to seatID is straightforward based on the problem statement:
For part 01 of the problem, the requirement is to find the highest possible seatId when given a batch on inputs where every line is a seat (string of FBLR characters).
Let’s write the process
function which would act as the driver, to parse the seat Input, retrieve seatIDs and then find the maximum value.
Cool! That’s all for Part 01.
Part 02
Part 02 is an extension to part 1, where we also need to return a specific missing seatId that meets a specific condition > the missing element has both it’s +1 and 1 in our id list.
The process
function would feed in the ids
to get the missingId.
Awesome! That’s all for Day 05. See ya 👋