Stack and Queue M....

Part B: Find the path of a maze by using a stack Your program uses a LinkedStack to check whether the maze has a 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.

Part C: Find the path of a maze by using a queue Use a LinkedQueue instead of LinkedStack to perform the task described in part 2.

******************Part B (LinkedStack) NEED HELP ********

from grid import Grid from linkedstack import LinkedStack from stack import ArrayStack from linkedQueue import LinkedQueue from node import Node from arrays import Array #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 = '.' stack = ArrayStack() 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 counter = 0 #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) if counter == 0: stack.pop() return stack def main(): maze = getMazeGridFromFile() tempStack = ArrayStack() print(str(maze)) (startRow, startColumn) = findStartPos(maze) result = getPath(startRow, startColumn, maze) print(maze) print('----------') if result != None: print("Maze has no solved: ") 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() 

*************(Part C LinkedQueue) NEED HELP*******

from grid import Grid from stack import ArrayStack #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 getOut(row, column, maze): stack = ArrayStack() stack.push((row, column)) while not stack.isEmpty(): (row, column) = stack.peek() if maze[row][column] == 'T': return stack elif maze[row][column] != '.': maze[row][column] = '.' counter = 0 if row != 0 and not maze[row - 1][column] in ('*', '.'): stack.push((row - 1, column)) counter += 1 if row + 1 != maze.getHeight() and not maze[row + 1][column] in ('*','.'): stack.push((row + 1, column)) counter += 1 if column + 1 != maze.getWidth() and not maze[row][column + 1] in ('*','.'): stack.push((row, column + 1)) counter += 1 if column != 0 and not maze[row][column - 1] in ('*','.'): stack.push((row, column - 1)) counter += 1 if counter == 0: stack.pop() def main(): maze = getMazeGridFromFile() tempStack = ArrayStack() print(str(maze)) (startRow, startCol) = findStartPos(maze) result = getOut(startRow, startCol, maze) print(maze) print('----------') if result != None: print("Maze solved: ") (col, row) = result.pop() tempStack.push((col, row)) (pcol, prow) = (col, row) while not result.isEmpty(): (col, row) = result.pop() if (pcol, prow): tempStack.push((col, row)) maze[col][row] = "0" print(maze) print("Path: " + tempStack) else: print("No path out of this maze") main() 

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

********************stack******************

from arrays import Array class ArrayStack(object): """Represents a stack using Array."""  def __init__(self): self._items = Array(0, None) self._top = -1 def __len__(self): """The number of items in the stack."""  return self._top + 1 def __str__(self): """The string representation of the stack."""  s = "" for i in xrange(self._top + 1): s += str(self._items[i]) + " " return s def isEmpty(self): return self._top == -1 def peek(self): """Precondition: stack is not empty."""  return self._items[self._top] def push(self,newindex): """Add new item to top of stack."""  self._top += 1 self._items[self._top] = newindex def pop(self): tmp = self._items[self._top] self._top -= 1 return tmp 

***************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 

*************linkedQueue**************

from node import Node

class LinkedQueue(object): def __init__(self): # empty queue (self._front, self._rear, self._size) = (None, None, 0)

def __len__(self): return self._size

def isEmpty(self): return self._size == 0

def enqueue(self, item): # add to rear node = Node(item, None) if self._size == 0: # empty queue self._front = node else: self._rear.next = node self._rear = node self._size += 1

def peek(self): if self._front == None: return None return self._front.data

def dequeue(self): # remove from front if self._front == None: # empty queue return None val = self._front.data self._front = self._front.next if (self._size == 1): self._rear = None self._size = self._size - 1 return val

def clear(self): (self._front, self._rear, self._size) = (None, None, 0)

def __iter__(self): # overloads iter current = self._front while current != None: yield current.data current = current.next

def __str__(self): # overloads str s = "" current = self._front while current != None: s = s + " " + str(current.data) current = current.next return s

def __contains__(self, item): # overloads in operator current = self._front while current != None: if item == current.data: return True current = current.next return False

def testQueue(): q = LinkedQueue() for i in range(10): q.enqueue(i) print(str(q)) print(5 in q) while (not q.isEmpty()): print(q.dequeue())

if __name__ == "__main__": testQueue()

*******************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])

*************************Arrays*************************

class Array(object): def __init__(self, length, fillValue=None): self._items = [fillValue] * length

def __getitem__(self, i): return self._items[i]

def __setitem__(self, i, value): self._items[i] = value

def __len__(self): return len(self._items)

def __iter__(self): return iter(self._items)

def __str__(self): return " ".join([str(e) for e in self._items])

***************node************************

class Node(object): def __init__(self, data = None, nextNode = None): (self.data, self.next) = (data, nextNode)

def __str__(self): return str(self.data)

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

23 50 ************************************************** ******* ******** **** ******* ************** ************* ******** **** ******* ************** *** * *** **** P ************** ** ****** * *** **** **** ******* *** ** * ******* **** **** ******* *** ******* ** * ******************* **** ******* *** ******* ** ******************* **** ******* *** ******* ************************* **** ******* *** ** ********* **** *** *** ** **** **** ******************** **** *** ********** **** **** ****** **** *** ********** **** ************************* **** *** ********** **** ************************* **** *** **** ************ ************ **** ******** ********** ************ ************ **** ******** ********** ************ ******* **** ******** ***** ************ **** ******* **** ******************* **** ******* **** ************************************* ******* **** ************************************* ************ ************************************* 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) 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)