From 5eb58ad076f2cd435b11b140820da224b60b73d5 Mon Sep 17 00:00:00 2001 From: Aria Date: Mon, 2 Jan 2023 21:58:56 +0000 Subject: initial commit --- 2020/13b.hs | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 51 insertions(+) create mode 100644 2020/13b.hs (limited to '2020/13b.hs') diff --git a/2020/13b.hs b/2020/13b.hs new file mode 100644 index 0000000..4a66ec2 --- /dev/null +++ b/2020/13b.hs @@ -0,0 +1,51 @@ +module Day13B where + +import System.Environment (getArgs) +import Data.List.Split (splitOn) +import Text.Read (readMaybe) +import Text.Printf + +-- Extended Euclidean Algorithm +-- Returns (s, t) such that as + bt = gcd(a,b) +extendedEu :: Int -> Int -> (Int, Int) +extendedEu _ 0 = (1, 0) +extendedEu a b = (t, s - q * t) + where (q, r) = quotRem a b + (s, t) = extendedEu b r + +-- Solve for x in (a, n) such that x = a mod n +-- Assumes all ns are coprime +crt :: [(Int, Int)] -> Int +crt xs | r < 0 = -(r + n') + | otherwise = r + where n' = product $ map snd xs + r = sum [a * snd (extendedEu n (n' `div` n)) * (n' `div` n) |(a, n) <- xs] + +-- Calculate the nearest time with the given parameters +solvePuzzle :: [Maybe Int] -> Int +solvePuzzle bs = crt [(i `mod` x, x) | (i, Just x) <- zip [0..] bs] + +-- Parse the input as a string +-- Returns (current time, list of buses / nothing if x) +parseInput :: String -> (Int, [Maybe Int]) +parseInput x = (read t, ts) + where (t:r) = lines x + bs = splitOn "," (head r) + ts :: [Maybe Int] + ts = map readMaybe bs + +-- Parse a file given the path +-- Returns (current time, list of buses / nothing if x) +parseFromFile :: String -> IO (Int, [Maybe Int]) +parseFromFile s = do + contents <- readFile s; + return $ parseInput contents; + +-- runghc --ghc-arg='-package split' 13a.hs inputs/day13 +main :: IO () +main = do + args <- getArgs; + (_, bs) <- parseFromFile (head args); + + printf "Answer = %d\n" (solvePuzzle bs) :: IO (); + return (); -- cgit v1.2.3