I really need help with this difficult assignment

Python Help
1

https://ucsb-cs9.github.io/s23/lab/lab04/
I honestly do not understand what to do with stacks
this is the core of my code:
Stack.py

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items) - 1]

    def size(self):
        return len(self.items)

testFile.py

from lab04 import solveMaze
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
def test_example():
	maze = [
['+','+','+','+','G','+'],
['+',' ','+',' ',' ','+'],
['+',' ',' ',' ','+','+'],
['+',' ','+','+',' ','+'],
['+',' ',' ',' ',' ','+'],
['+','+','+','+','+','+'] ]
	assert solveMaze(maze, 4, 4) == True
	assert maze == [
['+', '+', '+', '+', 'G', '+'],
['+', 8, '+', 11, 12, '+'],
['+', 7, 9, 10, '+', '+'],
['+', 6, '+', '+', 2, '+'],
['+', 5, 4, 3, 1, '+'],
['+', '+', '+', '+', '+', '+'] ]

test_example()
2

one of my candidate lab04.py:

from Stack import *

def solveMaze(maze, xcord, ycord):
    """
    solveMaze - a function that takes a maze (represented as a 2D list), and the starting x and y coordinates
    and returns True if it is possible to reach the goal (represented by the letter 'G') from the starting point,
    using only adjacent (up, down, left, right) empty spaces (represented by an empty string ""),
    and returns False otherwise.

    Arguments:
    - maze: a 2D list representing the maze, where each element is either a string (empty string or 'G')
            or an integer (representing the path taken to get to that point)
    - xcord: an integer representing the starting x-coordinate
    - ycord: an integer representing the starting y-coordinate

    Returns:
    - True if it is possible to reach the goal from the starting point
    - False otherwise
    """
    number_stack = Stack()
    maze_counter = 1
    maze[xcord][ycord] = maze_counter
    number_stack.push((xcord, ycord))

    while not number_stack.isEmpty():
        pos = number_stack.peek()
        if maze[pos[0]-1][pos[1]] == "G":
            return True
        if maze[pos[0]-1][pos[1]] == "":
            maze_counter += 1
            maze[pos[0]-1][pos[1]] = maze_counter
            number_stack.push((pos[0]-1, pos[1]))
            continue
        if maze[pos[0]][pos[1]-1] == "G":
            return True
        if maze[pos[0]][pos[1]-1] == "":
            maze_counter += 1
            maze[pos[0]][pos[1]-1] = maze_counter
            number_stack.push((pos[0], pos[1]-1))
            continue
        if maze[pos[0]+1][pos[1]] == "G":
            return True
        if maze[pos[0]+1][pos[1]] == "":
            maze_counter += 1
            maze[pos[0]+1][pos[1]] = maze_counter
            number_stack.push((pos[0]+1, pos[1]))
            continue
        if maze[pos[0]][pos[1]+1] == "G":
            return True
        if maze[pos[0]][pos[1]+1] == "":
            maze_counter += 1
            maze[pos[0]][pos[1]+1] = maze_counter
            number_stack.push((pos[0], pos[1]+1))
            continue
        number_stack.pop()

    return False

Just gets this as output:

C:\Users\cshang\PycharmProjects\if\read\lab04\venv\Scripts\python.exe C:\Users\cshang\PycharmProjects\if\read\lab04\testFile.py 
Traceback (most recent call last):
  File "C:\Users\cshang\PycharmProjects\if\read\lab04\testFile.py", line 25, in <module>
    test_example()
  File "C:\Users\cshang\PycharmProjects\if\read\lab04\testFile.py", line 16, in test_example
    assert solveMaze(maze, 4, 4) == True
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError

Process finished with exit code 1
3

I’ve had a quick look. The problem might be that the maze has spaces (' '), but your code is checking for empty strings ("").

1 Like
4

This is a nice exercise. I find that @MRAB is correct.

For debugging I found it helpful to see where we are in the maze:

def printMazePos(maze, x, y):
    print("At: (", x, y,")")
    saved = maze[x][y]
    maze[x][y] = "*"
    printMaze(maze)
    maze[x][y] = saved

A few other thoughts as I was trying to follow the logic:

This would be easier to follow if you used tuple unpacking here.

x, y = number_stack.peek()

Then you don’t need all the pos[] business.

Now, your loop has 4 copies of almost the same, of logic like this:

          if maze[x-1][y] == "G":
              return True
          if maze[x-1][y] == " ":
              maze_counter += 1
              maze[x-1][y] = maze_counter
              number_stack.push((x-1, y))
              continue

I think that deserves a nested function:

    def found(u,v):
        nonlocal maze_counter
        if maze[u][v] == "G":
            # Found the goal
            return True
        if maze[u][v] == " ":
            # Found unvisited cell: occupy
            maze_counter += 1
            maze[u][v] = maze_counter
            number_stack.push((u, v))
        return False

There are really three exits from that logic, so True and False is not quite enough. When it’s False we want to know whether any new direction of exploration was pushed or we are stuck. But we can see whether anything was added to the stack. Then your loop looks like:

    while not number_stack.isEmpty():
        x, y = number_stack.peek()
        printMazePos(maze, x, y)
        depth = number_stack.size()
        if found(x-1, y) or found(x, y-1) or found(x+1, y) or found(x, y+1):
            return True
        if number_stack.size() == depth:
            # No unexpored direction
            number_stack.pop()

That was fun.

1 Like
5

Fixed my code with this!
Thank you!