from node import Node from linkedStack import LinkedStack from grids import Grid #Get Maze from File def getMazeGridFromFile(): filename = "maze.txt" fileObj = open(filename, 'r') firstLine = fileObj.readline().strip().split() rows = int(firstLine[0]) columns = int(firstLine[1]) print(str(rows) + " " + str(columns)) maze = Grid(rows, columns) for row in range(rows): line = fileObj.readline().strip() column = 0 for ch in line: maze[row][column] =ch column += 1 return maze #Start Position def findStartPos(maze): """Returns the position of the start symbol in the grid."""  for row in range(len(maze)): for column in range(len(maze[row])): if maze[row][column] == 'P': return row, column return -1, -1 def getPath(startRow, startColumn, maze): letter = '0' stack = LinkedStack() stack.push(Node((startRow, startColumn), None)) while not stack.isEmpty(): node = stack.pop() (row, column) = node.data if maze[row][column] == 'T': return node elif maze[row][column] != letter: maze[row][column] = letter #try West if column > 0 and maze[row][column - 1] not in('*', letter): stack.push(Node((row, column-1), node)) #Try South if row + 1 != len(maze) and not maze[row +1][column] in ('*', letter): stack.push(Node((row + 1, column), node)) #Try East if column + 1 != len(maze[row]) and not maze[row][column+1] in ('*', letter): stack.push(Node((row, column + 1), node)) #Try North if row + 0 and not maze[row - 1][column] in ('*', letter): stack.push(Node((row - 1, column), node)) return None def main(): maze = getMazeGridFromFile() tempStack = LinkedStack() #print(str(maze)) print("Find the path of a maze by using a STACK: ") (startRow, startColumn) = findStartPos(maze) result = getPath(startRow, startColumn, maze) print(maze) print('-----------------------------------------------') if result != None: print("Maze has solved: ") path = LinkedStack() path.push(Node.data) node = node.next while (node != None): (i, j) = node.next path.push((i, j)) maze[i][j] = '0' maze[startRow][startColumn] n = 0 s = " " while not path.isEmpty(): s += str(path.pop() + ", ") n += 1 if n % 10 == 0: s = s + " " s = s.rstrip(", ") print(s) else: path = LinkedStack() path.push(node.data) node = node.next while (node != None): (i, j) = node.next path.push((i, j)) maze[i][j] = '0' maze[startRow][startColumn] n = 0 s = " " while not path.isEmpty(): s += str(path.pop() + ", ") n += 1 if n % 10 == 0: s = s + " " s = s.rstrip(", ") print(s) main() 

=================Other code file to run the Maze Correctly===============

********************node.py*********************************

"""node.py""" """Node class implementation""" class Node(object): def __init__(self, data = None, nextNode = None): (self.data, self.next) = (data, nextNode) def __str__(self): return str(self.data) 

**********linkedStack**************

"""linkedStack.py  implements LinkedStack """ from node import Node class LinkedStack(object): def __init__(self): # empty list (self._top, self._size) = (None, 0) def __len__(self): return self._size def isEmpty(self): return self._top == None def push(self, item): self._top = Node(item, self._top) self._size += 1 def peek(self): if self._top == None: return None return self._top.data def pop(self): # returns the data at top if it is not empty if self._top == None: # empty stack return None val = self._top.data self._top = self._top.next self._size = self._size - 1 return val def clear(self): self._size = 0 self._top = None def __iter__(self): # overloads iter current = self._top while current != None: yield current.data current = current.next def __str__(self): # overloads str s = "" current = self._top while current != None: s = str(current.data) + " " + s current = current.next return s def __contains__(self, item): # overloads in operator current = self._top while current != None: if item == current.data: return True current = current.next return False ******************Grid********************* 

from arrays import Array class Grid(object): def __init__(self, rows, columns, fillValue=None): self._data = Array(rows, list()) for i in range(rows): self._data[i] = Array(columns, fillValue) def __getitem__(self, i): return self._data[i] def getHeight(self): return len(self._data) def getWidth(self): return len(self._data[0]) def __iter__(self): return iter(self._data) def __len__(self): return len(self._data) def __str__(self): return " ".join([str(e) for e in self._data]) 

**********************************maze.txt**************************

************************************************** ******* ******** **** ******* ************** ************* ******** **** ******* ************** *** * *** **** P ************** ** ****** * *** **** **** ******* *** ** * ******* **** **** ******* *** ******* ** * ******************* **** ******* *** ******* ** ******************* **** ******* *** ******* ************************* **** ******* *** ** ********* **** *** *** ** **** **** ******************** **** *** ********** **** **** ****** **** *** ********** **** ************************* **** *** ********** **** ************************* **** *** **** ************ ************ **** ******** ********** ************ ************ **** ******** ********** ************ ******* **** ******** ***** ************ **** ******* **** ******************* **** ******* **** ************************************* ******* **** ************************************* ************ ************************************* T ************************************************** 

************************Find maze by using a stack ***************************

Your program should use a LinkedStack to check whether the maze has solution or not. If the maze has solutions, your program should mark the cells on the path of a solution with letter O except the first (P) and the last (T). You will also output the length of the path along with the row and column index of each cell on the path from P to T.

O0O OoO0OOO 00000000000000*"0 0 RRROO0000000OOO (7, 7),18, 7), (9, 7),10, 7),10, 6),10, 5),10, 4),10, 3),111, 3), 112, 3), 13, 3),14, 3,14, 4, 14, 5),114,),14 7),114, 8),(24, 9),24, 10),114, 11) 1, 12, (14, 13), (14, 14),(13, 14) 112, 14),(11, 141 (10. 141 (9, 141 (9. 151.(9. 1). 9, 17),19,10),19, 19),110, 19) (11 19), (12, 19),(13,19),124 19) 115, 19)1E, 19) 17, 191),(18, 19),(18, 20), (18, 2),118, 22),(18, 23),(18, 24),(18, 25),(18, 26),18.27) 18, 281, (18, 29), (18, 30),(8 31),118, 32),(17. 321, (16, 32), (16, 33)-(26, 34)-116 35) :16, 361(16, 37), (17, 37),[18, 37), 119, 37).(20. 37), (21. 37), (21. 38), (21, 39),(21, 40), (21, 41),(21, 42), (21, 43),(21, 44), 121, 45),21, 46),21, 47), (21, 48),(21, 49)