1
\$\begingroup\$

For a tilt maze general reference, you can refer to this example. The previous related code review discussion could be referred here.

The problem I want to resolve is to find all possible path (so that in the future I can find minimal path) from source to destination.

My major idea is:

  1. Represent the maze by flag which direction I can move from a specific cell
  2. Using recursion, move left/right, then move top/down, then left/right, then top/down, until the destination is reached

I'm not sure if my implementation is elegant, move left/right, then move top/down, then left/right, then top/down, until reach to destination, seems a bit hard-coded way. I'm wondering if there are any functional/logical bugs in my code -- even if I tested, but might be potential issues which I do not find yet.

  __ __ __ __ 
 |__   |__   |          
 |  |  |     |           
 |  |   __|  |      
 |     |   __|            
 |__|__ __ __|         

class MoveEnum:
    CAN_MOVE_LEFT = 1
    CAN_MOVE_RIGHT = 2
    CAN_MOVE_UP = 4
    CAN_MOVE_DOWN = 8

class Maze:
    def __init__(self, matrix):
        self.matrix = matrix
        self.results = []
    def move_left(self, x1, y1):
        while self.matrix[y1][x1] & MoveEnum.CAN_MOVE_LEFT:
            x1 -= 1
        return (x1, y1)
    def move_right(self, x1, y1):
        while self.matrix[y1][x1] & MoveEnum.CAN_MOVE_RIGHT:
            x1 += 1
        return (x1, y1)
    def move_up(self, x1, y1):
        while self.matrix[y1][x1] & MoveEnum.CAN_MOVE_UP:
            y1 -= 1
        return (x1, y1)
    def move_down(self, x1, y1):
        while self.matrix[y1][x1] & MoveEnum.CAN_MOVE_DOWN:
            print y1
            y1 += 1
        return (x1, y1)
    # find shortest move from x1 y1, to x2, y2
    def move_path(self, x1, y1, x2, y2, is_left_right, path):
        if x1 == x2 and y1 == y2:
            self.results.append(path[:])
        elif is_left_right:
            (x, y) = self.move_right(x1,y1)
            if x != x1:
                path.append((x, y))
                self.move_path(x, y, x2, y2, not is_left_right, path)
                path.pop(-1)
            (x, y) = self.move_left(x1,y1)
            if x != x1:
                path.append((x, y))
                self.move_path(x, y, x2, y2, not is_left_right, path)
                path.pop(-1)
        else:
            (x, y) = self.move_up(x1, y1)
            if y != y1:
                path.append((x, y))
                self.move_path(x, y, x2, y2, not is_left_right, path)
                path.pop(-1)
            (x, y) = self.move_down(x1, y1)
            if y != y1:
                path.append((x, y))
                self.move_path(x, y, x2, y2, not is_left_right, path)
                path.pop(-1)


if __name__ == "__main__":
    maze_matrix = [[MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_LEFT|MoveEnum.CAN_MOVE_DOWN, MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_LEFT|MoveEnum.CAN_MOVE_DOWN],
                   [MoveEnum.CAN_MOVE_DOWN, MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_DOWN, MoveEnum.CAN_MOVE_RIGHT|MoveEnum.CAN_MOVE_DOWN, MoveEnum.CAN_MOVE_LEFT|MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_DOWN],
                   [MoveEnum.CAN_MOVE_UP | MoveEnum.CAN_MOVE_DOWN, MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_DOWN|MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_LEFT, MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_DOWN],
                    [MoveEnum.CAN_MOVE_UP | MoveEnum.CAN_MOVE_DOWN | MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_UP | MoveEnum.CAN_MOVE_DOWN | MoveEnum.CAN_MOVE_LEFT, MoveEnum.CAN_MOVE_DOWN|MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_LEFT],
                   [MoveEnum.CAN_MOVE_UP, MoveEnum.CAN_MOVE_UP|MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_UP | MoveEnum.CAN_MOVE_RIGHT, MoveEnum.CAN_MOVE_LEFT]]
    maze = Maze(maze_matrix)
    maze.move_path(0,0,3,4,True,[])
    maze.move_path(0, 0, 3, 4, False, [])
    print maze.results
\$\endgroup\$
2
\$\begingroup\$

I'd still suggest using a closure, which I addressed in my last answer:

Your code is WET. As you write pretty much the same thing four times. Instead I'd use a builder function to remove this duplicate logic. This is as you can set the special changes in the builder function, and mutate the data in the returned function.

Take:

def _move(band, x_inc, y_inc):
    def inner(x, y):
        maze = self.maze
        while maze[y][x] & band:
            x += x_inc
            y += y_inc
        return x, y
    return inner

move_right = _move(2, 1, 0)

The name of MoveEnum could be changed to Moves, as the Enum part is useless when using it. I'd also change CAN_MOVE_* to just *, this is as it doesn't add any value. And so I'd much prefer it to be Moves.UP.

move_path is dodgy. You shouldn't have to pass a list to it, and it should really return results. Instead I would create another closure the outer function to create path, return results, and call the inner function. The inner function to perform the recursion as you currently have it.

\$\endgroup\$
  • \$\begingroup\$ Thanks Peilonrayz for the advices. Actually I have a high level question want to consult you, wondering if I need to record the places (cell x,y location) have been visited before? I have tested and there is no deadlock situation, but I am not confident if need a visited matrix as similar to what we did in BFS, DFS to avoid visit the same path again? \$\endgroup\$ – Lin Ma Nov 19 '16 at 7:18
  • \$\begingroup\$ Hi Peilonrayz, trying to practice closure, and found your definition of def _move(band, x_inc, y_inc): does not need to have self as first parameter? Is it a typo or on purpose? Thanks. \$\endgroup\$ – Lin Ma Nov 20 '16 at 22:12
  • 1
    \$\begingroup\$ For your first comment I didn't talk about move_path and won't. I mostly made this answer so I could reiterate my point. For you second comment I don't think you wrote it right, "found your definition of _move does not need to have self as first parameter?" If you meant (1) it doesn't need self as a parameter, then I'd respond with it doesn't. For (2) if you say it does, then if it's a class method maybe, look at my last answer. In this example I did make a mistake as in inner I use self where I should have used global maze, but it's not a method. \$\endgroup\$ – Peilonrayz Nov 21 '16 at 1:50
  • 1
    \$\begingroup\$ @LinMa I think your two comments answer each-other, ;P maze = self.maze is the self I'm on about \$\endgroup\$ – Peilonrayz Nov 26 '16 at 13:58
  • 1
    \$\begingroup\$ There is no best. Either you create one that is used in a class input(self, ...) or you make one that is a plain function input(...). Also can you not link me your posts, IMO it's rude, and you don't seem to want to use my suggestions. \$\endgroup\$ – Peilonrayz Nov 27 '16 at 1:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.