2D Maze solver using recursion in Python

Question

A company I interviewed for sent me a coding problem to solve. The problem was to find a solution to a maze, not necessarily the shortest one. The input would be like so:

###_###
#_____#
#_##_##
#_##__#
#_#####  

The output would be:

###a###
#dcb__#
#e##_##
#f##__#
#g#####  

Walls are represented by '#' and empty space represented by '_'. There can only be a single entrance and a single exit. The entrance will always be in the first row and the exit will always be in the last row. The path should be outlined by the alphabet. If the path requires more than 26 steps, then start over from 'a'.

My solution is like so:

1. Mark entrance as '+' and exit as '-'
2. Call solve() for starting point.
3. Loop neighbors that have empty space to move to and haven't been visited, using a generator.
4. Add neighbor to a list 'paths' that contain the points visited and call solve() for the latest point.
5. If the current point does not have any neighbors to move to, then we've reached a dead-end. So backtrack by popping that point from the 'paths' list, mark it as '!' in the maze and call solve() on the previous point.
6. The function completes when '-' is reached.

Here is the code for it.

class MazeRunner:

    def __init__(self, file_path):
        self.maze = self.load_maze(file_path)
        self.Point = collections.namedtuple('Point', 'row col')
        self.char_wheel = ord('a')
        self.paths = []

    def load_maze(self, file_path):
        with open(file_path,'r') as f:
            maze = [list(line.rstrip()) for line in f.readlines()]
        return maze

    def show_maze(self):
        for point in self.paths:
            self.maze[point.row][point.col] = chr(self.char_wheel)
            self.char_wheel += 1

            if self.char_wheel > ord('z'):
                self.char_wheel = ord('a')

        for row in self.maze:
            print(row)

    def mark_startstop(self):
        #Mark starting point with '+'
        col_ = self.maze[0].index('_')
        self.maze[0][col_] = '+'

        #Mark stopping point with '-'
        col_ = self.maze[-1].index('_')
        self.maze[-1][col_] = '-'

    def adjacent(self, current):
        yield self.Point(current.row-1, current.col)
        yield self.Point(current.row+1, current.col)
        yield self.Point(current.row, current.col-1)
        yield self.Point(current.row, current.col+1)

    def neighbors(self, current):
        for pos in self.adjacent(current):
            if pos.row in range(0,len(self.maze)) and pos.col in range(0,len(self.maze[0])):
                if self.maze[pos.row][pos.col] in ['_','-']:
                    yield pos

    def solve(self, current):

        print('\nPathing --> ',self.paths)
        print('Attempting solve('+str(current)+')\n')

        #Base cases
        if len(self.paths) < 1:
            print('Unsuccessful')
            return False

        elif self.maze[current.row][current.col] == '-':
            print('Maze completed!')
            return True

        #Recursive case
        else:
            for point in self.neighbors(current):
                print('\tChecking out '+str(point)+' - neighbor of '+str(current))
                if  self.maze[point.row][point.col] in ['_','-'] and point not in self.paths:
                    self.paths.append(point)
                    return self.solve(self.paths[-1])
                else:
                    print('\tSkipping '+str(point))


        #Handle Dead-end back-tracking
        self.maze[current.row][current.col] = '!'
        temp = self.paths.pop()
        print('\tReached Dead-end. Back-tracking. Popped '+str(temp))
        return self.solve(self.paths[-1])


    def find_path(self):

        self.mark_startstop()
        start_col = self.maze[0].index('+')
        start_row = 0
        self.paths.append(self.Point(start_row, start_col))
        self.solve(self.paths[-1])

def main():  

    parser = ArgumentParser('Maze Runner', description="This program finds solution to mazes given as input")
    parser.add_argument('--path', default='maze.txt', help='Path of the file containing the maze')

    args = parser.parse_args()

    path = args.path
    solver = MazeRunner(path)

    print('Maze loaded.')
    solver.show_maze()

    solver.find_path()
    solver.show_maze()  

How would you make it better in terms of time/space complexity and readability?

Answer 1

