# Find path from source to destination in tilt maze (part 2)

For a tilt maze general reference, you can refer to for example, this one.

Previous related code review discussion could be referred by this, and my major ideas how to define tilt maze data structure is learned from Peilonrayz. Since a large part of code/logics changed (e.g. I involved visited matrix) and I decide to make a new post.

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 the recursive way, 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. It seems a bit hard-coded way.

I'm wondering if 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, x, y):
self.matrix = matrix
self.results = []
self.positin=(x,y)
self.visited=[[False]*len(matrix[0]) for _ in range(len(matrix))]
def reset_visited(self):
self.visited = [[False] * len(self.matrix[0]) for _ in range(len(self.matrix))]
def _move(band, x_inc, y_inc):
def inner(self):
x,y=self.positin
while self.matrix[y][x] & band and (x+x_inc) < len(self.matrix[0]) \
and (y+y_inc)<len(self.matrix) and not self.visited[y+y_inc][x+x_inc]:
x+=x_inc
y+=y_inc
self.visited[y][x] = True
self.positin=(x,y)
return inner
move_left = _move(MoveEnum.CAN_MOVE_LEFT,-1, 0)
move_right = _move(MoveEnum.CAN_MOVE_RIGHT, 1, 0)
move_up= _move(MoveEnum.CAN_MOVE_UP,0,-1)
move_down = _move(MoveEnum.CAN_MOVE_DOWN, 0, 1)
# find shortest move from x1 y1, to x2, y2
def move_path(self, x2, y2, is_left_right, path):
x1 = self.positin[0]
y1 = self.positin[1]
self.visited[y1][x1] = True
if x1 == x2 and y1 == y2:
self.results.append(path[:])
return
elif is_left_right:
self.move_right()
(x,y)=self.positin
if x != x1:
path.append((x, y))
self.move_path(x2, y2, not is_left_right, path)
path.pop(-1)
self.positin=(x1,y1)
self.move_left()
(x, y) = self.positin
if x != x1:
path.append((x, y))
self.move_path(x2, y2, not is_left_right, path)
path.pop(-1)
self.positin = (x1, y1)
else:
self.move_up()
(x, y) = self.positin
if y != y1:
path.append((x, y))
self.move_path(x2, y2, not is_left_right, path)
path.pop(-1)
self.positin = (x1, y1)
self.move_down()
(x, y) = self.positin
if y != y1:
path.append((x, y))
self.move_path(x2, y2, not is_left_right, path)
path.pop(-1)
self.positin = (x1, y1)

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,0,0)
maze.move_path(3,4,True,[])
maze.reset_visited()
maze.positin=(0,0)
maze.move_path(3,4,False,[])
print maze.results