- 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 "" 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:

#

# Prints the maze with no spaces between cells.

def printMaze(maze):

# Part 2:

#

# (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:

#

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

= array(, )

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