drunken-walk.clj

(defn neighbors
  ([size yx] (neighbors [[0 0] [1 1] [-1 -1] [-1 1] [1 -1] [-1 0] [1 0] [0 -1] [0 1]] size yx))
  ([deltas size yx]
     (filter (fn [new-yx]
               (every? #(< -1 % size) new-yx))
             (map #(vec (map + yx %))
                deltas))))

(defn density [matrix y x]
  (let [neighbors (map #(get-in matrix %) (neighbors (count matrix) [y x]))
       full-neighbors (:full (frequencies neighbors))]
        (max 1 (* full-neighbors full-neighbors))))

(defn drunkards-walk
  [grid num-empty-cells]
  (let [height (count grid)
        width (count (first grid))]
    ; Guard against impossible demands.
    (when (<= num-empty-cells (* width height))

      (loop [grid grid
             ; Step 1: pick a random cell.
             x (rand-int width)
             y (rand-int height)
             empty-cells 0]

        ; Step 2: if we're done, return the grid.
        (if (= empty-cells num-empty-cells)
          grid

          (let [cell-was-full? (= (get-in grid [y x]) :full)
                ; Step 3: walk one step in a random direction.
                weights {:north (density grid (dec y) x)
                        :south (density grid (inc y) x)
                        :east (density grid y (inc x))
                        :west (density grid y (dec x))}
                direction (rand-nth (flatten [
                    (repeat (weights :north) :north)
                    (repeat (weights :south) :south)
                    (repeat (weights :east) :east)
                    (repeat (weights :west) :west)
                  ]))]

            ; Step 4: back to step 2.
            (recur (assoc-in grid [y x] :empty)
                   (case direction
                     :east (bound-between (inc x) 0 (dec width))
                     :west (bound-between (dec x) 0 (dec width))
                     x)
                   (case direction
                     :north (bound-between (dec y) 0 (dec height))
                     :south (bound-between (inc y) 0 (dec height))
                     y)
                   (if cell-was-full?
                     (inc empty-cells)
                     empty-cells))))))))

(-> (full-grid 200 200)
    (drunkards-walk 5000)
    draw-grid)