Some initial impressions that I'd note if I was an interviewer:

1. if len(self.paths) < 1 is better written as if len(self.paths) == 0 or if not self.paths
2. In self.neighbors you perform a check to see if an adjacent node is outside the maze. Try moving this logic into self.adjacent
3. Instead of solving recursively, which will fail for mazes longer than 1000 steps, instead use a while self.paths or similar
4. If you want to improve speed slightly (at the cost of space), consider pre-allocating self.paths, by making it large and filled with None. Then you can have a pointer to the current index and manipulate in the same way. However this leads to its own issues
5. For further improvements, consider using BFS instead of your current DFS, and implementing a bidirectional search. This should in theory make the search up to twice as fast. However, there's nothing strictly wrong with what you have
6. Consider first parsing your maze and change it to an array of ints. You could use bit masking to store information about each flag. If you convert "#" => 0b0000, "_" => 0b0001, "-"/"+" => 0b0011, you can check if it is possible to access a neighbor by checking if self.maze[i][j] & 0b0001. You can check if you've reached your goal by doing if self.maze[i][j] & 0b0010. You can keep track of which nodes you've already visited and store that in the third bit with self.maze[i][j] |= 0b0100 and then check if you've visited a node using if self.maze[i][j] & 0b0100.

If you want a better explanation of bit masking, please ask and I'll write something together.

EDIT: I threw together a working example, which uses bit masking and BFS (note that to change it to DFS you only have to edit current = self.paths.popleft() to current = self.paths.pop().

import collections
import string
import time

class MazeRunner:

    def __init__(self, file_path):
        self.maze = self.load_maze(file_path)
        self.Point = collections.namedtuple('Point', 'row col parent')
        self.paths = collections.deque()

    def load_maze(self, file_path):
        with open(file_path,'r') as f:
            maze = [list(line.rstrip()) for line in f.readlines()]
        maze_formatted = [["#_".find(l) for l in row] for row in maze]
        maze_formatted[-1] = [i*3 for i in maze_formatted[-1]]
        return maze_formatted

    def show_maze(self):
        for row in self.maze:
            s = ""
            for col in row:
                if str(col) in string.ascii_lowercase:
                    s += col
                else:
                    s += "# "[col&0b001]
            print(s)

    def neighbors(self, p):
        if p.row > 0 and self.maze[p.row-1][p.col] & 0b001:
            yield self.Point(p.row-1, p.col, p)
        if p.row < len(self.maze)-1 and self.maze[p.row+1][p.col] & 0b001:
            yield self.Point(p.row+1, p.col, p)
        if p.col > 0 and self.maze[p.row][p.col-1] & 0b001:
            yield self.Point(p.row, p.col-1, p)
        if p.col < len(self.maze[0])-1 and self.maze[p.row][p.col+1] & 0b001:
            yield self.Point(p.row, p.col+1, p)


    def solve(self):
        solution_found = False
        while self.paths:
            current = self.paths.popleft()
            if self.maze[current.row][current.col] & 0b010:
                solution_found = True
                print('Solution found!')
                break

            for point in self.neighbors(current):
                if not self.maze[point.row][point.col] & 0b100:
                    self.paths.append(point)
                    self.maze[point.row][point.col] |= 0b100;

        if not solution_found:
            return;

        final_path = []
        while current:
            final_path.append(current)
            current = current.parent

        final_path = final_path[::-1]
        for i, node in enumerate(final_path):
            self.maze[node.row][node.col] = string.ascii_lowercase[i%26]

    def find_path(self):
        start_col = self.maze[0].index(0b001)
        start_row = 0
        self.paths.append(self.Point(start_row, start_col, None))
        t0 = time.clock()
        self.solve()
        t1 = time.clock()
        print("Solution found in %.2fms" % ((t1-t0)*1000,))

def main():  

    path = "maze.txt"
    solver = MazeRunner(path)

    solver.find_path()
    solver.show_maze() 

if __name__ == "__main__":
    main()

This code always finds the (or rather one of) the shortest paths, and is about 5-10 times faster for some larger maze examples that I've tested it with.