AOC 2021 day 12 with somewhat general backtracking function in clojure

backtracking.clj

(def graph-1
  [[:start :A]
   [:start :b]
   [:A :c]
   [:A :b]
   [:b :d]
   [:A :end]
   [:b :end]])

(def graph-str
  "fs-end
he-DX
fs-he
start-DX
pj-DX
end-zg
zg-sl
zg-pj
pj-he
RW-he
fs-DX
pj-RW
zg-RW
start-pj
he-WI
zg-he
pj-fs
start-RW")

(defn graph-from-str [s]
  (->>
   (clojure.string/split s #"-|\R")
   (map keyword)
   (partition 2)
   (map vec)
   vec))

(def graph-2 (graph-from-str graph-str))

(defn small-cave? [node]
  (let [c (-> node name first str)]
    (= c (clojure.string/lower-case c))))

(defn small-caves [pg]
  (->> pg
       flatten
       (filter small-cave?)))

(defn choices [g v]
  (->> g
       (filter #((set %) v))
       flatten
       (filter #(not= % v))
       set))

(defn backtrack [choice-fn reduction-fn coll]
  (loop [acc coll choice-path [] choicepoint-stack [(choice-fn coll [])]]
    (let [depth (count choice-path)
          choicepoint (get choicepoint-stack depth)
          choices (if choicepoint choicepoint (choice-fn acc choice-path))
          choice (first choices)]
      (if (and (zero? depth) (not choice))
        acc
        (if (not choice)
          (recur (reduction-fn acc choice-path) (pop choice-path) (if (not= depth (count choicepoint-stack)) (pop choicepoint-stack) choicepoint-stack))
          (recur acc (conj choice-path choice) (assoc choicepoint-stack depth (clojure.set/difference choices #{choice}))))))))

(defn solve-1 [graph]
  (backtrack
   (fn [m p] (cond
               (empty? p) #{:start}
               (= :end (peek p)) #{}
               :else (clojure.set/difference (choices (:graph m) (last p)) (set (small-caves p)))))
   (fn [m p] (if (-> p peek (= :end)) (update m :paths-taken conj p) m))
   {:graph graph}))

(defn solve-2 [graph]
  (backtrack
   (fn [m p] (cond
               (empty? p) #{:start}
               (= :end (peek p)) #{}
               (->> p small-caves frequencies vals (every? #(> 2 %))) (clojure.set/difference (choices (:graph m) (last p)) #{:start})
               :else (clojure.set/difference (choices (:graph m) (last p)) (set (small-caves p)))))
   (fn [m p] (if (-> p peek (= :end)) (update m :paths-taken conj p) m))
   {:graph graph}))


(comment
  (-> graph-1
      solve-2
      :paths-taken)
=> 
([:start :b :end]
 [:start :b :d :b :end]
 [:start :b :d :b :A :end]
 [:start :b :d :b :A :c :A :end]
 [:start :b :A :end]
 [:start :b :A :b :end]
 [:start :b :A :b :A :end]
 [:start :b :A :b :A :c :A :end]
 [:start :b :A :c :A :end]
 [:start :b :A :c :A :b :end]
 [:start :b :A :c :A :b :A :end]
 [:start :b :A :c :A :c :A :end]
 [:start :A :end]
 [:start :A :b :end]
 [:start :A :b :d :b :end]
 [:start :A :b :d :b :A :end]
 [:start :A :b :d :b :A :c :A :end]
 [:start :A :b :A :end]
 [:start :A :b :A :b :end]
 [:start :A :b :A :b :A :end]
 [:start :A :b :A :b :A :c :A :end]
 [:start :A :b :A :c :A :end]
 [:start :A :b :A :c :A :b :end]
 [:start :A :b :A :c :A :b :A :end]
 [:start :A :b :A :c :A :c :A :end]
 [:start :A :c :A :end]
 [:start :A :c :A :b :end]
 [:start :A :c :A :b :d :b :end]
 [:start :A :c :A :b :d :b :A :end]
 [:start :A :c :A :b :A :end]
 [:start :A :c :A :b :A :b :end]
 [:start :A :c :A :b :A :b :A :end]
 [:start :A :c :A :b :A :c :A :end]
 [:start :A :c :A :c :A :end]
 [:start :A :c :A :c :A :b :end]
 [:start :A :c :A :c :A :b :A :end])



)