advent-22-12

(require 'clojure.set)

(defn get-node [grid coords & [data]]
  (let [node (get-in grid coords)] (get node data node)))

(defn get-neighbors [[x y :as current] unvisited grid]
  (->> [[x (inc y)] [x (dec y)] [(dec x) y] [(inc x) y]]
    (filter #(get-in grid %))
    (filter #(<= (- (get-node grid % "val") (get-node grid current "val")) 1))
    (filter unvisited)
))

(defn update-neighbors [grid distance neighbors]
  (reduce
    #(if (<= (get-node grid %2 "dis") distance) %1 (assoc-in %1 (conj %2 "dis") (+ 1 distance)))
    grid neighbors))

(defn get-next [neighbors grid end]
  (->> neighbors
    (sort-by #(get-node grid % "dis"))
    first
))

(defn ohai-Dijkstra [current unvisited queue grid end & [start]]
  (let [grid (if (nil? start) grid (assoc-in grid (conj current "dis") 0))]
  (if
    (= current end) (get-node grid current "dis")
    (let [neighbors (get-neighbors current unvisited grid)
          queue (clojure.set/union queue (set neighbors))
          grid (update-neighbors grid (get-node grid current "dis") neighbors)]
      (if
        (empty? queue) nil
        (let [node (get-next queue grid end)]
          (recur node (disj unvisited current) (disj queue node) grid end nil)))))))

(defn prepare-input [grid] (let [width (count (first grid))]
  (->> grid
    flatten
    (map-indexed vector)
    (reduce
      (fn [[nodes start end unvisited] [pos altitude]]
        (let
          [
           s (= altitude \S)
           e (= altitude \E)
           alt (cond s (int \a) e (int \z) :else (int altitude))
           pos [(quot pos width) (mod pos width)]
           item {"val" alt "pos" pos "dis" (+ 1 (* width (count nodes)))}
          ] [
             (assoc-in nodes pos item)
             (or start (when s pos))
             (or end (when e pos))
             (conj unvisited pos)
          ]))
      [grid nil nil #{} []])
)))

(with-open [rdr (clojure.java.io/reader "heights.in")]
  (let [
    grid (->> rdr line-seq (map vec) vec)
    [grid start end unvisited lowest] (prepare-input grid)
    lowest (->> grid flatten (filter #(= (% "val") 97)) (map #(% "pos")))
  ]
    (println (ohai-Dijkstra start unvisited #{} grid end true))
    (println (->> lowest (map #(ohai-Dijkstra % unvisited #{} grid end true)) (filter some?) (apply min)))
))