maze.clj

maze.clj

;; origin
(let [walls     (grid 2 2)
      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)
            steps (zipmap (take-while unvisited walk) (next walk))]
        (recur (reduce disj walls (map set steps))
               (reduce disj unvisited (keys steps))))
      walls)))

;; 
(let [walls             (grid 2 2)
      ;;=> #{#{[1 1] [0 1]} #{[1 0] [1 1]} #{[0 0] [0 1]} #{[0 0] [1 0]}}
      src->dsts         (->> walls
                             (map seq)
                             (reduce (fn [acc [a b]]
                                       (merge-with into acc {a [b] b [a]})) {}))
      ;;=> {[1 1] [[0 1] [1 0]], [0 1] [[1 1] [0 0]], [1 0] [[1 1] [0 0]], [0 0] [[0 1] [1 0]]}
      start-loc         (rand-nth (keys src->dsts))
      ;;=> [1 1]
      unvisited-loc-set (-> src->dsts
                            (keys)
                            (set)
                            (disj start-loc))
      ;;=> #{[0 0] [1 0] [0 1]}
      step-fn           (comp rand-nth src->dsts)]
  (loop [ret               walls
         unvisited-loc-set unvisited-loc-set]
    (if (empty? unvisited-loc-set)
      ret
      (let [loc            (rand-nth (seq unvisited-loc-set))
            walk-locs      (iterate step-fn loc)
            walk-loc->dsts (zipmap (take-while unvisited-loc-set walk-locs)
                                   (next walk-locs))]
        (recur (reduce disj ret (map set walk-loc->dsts))
               (reduce disj unvisited-loc-set (keys walk-loc->dsts)))))))