Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
ClojureProgramming Issue 7 problem with Maze/Ariadne's Zip
;; providing this for
;; I just copy-pasted the relevant code from
;; there were a couple changes. see comments below...
(defn maze
"Returns a random maze carved out of walls; walls is a set of
2-item sets #{a b} where a and b are locations.
The returned maze is a set of the remaining walls."
(let [paths (reduce (fn [index [a b]]
(merge-with into index {a [b] b [a]}))
{} (map seq walls))
start-loc (rand-nth (keys paths))]
(loop [walls walls
unvisited (disj (set (keys paths)) start-loc)]
(if-let [loc (when-let [s (seq unvisited)] (rand-nth s))]
(let [walk (iterate (comp rand-nth paths) loc)
;;; CompilerException java.lang.RuntimeException: Unable to resolve symbol: <8> in this context, compiling:(NO_SOURCE_PATH:14)
;;; so, I removed the <8> at the end of this line
;;; steps (zipmap (take-while unvisited walk) (next walk))]<8>
steps (zipmap (take-while unvisited walk) (next walk))]
(recur (reduce disj walls (map set steps))
(reduce disj unvisited (keys steps))))
(defn grid
[w h]
(set (concat
(for [i (range (dec w)) j (range h)] #{[i j] [(inc i) j]})
(for [i (range w) j (range (dec h))] #{[i j] [i (inc j)]}))))
(require '[ :as z])
(defn ariadne-zip
[labyrinth loc]
(let [paths (reduce (fn [index [a b]]
(merge-with into index {a [b] b [a]}))
{} (map seq labyrinth))
children (fn [[from to]]
(seq (for [loc (paths to)
:when (not= loc from)]
[to loc])))]
(z/zipper (constantly true)
[nil loc])))
(defn draw
[w h maze path]
(doto (javax.swing.JFrame. "Maze")
(doto (proxy [javax.swing.JPanel] []
(paintComponent [^java.awt.Graphics g]
(let [g (doto ^java.awt.Graphics2D (.create g)
(.scale 10 10)
(.translate 1.5 1.5)
(.setStroke (java.awt.BasicStroke. 0.4)))]
(.drawRect g -1 -1 w h)
(doseq [[[xa ya] [xb yb]] (map sort maze)]
(let [[xc yc] (if (= xa xb)
[(dec xa) ya]
[xa (dec ya)])]
(.drawLine g xa ya xc yc)))
(.translate g -0.5 -0.5)
(.setColor g java.awt.Color/RED)
(doseq [[[xa ya] [xb yb]] path]
(.drawLine g xa ya xb yb)))))
(.setPreferredSize (java.awt.Dimension.
(* 10 (inc w)) (* 10 (inc h))))))
(.setVisible true)))
;; wrapped up the example in a (testit)
;; UPDATED with the erratum from cgrand...but I still see hangs.
;; UPDATED with cgrand's comment--fixed, I think!
(defn testit []
(let [w 40, h 40 ;; changed so I could see if the maze really had issues or not.
grid (grid w h)
walls (maze grid)
;;testit (draw w h walls #{}) ;; add drawing just to look at walls
labyrinth (reduce disj grid walls)
places (distinct (apply concat labyrinth))
theseus (rand-nth places)
minotaur (rand-nth places)
full-path #(conj (z/path %) (z/node %)) ; erratum
;;testit2 (do (println "theseus" theseus "minotaur" minotaur)
;; (println "labyrinth" labyrinth)) ;; add for testing
path (->> theseus
(ariadne-zip labyrinth)
(iterate z/next)
(filter #(= minotaur (second (z/node %)))) ; erratum: replace first with second
first full-path rest)] ; erratum: replaced z/path by full-path
(draw w h walls path))
;; just load a repl via java -jar clojure-1.3.0.jar
;; paste this text, then invoke (testit) multiple times.

cgrand commented May 19, 2012

fixed here clojurebook/ClojureProgramming@9ffe8d4
thanks for the report


rogerallen commented May 20, 2012

Hi Christophe, I updated the code with your edit, but it still seems to hang for me. I think I got the edit right...can you take another look?

I made two sample testcases at the bottom of the gist. (testgood) returns the path. (testbad) hangs. If I run (testit) a few times, it produces other testcases that hang.

cgrand commented May 21, 2012


rogerallen commented May 22, 2012

Ah, that seems to fix it. See updated gist above--thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment