maze_runner.py

"""
Breadth-first search maze runner

maze_runner.py path-to-maze-file

Make sure your map has an entrance and exit on left & right side
respectively.

EXAMPLE:
###########
          #
# ##### # #
#   #   # #
### # ### #
#     #   #
# # ### ###
# #   #   #
# ### #  ##
#     #
###########
"""

import sys
import queue


class Square(object):

    def __init__(self, x, y, parent=None):
        self.x, self.y, self.parent = x, y, parent

    def get_adjacent(self):
        # return all squares above, below, left and right
        return [
            Square(self.x + 1, self.y, self),
            Square(self.x - 1, self.y, self),
            Square(self.x, self.y + 1, self),
            Square(self.x, self.y - 1, self),
        ]


class Maze(object):

    def __init__(self, matrix):
        self.matrix = matrix
        self.matrix_size = len(self.matrix) - 1

        # find the entrance and exit points left/right of the maze

        self.entrance_x, self.entrance_y = 0, 0
        self.exit_x, self.exit_y = self.matrix_size, 0

        for counter, row in enumerate(self.matrix):

            if row[0] == ' ':
                self.entrance_y = counter

            if row[len(row) - 1] == ' ':
                self.exit_y = counter

        if 0 in (self.entrance_y, self.exit_y):
            raise ValueError(
                "Must be entrance, exit on left side, right side of maze")

    def is_open(self, x, y):
        try:
            return self.char_at(x, y) == ' '
        except IndexError:
            return False

    def solve(self):
        """
        Find the end square. Returns None if no exit found.
        """
        # search key
        sq = Square(self.entrance_x, self.entrance_y)

        q = queue.Queue()
        q.put(sq)

        while not q.empty():

            sq = q.get()

            # have we found the exit?
            if sq.x == self.exit_x and sq.y == self.exit_y:
                return sq

            # mark visited
            self.mark(sq.x, sq.y, '-')

            # if open then add adjacent square to queue
            for adj in sq.get_adjacent():
                if self.is_open(adj.x, adj.y):
                    q.put(adj)

        return None

    def render(self):
        for row in self.matrix:
            print("".join(row))

    def mark(self, x, y, ch):
        self.matrix[y][x] = ch

    def char_at(self, x, y):
        return self.matrix[y][x]

    def clear(self):
        # remove all the marked squares
        for y, row in enumerate(self.matrix):
            for x, _ in enumerate(row):
                if self.char_at(x, y) == '-':
                    self.mark(x, y, ' ')

    def run(self):
        """
        Finds route, then prints maze
        """

        sq = self.solve()
        self.clear()

        if sq is None:
            print("No exit found")
            self.render()
            return

        # change squares to show route
        self.mark(sq.x, sq.y, '>')

        while sq.parent is not None:
            sq = sq.parent
            self.mark(sq.x,  sq.y, '*')

        self.render()


if __name__ == "__main__":

    try:
        filename = sys.argv[1]
    except IndexError:
        print("Please provide a filename")
        sys.exit(1)

    matrix = []

    with open(filename, "r") as fp:
        for line in fp.readlines():
            matrix.append([c for c in line[:-1]])

    maze = Maze(matrix)
    maze.run()