#### Advent of Code 2020 - Day 5

Day 5 of AoC 2020 (Binary Boarding) is a bit of a trick problem. However, once you understand the pattern inherent in the problem description, this is extremely straightforward. As always, spoilers ahead.

The problem description describes the use of *binary space partitioning*, in
essence splitting the search space in half at every step, then picking one of
the halves and proceeding with the search. A naive implementation would take the
upper and lower bounds and recalculate the bounds after each character.

But, this is unnecessary, and can be solved by simply mapping the characters to
`0`

and `1`

, and converting the binary string into an integer. Why does this
work? Let’s take a simple example `FBFBBFFRLR`

, as given in the problem
description. Let’s just take the seat column (`RLR`

).

- Start by considering the whole range 0-7
- The first
`R`

tells us to take the upper half of this range (4-7) - The second letter (
`L`

) means take the lower half of the now restricted range (4-5) - The last letter (
`R`

) means to take the upper half - giving us the seat column`5`

Let’s use the binary encoding to visualize this further.

Step | Character | Binary Encoding | Range |
---|---|---|---|

0 | - | XXX | 0 - 7 |

1 | R | 1XX | 4 - 7 |

2 | L | 10X | 4 - 5 |

3 | R | 101 | 5 |

As you can see from the binary encoding column, the `X`

characters are
essentially floating values, which means that they could take either 0 or 1, and
the range is found by setting them to all `0`

or all `1`

. But, once we have all
the positions resolved, we are down to a single value in the range.

In the same way, by replacing `F`

with `0`

and `B`

with `1`

, we can compute the
seat row. However, we don’t actually need the row and column, we only need the
seat ID, which is, conveniently, `row * 8 + column`

, or the value by just
converting all characters to `0`

or `1`

and converting from binary to integer.

With the above example (`FBFBBFFRLR`

), we can compute the result as
`0101100101`

, or `357`

, as shown in the table below:

Step | Character | Binary Encoding | Range |
---|---|---|---|

0 | - | XXXXXXXXXX | 0 - 1023 |

1 | F | 0XXXXXXXXX | 0 - 511 |

2 | B | 01XXXXXXXX | 256 - 511 |

3 | F | 010XXXXXXX | 256 - 383 |

4 | B | 0101XXXXXX | 320 - 383 |

5 | B | 01011XXXXX | 352 - 383 |

6 | F | 010110XXXX | 352 - 367 |

7 | F | 0101100XXX | 352 - 359 |

8 | R | 01011001XX | 356 - 359 |

9 | L | 010110010X | 356 - 357 |

10 | R | 0101100101 | 357 |

Now, we have all we need to compute the seat ID using the character to bit mapping defined above.

```
def seat_id(seat):
mapping = {'F': '0', 'B': '1', 'L': '0', 'R': '1'}
return int(''.join(mapping[c] for c in seat), 2)
with open('input') as datafile:
data = datafile.read().splitlines()
seats = sorted(seat_id(seat) for seat in data)
max_seat = seats[-1]
```

With the above snippet, we have the solution for part 1. For part 2, we know that the plane is full, and the only missing seat in the sorted list is our seat. The problem states tht we are somewhere in the middle, so we can just walk through the list, comparing the current seat with the previous seat, and when the difference is not 1, we have found our missing seat.

```
last = seat[0]
for seat in seats[1:]:
if seat != last+1:
print(last+1)
break
last = seat
```