It’s day 5 of Advent of Code, and we’re boarding our plane for Christmas vacation. Oddly, the seats are designated via binary space partitioning, where a string like `FBFBBFFRLR`

tells you to narrow your search for your seat down to the `F`

ront, `B`

ack, `R`

, or `L`

eft half of the plane.

This all seems a bit weird, until you realize that these are just binary numbers – 7 bits for the row, and 3 bits for the column. I realized after the fact that Haskell actually defines bitwise operations for integers in `base`

– Data.Bits – but implementing it ourself ain’t too hard:

```
getRowCol :: Text -> (Int, Int)
= (row, col)
getRowCol txt where
= Text.splitAt 7 txt
(rowCode, colCode) = interpretAsBinary (== 'B') rowCode
row = interpretAsBinary (== 'R') colCode
col = Text.foldl (shiftAndAdd is1) 0
interpretAsBinary is1 int :: Int) c =
shiftAndAdd is1 (let digit = if is1 c then 1 else 0
in (int * 2) + digit
```

Each seat also has an “ID” assigned by the formula `8 * row + col`

, and the first answer we’re asked to give is the highest seat ID occupied (given our puzzle input as the list of our fellow passengers’ boarding passes in `FBFBBFFRLR`

form). Simple enough that I won’t bother including it here.

The second answer is a little more interesting. You see, in the story of this puzzle, we’ve dropped our own boarding pass, so we don’t know which seat ours is – but, we do know that this is a completely full flight, and we can see everyone else’s boarding passes. We need to figure out our own seat’s ID.

This problem is actually more or less the same as a classic tech interview problem: given `n - 1`

unique numbers in the range `[1, n]`

, determine which one is missing. You can do this in one pass and constant space with `sum [1 .. n] - sum givenNumbers`

. Modulo a wrinkle where some seats at the very front and very back of the plane are missing, we can apply this to our own boarding pass issue as well – observe that the formula `8 * row + col`

means that the seats will form a continuous set of integers (minus our own missing seat ID).

```
answer2 :: [Text] -> Int
=
answer2 inp let takenIds = map (uncurry toId . getRowCol) inp
in sum [minimum takenIds .. maximum takenIds] - sum takenIds
```

As always, my full solution can be found on GitHub: https://github.com/ewilden/aoc-2020/blob/main/src/Day05.hs