For this lab, you will need to create three files:

• lab04.py- file containing your solution to writing thesolveMazefunction as described in this writeup
• Stack.py- file containing your class definition of a Python Stack using Python Lists
• testFile.py- file containing pytest functions testing if your solution works as expected for your own mazes you'll create.

Solving a maze

We can explore and solve a maze by utilizing a Stack data structure. The idea is given coordinates (x,y positions), we can explore in certain directions until we reach dead ends or our goal. If we do reach a dead end, a Stack data structure can help us keep track of coordinates we've visited and allow us to "backtrack" to a certain point.

More context on this specific problem is covered in the book (See Recursion Chapter 4.6: Exploring a Maze). The book explains how this problem can be solved recursively, but in this lab we will not use recursion - rather we will do what recursion does for us and manually keep track of positions visited using our implementation of a Stack data structure.

Representing a maze

There can be several ways to represent a maze, but we will use a n x m 2D List. An example below will help explain how the 2D List is being used as a maze:

maze = [ ['+','+','+','+','+','+'], ['+',' ','+',' ',' ','G'], ['+',' ',' ',' ','+','+'], ['+',' ','+','+',' ','+'], ['+',' ',' ',' ',' ','+'], ['+','+','+','+','+','+'] ] 

The above example is a 6 x 6 maze.maze[x][y]will represent a single item in the 2D List.maze[x]will contain a list andmaze[x][y]will contain a single element (the ythitem in the xthlist). Since we're dealing with Python 2D Lists (a Python list where the elements are Python Lists), the indices of the maze coordinates start with 0. The top left position of the maze will be indexed atmaze[0][0]and the bottom right position of the maze will be indexed atmaze[n-1][m-1]. If you would like to review Python 2D Lists, you may find the following CS 8 notes useful:https://ucsb-cs8.github.io/m19-wang/lectures/lect10/

Note:This layout is different than a traditional cartesian coordinate system. As we move right the y value increases, as we move left the y value decreases, as we move up the x value decreases, and as we move down the x value increases.

The initial maze element can have one of three states:

• ' '- an empty space. This indicates the space can be moved into
• '+'- a wall. This indicates that you cannot move into this position
• 'G'- a goal. We are trying to see if a path exists to this position

Traversing the maze

Your program will need to traverse the 2D maze given a starting coordinate. As your program traverses the maze, you will need to keep track of the number of steps your algorithm takes and replace the' 'elements in the maze as you move along with the number of steps value. (Lists (and 2D Lists) are mutable, so we should be able to change the maze structure as our algorithm progresses and it should keep these changes!). You may traverse the spaces horizontally and vertically (not diagonally).

You must implement your traversal in following way:

• When reaching a certain coordinate, you must check and move clockwise in the following order:North, then East, then South, then West
• You will always be given a starting coordinate. This will be the first step taken
• You will traverse the maze until you reach a goal ('G'). Once we reach the goal, our algorithm can stop (no need to keep traversing the maze)

Using the maze provided above, let's assume your starting position is atmaze[4][4]. After your algorithm finshes,mazewill have the following updates containing the number of steps:

[ ['+', '+', '+', '+', '+', '+'], ['+', 8, '+', 11, 12, 'G'], ['+', 7, 9, 10, '+', '+'], ['+', 6, '+', '+', 2, '+'], ['+', 5, 4, 3, 1, '+'], ['+', '+', '+', '+', '+', '+'] ] 

This format is not too easy on the eyes, so we're providing a helper function below that you can use to print out the state of the maze in a more user-friendly way:

def printMaze(maze): for row in range(len(maze)): for col in range(len(maze[0])): print("|{:<2}".format(maze[row][col]), sep='',end='') print("|") return 

We can print the initial maze in the following format:

|+ |+ |+ |+ |+ |+ | |+ | |+ | | |G | |+ | | | |+ |+ | |+ | |+ |+ | |+ | |+ | | | | |+ | |+ |+ |+ |+ |+ |+ | 

And we can print the maze after our algorithm runs in the following format:

