4

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)))
Improve this question
1

1 Answer 1

Reset to default
8

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Incidentally, you can do things rather more nicely here by working with x/y pairs as actual objects, rather than two distinct numbers. For example, if pos is [4 3] and dir is [0 -1], then (map + pos dir) yields [4 2]. Much easier than managing x and y separately all over the place.
Valid point about the unnecessary optimization by utilizing the bitfields to store the information about each individual cell. Excellent answer and very useful feedback.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.