Python code below in BOLD In this project, you will: - Complete the code to solv
ID: 3602968 • Letter: P
Question
Python
code below in BOLD
In this project, you will:
- 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.
"""
Determines the solution to a maze problem.
Uses a grid to represent the maze.
This grid is input from a text file.
Uses a stack-based backtracking algorithm.
Replace any "<your code goes here>" 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 sysmbol.")
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 goes here
# Prints the maze with no spaces between cells.
def printMaze(maze):
# Part 2:
# your code goes here
# (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 goes here
return False
main()
Explanation / Answer
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 sysmbol.")
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 goes here
(rows, cols) = (maze.getHeight(), maze.getWidth())
for i in range(rows):
for j in range(cols):
if maze[i][j] == START:
return (i, j)
return (-1, -1)
# Prints the maze with no spaces between cells.
def printMaze(maze):
# Part 2:
# your code goes here
(rows, cols) = (maze.getHeight(), maze.getWidth())
for i in range(rows):
for j in range(cols):
print(maze[i][j], end="")
print()
# (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 goes here
if (row -1) > 0 and not maze[row-1][column] in [VISITED, BARRIER]:
stack.push((row-1, column))
if (column -1) > 0 and not maze[row][column-1] in [VISITED, BARRIER]:
stack.push((row, column-1))
if (row+1) < maze.getHeight() and not maze[row+1][column] in [VISITED, BARRIER]:
stack.push((row+1, column))
if (column+1) < maze.getWidth() and not maze[row][column+1] in [VISITED, BARRIER]:
stack.push((row, column+1))
return False
main()
# copy pastable code link: https://paste.ee/p/PCRyK
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.