day13

3 files changed, 33 insertions, 0 deletions

diff --git a/day13 b/day13
new file mode 100644
index 0000000..7e74881
--- /dev/null
+++ b/day13
@@ -0,0 +1,2 @@
+1000390
+23,x,x,x,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,383,x,x,x,x,x,x,x,x,x,x,x,x,13,17,x,x,x,x,19,x,x,x,x,x,x,x,x,x,29,x,503,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37
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
diff --git a/day13.ijs b/day13.ijs
new file mode 100644
index 0000000..9accec0
--- /dev/null
+++ b/day13.ijs
@@ -0,0 +1,9 @@
+load 'aoc.ijs'
+'t oy' =: lines 'day13'
+x =: 0
+y =: 0 -.~ oy =: x: ".&> (<;._1 ',',oy)
+
+(n{y)*v{~n=.{./:v=.y-y|".t  NB. 2298
+
+minv =: ]|(^-&2x)  NB. x assumed prime
+(*/y)|+/(-oy i. y)*((*/%])([*minv)])y  NB. 783685719679632