Find path from source to destination in tilt maze

Question

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

Answer 1

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.

• Lin Ma: 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?
• Lin Ma: 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.
• Peilonrayz: 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.
• Peilonrayz: @LinMa I think your two comments answer each-other, ;P maze = self.maze is the self I'm on about
• Peilonrayz: 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.