Day 22

2 files changed, 155 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)
diff --git a/2019/22.in b/2019/22.in
new file mode 100644
index 0000000..673bd8f
--- /dev/null
+++ b/2019/22.in
@@ -0,0 +1,100 @@
+deal with increment 41
+cut 6859
+deal with increment 23
+cut -4435
+deal into new stack
+deal with increment 27
+cut -337
+deal with increment 50
+cut 5290
+deal into new stack
+deal with increment 59
+cut -9939
+deal with increment 32
+cut 4074
+deal with increment 25
+cut -2391
+deal into new stack
+deal with increment 40
+cut -8095
+deal with increment 44
+cut 9150
+deal with increment 5
+cut -5330
+deal with increment 61
+cut -1038
+deal with increment 3
+cut 2873
+deal with increment 56
+cut 6080
+deal with increment 59
+cut -6859
+deal with increment 21
+cut -2316
+deal with increment 42
+cut -8349
+deal with increment 60
+cut 5774
+deal with increment 63
+cut -1754
+deal with increment 48
+cut 4009
+deal with increment 10
+cut -7026
+deal with increment 73
+cut 3867
+deal into new stack
+cut 3754
+deal with increment 23
+cut 4222
+deal with increment 23
+deal into new stack
+cut 7294
+deal into new stack
+deal with increment 13
+cut -9537
+deal with increment 20
+cut 2910
+deal with increment 30
+deal into new stack
+cut 9409
+deal with increment 23
+deal into new stack
+deal with increment 32
+cut 6945
+deal with increment 21
+deal into new stack
+cut -3297
+deal with increment 75
+cut -5300
+deal into new stack
+deal with increment 29
+cut 8131
+deal with increment 50
+cut -8998
+deal with increment 19
+cut -1983
+deal with increment 13
+deal into new stack
+cut -7555
+deal with increment 62
+cut 5612
+deal with increment 14
+cut -412
+deal with increment 46
+cut -7349
+deal with increment 57
+cut -8783
+deal with increment 33
+deal into new stack
+deal with increment 56
+cut 4283
+deal into new stack
+cut 8053
+deal with increment 7
+cut -2776
+deal with increment 66
+cut -9633
+deal with increment 62
+deal into new stack
+deal with increment 12