add day13, crt from rosetta

1 files changed, 27 insertions, 0 deletions

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