aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorAkshay <[email protected]>2020-12-13 06:35:25 +0000
committerAkshay <[email protected]>2020-12-13 06:35:25 +0000
commita961cfecaf9c21f41dfabe8d105512326b5881e0 (patch)
tree4c234f5f64190984bf9fd67b42e247bce95bb8ba /lib
parente3d58e974a07b39922696697f23727c6ae333d04 (diff)
add day13, crt from rosetta
Diffstat (limited to 'lib')
-rw-r--r--lib/Utils.hs27
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
65 grid = Map.fromList [((x, y), a) | (y, row) <- zip [0..] rows , (x, a) <- zip [0..] row] 65 grid = Map.fromList [((x, y), a) | (y, row) <- zip [0..] rows , (x, a) <- zip [0..] row]
66 width = length (head rows) 66 width = length (head rows)
67 height = length rows 67 height = length rows
68
69-- number theory
70
71egcd :: Int -> Int -> (Int, Int)
72egcd _ 0 = (1, 0)
73egcd a b = (t, s - q * t)
74 where
75 (s, t) = egcd b r
76 (q, r) = a `quotRem` b
77
78modInv :: Int -> Int -> Maybe Int
79modInv a b =
80 case egcd a b of
81 (x, y)
82 | a * x + b * y == 1 -> Just x
83 | otherwise -> Nothing
84
85-- from rosetta code
86chineseRemainder :: [(Int, Int)] -> Maybe Int
87chineseRemainder ls =
88 zipWithM modInv crtModulii modulii >>=
89 (Just . (`mod` modPI) . sum . zipWith (*) crtModulii . zipWith (*) residues)
90 where
91 residues = map fst ls
92 modulii = map snd ls
93 modPI = product modulii
94 crtModulii = (modPI `div`) <$> modulii