amalloy-4clojure-solution106.clj

;; amalloy's solution to Number Maze
;; https://4clojure.com/problem/106

(let [paths (fn [[curr :as path]]
              (for [op [* / +]
                    :let [next (op curr 2)]
                    :when (integer? next)]
                (cons next path)))
      bfs (fn [choices]
              (mapcat paths choices))]
  (fn [start end]
    (let [goal (comp #{end} first)]
      (->> [[start]]
           (iterate bfs)
           (map #(filter goal %))
           (filter seq)
           ffirst
           count))))

;; much faster, prunes already-tried numbers
(let [paths (fn [[curr :as path]]
              (for [op [* / +]
                    :let [next (op curr 2)]
                    :when (integer? next)]
                (cons next path)))
      bfs (fn [[found choices]]
            (reduce (fn [[found search-space] [dest :as path]]
                      [(conj found dest)
                       (if (found dest)
                         search-space
                         (conj search-space path))])
                    [found []]
                    (mapcat paths choices)))]
  (fn [start end]
    (let [goal (comp #{end} first)]
      (->> [#{} [[start]]]
           (iterate bfs)
           (map second)
           (map #(filter goal %))
           (filter seq)
           ffirst
           time))))

;; faster still, guessing not to bother with solutions that involve 
;; a number greater than 4N (thus preventing infinite combinatorial
;; explosion even when solution is long)

(let [paths (fn [[curr :as path]]
              (for [op [* / +]
                    :let [next (op curr 2)]
                    :when (integer? next)]
                (cons next path)))
      bfs (fn [max [found choices]]
            (reduce (fn [[found search-space] [dest :as path]]
                      [(conj found dest)
                       (if (or (>= dest max)
                               (found dest))
                         search-space
                         (conj search-space path))])
                    [found []]
                    (mapcat paths choices)))]
  (def solve (fn [start end]
               (let [goal (comp #{end} first)
                     threshold (* 4 (max start end))]
                 (->> [#{} [[start]]]
                      (iterate #(bfs threshold %))
                      (map second)
                      (map #(filter goal %))
                      (filter seq)
                      ffirst
                      reverse
                      time)))))