coding dojo - maze solving

babashka-maze-solving-clojure-asciinema.md

core.clj

#!/usr/bin/env bb

;; To run this file:
;;
;; * Install Babashka: https://github.com/borkdude/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)

;; USER INPUT

(defn to-int [string]
  (try
    (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))


;; MAZE GENERATION


(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)]
          (recur
            (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)]})))


;; Maze PRINTING


(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)]})
               (cond
                 (= portal [i j]) " ▒▒▒"
                 (= player [i j]) "  @ "
                 (visited  [i j]) "  . "
                 :else            "    ")
               (cond
                 (= 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 "+")))


;; DISTANCE MAP CALCULATION


(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}))
      count
      (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 https://github.com/jeroenvanwijgerden/portalmaze)


(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)
                 set)}))

(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]
   (cond
     (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))))


;; SUPER-GLUE

(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: https://github.com/babashka/book/issues/6
      (print-maze state))
    (if (= (:player state) (:portal state))
      (println "The portal has been found!!!")
      (recur (update-state state)))))