Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
coding dojo - maze solving
#!/usr/bin/env bb
;; To run this file:
;; * Install Babashka:
;; (for mac users: `brew install borkdude/brew/babashka`)
;; * If needed make sure babashka `bb` is on your PATH
;; (so the hash-bang at the start of this file will work)
;; * Run it from a terminal like you would run normal source:
;; `./core.clj` (make sure the file has executable rights)
;; * Or run it from the terminal via bb: `bb core.clj`
;; * Run `./core.clj -h` to see the commandline options
;; To work with babashka in a REPL flow:
;; * Start a babashka nrepl in your terminal: `bb --nrepl-server`
;; * Then, in your IDE connect with that server and port (localhost:1667 by default)
;; Finally, to enjoy the live searching of the player you might have to resize your console
;; (depending on the size of the maze you've chosen)
(defn to-int [string]
(Integer. string)
(catch Exception)))
(defn valid-int? [int]
(and (integer? int) (pos? int) (< int 33)))
(def validate-msg "Must be a positive integer <= 32")
(def cli-options
[["-c" "--cols COLS" "Number of columns in the maze"
:default 8
:parse-fn to-int
:validate [valid-int? validate-msg] ]
["-r" "--rows ROWS" "Number of rows in the maze"
:default 8
:parse-fn to-int
:validate [valid-int? validate-msg]]
["-h" "--help"]])
(def options (tools.cli/parse-opts *command-line-args* cli-options))
(defn north-of [[row col]] [(dec row) col])
(defn south-of [[row col]] [(inc row) col])
(defn west-of [[row col]] [row (dec col)])
(defn east-of [[row col]] [row (inc col)])
(defn neighbours [rows cols cell]
(filter (fn [[i j]] (and (< -1 i rows) (< -1 j cols))) ((juxt north-of east-of south-of west-of) cell)))
(defn visited? [fallen-walls rows cols cell]
(some fallen-walls (for [n (neighbours rows cols cell)] #{n cell})))
(defn find-unvisited-neighbours [fallen-walls rows cols cell]
(let [n (neighbours rows cols cell)]
(remove #(visited? fallen-walls rows cols %) n)))
(defn generate-maze [rows cols]
(loop [fallen-walls #{}
backtrackstack '([0 0])]
(if-some [cell (peek backtrackstack)]
(if-some [unvn (seq (find-unvisited-neighbours fallen-walls rows cols cell))]
(let [next (rand-nth unvn)]
(conj fallen-walls #{next cell})
(conj backtrackstack next)))
(recur fallen-walls (pop backtrackstack)))
{:fallen-walls fallen-walls
:cols cols
:rows rows
:portal [(rand-int rows) (rand-int cols)]})))
(defn print-maze [{:keys [fallen-walls rows cols portal player visited]}]
(doseq [_ (range cols)]
(print "+---"))
(println "+")
(doseq [i (range rows)]
(doseq [j (range cols)]
(print (if (fallen-walls #{[i j] [i (dec j)]})
(= portal [i j]) " ▒▒▒"
(= player [i j]) " @ "
(visited [i j]) " . "
:else " ")
(= portal [i j]) "|▒▒▒"
(= player [i j]) "| @ "
(visited [i j]) "| . "
:else "| "))))
(println "|")
(doseq [j (range cols)]
(print (if (fallen-walls #{[i j] [(inc i) j]}) "+ " "+---")))
(println "+")))
(defn fallen? [fallen-walls wall]
(contains? fallen-walls wall))
(defn distance [fallen-walls cell directionf]
(loop [current cell
next (directionf current)
count 0]
(if (not (fallen? fallen-walls #{current next}))
(recur next (directionf next) (inc count)))))
(defn distance-map [fallen-walls cell]
{:n (distance fallen-walls cell north-of)
:e (distance fallen-walls cell east-of)
:s (distance fallen-walls cell south-of)
:w (distance fallen-walls cell west-of)})
;; MAZE SOLVING (Courtesy of
(def offset {:n [-1 0] :e [0 1] :s [1 0] :w [0 -1]})
(def opposite {:n :s :e :w :s :n :w :e})
(defn adj [pos dir]
(map + pos (offset dir)))
(defn entered-new-junction? [state]
(not (contains? (:junctions state) (:player state))))
(defn scan [state]
(update state :junctions assoc (:player state)
{:direction-of-origin (opposite (peek (:steps state)))
:directions-to-visit (->> (distance-map (:fallen-walls state) (:player state))
(filter (fn [[dir dist]]
(and (pos? dist)
(not (contains? (:junctions state) (adj (:player state) dir))))))
(map first)
(defn maybe-move-forwards [state]
(if-let [random-direction-to-visit (first (get-in state [:junctions (:player state) :directions-to-visit]))]
(-> state
(update :player #(adj % random-direction-to-visit))
(update-in [:junctions (:player state) :directions-to-visit] disj random-direction-to-visit)
(update :steps conj random-direction-to-visit))
(assoc state :forward? false)))
(defn move-backwards [state]
(let [dir-to-move-backwards-in (get-in state [:junctions (:player state) :direction-of-origin])]
(-> state
(update :player #(adj % dir-to-move-backwards-in))
(update :steps conj dir-to-move-backwards-in)
;; hack which results in less code (and a couple of redundant extra calls)
(assoc :forward? true))))
(defn next-state [state]
(entered-new-junction? state) (scan state)
(:forward? state) (maybe-move-forwards state)
:else (move-backwards state)))
(defn update-state [state]
(let [new-state (next-state state)
visited (conj (:visited new-state) (:player new-state))]
(-> new-state
(assoc :oldpos (:player state))
(assoc :visited visited))))
(when (:errors options)
(println (:errors options))
(System/exit 1))
(when ((comp :help :options) options)
(println (:summary options))
(System/exit 1))
(let [cols ((comp :cols :options) options)
rows ((comp :rows :options) options)
maze (generate-maze rows cols)
init-state (-> maze
(assoc :player (list (rand-int rows) (rand-int cols)))
(assoc :portal (list (rand-int rows) (rand-int cols)))
(assoc :oldpos (list -1 -1))
(assoc :steps [])
(assoc :junctions {})
(assoc :visited #{})
(assoc :forward? true))]
(loop [state init-state]
(Thread/sleep 100)
(when (not (= (:player state) (:oldpos state)))
(println "\033[H\033[2J") ; equals 'clear' command in shell -> see:
(print-maze state))
(if (= (:player state) (:portal state))
(println "The portal has been found!!!")
(recur (update-state state)))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment