# Advent of Code 2020 Day 5

## Part 1

Day 5’s problem is all about cutting stuff in halves. The problem mentions an
“airline [that] uses *binary space partitioning* to seat people”. On a ticket,
there is 10 characters that are either `F`

for front, `B`

for back, `L`

for
left, `R`

for right. The first seven characters help us determine the row (there
are exactly 128 rows) while the last three are used to identify the exact seat
in the row (there are exactly 8 seats in a row).

We are then told how each of this character help us to determine our seat in the
plane. The example provided is `FBFBBFFRLR`

, which means:

`F`

means we take the front part, thus keeping rows`0`

through`63`

`B`

means we take the back part, thus keeping rows`32`

through`63`

.`F`

means we take the front part, thus keeping rows`32`

through`47`

`B`

means we take the back part, thus keeping rows`40`

through`47`

.`B`

means we take the back part, thus keeping rows`44`

through`47`

.`F`

means we take the front part, thus keeping rows`44`

through`45`

- The seventh
`F`

keeps the lower row:`44`

. - The first character for the actual seat is
`R`

, which means we take the upper half, thus keeping seats`4`

to`7`

. - Then,
`L`

means we take the lower half, thus keeping seats`4`

to`5`

. - Finally,
`R`

means we take the upper value: seat`5`

.

In the end, the expected output is a seat ID which is computed with the
following formula: `seat_id = row * 8 + seat`

.

The name is this problem is an indication of how we can solve it. Basically, we
can represent the possible rows with an interval `A = [I, J]`

that we are going
to cut in half every time we look at a letter. The difficulty then consists of
computing the new bounds correctly. Let’s take a closer look at our problem:

```
A = [0, 127]
|----------- ... ------------|
0 127
```

The objective now is to shift the lower or upper bound so that the resulting
interval is half the length of the former one. So the next step is either
`[0, 63]`

or `[64, 127]`

. With these two intervals, we can start to see a
pattern taking form:

- If we take the lower half,
`max = max - (length / 2)`

; - If we take the upper half,
`min = min + (length / 2)`

.

If we follow the example, the first character on the ticket is an `F`

, and so
the interval becomes `[0, 63]`

, with a new length of 64. The second character is
a `B`

which means we have to take the upper half. So, if we apply the formula
just above, we should get:

`min = min + (length / 2) = 0 + 32`

, and so the interval becomes `[32, 63]`

which is also the interval given by the problem statement. Our solution seems
correct, and we can now implement it in Python (the objective is to find the
highest seat ID):

```
seats = []
for ticket in tickets:
row_min, row_max = 0, 127
seat_min, seat_max = 0, 7
for character in ticket:
if character == "F":
row_max -= int(len(range(row_min, row_max + 1)) / 2)
elif character == "B":
row_min += int(len(range(row_min, row_max + 1)) / 2)
elif character == "R":
seat_max -= int(len(range(seat_min, seat_max + 1)) / 2)
elif character == "L":
seat_minA += int(len(range(seat_min, seat_max + 1)) / 2)
seat_id = row_min * 8 + seat_min # It doesn't matter which value we chose
# row_min == row_max and seat_min == seat_max
seats.append(seat_id)
print(max(seats))
```

## Part 2

In Part 2, we are told that our input data is a list of seat IDs that all have adjacent values except for our seat. Since all seat IDs are integers, we can very quickly sort the list of IDs produced in Part 1 and iterate through that list to find out the only missing value.

The solution is quite straightforward:

```
seats.sort()
for i, seat in enumerate(seats[:-1]):
if seat + 1 != seats[i + 1]:
print(seat + 1)
break
```

## Concepts and difficulties

In Day 5, the main difficulty is (as often) to model the problem appropriately. Once we figure out that the intervals are being cut in half at each pass, it is quite easy to conclude that the bounds need to be modified by half the length of the interval.

After that, Part 2 is probably simpler than Part 1. The trick is to see that
sorting the list of `seat_id`

will help us easily find the missing seat.