advent-of-code-2024

commit 4a940e998f54d87e8893913334872f90b7a3e73c
parent a830181c88f262b1facfdc16d53bd1d883a94440
Author: Lukas Henkel <lh@entf.net>
Date:   Sat, 14 Dec 2024 20:46:40 +0100

Add some utils

While experimenting I added some stuff that might be useful for future days

Diffstat:
M
src/utils.lisp
 | 
27
++++++++++++++++++++++++++-

1 file changed, 26 insertions(+), 1 deletion(-)
diff --git a/src/utils.lisp b/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)))