Idiomatic Clojure implementation of maze generation algorithm
Question: I am implementing algorithms to create and solve mazes in both Python and
Clojure. I have experience with Python and am working to learn Clojure. I am
likely doing too literal of a conversion from Python to Clojure and I am
looking for input on a more idiomatic way to implement the code in Clojure.

First the working Python implementation

    
    
    import random
    
    N, S, E, W = 1, 2, 4, 8
    DX = {E: 1, W: -1, N: 0, S: 0}
    DY = {E: 0, W: 0, N: -1, S: 1}
    OPPOSITE = {E: W, W: E, N: S, S: N}
    
    
    def recursive_backtracker(current_x, current_y, grid):
        directions = random_directions()
        for direction in directions:
            next_x, next_y = current_x + DX[direction], current_y + DY[direction]
            if valid_unvisited_cell(next_x, next_y, grid):
                grid = remove_walls(current_y, current_x, next_y, next_x, direction, grid)
                recursive_backtracker(next_x, next_y, grid)
        return grid
    
    
    def random_directions():
        directions = [N, S, E, W]
        random.shuffle(directions)
        return directions
    
    
    def valid_unvisited_cell(x, y, grid):
        return (0 <= y <= len(grid) - 1) and (0 <= x <= len(grid[y]) - 1) and grid[y][x] == 0
    
    
    def remove_walls(cy, cx, ny, nx, direction, grid):
        grid[cy][cx] |= direction
        grid[ny][nx] |= OPPOSITE[direction]
        return grid
    

Now the Clojure version that I have so far. Currently I believe it is not
working because I am using the for macro which is passing a symbol into recur
when it needs to be passing a vector. As I was trying to find a solution for
this issue I felt like I was trying too hard to force the code to be Python
which prompted this question. Any guidance is appreciated.

    
    
    (ns maze.core)
    
    (def DIRECTIONS { :N 1, :S 2, :E 4, :W 8})
    (def DX { :E 1, :W -1, :N 0, :S 0})
    (def DY { :E 0, :W 0, :N -1, :S 1})
    (def OPPOSITE { :E 8, :W 4, :N 2, :S 1})
    
    (defn make-empty-grid
      [w h]
      (vec (repeat w (vec (repeat h 0)))))
    
    (defn valid-unvisited-cell?
      [x y grid]
      (and
        (<= 0 y (- (count grid) 1)) ; within a column
        (<= 0 x (- (count (nth grid y)) 1)) ; within a row
        (= 0 (get-in grid [x y])))) ; unvisited
    
    (defn remove-walls
      [cy, cx, ny, nx, direction, grid]
      (-> grid
        (update-in [cy cx] bit-or (DIRECTIONS direction))
        (update-in [ny nx] bit-or (OPPOSITE direction))))
    
    (defn recursive-backtracker
      [current-x current-y grid]
      (loop [current-x current-x current-y current-x grid grid]
        (let [directions (clojure.core/shuffle [:N :S :E :W])]
          (for [direction directions]
            (let [next-x (+ current-x (DX direction))
                  next-y (+ current-y (DY direction))]
              (if (valid-unvisited-cell? next-x next-y grid)
                (loop next-x next-y (remove-walls current-x current-y next-x next-y direction grid)))))
          grid)))
    


Answer: This seems like a basically reasonable translation of the Python code into
Clojure (including some stuff beginners often miss - nicely done)...until we
get to `recursive-backtracker`, the heart of the problem. You can't just
transliterate the Python here, because your algorithm assumes mutability of
`grid`: you call yourself recursively four times inside the `for` loop, and
you need changes made to the grid to be reflected. That's not how Clojure
works, so this whole thing doesn't work. The actual error you're getting is an
unrelated syntax error (double-check the interface to loop/recur), but it's
not really relevant here since you have to rewrite the function anyway, so
I'll leave it at that.

Now, how can you rewrite this function to work without mutating `grid`? As is
so often the case, you can use `reduce`: for each of the four directions, you
call `recursive-backtracker`, getting back a modified grid, and you make sure
to use _that modified grid_ for the next recursive call. The general outline
will look like this:

    
    
    (defn recursive-backtracker
      [current-x current-y grid]
      (reduce (fn [grid direction]
                (let [next-x (+ current-x (DX direction))
                      next-y (+ current-y (DY direction))]
                  (if (valid-unvisited-cell? next-x next-y grid)
                    (recursive-backtracker next-x next-y
                                           (remove-walls current-x current-y next-x next-y
                                                         direction grid))
                    grid)))
              grid, (clojure.core/shuffle [:N :S :E :W])))
    

With that definition, `(recursive-backtracker 0 0 (make-empty-grid 5 5))`
produces `[[2 5 6 3 5] [4 10 9 6 9] [14 3 1 12 4] [12 6 3 9 12] [10 11 3 3
9]]` \- is that a valid maze? It looks okay, but I don't know. You probably
don't either. Which brings me to another point: using integers and bitwise
arithmetic is an exercise in pointless optimization. Instead, make each entry
in the grid be a map, or a set, containing keywords saying what directions are
open for it. Then on inspection you can at least get a general idea for
whether the maze is self-consistent.

