1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.