From d58d88e5c3563e50897a3c7b1cbd16b6e3ed38c9 Mon Sep 17 00:00:00 2001
From: Leah Neukirchen <leah@vuxu.org>
Date: Mon, 14 Dec 2020 20:28:30 +0100
Subject: day13

---
 day13.clj | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)
 create mode 100644 day13.clj

(limited to 'day13.clj')

diff --git a/day13.clj b/day13.clj
new file mode 100644
index 0000000..6f91046
--- /dev/null
+++ b/day13.clj
@@ -0,0 +1,22 @@
+(let [[a l] (clojure.string/split-lines (slurp "day13"))]
+  (def time (read-string a))
+  (def buses (map read-string (replace {"x" "0"}
+                                       (clojure.string/split l #",")))))
+
+(->> (remove #{0} buses)
+     (map #(vector % (- % (mod time %))))
+     (apply min-key second)
+     (apply *)) ; => 2298
+
+(defn minv "Compute x^-1 mod y naively."
+  [x y]
+  (some #(if (= 1 (mod (* x %) y)) %) (range 1 y)))
+
+;; using chinese remainder theorem
+(let [[a b] (apply map vector
+                   (remove (comp zero? second) (map-indexed vector buses)))
+      N (apply * b)
+      y (map #(/ N %) b)
+      z (map minv y b)
+      x (map * (map - a) y z)]
+  (mod (apply + x) N)) ; => 783685719679632
-- 
cgit 1.4.1