initial commit

1 files changed, 51 insertions, 0 deletions

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