4
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Have you submitted your solution yet? What feedback did you get? \$\endgroup\$ – 200_success Jul 10 '18 at 4:45
  • \$\begingroup\$ @200_success Yes, I had already submitted my code before posting here. There wasn't much of a feedback from the interviewer but there were follow-up questions about the choices I made such as my use of recursion, generators and time-complexity of the program. \$\endgroup\$ – Apoorva Vinod Jul 10 '18 at 23:01
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you, wonderful insights. The part about bit masking is interesting. I did not know that bit masking would be faster than string comparisons, I will take that into account next time I come across a similar scenario. I knew recursion wouldn't be a feasible option for larger mazes. I kinda wanted to bait them into asking me about that scalability issue though. Thank you for taking the time to write down a working example! \$\endgroup\$ – Apoorva Vinod Jul 10 '18 at 23:55
  • 1
    \$\begingroup\$ In this case, the bit masking wasn't extremely helpful, even if it did provide a speedup. However, the power of masking comes when you want to check for multiple properties at once. If we use 32/64 bit integers, we can check up to 32/64 flags in a single comparison using if (number & bitmask) == magic_number (e.g. if (number & 0b10101) == 0b10001 checks if the first and fifth bit are set, and the third bit is not set). The applications can be pretty niche, but it's a great trick when applicable. \$\endgroup\$ – maxb Jul 11 '18 at 6:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.