44 lines
1.3 KiB
Haskell
44 lines
1.3 KiB
Haskell
import Data.List (sort)
|
|
|
|
|
|
main :: IO()
|
|
main = do
|
|
input <- readFile "input"
|
|
print . mySeat . map seatId . map seat . lines $ input
|
|
|
|
|
|
mySeat :: [Int] -> Int
|
|
mySeat = findGap . sort
|
|
|
|
findGap :: [Int] -> Int
|
|
findGap (a:b:rest)
|
|
| (b - a) > 1 = b - 1
|
|
| otherwise = findGap $ b:rest
|
|
|
|
seatId :: (Int, Int) -> Int
|
|
seatId (row, col) = (row * 8) + col
|
|
|
|
seat :: String -> (Int, Int)
|
|
seat line = (row fst, col snd) where (fst, snd) = splitAt 7 line
|
|
|
|
row :: String -> Int
|
|
row = partition 'F' 'B' 0 127
|
|
|
|
col :: String -> Int
|
|
col = partition 'L' 'R' 0 7
|
|
|
|
-- Perform binary space partition. The first two arguments are the characters
|
|
-- which indicate that the lower or upper part of the space will be used
|
|
-- respectively. The second two are the starting upper and lower bounds of the
|
|
-- search space. The last is the instructions string.
|
|
partition :: Char -> Char -> Int -> Int -> String -> Int
|
|
partition _ _ min _ [] = min
|
|
partition lowerC upperC min max str@(c:cs)
|
|
| c == upperC = partition' (mid min max) max cs
|
|
| c == lowerC = partition' min (mid min max) cs
|
|
| otherwise = partition' min max cs
|
|
where partition' = partition lowerC upperC
|
|
|
|
-- Find the midpoint of two integers, e.g. the midpoint of 0 and 7 is 4
|
|
mid :: Int -> Int -> Int
|
|
mid a b = div (a + b + 1) 2
|