|+ |+ |+ |+ |+ |+ | |+ |8 |+ |11|12|G | |+ |7 |9 |10|+ |+ | |+ |6 |+ |+ |2 |+ | |+ |5 |4 |3 |1 |+ | |+ |+ |+ |+ |+ |+ | 

Note that our starting coordinate (maze[4][4]) is the first step we take. Then it traverses North (step 2) until it can't go any further. Then we need to "backtrack" and check the other clockwise directions ofmaze[4][4]such asNorth (already visited), East (runs into a wall), then South (runs into a wall), then West (can continue, so it then takes the 3rd step), and so on.Notethat'G'or'+'should never be overwritten when traversing the maze.

Utilizing a Stack to keep track of where we've visited

Instead of using a recursive solution like the book describes, we will use a Stack in our solution. It essentially is doing the same thing as recursion, except now we have to manually push and pop the position(s) that we've visited that may have other directions to check.

• As we move along the maze, we should be pushing the coordinates of where we're visiting onto the Stack, and we want to replace the empty space (' ') with the current number of steps taken in the 2D List maze structure.
• Since we're defining positions as[x][y]indices on the 2D maze, I would recommend pushing these coordinates as a list onto the stack ([x,y]). When extracting a coordinate list type on the Stack, you can index x with [0] and y with [1] as needed.
• We want to make sure we don't move to a position we've already visited (since that might end up in an infinite loop!). So keep in mind we should only move to coordinates with a' 'value.
• The top of our Stack will be the current position we're at, and check if we are able to move to a valid adjacent coordinate. If not, then we need to remove that position from the Stack and check the next top element in the Stack (containing ax,yposition that has more directions to check).
• As long as there are items in the Stack, that means there are still positions that have possible directions to check.
• If our Stack does not have any items, this implies there are no more positions with directions to check. If we haven't reached our goal, then this implies there is no path from the given starting position to the goal.

lab04.py

This file will contain a single function definitionsolveMaze(maze, startX, startY). Themazeparameter will be the 2D List maze as described above.startXandstartYare the starting coordinates used when traversing the maze (maze[startX][startY]). You may assume thatstartXandstartYposition is a valid position (it's contained within the maze and no+orGvalue exists in that position in the 2D List).

ThesolveMazefunction will utilize a Stack and update the maze elements with the number of steps at each traversed position. It should returnTrueif a path exists and the goal was reached, and returnFalseif no path to the goal exists.

Stack.py

This file will simply contain a Stack class implementationexactlyas the one covered in the book using Python Lists (we'll also cover this implementation in lecture - no need to write pytests for this, but Gradescope will check to see if this implementation is correct). This should contain a constructor (__init__), and theisEmpty,push,pop,peek, andsizemethods. Your solutionmustutilize the Stack data structure and any of its methods to manage the traversal through the maze.

testFile.pypytest

This file will contain unit tests using pytest to test if yoursolveMazefunctionality is correct. Think of various mazes (with or without solutions and different sizes) and check to see if the traversal is correct according to these instructions. Write your tests first in order to check the correctness of your function. Again, Gradescope requirestestfile.pyto be submitted before running any autograded tests. You should write at least one test where a solution exists (different than the one provided in these instructions), and another test where a solution does not exist. Remember that testing can help you debug your algorithm and ensure your functionality works as expected.

An example of how we could write a pytest using the maze above using pytest:

def test_example(): maze = [ ['+','+','+','+','+','+'], ['+',' ','+',' ',' ','G'], ['+',' ',' ',' ','+','+'], ['+',' ','+','+',' ','+'], ['+',' ',' ',' ',' ','+'], ['+','+','+','+','+','+'] ] assert solveMaze(maze, 4, 4) == True assert maze == [ ['+', '+', '+', '+', '+', '+'], ['+', 8, '+', 11, 12, 'G'], ['+', 7, 9, 10, '+', '+'], ['+', 6, '+', '+', 2, '+'], ['+', 5, 4, 3, 1, '+'], ['+', '+', '+', '+', '+', '+'] ]