Advent of Code Day 5: Binary Boarding Passes

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 Front, Back, R, or Left 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)
getRowCol txt = (row, col)
  where
    (rowCode, colCode) = Text.splitAt 7 txt
    row = interpretAsBinary (== 'B') rowCode
    col = interpretAsBinary (== 'R') colCode
    interpretAsBinary is1 = Text.foldl (shiftAndAdd is1) 0
    shiftAndAdd is1 (int :: Int) c =
      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