Instructions For this lab, you will need to create three files: - 1ab04. py - file containing your solution to writing the solveMaze function 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. Note: Gradescope's autograder requires you to submit your testFile. py in order for it to run your code (hopefully you're practicing TDD and use your tests to check correctness!) There will be no starter code for this assignment, but rather function descriptions and helper functions are given in the specification below. It's recommended that you organize your lab work in its own directory. This way all files for a lab are located in a single folder. Also, this will be easy to import various files into your code using the import / from technique shown in lecture. 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 in 2D List. An example below will help explain how the 2D List is being used as 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=[ ['+','+','+','+','+','+'], :[I+I'I I'I+l'l I'I I'IGI]' [I+I'I III III III+III+I]' '[|+|'| III+III+III III+I]I '[I+I'I l'l l'l I'l I'I+I]' [I+I'I+lll+l'I+III+III+I]] 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 and maze [x] [y] will contain a single element (the yth item in the xth list). 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 at maze [0] [0] and the bottom right position of the maze will be indexed at maze [n 1] [ml]. If you would like to review Python 2D Lists, you may find the following CS 8 notes useful: https://ucsbc58.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 ('6 ' ). 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 at maze [4] [4] . After your algorithm finshes, maze will have the following updates containing the number of steps: I, I+I' I+I' I+I' I+I' I+I]' ', 8, '+', 11, 12, 'G'], ', 7, 9, 10, '+', '+'], 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= for row in range(1en(maze)): for col in range(1en(maze[0])): print("|{: