# Find path from source to destination in tilt maze

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


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.

• 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 Nov 19 '16 at 7:18
• 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. – Lin Ma Nov 20 '16 at 22:12
• 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 Nov 21 '16 at 1:50
• @LinMa I think your two comments answer each-other, ;P maze = self.maze is the self I'm on about – Peilonrayz Nov 26 '16 at 13:58
• 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. – Peilonrayz Nov 27 '16 at 1:54