1 files changed, 55 insertions, 0 deletions
diff --git a/2019/22.hs b/2019/22.hs
new file mode 100644
index 0000000..24609f0
--- /dev/null
+++ b/2019/22.hs
@@ -0,0 +1,55 @@
+module Main where
+
+import Input
+
+
+egcd :: Integer -> Integer -> (Integer, Integer, Integer)
+egcd m n = go 1 0 m 0 1 n
+  where
+    go a1 b1 r1 _  _  0  = (r1, a1, b1)
+    go a1 b1 r1 a2 b2 r2 =
+        let (q, r) = r1 `divMod` r2
+        in go a2 b2 r2 (a1 - q * a2) (b1 - q * b2) r
+
+-- multiplicative inverse of k mod n
+multinv :: Integer -> Integer -> Integer
+multinv k n =
+    let (1, x, _) = egcd k n  -- x * k + y * n = 1  =>  x * k = 1 mod n
+    in x
+
+-- Affine multiplier addend modulus
+data Affine = Affine Integer Integer Integer
+  deriving (Show)
+
+instance Semigroup Affine where
+    Affine a1 b1 m1 <> Affine a2 b2 m2
+        | m1 == m2 = Affine ((a1 * a2) `mod` m1) ((a1 * b2 + b1) `mod` m1) m1
+        | otherwise = error "<>'ing incompatible Affine's"
+
+apply :: Affine -> Integer -> Integer
+apply (Affine a b m) x = (a * x + b) `mod` m
+
+inverse :: Affine -> Affine
+inverse (Affine a b m) = Affine (multinv a m) 0 m <> Affine 1 (-b) m
+
+power :: Semigroup m => m -> Int -> m
+power x 1 = x
+power x n | n < 1 = error "non-positive exponent in 'power'"
+          | even n = power (x <> x) (n `quot` 2)
+          | otherwise = power x (n - 1) <> x
+
+parse :: String -> (Integer, Integer)
+parse ('c':'u':'t':' ':s) = (1, negate (read s))
+parse ('d':_:_:_:_:'w':s) = (read (drop 14 s), 0)
+parse ('d':_:_:_:_:'i':_) = (-1, -1)
+parse _ = undefined
+
+main :: IO ()
+main = do
+    techlist <- map parse <$> getInput 22
+
+    let technique1 = foldl1 (<>) [Affine a b 10007 | (a, b) <- reverse techlist]
+        technique2 = foldl1 (<>) [Affine a b 119315717514047 | (a, b) <- reverse techlist]
+
+    print (apply technique1 2019)
+    print (apply (power (inverse technique2) 101741582076661) 2020)