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
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) = (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