Factor out A* implementation

[adventofcode2019.git] / src / adventofcode2019 / lib.clj

diff --git a/src/adventofcode2019/lib.clj b/src/adventofcode2019/lib.clj
index e81b3062011eb7d0149008ad82c4ab0cabb12535..aaeac0ca8f64ca9652c516494d1fe3b234027a38 100644 (file)
--- a/src/adventofcode2019/lib.clj
+++ b/src/adventofcode2019/lib.clj
@@ -2,7 +2,8 @@
   [:require [clojure.string :as str]
    [clojure.edn :as edn]
    [clojure.java.io :as io]
-   [clojure.java.shell :refer [sh]]])
+   [clojure.java.shell :refer [sh]]
+   [clojure.data.priority-map :refer [priority-map-by]]])
 
 (defn get-list-from-file
   ([file-name]
@@ -24,6 +25,36 @@
   (+ (Math/abs (- ax bx))
      (Math/abs (- ay by))))
 
+(defn a-star
+  "succ :: state -> [state]
+  cost :: cost -> state -> cost
+  heur :: state -> cost
+  init :: state
+  des? :: state -> bool"
+  [succ cost heur init des?]
+  (let [update-openl (fn [ol sn pt cs]
+                       (reduce (fn [o p]
+                                 (assoc o p [(cost cs p) (heur p)]))
+                               ol (remove sn (succ pt))))
+        openl (priority-map-by (fn [[ag ah] [bg bh]]
+                                 (let [cmp (compare (+ ag ah) (+ bg bh))
+                                       cmp-g (compare ag bg)
+                                       cmp-h (compare ah bh)]
+                                   (if-not (zero? cmp)
+                                     cmp
+                                     (if-not (zero? cmp-g)
+                                       cmp-g
+                                       cmp-h)))))]
+    (loop [openl (assoc openl init [0 (heur init)])
+           seen #{init}]
+      (let [[point [dist _]] (peek openl)]
+        (cond
+          (empty? openl) [nil ##Inf]
+          (des? point) [point dist]
+          :else (let [openl (update-openl (pop openl) seen point dist)
+                      seen (apply conj seen (keys openl))]
+                  (recur openl seen)))))))
+
 (defn mmap [f m]
   (zipmap (keys m) (map f (vals m))))