Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25
Part 1
Day 5 hits us with an introduction to binary numbers. After some light string parsing, we need to be able convert a string of 1's and 0's (disguised as other characters) into an integer value.
import D5input
-- input :: [String]
toBinary :: String -> Int -> Int
toBinary [] _ = 0
toBinary (c:cs) p2 =
let contribution = if c == 'B' || c == 'R' then p2 else 0
in contribution + toBinary cs (p2 `div` 2)
seatId :: String -> Int
seatId s =
let row = toBinary (take 7 s) 64
col = toBinary (drop 7 s) 4
in row * 8 + col
solve :: Int
solve = foldr max (-1) $ map seatId input
main :: IO ()
main = print $ solve
We first write a toBinary conversion function that converts a String to an Int. Recursion is again a natural way to implement this, although this implementation is a little lazy relies on the caller precomputing the value of the most significant digit. There is probably a more elegant way to write this conversion, but in this problem we know the length of each string we are going to convert beforehand, and therefore we know the value of the most significant digit. As we recurse, we divide this value by 2 before we pass down to reflect the fact that the digit contributes half as much to the overall value.
Once we have this conversion function available, our seatId function can simply split the string into the part for row and the part for column and then compute the seat ID. In part 1, we are asked for the largest seat ID, which we can accomplish by performing a max fold over the seat IDs.
Part 2
It took a little bit to understand what part 2 was asking, but it boils down to this: the input results in a contiguous sequence of seat IDs, except for one ID missing in the middle - what is the missing ID? I used Data.Set in my solution.
import D5input
-- input :: [String]
import qualified Data.Set as Set
toBinary :: String -> Int -> Int
toBinary [] _ = 0
toBinary (c:cs) p2 =
let contribution = if c == 'B' || c == 'R' then p2 else 0
in contribution + toBinary cs (p2 `div` 2)
seatId :: String -> Int
seatId s =
let row = toBinary (take 7 s) 64
col = toBinary (drop 7 s) 4
in row * 8 + col
maxSeat :: Int
maxSeat = foldr max (-1) $ map seatId input
minSeat :: Int
minSeat = foldr min (maxBound :: Int) $ map seatId input
solve :: Int
solve =
let passIds = Set.fromList $ map seatId input
allIds = Set.fromList [minSeat..maxSeat]
in Set.elemAt 0 (allIds Set.\\ passIds)
main :: IO ()
main = print $ solve
Given the guarantees provided by the problem, we can easily generate all possible seat IDs by first determining the minimum seat ID and the maximum seat ID. The maximum was already found in part 1, and an analogous foldr expression gives us the minimum.
Once we have that, we construct two sets. The first set, passIds, contains all seat IDs in the input. The second set, allIds, contains all possible seat IDs, and is constructed from minSeat and maxSeat. Finding the missing ID is then a simple set difference (which is written as \\ in Haskell). Again, we expect exactly one element in the set difference, so we extract it via Set.elemAt 0.
Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25