lab04 : Maze Solver using Stacks

num ready? description assigned due
lab04 true Maze Solver using Stacks Tue 04/30 11:59PM Thu 05/09 11:59PM

Table of Contents

Learning Goals

In this lab, you’ll practice:

Note: It is important that you start this lab early so you can utilize our office hours to seek assistance / ask clarifying questions during the week before the deadline if needed!

For this writeup, it might be helpful to draw the provided mazes and write the indices next to the rows and columns to make it easier to follow the instructions.

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 the maze in different 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, or 5.11 in the online book). 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.

In the above example, G is located at maze[0][4], so maze[0] contains the list where G is found.

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:

Also Note: You may assume that a maze will always be enclosed with a border ('+') or the Goal ('G') - there won’t be any open spaces along the borders of the maze.

Traversing the maze

Your function will need to traverse the 2D maze given a starting coordinate. As your function 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 “step number” value. By following these numbered steps, you can trace how the algorithm was traversing the maze to reach the goal.

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

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:

[ ['+', '+', '+', '+', 'G', '+'],
  ['+', 8, '+', 11, 12, '+'],
  ['+', 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 print_maze(maze):
	for row in range(len(maze)):
		for col in range(len(maze[0])):
			print(f"|{maze[row][col]:<2}", sep='',end='')
		print("|")

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:

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

Note that our starting coordinate (maze[4][4]) is the first step we take (and mark the grid with a 1). Then it traverses North (step 2) until it can’t go any further. For example, in step 2’s position (at coordinate maze[3][4]), it tries to check North (runs into a wall), then West (runs into a wall), then South (already visited), then East (runs into a wall), so we can’t continue. At this point, we need to “backtrack” to step 1 and check the other counterclockwise directions of maze[4][4], so at step 1 it tries to go North (already visited as indicated with step 2), then West, which is open (can continue, so now it takes the 3rd step), and so on.

Note that '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) we’ve visited that may have other directions to check.

Instructions

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

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.

lab04.py

This file will contain a single function definition maze_path_exists(maze, start_x, start_y). The maze parameter will be the 2D List maze as described above. start_x and start_y are the starting coordinates used when traversing the maze (maze[start_x][start_y]). You may assume that start_x and start_y position is a valid position (i.e., it’s contained within the maze and no + or G value exists in that position in the 2D List).

The maze_path_exists function will utilize a Stack and update the maze elements with the number of steps at each traversed position. It should return True if a path exists and the goal was reached, and return False if no path to the goal exists.

Stack.py

This file will simply contain a Stack class implementation exactly as 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 the isEmpty, push, pop, peek, and size methods. Your solution must utilize the Stack data structure and any of its methods to manage the traversal through the maze.

testFile.py

This file will contain unit tests using pytest to test if your maze_path_exists functionality 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 requires testFile.py to 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: first, check the return value of the function, then verify that the maze after the function execution looks as expected. Solving the path through the maze on paper can help write these test cases.

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

Submission

Once you’re done with writing your class / function definitions and tests, submit your lab04.py, Stack.py and testFile.py files to the Lab04 assignment on Gradescope. There will be various unit tests Gradescope to ensure your code is working correctly based on the specifications given in this lab.

Also, double-check and remove any print statements in your submission. Sometimes print statements confuses the autograder and may result in an error message.

If the tests don’t pass, you may get some error message that may or may not be obvious at this point. Don’t worry - if the tests didn’t pass, take a minute to think about what may have caused the error. If your tests didn’t pass and you’re still not sure why you’re getting the error, feel free to ask your TAs or Learning Assistants.


Step-by-Step Traversal of the Maze

To illustrate how our given algorithm works, let's see the following example:

Let's say the starting maze and stack looks like this: (first step already taken)

[
	['+', '+', '+', '+', 'G', '+']                  |   |
	['+', ' ', '+', ' ', ' ', '+']                  |   |
	['+', ' ', ' ', ' ', '+', '+']                  |   |
	['+', ' ', '+', '+', ' ', '+']                  |   |
	['+', ' ', ' ', ' ',  1 , '+'] <- now at 1      |4,4| <- keep track of where we are
	['+', '+', '+', '+', '+', '+']                  |---|
]
For each step, we check the 4 directions (north, west, south, east) one by one to see if there is a valid slot to move.

[
	['+', '+', '+', '+', 'G', '+']                  |   |
	['+', ' ', '+', ' ', ' ', '+']                  |   |
	['+', ' ', ' ', ' ', '+', '+']                  |   |
	['+', ' ', '+', '+',    , '+'] <- north good    |   |
	['+', ' ', ' ', ' ',  1 , '+']                  |4,4|
	['+', '+', '+', '+', '+', '+']                  |---|
]
Since north is valid, we take a step to the north and update the maze and the stack accordingly:

[
	['+', '+', '+', '+', 'G', '+']                  |   |
	['+', ' ', '+', ' ', ' ', '+']                  |   |
	['+', ' ', ' ', ' ', '+', '+']                  |   |
	['+', ' ', '+', '+',  2 , '+'] <- now at 2      |3,4| <- keep track of where we are
	['+', ' ', ' ', ' ',  1 , '+']                  |4,4|
	['+', '+', '+', '+', '+', '+']                  |---|
]
Now, start from 2, we check the 4 directions (North, West, South, Eastt) one by one to see if there is a valid slot to move.

[
	['+', '+', '+', '+', 'G', '+']                  |   |
	['+', ' ', '+', ' ', ' ', '+']                  |   |
	['+', ' ', ' ', ' ', '+', '+']                  |   |
	['+', ' ', '+', '+',  2 , '+'] <- NWSE blocked  |3,4|
	['+', ' ', ' ', ' ',  1 , '+']                  |4,4|
	['+', '+', '+', '+', '+', '+']                  |---|
]
When all 4 directions NWSE are blocked, we take a step back by popping the stack:

[
	['+', '+', '+', '+', 'G', '+']                  |   |
	['+', ' ', '+', ' ', ' ', '+']                  |   |
	['+', ' ', ' ', ' ', '+', '+']                  |   |
	['+', ' ', '+', '+',  2 , '+']                  |   | <- pop
	['+', ' ', ' ', ' ',  1 , '+'] <- back to 1     |4,4| <- where to go back
	['+', '+', '+', '+', '+', '+']                  |---|
]
Start from 1, again, we check the 4 directions (north, west, south, east) one by one to see if there is a valid slot to move.

we check the north (this time occupied), then the west, and since the west is valid, we go west:

[
	['+', '+', '+', '+', 'G', '+']                  |   |
	['+', ' ', '+', ' ', ' ', '+']                  |   |
	['+', ' ', ' ', ' ', '+', '+']                  |   |
	['+', ' ', '+', '+',  2 , '+']                  |4,3| <- keep track of where we are
	['+', ' ', ' ',  3 ,  1 , '+'] <- now at 3      |4,4|
	['+', '+', '+', '+', '+', '+']                  |---|
]

The algorithm given is straightforward, and all you need to do is translate this procedure into python code. Our suggestion is reading the lab description carefully. It indeed contains all you need.

If you’d like an additional walkthrough, here’s a handwritten explanation of the various elements you will need to solve this lab: https://www.loom.com/share/b3323f2125d447dcbc7d18b96e45dda4?sid=092fe2c5-cf90-48fa-ae40-ead8c12c86c7

Troubleshooting