day13

1 files changed, 22 insertions, 0 deletions

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