X-Git-Url: http://git.jkinsey.net/?p=adventofcode2019.git;a=blobdiff_plain;f=src%2Fadventofcode2019%2Fday18.clj;fp=src%2Fadventofcode2019%2Fday18.clj;h=cbe88c9c011070216c294dd469f66de1fad33050;hp=0000000000000000000000000000000000000000;hb=7a710645a2234dcb568c2e971b5b0367217d0ea8;hpb=21ab31d9418c308ae58d73141184be8b42a11ab8

diff --git a/src/adventofcode2019/day18.clj b/src/adventofcode2019/day18.clj
new file mode 100644
index 0000000..cbe88c9
--- /dev/null
+++ b/src/adventofcode2019/day18.clj
@@ -0,0 +1,85 @@
+(ns adventofcode2019.day18
+  [:require [adventofcode2019.lib :refer :all]
+   [adventofcode2019.intcode :as i]
+   [clojure.string :as str]
+   [clojure.set :as set]
+   [clojure.core.match :refer [match]]
+   [clojure.math.combinatorics :as combo]
+   [clojure.data.priority-map :refer [priority-map-by]]])
+
+(defn build-world [input]
+  (let [point-encode (->> input
+                          (map-indexed
+                           (fn [y xs]
+                             (map-indexed
+                              (fn [x c]
+                                [c [x y]]) xs)))
+                          (apply concat))
+        passages (->> point-encode
+                      (filter #(= \. (first %)))
+                      (map second)
+                      (set))
+        interesting (->> point-encode
+                         (filter #(and (not= \. (first %))
+                                       (not= \# (first %))))
+                         (into {}))
+        dkeys (select-keys interesting (filter #(Character/isLowerCase %)
+                                               (keys interesting)))
+        doors (select-keys interesting (filter #(Character/isUpperCase %)
+                                               (keys interesting)))
+        player (interesting \@)]
+    {:p player
+     :t (apply conj passages player (vals dkeys))
+     :k dkeys
+     :d doors}))
+
+(defn path-between [trav point-a point-b]
+  (let [succ (fn [sn [x y]]
+               (filter (every-pred trav (complement sn))
+                       [[(inc x) y] [(dec x) y]
+                        [x (inc y)] [x (dec y)]]))
+        update-openl (fn [ol sn pt ds]
+                       (reduce (fn [m p] 
+                                 (assoc m p [ds (manhattan-distance p point-b)]))
+                               ol (succ sn pt)))
+        openl (priority-map-by (fn [[ag ah] [bg bh]]
+                                 (compare (+ ag ah) (+ bg bh))))]
+    (loop [openl (assoc openl point-a 
+                        [0 (manhattan-distance point-a point-b)])
+           seen #{point-a}]
+      (cond 
+        (contains? openl point-b) (first (openl point-b))
+        (empty? openl) ##Inf
+        :else (let [[point [dist _]] (peek openl)
+                    seen (conj seen point)]
+                (recur (update-openl (pop openl) seen point (inc dist)) seen))))))
+
+(defn accessible [{player :p dkeys :k trav :t}]
+  (->> dkeys
+       (mmap (partial path-between trav player))
+       (remove #(= ##Inf (second %)))
+       (into {})))
+
+(defn acquire-all-keys [world]
+  (if (empty? (world :k)) 0
+    (let [accessible-keys (accessible world)
+          successor-world (fn [[kc ds]]
+                            (let [kp (get-in world [:k kc])
+                                  dc (Character/toUpperCase kc)
+                                  dp (get-in world [:d dc])]
+                              [ds (-> world
+                                      (assoc :p kp)
+                                      (update :t conj dp)
+                                      (update-in [:k] dissoc kc))]))
+          successors (map successor-world accessible-keys)
+          combine-levels (fn [[ds wo]] (+ ds (acquire-all-keys wo)))
+          ret (reduce min (map combine-levels successors))]
+      (clojure.pprint/pprint world)
+      (clojure.pprint/pprint ret)
+      ret)))
+
+(defn day18 []
+  (let [input (get-list-from-file (input-file))
+        world (build-world input)]
+    (part1 (acquire-all-keys world))
+    #_(part2)))