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:
- Mark entrance as '+' and exit as '-'
- Call solve() for starting point.
- Loop neighbors that have empty space to move to and haven't been visited, using a generator.
- Add neighbor to a list 'paths' that contain the points visited and call solve() for the latest point.
- 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.
- 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.index('_') self.maze[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)): 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.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?