Questions: Maze Explorer, Find all paths

Hi all! Thanks for all your help!

So in the Maze Explorer project:
https://www.codecademy.com/paths/computer-science/tracks/complex-data-structures/modules/cspath-graphs/projects/maze-explorer

I wanted to build a method that would find all the paths and see if the path you chose was the cheapest path or not.

This is the code that works:

def find_best_path(self, current_room = 'entrance', path = []):
  #We need a recursive algorithm!!!
  #ie path from treasure room to treasure room will return a none
  #and build up from the base case
    path = path + [current_room]
    if current_room == 'treasure room':
      return [path]
    paths = []
    connected_rooms = list(self.graph_dict[current_room].get_edges())
    for room in connected_rooms:
      if room not in path:
        extended_paths = self.find_best_path(room, path)
        for p in extended_paths:
          paths.append(p)
    return paths

So I had not yet done the recursion formula tutorials and now I understand this a lot more, but I have a few questions still.

One: this variable extended_paths, what data type is it? I can see it’s iterable, but how is it storing all the different paths that are coming through the recursive step? Are they lists? At what point does the program know to make the recursive step an iterative formula?

Two: I had a lot of trouble making this work initially, and I found out that if I replaced this line:
path = path + [current_room]

with either of these:

path.append(current_room)
path += [current_room]

it doesn’t work as expected, and only takes the first path through. I’m not sure why that happens but I have a hunch it has something to do with passing the memory allocation of the path variable instead of an instance of it. Am I on the right track?

All help appreciated!!!

you can ask python what type it is, but the value comes from your own code so you could look at that as well.

some of your operations are more expensive than they should be, adding something to a list can be done in constant time instead of making a full copy, and testing whether you’ve been somewhere is something you can do with a lookup table instead of searching through everywhere you’ve been.

finding all paths with depth first is a lot of duplicated work, consider instead pouring water at the entrance and moving the water edges outwards until one path hits an exit. this results in visiting each location once and once only, and finds the shortest path before any longer paths

even better yet is to only forward the search area in the location that has the best potential to be shortest

think of it as if you had to carry it out manually yourself. some ways you can search for the exit of a maze are such silly amounts of work that it can almost be considered the wrong thing to do

2 Likes