- Complete the code to solve a maze - Discuss related data structures topics Pro
ID: 3755798 • Letter: #
Question
- Complete the code to solve a maze - Discuss related data structures topicsProgramming ----------- In this part, you will complete the code to solve a maze.
Begin with the "solveMaze.py" starter file. This file contains comment instructions that tell you where to add your code.
Each maze resides in a text file (with a .txt extension). The following symbols are used in the mazes: BARRIER = '-' # barrier FINISH = 'F' # finish (goal) OPEN = 'O' # open step START = 'S' # start step VISITED = '#' # visited step
There are 4 mazes you can use to test your code: maze1.txt maze2.txt maze3.txt maze4.txt The instructor may use other mazes to test your code.
Make sure your output matches the following expected output: maze1 output.txt maze2 output.txt maze3 output.txt maze4 output.txt
See the "Course Project Guidance" document for programming guidance.
Discussion ---------- In this part you will discuss the following related data structures topics:
1) Discuss the structure, behavior, and practical uses of the two data structures (grid and stack) used in our maze solving program.
2) Discuss the space and time efficiencies of the stack-based backtracking algorithm used in our maze solving program.
3) Discuss how you could use a graph data structure to represent and solve a maze. ~~~~~~~~~~~~~~~~~~~ Files in the same folder ------------------------ Depending on which implementation you use for part 1, you may need to include other files in the same folder.
Imports ------- Depending on which implementation you use for part 1, you may need to include additional import statement(s).
Part 1 ------ This week's example files include 2 different implementations of this function. Choose one and copy that implementation here.
Part 2 ------ The courses and their prerequisites are shown in a comment. The courses are each named with a single capital letter.
Part 3 ------ The courses and their prerequisites are shown in a comment.
Part 4 ------ Use an appropriate graph iterator.
Part 5 ------ Use an appropriate graph iterator.
Part 6 ------ If you used the stack-based implementation of the topologicalSort() function, it can produce a different, correct ordering for each run of your program.
The following are some of the possible correct orderings: B A C E D F G H A C E B D F G H A B C E D F G H A B C D F E G H B A C D F E G H
~~~~~~~~~~~~~~~~~~~~
>>> Enter a file name for the maze: maze1.txt The maze: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOF --------------------------------------------------
Maze solved: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- ########--------------O--OO-------O-O---O----O---- -------#---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------#---O-------O--O-O--------------------O---- ---#####---O-------O--OOO--------------------O---- -------#---O-------O-------------------------O---- -------#---O--#####################----------O---- ---#####---O--#----#----#--------------------O---- ---#----------#----#----###############------O---- ---#######----#----#-------------------------O---- ---#----------#----#------#------------------O---- ---############----###########--O------------O---- --------O----------#------#-----O------------O---- --------O----------#------#-----######-------O---- --------OOOOOO-----#------------#----#-------O---- -------------------##############----#####---O---- -------------------------O-----------#-------O---- -------------------------O-----------#------------ -------------------------O-----------############F --------------------------------------------------
>>>
~~~~~~~~~~~~~~~~~~~~~~~~~~~
23 50 -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOF --------------------------------------------------
~~~~~~~~~~~~~~~~~~~~~~
>>> Enter a file name for the maze: maze2.txt The maze: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- OOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOF --------------------------------------------------
This maze does not have a start symbol. >>>
~~~~~~~~~~~~~~~~~~~
23 50 -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- OOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOF --------------------------------------------------
~~~~~~~~~~~~~~~~~~~~~
>>> Enter a file name for the maze: maze3.txt The maze: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOO --------------------------------------------------
There is no solution for this maze. >>>
~~~~~~~~~~~~~~~~~
23 50 -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOO --------------------------------------------------
~~~~~~~~~~~~~~~~~~~~
>>> Enter a file name for the maze: maze4.txt The maze: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOFOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOO --------------------------------------------------
Maze solved: -------------------------------------------------- -------##############################--------O---- -------#--------------O-------------#--------O---- -------#--------------O---OOOOF####-#---OOOOOO---- ########--------------O--OO-------#-#---O----O---- -------#---#########--O-OO--------###OOOO----O---- -------#---#-------#--O-O--------------------O---- ---#####---#-------#--OOO--------------------O---- -------#---#-------#-------------------------O---- -------#---#--#####################----------O---- ---#####---#--#----#----#--------------------O---- ---#----------#----#----###############------O---- ---#######----#----#-------------------------O---- ---#----------#----#------#------------------O---- ---############----###########--#------------O---- --------#----------#------#-----#------------O---- --------#----------#------#-----######-------O---- --------######-----#------------#----#-------O---- -------------------##############----#####---O---- -------------------------#-----------#-------O---- -------------------------#-----------#------------ -------------------------#-----------############# --------------------------------------------------
>>>
~~~~~~~~~~~~~~~~~~~~~
23 50 -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOFOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOO --------------------------------------------------
~~~~~~~~~~~~~~~~~
""" Determines the solution to a maze problem. Uses a gid to represent the maze. This grid is input from a text file. Uses a stack-based backtracking algorithm.
Replace any "<your code>" comments with your own code statement(s) to accomplish the specified task. Do not change any other code.
The following files must be in the same folder: abstractcollection.py abstractstack.py arrays.py arraystack.py grid.py """
from arraystack import ArrayStack from grid import Grid
BARRIER = '-' # barrier FINISH = 'F' # finish (goal) OPEN = 'O' # open step START = 'S' # start step VISITED = '#' # visited step
def main(): maze = getMaze() print("The maze:") printMaze(maze) (startRow, startCol) = findStartPosition(maze) if (startRow, startCol) == (-1, -1): print("This maze does not have a start symbol.") return success = solveMaze(startRow, startCol, maze) if success: print("Maze solved:") printMaze(maze) else: print("There is no solution for this maze.") def getMaze(): """Reads the maze from a text file and returns a grid that represents it.""" name = input("Enter a file name for the maze: ") fileObj = open(name, 'r') firstLine = list(map(int, fileObj.readline().strip().split())) rows = firstLine[0] columns = firstLine[1] maze = Grid(rows, columns) for row in range(rows): line = fileObj.readline().strip() column = 0 for character in line: maze[row][column] = character column += 1 return maze
# Returns a tuple containing the row and column position of the start symbol. # If there is no start symbol, returns the tuple (-1, -1) def findStartPosition(maze): # Part 1: # <your code>
# Prints the maze with no spaces between cells. def printMaze(maze): # Part 2: # <your code> # (row,column) is the position of the start symbol in the maze. # Returns True if the maze can be solved or False otherwise. def solveMaze(row, column, maze): # States are tuples of coordinates of cells in the grid. stack = ArrayStack() stack.push((row, column)) while not stack.isEmpty(): (row, column) = stack.pop() if maze[row][column] == FINISH: return True if maze[row][column] == VISITED: continue
# Cell has not been visited. # Mark it as visited. maze[row][column] = VISITED # Push adjacent unvisited positions onto the stack: # Part 3: # <your code> return False
main()
~~~~~~~~~~~~~~~
""" File: abstractcollection.py Copyright 2015 by Ken Lambert
"""
class AbstractCollection(object): """An abstract collection implementation."""
# Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._size = 0 self._modCount = 0 if sourceCollection: for item in sourceCollection: self.add(item)
# Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return len(self) == 0 def __len__(self): """Returns the number of items in self.""" return self._size
def __str__(self): """Returns the string representation of self, using [] as delimiters.""" return "[" + ", ".join(map(str, self)) + "]"
def __eq__(self, other): """Returns True if self equals other, or False otherwise. Compares pairs of items in the two sequences generated by the iterators on self and other.""" if self is other: return True if type(self) != type(other) or len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True
def __add__(self, other): """Returns a new collection containing the contents of self and other.""" result = type(self)(self) for item in other: result.add(item) return result
def count(self, item): """Returns the number of instance of item in self.""" counter = 0 for nextItem in self: if item == nextItem: counter += 1 return counter
# These methods track and update the modCount, which is used to # prevent mutations within the context of an iterator (for loop)
def getModCount(self): """Returns the number of modifications to the collection.""" return self._modCount
def incModCount(self): """Increments the number of modifications to the collection.""" self._modCount += 1
~~~~~~~~~~~~~~~~~~
""" File: abstractstack.py Copyright 2015 by Ken Lambert
"""
from abstractcollection import AbstractCollection
class AbstractStack(AbstractCollection): """Represents an abstract stack."""
def __init__(self, sourceCollection): """Initializes the stack at this level.""" AbstractCollection.__init__(self, sourceCollection)
def add(self, item): """For compatibility with other collections.""" self.push(item)
~~~~~~~~~~~~~~~~~~
""" File: arrays.py Copyright 2015 by Ken Lambert
An Array is a restricted list whose clients can use only [], len, iter, and str.
To instantiate, use
<variable> = array(<capacity>, <optional fill value>)
The fill value is None by default. """
class Array(object): """Represents an array."""
def __init__(self, capacity, fillValue = None): """Capacity is the static size of the array. fillValue is placed at each position.""" self._items = list() for count in range(capacity): self._items.append(fillValue)
def __len__(self): """-> The capacity of the array.""" return len(self._items)
def __str__(self): """-> The string representation of the array.""" return str(self._items)
def __iter__(self): """Supports iteration over a view of an array.""" return iter(self._items)
def __getitem__(self, index): """Subscript operator for access at index.""" return self._items[index]
def __setitem__(self, index, newItem): """Subscript operator for replacement at index.""" self._items[index] = newItem
~~~~~~~~~~~~~~~
""" File: arraystack.py Copyright 2015 by Ken Lambert
"""
from arrays import Array from abstractstack import AbstractStack
class ArrayStack(AbstractStack): """An array-based stack implementation."""
# Class variable DEFAULT_CAPACITY = 10
# Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._items = Array(ArrayStack.DEFAULT_CAPACITY) AbstractStack.__init__(self, sourceCollection)
# Accessor methods def __iter__(self): """Supports iteration over a view of self. Visits items from bottom to top of stack.""" modCount = self.getModCount() cursor = 0 while cursor < len(self): yield self._items[cursor] if modCount != self.getModCount(): raise AttributeError("Illegal modification of backing store") cursor += 1
def peek(self): """Returns the item at the top of the stack. Precondition: the stack is not empty. Raises: KeyError if stack is empty.""" if self.isEmpty(): raise KeyError("The stack is empty") return self._items[len(self) - 1]
# Mutator methods def clear(self): """Makes self become empty.""" self._size = 0 self._modCount = 0 self._items = Array(ArrayStack.DEFAULT_CAPACITY)
def push(self, item): """Inserts item at top of the stack.""" # Resize array here if necessary if len(self) == len(self._items): tempArray = Array(len(self) * 2) for i in range(len(self)): tempArray[i] = self._items[i] self._items = tempArray self._items[len(self)] = item self._size += 1 self.incModCount()
def pop(self): """Removes and returns the item at the top of the stack. Precondition: the stack is not empty. Raises: KeyError if stack is empty. Postcondition: the top item is removed from the stack.""" if self.isEmpty(): raise KeyError("The stack is empty") oldItem = self._items[len(self) - 1] self._size -= 1 self.incModCount() # Resize the array here if necessary if len(self) <= .25 * len(self._items) and ArrayStack.DEFAULT_CAPACITY <= len(self._items) // 2: tempArray = Array(len(self._items) // 2) for i in range(len(self)): tempArray[i] = self._items[i] self._items = tempArray
return oldItem ~~~~~~~~~~~~~~~~~~~
""" File: grid.py Copyright 2015 by Ken Lambert
"""
from arrays import Array
class Grid(object): """Represents a two-dimensional array."""
def __init__(self, rows, columns, fillValue = None): self._data = Array(rows) for row in range(rows): self._data[row] = Array(columns, fillValue)
def getHeight(self): """Returns the number of rows.""" return len(self._data)
def getWidth(self): "Returns the number of columns.""" return len(self._data[0])
def __getitem__(self, index): """Supports two-dimensional indexing with [][].""" return self._data[index]
def __str__(self): """Returns a string representation of the grid.""" result = "" for row in range(self.getHeight()): for col in range(self.getWidth()): result += str(self._data[row][col]) + " " result += " " return result
def __iter__(self): """Yields the grid's items in row major order.""" row = 0 while row < self.getHeight(): column = 0 while column < self.getWidth(): yield self[row][column] column += 1 row += 1
def main(rows = 10, columns = 10, fillValue = 1): g = Grid(rows, columns, fillValue) print("The grid: ", g) for row in range(g.getHeight()): for column in range(g.getWidth()): g[row][column] = (row, column) print("The grid positions: ", g) print("The items in row major order:") for item in g: print(item)
if __name__ == "__main__": main()
~~~~~~~~~~~ Thanks in advance - Complete the code to solve a maze - Discuss related data structures topics
Programming ----------- In this part, you will complete the code to solve a maze.
Begin with the "solveMaze.py" starter file. This file contains comment instructions that tell you where to add your code.
Each maze resides in a text file (with a .txt extension). The following symbols are used in the mazes: BARRIER = '-' # barrier FINISH = 'F' # finish (goal) OPEN = 'O' # open step START = 'S' # start step VISITED = '#' # visited step
There are 4 mazes you can use to test your code: maze1.txt maze2.txt maze3.txt maze4.txt The instructor may use other mazes to test your code.
Make sure your output matches the following expected output: maze1 output.txt maze2 output.txt maze3 output.txt maze4 output.txt
See the "Course Project Guidance" document for programming guidance.
Discussion ---------- In this part you will discuss the following related data structures topics:
1) Discuss the structure, behavior, and practical uses of the two data structures (grid and stack) used in our maze solving program.
2) Discuss the space and time efficiencies of the stack-based backtracking algorithm used in our maze solving program.
3) Discuss how you could use a graph data structure to represent and solve a maze. ~~~~~~~~~~~~~~~~~~~ Files in the same folder ------------------------ Depending on which implementation you use for part 1, you may need to include other files in the same folder.
Imports ------- Depending on which implementation you use for part 1, you may need to include additional import statement(s).
Part 1 ------ This week's example files include 2 different implementations of this function. Choose one and copy that implementation here.
Part 2 ------ The courses and their prerequisites are shown in a comment. The courses are each named with a single capital letter.
Part 3 ------ The courses and their prerequisites are shown in a comment.
Part 4 ------ Use an appropriate graph iterator.
Part 5 ------ Use an appropriate graph iterator.
Part 6 ------ If you used the stack-based implementation of the topologicalSort() function, it can produce a different, correct ordering for each run of your program.
The following are some of the possible correct orderings: B A C E D F G H A C E B D F G H A B C E D F G H A B C D F E G H B A C D F E G H
~~~~~~~~~~~~~~~~~~~~
>>> Enter a file name for the maze: maze1.txt The maze: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOF --------------------------------------------------
Maze solved: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- ########--------------O--OO-------O-O---O----O---- -------#---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------#---O-------O--O-O--------------------O---- ---#####---O-------O--OOO--------------------O---- -------#---O-------O-------------------------O---- -------#---O--#####################----------O---- ---#####---O--#----#----#--------------------O---- ---#----------#----#----###############------O---- ---#######----#----#-------------------------O---- ---#----------#----#------#------------------O---- ---############----###########--O------------O---- --------O----------#------#-----O------------O---- --------O----------#------#-----######-------O---- --------OOOOOO-----#------------#----#-------O---- -------------------##############----#####---O---- -------------------------O-----------#-------O---- -------------------------O-----------#------------ -------------------------O-----------############F --------------------------------------------------
>>>
~~~~~~~~~~~~~~~~~~~~~~~~~~~
23 50 -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOF --------------------------------------------------
~~~~~~~~~~~~~~~~~~~~~~
>>> Enter a file name for the maze: maze2.txt The maze: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- OOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOF --------------------------------------------------
This maze does not have a start symbol. >>>
~~~~~~~~~~~~~~~~~~~
23 50 -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- OOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOF --------------------------------------------------
~~~~~~~~~~~~~~~~~~~~~
>>> Enter a file name for the maze: maze3.txt The maze: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOO --------------------------------------------------
There is no solution for this maze. >>>
~~~~~~~~~~~~~~~~~
23 50 -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOO --------------------------------------------------
~~~~~~~~~~~~~~~~~~~~
>>> Enter a file name for the maze: maze4.txt The maze: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOFOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOO --------------------------------------------------
Maze solved: -------------------------------------------------- -------##############################--------O---- -------#--------------O-------------#--------O---- -------#--------------O---OOOOF####-#---OOOOOO---- ########--------------O--OO-------#-#---O----O---- -------#---#########--O-OO--------###OOOO----O---- -------#---#-------#--O-O--------------------O---- ---#####---#-------#--OOO--------------------O---- -------#---#-------#-------------------------O---- -------#---#--#####################----------O---- ---#####---#--#----#----#--------------------O---- ---#----------#----#----###############------O---- ---#######----#----#-------------------------O---- ---#----------#----#------#------------------O---- ---############----###########--#------------O---- --------#----------#------#-----#------------O---- --------#----------#------#-----######-------O---- --------######-----#------------#----#-------O---- -------------------##############----#####---O---- -------------------------#-----------#-------O---- -------------------------#-----------#------------ -------------------------#-----------############# --------------------------------------------------
>>>
~~~~~~~~~~~~~~~~~~~~~
23 50 -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOFOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOO --------------------------------------------------
~~~~~~~~~~~~~~~~~
""" Determines the solution to a maze problem. Uses a gid to represent the maze. This grid is input from a text file. Uses a stack-based backtracking algorithm.
Replace any "<your code>" comments with your own code statement(s) to accomplish the specified task. Do not change any other code.
The following files must be in the same folder: abstractcollection.py abstractstack.py arrays.py arraystack.py grid.py """
from arraystack import ArrayStack from grid import Grid
BARRIER = '-' # barrier FINISH = 'F' # finish (goal) OPEN = 'O' # open step START = 'S' # start step VISITED = '#' # visited step
def main(): maze = getMaze() print("The maze:") printMaze(maze) (startRow, startCol) = findStartPosition(maze) if (startRow, startCol) == (-1, -1): print("This maze does not have a start symbol.") return success = solveMaze(startRow, startCol, maze) if success: print("Maze solved:") printMaze(maze) else: print("There is no solution for this maze.") def getMaze(): """Reads the maze from a text file and returns a grid that represents it.""" name = input("Enter a file name for the maze: ") fileObj = open(name, 'r') firstLine = list(map(int, fileObj.readline().strip().split())) rows = firstLine[0] columns = firstLine[1] maze = Grid(rows, columns) for row in range(rows): line = fileObj.readline().strip() column = 0 for character in line: maze[row][column] = character column += 1 return maze
# Returns a tuple containing the row and column position of the start symbol. # If there is no start symbol, returns the tuple (-1, -1) def findStartPosition(maze): # Part 1: # <your code>
# Prints the maze with no spaces between cells. def printMaze(maze): # Part 2: # <your code> # (row,column) is the position of the start symbol in the maze. # Returns True if the maze can be solved or False otherwise. def solveMaze(row, column, maze): # States are tuples of coordinates of cells in the grid. stack = ArrayStack() stack.push((row, column)) while not stack.isEmpty(): (row, column) = stack.pop() if maze[row][column] == FINISH: return True if maze[row][column] == VISITED: continue
# Cell has not been visited. # Mark it as visited. maze[row][column] = VISITED # Push adjacent unvisited positions onto the stack: # Part 3: # <your code> return False
main()
~~~~~~~~~~~~~~~
""" File: abstractcollection.py Copyright 2015 by Ken Lambert
"""
class AbstractCollection(object): """An abstract collection implementation."""
# Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._size = 0 self._modCount = 0 if sourceCollection: for item in sourceCollection: self.add(item)
# Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return len(self) == 0 def __len__(self): """Returns the number of items in self.""" return self._size
def __str__(self): """Returns the string representation of self, using [] as delimiters.""" return "[" + ", ".join(map(str, self)) + "]"
def __eq__(self, other): """Returns True if self equals other, or False otherwise. Compares pairs of items in the two sequences generated by the iterators on self and other.""" if self is other: return True if type(self) != type(other) or len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True
def __add__(self, other): """Returns a new collection containing the contents of self and other.""" result = type(self)(self) for item in other: result.add(item) return result
def count(self, item): """Returns the number of instance of item in self.""" counter = 0 for nextItem in self: if item == nextItem: counter += 1 return counter
# These methods track and update the modCount, which is used to # prevent mutations within the context of an iterator (for loop)
def getModCount(self): """Returns the number of modifications to the collection.""" return self._modCount
def incModCount(self): """Increments the number of modifications to the collection.""" self._modCount += 1
~~~~~~~~~~~~~~~~~~
""" File: abstractstack.py Copyright 2015 by Ken Lambert
"""
from abstractcollection import AbstractCollection
class AbstractStack(AbstractCollection): """Represents an abstract stack."""
def __init__(self, sourceCollection): """Initializes the stack at this level.""" AbstractCollection.__init__(self, sourceCollection)
def add(self, item): """For compatibility with other collections.""" self.push(item)
~~~~~~~~~~~~~~~~~~
""" File: arrays.py Copyright 2015 by Ken Lambert
An Array is a restricted list whose clients can use only [], len, iter, and str.
To instantiate, use
<variable> = array(<capacity>, <optional fill value>)
The fill value is None by default. """
class Array(object): """Represents an array."""
def __init__(self, capacity, fillValue = None): """Capacity is the static size of the array. fillValue is placed at each position.""" self._items = list() for count in range(capacity): self._items.append(fillValue)
def __len__(self): """-> The capacity of the array.""" return len(self._items)
def __str__(self): """-> The string representation of the array.""" return str(self._items)
def __iter__(self): """Supports iteration over a view of an array.""" return iter(self._items)
def __getitem__(self, index): """Subscript operator for access at index.""" return self._items[index]
def __setitem__(self, index, newItem): """Subscript operator for replacement at index.""" self._items[index] = newItem
~~~~~~~~~~~~~~~
""" File: arraystack.py Copyright 2015 by Ken Lambert
"""
from arrays import Array from abstractstack import AbstractStack
class ArrayStack(AbstractStack): """An array-based stack implementation."""
# Class variable DEFAULT_CAPACITY = 10
# Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._items = Array(ArrayStack.DEFAULT_CAPACITY) AbstractStack.__init__(self, sourceCollection)
# Accessor methods def __iter__(self): """Supports iteration over a view of self. Visits items from bottom to top of stack.""" modCount = self.getModCount() cursor = 0 while cursor < len(self): yield self._items[cursor] if modCount != self.getModCount(): raise AttributeError("Illegal modification of backing store") cursor += 1
def peek(self): """Returns the item at the top of the stack. Precondition: the stack is not empty. Raises: KeyError if stack is empty.""" if self.isEmpty(): raise KeyError("The stack is empty") return self._items[len(self) - 1]
# Mutator methods def clear(self): """Makes self become empty.""" self._size = 0 self._modCount = 0 self._items = Array(ArrayStack.DEFAULT_CAPACITY)
def push(self, item): """Inserts item at top of the stack.""" # Resize array here if necessary if len(self) == len(self._items): tempArray = Array(len(self) * 2) for i in range(len(self)): tempArray[i] = self._items[i] self._items = tempArray self._items[len(self)] = item self._size += 1 self.incModCount()
def pop(self): """Removes and returns the item at the top of the stack. Precondition: the stack is not empty. Raises: KeyError if stack is empty. Postcondition: the top item is removed from the stack.""" if self.isEmpty(): raise KeyError("The stack is empty") oldItem = self._items[len(self) - 1] self._size -= 1 self.incModCount() # Resize the array here if necessary if len(self) <= .25 * len(self._items) and ArrayStack.DEFAULT_CAPACITY <= len(self._items) // 2: tempArray = Array(len(self._items) // 2) for i in range(len(self)): tempArray[i] = self._items[i] self._items = tempArray
return oldItem ~~~~~~~~~~~~~~~~~~~
""" File: grid.py Copyright 2015 by Ken Lambert
"""
from arrays import Array
class Grid(object): """Represents a two-dimensional array."""
def __init__(self, rows, columns, fillValue = None): self._data = Array(rows) for row in range(rows): self._data[row] = Array(columns, fillValue)
def getHeight(self): """Returns the number of rows.""" return len(self._data)
def getWidth(self): "Returns the number of columns.""" return len(self._data[0])
def __getitem__(self, index): """Supports two-dimensional indexing with [][].""" return self._data[index]
def __str__(self): """Returns a string representation of the grid.""" result = "" for row in range(self.getHeight()): for col in range(self.getWidth()): result += str(self._data[row][col]) + " " result += " " return result
def __iter__(self): """Yields the grid's items in row major order.""" row = 0 while row < self.getHeight(): column = 0 while column < self.getWidth(): yield self[row][column] column += 1 row += 1
def main(rows = 10, columns = 10, fillValue = 1): g = Grid(rows, columns, fillValue) print("The grid: ", g) for row in range(g.getHeight()): for column in range(g.getWidth()): g[row][column] = (row, column) print("The grid positions: ", g) print("The items in row major order:") for item in g: print(item)
if __name__ == "__main__": main()
~~~~~~~~~~~ Thanks in advance - Complete the code to solve a maze - Discuss related data structures topics
Programming ----------- In this part, you will complete the code to solve a maze.
Begin with the "solveMaze.py" starter file. This file contains comment instructions that tell you where to add your code.
Each maze resides in a text file (with a .txt extension). The following symbols are used in the mazes: BARRIER = '-' # barrier FINISH = 'F' # finish (goal) OPEN = 'O' # open step START = 'S' # start step VISITED = '#' # visited step
There are 4 mazes you can use to test your code: maze1.txt maze2.txt maze3.txt maze4.txt The instructor may use other mazes to test your code.
Make sure your output matches the following expected output: maze1 output.txt maze2 output.txt maze3 output.txt maze4 output.txt
See the "Course Project Guidance" document for programming guidance.
Discussion ---------- In this part you will discuss the following related data structures topics:
1) Discuss the structure, behavior, and practical uses of the two data structures (grid and stack) used in our maze solving program.
2) Discuss the space and time efficiencies of the stack-based backtracking algorithm used in our maze solving program.
3) Discuss how you could use a graph data structure to represent and solve a maze. ~~~~~~~~~~~~~~~~~~~ Files in the same folder ------------------------ Depending on which implementation you use for part 1, you may need to include other files in the same folder.
Imports ------- Depending on which implementation you use for part 1, you may need to include additional import statement(s).
Part 1 ------ This week's example files include 2 different implementations of this function. Choose one and copy that implementation here.
Part 2 ------ The courses and their prerequisites are shown in a comment. The courses are each named with a single capital letter.
Part 3 ------ The courses and their prerequisites are shown in a comment.
Part 4 ------ Use an appropriate graph iterator.
Part 5 ------ Use an appropriate graph iterator.
Part 6 ------ If you used the stack-based implementation of the topologicalSort() function, it can produce a different, correct ordering for each run of your program.
The following are some of the possible correct orderings: B A C E D F G H A C E B D F G H A B C E D F G H A B C D F E G H B A C D F E G H
~~~~~~~~~~~~~~~~~~~~
>>> Enter a file name for the maze: maze1.txt The maze: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOF --------------------------------------------------
Maze solved: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- ########--------------O--OO-------O-O---O----O---- -------#---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------#---O-------O--O-O--------------------O---- ---#####---O-------O--OOO--------------------O---- -------#---O-------O-------------------------O---- -------#---O--#####################----------O---- ---#####---O--#----#----#--------------------O---- ---#----------#----#----###############------O---- ---#######----#----#-------------------------O---- ---#----------#----#------#------------------O---- ---############----###########--O------------O---- --------O----------#------#-----O------------O---- --------O----------#------#-----######-------O---- --------OOOOOO-----#------------#----#-------O---- -------------------##############----#####---O---- -------------------------O-----------#-------O---- -------------------------O-----------#------------ -------------------------O-----------############F --------------------------------------------------
>>>
~~~~~~~~~~~~~~~~~~~~~~~~~~~
23 50 -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOF --------------------------------------------------
~~~~~~~~~~~~~~~~~~~~~~
>>> Enter a file name for the maze: maze2.txt The maze: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- OOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOF --------------------------------------------------
This maze does not have a start symbol. >>>
~~~~~~~~~~~~~~~~~~~
23 50 -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- OOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOF --------------------------------------------------
~~~~~~~~~~~~~~~~~~~~~
>>> Enter a file name for the maze: maze3.txt The maze: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOO --------------------------------------------------
There is no solution for this maze. >>>
~~~~~~~~~~~~~~~~~
23 50 -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOOOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOO --------------------------------------------------
~~~~~~~~~~~~~~~~~~~~
>>> Enter a file name for the maze: maze4.txt The maze: -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOFOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOO --------------------------------------------------
Maze solved: -------------------------------------------------- -------##############################--------O---- -------#--------------O-------------#--------O---- -------#--------------O---OOOOF####-#---OOOOOO---- ########--------------O--OO-------#-#---O----O---- -------#---#########--O-OO--------###OOOO----O---- -------#---#-------#--O-O--------------------O---- ---#####---#-------#--OOO--------------------O---- -------#---#-------#-------------------------O---- -------#---#--#####################----------O---- ---#####---#--#----#----#--------------------O---- ---#----------#----#----###############------O---- ---#######----#----#-------------------------O---- ---#----------#----#------#------------------O---- ---############----###########--#------------O---- --------#----------#------#-----#------------O---- --------#----------#------#-----######-------O---- --------######-----#------------#----#-------O---- -------------------##############----#####---O---- -------------------------#-----------#-------O---- -------------------------#-----------#------------ -------------------------#-----------############# --------------------------------------------------
>>>
~~~~~~~~~~~~~~~~~~~~~
23 50 -------------------------------------------------- -------OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO--------O---- -------O--------------O-------------O--------O---- -------O--------------O---OOOOFOOOO-O---OOOOOO---- SOOOOOOO--------------O--OO-------O-O---O----O---- -------O---OOOOOOOOO--O-OO--------OOOOOOO----O---- -------O---O-------O--O-O--------------------O---- ---OOOOO---O-------O--OOO--------------------O---- -------O---O-------O-------------------------O---- -------O---O--OOOOOOOOOOOOOOOOOOOOO----------O---- ---OOOOO---O--O----O----O--------------------O---- ---O----------O----O----OOOOOOOOOOOOOOO------O---- ---OOOOOOO----O----O-------------------------O---- ---O----------O----O------O------------------O---- ---OOOOOOOOOOOO----OOOOOOOOOOO--O------------O---- --------O----------O------O-----O------------O---- --------O----------O------O-----OOOOOO-------O---- --------OOOOOO-----O------------O----O-------O---- -------------------OOOOOOOOOOOOOO----OOOOO---O---- -------------------------O-----------O-------O---- -------------------------O-----------O------------ -------------------------O-----------OOOOOOOOOOOOO --------------------------------------------------
~~~~~~~~~~~~~~~~~
""" Determines the solution to a maze problem. Uses a gid to represent the maze. This grid is input from a text file. Uses a stack-based backtracking algorithm.
Replace any "<your code>" comments with your own code statement(s) to accomplish the specified task. Do not change any other code.
The following files must be in the same folder: abstractcollection.py abstractstack.py arrays.py arraystack.py grid.py """
from arraystack import ArrayStack from grid import Grid
BARRIER = '-' # barrier FINISH = 'F' # finish (goal) OPEN = 'O' # open step START = 'S' # start step VISITED = '#' # visited step
def main(): maze = getMaze() print("The maze:") printMaze(maze) (startRow, startCol) = findStartPosition(maze) if (startRow, startCol) == (-1, -1): print("This maze does not have a start symbol.") return success = solveMaze(startRow, startCol, maze) if success: print("Maze solved:") printMaze(maze) else: print("There is no solution for this maze.") def getMaze(): """Reads the maze from a text file and returns a grid that represents it.""" name = input("Enter a file name for the maze: ") fileObj = open(name, 'r') firstLine = list(map(int, fileObj.readline().strip().split())) rows = firstLine[0] columns = firstLine[1] maze = Grid(rows, columns) for row in range(rows): line = fileObj.readline().strip() column = 0 for character in line: maze[row][column] = character column += 1 return maze
# Returns a tuple containing the row and column position of the start symbol. # If there is no start symbol, returns the tuple (-1, -1) def findStartPosition(maze): # Part 1: # <your code>
# Prints the maze with no spaces between cells. def printMaze(maze): # Part 2: # <your code> # (row,column) is the position of the start symbol in the maze. # Returns True if the maze can be solved or False otherwise. def solveMaze(row, column, maze): # States are tuples of coordinates of cells in the grid. stack = ArrayStack() stack.push((row, column)) while not stack.isEmpty(): (row, column) = stack.pop() if maze[row][column] == FINISH: return True if maze[row][column] == VISITED: continue
# Cell has not been visited. # Mark it as visited. maze[row][column] = VISITED # Push adjacent unvisited positions onto the stack: # Part 3: # <your code> return False
main()
~~~~~~~~~~~~~~~
""" File: abstractcollection.py Copyright 2015 by Ken Lambert
"""
class AbstractCollection(object): """An abstract collection implementation."""
# Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._size = 0 self._modCount = 0 if sourceCollection: for item in sourceCollection: self.add(item)
# Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return len(self) == 0 def __len__(self): """Returns the number of items in self.""" return self._size
def __str__(self): """Returns the string representation of self, using [] as delimiters.""" return "[" + ", ".join(map(str, self)) + "]"
def __eq__(self, other): """Returns True if self equals other, or False otherwise. Compares pairs of items in the two sequences generated by the iterators on self and other.""" if self is other: return True if type(self) != type(other) or len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True
def __add__(self, other): """Returns a new collection containing the contents of self and other.""" result = type(self)(self) for item in other: result.add(item) return result
def count(self, item): """Returns the number of instance of item in self.""" counter = 0 for nextItem in self: if item == nextItem: counter += 1 return counter
# These methods track and update the modCount, which is used to # prevent mutations within the context of an iterator (for loop)
def getModCount(self): """Returns the number of modifications to the collection.""" return self._modCount
def incModCount(self): """Increments the number of modifications to the collection.""" self._modCount += 1
~~~~~~~~~~~~~~~~~~
""" File: abstractstack.py Copyright 2015 by Ken Lambert
"""
from abstractcollection import AbstractCollection
class AbstractStack(AbstractCollection): """Represents an abstract stack."""
def __init__(self, sourceCollection): """Initializes the stack at this level.""" AbstractCollection.__init__(self, sourceCollection)
def add(self, item): """For compatibility with other collections.""" self.push(item)
~~~~~~~~~~~~~~~~~~
""" File: arrays.py Copyright 2015 by Ken Lambert
An Array is a restricted list whose clients can use only [], len, iter, and str.
To instantiate, use
<variable> = array(<capacity>, <optional fill value>)
The fill value is None by default. """
class Array(object): """Represents an array."""
def __init__(self, capacity, fillValue = None): """Capacity is the static size of the array. fillValue is placed at each position.""" self._items = list() for count in range(capacity): self._items.append(fillValue)
def __len__(self): """-> The capacity of the array.""" return len(self._items)
def __str__(self): """-> The string representation of the array.""" return str(self._items)
def __iter__(self): """Supports iteration over a view of an array.""" return iter(self._items)
def __getitem__(self, index): """Subscript operator for access at index.""" return self._items[index]
def __setitem__(self, index, newItem): """Subscript operator for replacement at index.""" self._items[index] = newItem
~~~~~~~~~~~~~~~
""" File: arraystack.py Copyright 2015 by Ken Lambert
"""
from arrays import Array from abstractstack import AbstractStack
class ArrayStack(AbstractStack): """An array-based stack implementation."""
# Class variable DEFAULT_CAPACITY = 10
# Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._items = Array(ArrayStack.DEFAULT_CAPACITY) AbstractStack.__init__(self, sourceCollection)
# Accessor methods def __iter__(self): """Supports iteration over a view of self. Visits items from bottom to top of stack.""" modCount = self.getModCount() cursor = 0 while cursor < len(self): yield self._items[cursor] if modCount != self.getModCount(): raise AttributeError("Illegal modification of backing store") cursor += 1
def peek(self): """Returns the item at the top of the stack. Precondition: the stack is not empty. Raises: KeyError if stack is empty.""" if self.isEmpty(): raise KeyError("The stack is empty") return self._items[len(self) - 1]
# Mutator methods def clear(self): """Makes self become empty.""" self._size = 0 self._modCount = 0 self._items = Array(ArrayStack.DEFAULT_CAPACITY)
def push(self, item): """Inserts item at top of the stack.""" # Resize array here if necessary if len(self) == len(self._items): tempArray = Array(len(self) * 2) for i in range(len(self)): tempArray[i] = self._items[i] self._items = tempArray self._items[len(self)] = item self._size += 1 self.incModCount()
def pop(self): """Removes and returns the item at the top of the stack. Precondition: the stack is not empty. Raises: KeyError if stack is empty. Postcondition: the top item is removed from the stack.""" if self.isEmpty(): raise KeyError("The stack is empty") oldItem = self._items[len(self) - 1] self._size -= 1 self.incModCount() # Resize the array here if necessary if len(self) <= .25 * len(self._items) and ArrayStack.DEFAULT_CAPACITY <= len(self._items) // 2: tempArray = Array(len(self._items) // 2) for i in range(len(self)): tempArray[i] = self._items[i] self._items = tempArray
return oldItem ~~~~~~~~~~~~~~~~~~~
""" File: grid.py Copyright 2015 by Ken Lambert
"""
from arrays import Array
class Grid(object): """Represents a two-dimensional array."""
def __init__(self, rows, columns, fillValue = None): self._data = Array(rows) for row in range(rows): self._data[row] = Array(columns, fillValue)
def getHeight(self): """Returns the number of rows.""" return len(self._data)
def getWidth(self): "Returns the number of columns.""" return len(self._data[0])
def __getitem__(self, index): """Supports two-dimensional indexing with [][].""" return self._data[index]
def __str__(self): """Returns a string representation of the grid.""" result = "" for row in range(self.getHeight()): for col in range(self.getWidth()): result += str(self._data[row][col]) + " " result += " " return result
def __iter__(self): """Yields the grid's items in row major order.""" row = 0 while row < self.getHeight(): column = 0 while column < self.getWidth(): yield self[row][column] column += 1 row += 1
def main(rows = 10, columns = 10, fillValue = 1): g = Grid(rows, columns, fillValue) print("The grid: ", g) for row in range(g.getHeight()): for column in range(g.getWidth()): g[row][column] = (row, column) print("The grid positions: ", g) print("The items in row major order:") for item in g: print(item)
if __name__ == "__main__": main()
~~~~~~~~~~~ Thanks in advance
Explanation / Answer
MazeWidth% = 11 MazeHeight% = 9 MazeCell% = 50 VDU 23,22,MazeWidth%*MazeCell%/2+3;MazeHeight%*MazeCell%/2+3;8,16,16,128 VDU 23,23,3;0;0;0; : REM Line thickness OFF PROCgeneratemaze(Maze&(), MazeWidth%, MazeHeight%, MazeCell%) PROCsolvemaze(Path{()}, Maze&(), 0, MazeHeight%-1, MazeWidth%-1, 0, MazeCell%) END DEF PROCsolvemaze(RETURN s{()}, m&(), x%, y%, dstx%, dsty%, s%) LOCAL h%, i%, n%, p%, q%, w% w% = DIM(m&(),1) h% = DIM(m&(),2) DIM s{(w%*h%) x%,y%} GCOL 3,14 m&(x%,y%) OR= &80 REPEAT FOR i% = 0 TO 3 CASE i% OF WHEN 0: p% = x%-1 : q% = y% WHEN 1: p% = x%+1 : q% = y% WHEN 2: p% = x% : q% = y%-1 WHEN 3: p% = x% : q% = y%+1 ENDCASE IF p% >= 0 IF p% = 0 IF q% x% IF m&(p%,q%) AND 1 EXIT FOR IF q% > y% IF m&(p%,q%) AND 2 EXIT FOR IF x% > p% IF m&(x%,y%) AND 1 EXIT FOR IF y% > q% IF m&(x%,y%) AND 2 EXIT FOR ENDIF NEXT IF i% < 4 THEN m&(p%,q%) OR= &80 s{(n%)}.x% = x% s{(n%)}.y% = y% n% += 1 ELSE IF n% > 0 THEN n% -= 1 p% = s{(n%)}.x% q% = s{(n%)}.y% ENDIF ENDIF LINE (x%+0.5)*s%,(y%+0.5)*s%,(p%+0.5)*s%,(q%+0.5)*s% x% = p% y% = q% UNTIL x%=dstx% AND y%=dsty% s{(n%)}.x% = x% s{(n%)}.y% = y% ENDPROC DEF PROCgeneratemaze(RETURN m&(), w%, h%, s%) LOCAL x%, y% DIM m&(w%, h%) FOR y% = 0 TO h% LINE 0,y%*s%,w%*s%,y%*s% NEXT FOR x% = 0 TO w% LINE x%*s%,0,x%*s%,h%*s% NEXT GCOL 15 PROCcell(m&(), RND(w%)-1, y% = RND(h%)-1, w%, h%, s%) ENDPROC DEF PROCcell(m&(), x%, y%, w%, h%, s%) LOCAL i%, p%, q%, r% m&(x%,y%) OR= &40 : REM Mark visited r% = RND(4) FOR i% = r% TO r%+3 CASE i% MOD 4 OF WHEN 0: p% = x%-1 : q% = y% WHEN 1: p% = x%+1 : q% = y% WHEN 2: p% = x% : q% = y%-1 WHEN 3: p% = x% : q% = y%+1 ENDCASE IF p% >= 0 IF p% = 0 IF q% x% m&(p%,q%) OR= 1 : LINE p%*s%,y%*s%+4,p%*s%,(y%+1)*s%-4 IF q% > y% m&(p%,q%) OR= 2 : LINE x%*s%+4,q%*s%,(x%+1)*s%-4,q%*s% IF x% > p% m&(x%,y%) OR= 1 : LINE x%*s%,y%*s%+4,x%*s%,(y%+1)*s%-4 IF y% > q% m&(x%,y%) OR= 2 : LINE x%*s%+4,y%*s%,(x%+1)*s%-4,y%*s% PROCcell(m&(), p%, q%, w%, h%, s%) ENDIF NEXTRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.