From 99dcde4240c2f823af21d05985152fa58e84f9ed Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Fri, 24 Mar 2023 01:17:50 +0100 Subject: 2020-13 in haskell --- 2020/13-Shuttle_Search/example | 2 ++ 2020/13-Shuttle_Search/first.hs | 53 +++++++++++++++++++++++++++ 2020/13-Shuttle_Search/input | 2 ++ 2020/13-Shuttle_Search/second.hs | 77 ++++++++++++++++++++++++++++++++++++++++ 4 files changed, 134 insertions(+) create mode 100644 2020/13-Shuttle_Search/example create mode 100644 2020/13-Shuttle_Search/first.hs create mode 100644 2020/13-Shuttle_Search/input create mode 100644 2020/13-Shuttle_Search/second.hs diff --git a/2020/13-Shuttle_Search/example b/2020/13-Shuttle_Search/example new file mode 100644 index 0000000..d76f619 --- /dev/null +++ b/2020/13-Shuttle_Search/example @@ -0,0 +1,2 @@ +939 +7,13,x,x,59,x,31,19 diff --git a/2020/13-Shuttle_Search/first.hs b/2020/13-Shuttle_Search/first.hs new file mode 100644 index 0000000..c59097f --- /dev/null +++ b/2020/13-Shuttle_Search/first.hs @@ -0,0 +1,53 @@ +-- requires cabal install --lib megaparsec parser-combinators +module Main (main) where +import Control.Monad (void, when) +import Data.List (elemIndex) +import Data.Maybe (catMaybes, fromJust) +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char +import System.Exit (die) + +exampleExpectedOutput = 295 + +type Input = (Int, [Maybe Int]) + +type Parser = Parsec Void String + +parseShuttle :: Parser (Maybe Int) +parseShuttle = do + num <- (Just . read <$> some digitChar) <|> (char 'x' *> return Nothing) + void . optional $ char ',' + return $ num + +parseOps :: Parser Input +parseOps = do + time <- some digitChar + void $ char '\n' + shuttles <- some parseShuttle + void $ char '\n' + void $ eof + return $ ((read time), shuttles) + +parseInput :: String -> IO Input +parseInput filename = do + input <- readFile filename + case runParser parseOps filename input of + Left bundle -> die $ errorBundlePretty bundle + Right ops -> return ops + +compute :: Input -> Int +compute (time, shuttles) = departure * busId + where + busId = allShuttles !! (fromJust $ elemIndex departure nextDepartures) + departure = minimum nextDepartures + nextDepartures = map (\a -> (-time) `mod` a) allShuttles + allShuttles = catMaybes shuttles + +main :: IO () +main = do + example <- parseInput "example" + let exampleOutput = compute example + when (exampleOutput /= exampleExpectedOutput) (die $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput) + input <- parseInput "input" + print $ compute input diff --git a/2020/13-Shuttle_Search/input b/2020/13-Shuttle_Search/input new file mode 100644 index 0000000..c16c8bb --- /dev/null +++ b/2020/13-Shuttle_Search/input @@ -0,0 +1,2 @@ +1001612 +19,x,x,x,x,x,x,x,x,41,x,x,x,37,x,x,x,x,x,821,x,x,x,x,x,x,x,x,x,x,x,x,13,x,x,x,17,x,x,x,x,x,x,x,x,x,x,x,29,x,463,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,23 diff --git a/2020/13-Shuttle_Search/second.hs b/2020/13-Shuttle_Search/second.hs new file mode 100644 index 0000000..242824d --- /dev/null +++ b/2020/13-Shuttle_Search/second.hs @@ -0,0 +1,77 @@ +-- requires cabal install --lib megaparsec parser-combinators +module Main (main) where +import Control.Monad (void, when, zipWithM) +import Data.Either (fromRight) +import Data.List (foldl') +import Data.Void (Void) +import Text.Megaparsec +import Text.Megaparsec.Char +import System.Exit (die) + +exampleExpectedOutput = 1068781 + +type Input = [Maybe Int] + +type Parser = Parsec Void String + +parseShuttle :: Parser (Maybe Int) +parseShuttle = do + num <- (Just . read <$> some digitChar) <|> (char 'x' *> return Nothing) + void . optional $ char ',' + return $ num + +parseOps :: Parser Input +parseOps = do + void $ some digitChar + void $ char '\n' + shuttles <- some parseShuttle + void $ char '\n' + void $ eof + return $ shuttles + +parseInput :: String -> IO Input +parseInput filename = do + input <- readFile filename + case runParser parseOps filename input of + Left bundle -> die $ errorBundlePretty bundle + Right ops -> return ops + +-- From rosetta code https://rosettacode.org/wiki/Chinese_remainder_theorem#Haskell +egcd :: Int -> Int -> (Int, Int) +egcd _ 0 = (1, 0) +egcd a b = (t, s - q * t) + where + (s, t) = egcd b r + (q, r) = a `quotRem` b + +modInv :: Int -> Int -> Either String Int +modInv a b = + case egcd a b of + (x, y) + | a * x + b * y == 1 -> Right x + | otherwise -> + Left $ "No modular inverse for " ++ show a ++ " and " ++ show b + +chineseRemainder :: [Int] -> [Int] -> Either String Int +chineseRemainder residues modulii = + zipWithM modInv crtModulii modulii >>= + (Right . (`mod` modPI) . sum . zipWith (*) crtModulii . zipWith (*) residues) + where + modPI = product modulii + crtModulii = (modPI `div`) <$> modulii +-- end of snippet from rosetta code + +compute :: Input -> Int +compute input = fromRight 0 . uncurry chineseRemainder $ unzip $ fst $ foldl' accumul ([], 0) input + where + accumul :: ([(Int, Int)], Int) -> Maybe Int -> ([(Int, Int)], Int) + accumul (acc, i) Nothing = (acc, i+1) + accumul (acc, i) (Just v) = (acc ++ [(-i, v)], i+1) + +main :: IO () +main = do + example <- parseInput "example" + let exampleOutput = compute example + when (exampleOutput /= exampleExpectedOutput) (die $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput) + input <- parseInput "input" + print $ compute input -- cgit v1.2.3