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`

or`R`

, 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`

or`L`

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.

```
#[derive(Debug)]
struct Seat {
row: i32,
column: i32,
}
// In our case the delimiter is a character that determines if the range should be partitioned, and whether to use the upper or the lower partition.
#[derive(Debug)]
struct RangeDelimiters {
upper: char,
lower: char,
}
// Seat Range is what hold's the range values during the partitioning process.
struct SeatRange {
start: i32,
end: i32,
}
```

Let's also define some constants denoting the total number of possible rows and columns in the airline.

```
const TOTAL_ROWS: i32 = 128;
const TOTAL_COLUMNS: i32 = 7;
```

Now let's create a function to parse the seat string, and return the row and column.

```
fn parse_seat(seat: &str) -> Result<Seat, String> {
lazy_static! {
// the regex parses the string, into a letters of length 7, 3
static ref SEAT_REGEX: Regex = Regex::new(r"(\w{7})(\w{3})").unwrap();
}
if seat.len() < 10 {
return Err("Invalid seat".to_owned());
}
let captures = SEAT_REGEX.captures(seat).unwrap();
let rows: &str = &captures[1];
let columns: &str = &captures[2];
if rows.len() < 7 || columns.len() < 3 {
return Err("Invalid seat".to_owned());
}
let row_range_delimiters = RangeDelimiters {
upper: 'B',
lower: 'F',
};
let column_range_delimiters = RangeDelimiters {
upper: 'R',
lower: 'L',
};
let SeatRange {
start: seat_row, ..
} = get_range_from_seat(rows, row_range_delimiters, TOTAL_ROWS);
let SeatRange {
end: seat_column, ..
} = get_range_from_seat(columns, column_range_delimiters, TOTAL_COLUMNS);
let seat = Seat {
row: seat_row,
column: seat_column,
};
Ok(seat)
}
```

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:

```
fn get_range_from_seat(seat: &str, delimeters: RangeDelimiters, max_count: i32) -> SeatRange {
// initialize range from 0 to maximum value.
let mut range = SeatRange {
start: 0,
end: max_count,
};
let RangeDelimiters { lower, upper } = delimeters;
// perform the actual binary partitioning
for char in seat.chars() {
if char == lower {
range.end = (range.start + range.end) / 2;
} else if char == upper {
range.start = range.start + (range.end - range.start) / 2;
}
}
// return the range
range
}
```

Now that we have a row, column pair the conversion to seatID is straightforward based on the problem statement:

```
fn get_seat_id(seat: Seat) -> i32 {
seat.row * 8 + seat.column
}
```

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.

```
fn process(input: &str) -> (i32, i32) {
let ids: Vec<i32> = input
.lines()
.map(|line| {
let seat = match parse_seat(line) {
Ok(seat) => seat,
Err(e) => {
eprintln!("Error: {}", e);
process::exit(1);
}
};
get_seat_id(seat)
})
.collect::<Vec<i32>>();
let max = *ids.iter().max().unwrap();
return max;
}
```

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.

```
fn get_missing_id(mut ids: Vec<i32>) -> i32 {
ids.sort();
let mut prev = ids[0];
let ids: Vec<i32> = ids[1..].to_vec();
for curr in ids {
if prev != curr - 1 {
break;
}
prev += 1;
}
prev + 1
}
```

The `process`

function would feed in the `ids`

to get the missingId.

Awesome! That's all for Day 05. See ya 👋