From a961cfecaf9c21f41dfabe8d105512326b5881e0 Mon Sep 17 00:00:00 2001
From: Akshay <nerdy@peppe.rs>
Date: Sun, 13 Dec 2020 12:05:25 +0530
Subject: add day13, crt from rosetta

---
 aoc.cabal      |  6 ++++++
 execs/Day13.hs | 25 +++++++++++++++++++++++++
 input/13       |  2 ++
 lib/Utils.hs   | 27 +++++++++++++++++++++++++++
 4 files changed, 60 insertions(+)
 create mode 100644 execs/Day13.hs
 create mode 100644 input/13

diff --git a/aoc.cabal b/aoc.cabal
index dfd102e..87867f4 100644
--- a/aoc.cabal
+++ b/aoc.cabal
@@ -93,3 +93,9 @@ executable Day12
   build-depends:       base, aoc, containers
   default-language:    Haskell2010
   hs-source-dirs:      execs
+
+executable Day13
+  main-is:             Day13.hs
+  build-depends:       base, aoc, containers, split
+  default-language:    Haskell2010
+  hs-source-dirs:      execs
diff --git a/execs/Day13.hs b/execs/Day13.hs
new file mode 100644
index 0000000..07d379d
--- /dev/null
+++ b/execs/Day13.hs
@@ -0,0 +1,25 @@
+module Main where
+
+import Utils
+import Data.List.Split
+import Data.Tuple
+import Data.List (sortOn)
+import Data.Bifunctor
+import Control.Monad (zipWithM, ap)
+
+earliest :: Int -> [Int] -> Int
+earliest start ls = t * b
+    where (t, b) = minimum $ map swap $ zip `ap` map (mod start) $ ls
+
+gold :: [(Int, Int)] -> Int
+gold ls = t
+    where Just t = chineseRemainder ls
+
+main :: IO ()
+main = do
+    n <- lines <$> readFile "input/13"
+    let start   = read (head n) :: Int
+        departs = map read $ filter (/= "x") $ splitOn "," (last n)
+        offs    = map (bimap negate read) $ filter ((/= "x") . snd) $ zip [0..] $ splitOn "," (last n)
+    print $ earliest (negate start) departs
+    print $ gold offs
diff --git a/input/13 b/input/13
new file mode 100644
index 0000000..dec83ff
--- /dev/null
+++ b/input/13
@@ -0,0 +1,2 @@
+1000053
+19,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,523,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,13,x,x,x,x,23,x,x,x,x,x,29,x,547,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,17
diff --git a/lib/Utils.hs b/lib/Utils.hs
index 56d9c69..e0f9d62 100644
--- a/lib/Utils.hs
+++ b/lib/Utils.hs
@@ -65,3 +65,30 @@ makeGrid s = (grid, width, height) where
     grid = Map.fromList [((x, y), a) | (y, row) <- zip [0..] rows , (x, a) <- zip [0..] row]
     width = length (head rows)
     height = length rows
+
+-- number theory 
+
+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 -> Maybe Int
+modInv a b =
+    case egcd a b of
+      (x, y)
+        | a * x + b * y == 1 -> Just x
+        | otherwise -> Nothing
+
+-- from rosetta code
+chineseRemainder :: [(Int, Int)] -> Maybe Int
+chineseRemainder ls =
+    zipWithM modInv crtModulii modulii >>=
+        (Just . (`mod` modPI) . sum . zipWith (*) crtModulii . zipWith (*) residues)
+            where
+                residues = map fst ls
+                modulii = map snd ls
+                modPI = product modulii
+                crtModulii = (modPI `div`) <$> modulii
-- 
cgit v1.2.3