solve-maze.clj

(ns sample.solve-maze)

(defn visited
  [maze]
  (concat (vals (:transitions maze))
          (keys (:transitions maze))))

(def escape
  {
   :clear  "\033[2J"
   :reset  "\u001B[0m"
   :black  "\u001B[30m"
   :red    "\u001B[31m"
   :green  "\u001B[32m"
   :yellow "\u001B[33m"
   :blue   "\u001B[34m"
   :cyan   "\u001B[36m"
   :gray   "\u001B[37m"
   })

(defn str-point
  [color]
  (str (color escape) "\u2588\u2588"))

(defn str-row
  [maze y]
  (str
    (apply str
           (for [x (range (:width maze))]
             (let [point [x y]]
               (str-point
                 (cond
                   (= point (:start maze)) :red
                   (= point (:end maze)) :blue
                   (some #{point} (:solution maze)) :green
                   (some #{point} (:open maze)) :cyan
                   (some #{point} (visited maze)) :yellow
                   ((:points maze) point) :gray
                   :else :black)))))
    (System/lineSeparator)))

'(defn print-maze [maze _] (println "===>" (dissoc maze :points)))
(defn print-maze
  [maze last?]
  (print (str
           (:clear escape)
           (apply str (for [y (range (:height maze))]
                        (str-row maze y)))
           (:reset escape)
           (when-not last? (System/lineSeparator))))
  (flush)
  (Thread/sleep (:delay maze)))

(defn neighbors
  [maze [x y]]
  (let [around [[(dec x) y] [(inc x) y] [x (dec y)] [x (inc y)]]
        valid (keep #((:points maze) %) around)
        not-seen (filter #(and (not (some #{%} (:open maze)))
                               (not (some #{%} (visited maze)))) valid)
        result (case (:algorithm maze)
                 :deterministic not-seen
                 :random (shuffle not-seen))]
    (vec result)))

(defn next-step
  [maze]
  (let [opens (:open maze)
        found-end (some #{(:end maze)} (keys (:transitions maze)))]
    (if (or (empty? opens)
            found-end)
      (assoc maze :status :solved)
      (let [open-item (first opens)
            new-neighbors (neighbors maze open-item)
            with-neighbors (concat opens new-neighbors)
            with-neighbors-wout-item (remove #(= open-item %) with-neighbors)
            new-transitions (map #(vector % open-item) new-neighbors)]
        (-> maze
            (assoc :open with-neighbors-wout-item)
            (update :transitions #(apply conj % new-transitions)))))))

(defn find-solution
  [maze]
  (loop [prev (:end maze)
         maze maze]
    (if prev
      (do
        (print-maze maze false)
        (recur ((:transitions maze) prev)
               (update maze :solution #(conj % prev))))
      (print-maze maze true))))

(defn solve
  [maze]
  (loop [maze (assoc maze :status :solving
                          :open [(:start maze)]
                          :transitions {}
                          :solution [])]
    (print-maze maze false)
    (if (not= :solved (:status maze))
      (recur (next-step maze))
      (find-solution maze))))

(def width 11)
(def height 11)
(def maze {:width     width
           :height    height
           :points    (set
                        (for [x (range width)
                              y (range height)
                              :when (or (even? x) (even? y))
                              ;:when (or (even? x) (zero? (mod y 5)))
                              ]
                          [x y]))
           :start     [0 0]
           :end       [8 9]
           ;:algorithm :deterministic
           :algorithm :random
           :delay     10
           })

(solve maze)