commit - a830181c88f262b1facfdc16d53bd1d883a94440
commit + 4a940e998f54d87e8893913334872f90b7a3e73c
blob - 809269e5478f7d5ea951c7fbd5102d7c567bfb8e
blob + 319428bc76d8b327693cbeffd71b6a24ca073679
--- src/utils.lisp
+++ src/utils.lisp
@@ -30,7 +30,9 @@
    #:do-map-neighbours
    #:read-number-list
    #:find-pattern
-   #:define-parser))
+   #:define-parser
+   #:modular-inverse
+   #:crt))
 (in-package #:aoc/utils)
 
 (defun normalize-type (type)
@@ -295,3 +297,26 @@
              (declare (special ,@callback-syms))
              (do-parse stream ,table-var))
            (values ,@(mapcar #'car variable-bindings)))))))
+
+(defun gcd-extended (a b)
+  (if (zerop b)
+      (values a 1 0)
+      (multiple-value-bind (gcd x1 y1)
+          (gcd-extended b (mod a b))
+        (values gcd y1 (- x1 (* y1 (floor a b)))))))
+
+(defun modular-inverse (a m)
+  (multiple-value-bind (gcd x y)
+      (gcd-extended a m)
+    (declare (ignore y))
+    (if (/= gcd 1)
+        nil
+        (mod x m))))
+
+(defun crt (x y w h)
+  (let* ((m (lcm w h))
+         (w-inv (modular-inverse w h))
+         (h-inv (modular-inverse h w)))
+    (mod (+ (* y w w-inv)
+            (* x h h-inv))
+         m)))