In this part, you will complete the code to solve a maze.
- 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 "
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
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 += "\n"
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:\n", g)
for row in range(g.getHeight()):
for column in range(g.getWidth()):
g[row][column] = (row, column)
print("The grid positions:\n", g)
print("The items in row major order:")
for item in g:
print(item)
if __name__ == "__main__": main()
Homework Answers
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% < w% IF q% >= 0 IF q% < h% IF m&(p%,q%) < &80 THEN
IF p% > 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% < w% IF q% >= 0 IF q% < h% IF m&(p%,q%) < &40 THEN
IF p% > 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
NEXT
Maze Solving with Stacks Problem Statement Consider a maze made up of rectangular array of squares,...
Maze Solving with Stacks Problem Statement Consider a maze made up of rectangular array of squares, such as the following one: X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X Figure...
Here is my code for minesweeper in python and it has something wrong. Could you please help me to fix it? import tkinter as tk import random class Minesweeper: def __init__(self): self.main = tk.Tk()...
Here is my code for minesweeper in python and it has something
wrong. Could you please help me to fix it?
import tkinter as tk
import random
class Minesweeper:
def __init__(self):
self.main = tk.Tk()
self.main.title("mine sweeper")
self.define_widgets()
self.mines = random.sample( [(i,j) for i in range(25) for j in
range(50) ],self.CustomizeNumberOfMines())
print(self.mines)
self.main.mainloop()
self.CustomizeNumberOfMines()
def define_widgets(self):
""" Define a canvas object, populate it with squares and
possible texts """
self.canvas = tk.Canvas(self.main, width = 1002, height=502,
bg="#f0f0f0")
self.canvas.grid(row=0, column=0)
self.boxes =...
The Problem A robot is asked to navigate a maze. It is placed at a certain...
The Problem A robot is asked to navigate a maze. It is placed at a certain position (the starting position) in the maze and is asked to try to reach another position (the goal position). Positions in the maze will either be open or blocked with an obstacle. Positions are identified by (x,y) coordinates. At any given moment, the robot can only move 1 step in one of 4 directions. Valid moves are: ● Go North: (x,y) -> (x,y-1) ●...
Solve the code below: CODE: """ Code for handling sessions in our web application """ from bottle import request, response import uuid import json import model import dbsche...
Solve the code below:
CODE:
"""
Code for handling sessions in our web application
"""
from bottle import request, response
import uuid
import json
import model
import dbschema
COOKIE_NAME = 'session'
def get_or_create_session(db):
"""Get the current sessionid either from a
cookie in the current request or by creating a
new session if none are present.
If a new session is created, a cookie is set in the response.
Returns the session key (string)
"""
def add_to_cart(db, itemid, quantity):
"""Add an...
In this question, you will test, using a backtracking algorithm, if a mouse can escape from...
In this question, you will test, using a backtracking algorithm, if a mouse can escape from a rectangular maze. To ensure consistency of design, start your solution with maze_start.c. The backtracking algorithm helps the mouse by systematically trying all the routes through the maze until it either finds the escape hatch or exhausts all possible routes (and concludes that the mouse is trapped in the maze). If the backtracking algorithm finds a dead end, it retraces its path until it...
You will create a PYTHON program for Tic-Tac-Toe game. Tic-Tac-Toe is normally played with two people....
You will create a PYTHON program for Tic-Tac-Toe game. Tic-Tac-Toe is normally played with two people. One player is X and the other player is O. Players take turns placing their X or O. If a player gets three of his/her marks on the board in a row, column, or diagonal, he/she wins. When the board fills up with neither player winning, the game ends in a draw 1) Player 1 VS Player 2: Two players are playing the game...
Assignment Predator / Prey Objectives Reading from and writing to text files Implementing mathematical formulas in...
Assignment Predator / Prey Objectives Reading from and writing to text files Implementing mathematical formulas in C++ Implementing classes Using vectors Using command line arguments Modifying previously written code Tasks For this project, you will implement a simulation for predicting the future populations for a group of animals that we’ll call prey and their predators. Given the rate at which prey births exceed natural deaths, the rate of predation, the rate at which predator deaths exceeds births without a food...
Here is my code for minesweeper in python and it has something
wrong. Could you please help me to fix it?
import tkinter as tk
import random
class Minesweeper:
def __init__(self):
self.main = tk.Tk()
self.main.title("mine sweeper")
self.define_widgets()
self.mines = random.sample( [(i,j) for i in range(25) for j in
range(50) ],self.CustomizeNumberOfMines())
print(self.mines)
self.main.mainloop()
self.CustomizeNumberOfMines()
def define_widgets(self):
""" Define a canvas object, populate it with squares and
possible texts """
self.canvas = tk.Canvas(self.main, width = 1002, height=502,
bg="#f0f0f0")
self.canvas.grid(row=0, column=0)
self.boxes =...
Solve the code below:
CODE:
"""
Code for handling sessions in our web application
"""
from bottle import request, response
import uuid
import json
import model
import dbschema
COOKIE_NAME = 'session'
def get_or_create_session(db):
"""Get the current sessionid either from a
cookie in the current request or by creating a
new session if none are present.
If a new session is created, a cookie is set in the response.
Returns the session key (string)
"""
def add_to_cart(db, itemid, quantity):
"""Add an...
Most questions answered within 3 hours.
-
When bond rating companies rate a bond, which are qualities they
evaluate? Pick more than 1...
asked 12 seconds ago -
Describe an experiment to test the assumption that the heat
capacity for the binding of the...
asked 22 seconds ago -
Animals in cold climates often depend on two layers of
insulation: a layer of body fat...
asked 4 minutes ago -
The owner of Genuine Subs, Inc., hopes to expand the present
operation by adding one new...
asked 7 minutes ago -
Find the in-line equilibrium location with respect to two
particles located on the z-axis, the first...
asked 8 minutes ago -
Data from PT Li (in thousand rupiah)
are as follows:
Inventory decrease
90,000
Prepaid expense...
asked 15 minutes ago -
Let X and Y be i.i.d. random variables with finite second
moments. Show that Cov(X+Y, X...
asked 22 minutes ago -
An ANOVA comparing two groups is equivalent to an independent
samples t-test.
True
False
asked 34 minutes ago -
Some supermarkets are using customer tracking technology that
traces the flow of customers
through the shop....
asked 25 minutes ago -
A dock worker applies a constant horizontal force of 75.0 N to a
block of ice...
asked 34 minutes ago -
You are the CEO of a major corporation whose databases were
recently hacked, and sensitive customer...
asked 39 minutes ago -
Amazon is not just a
surviving company of the 1990s tech boom; it is now one...
asked 37 minutes ago