Last active
May 28, 2020 13:14
-
-
Save ivos/848ac47049966ea4ebc74e3eccd38dce to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment