diff options
Diffstat (limited to 'day13.clj')
-rw-r--r-- | day13.clj | 22 |
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 |