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

At the last of the output of my code, it is not giving proper output. Plz… tell where i am doing mistake
from vertex import Vertex

class Graph:

def init(self):

self.graph_dict = {}

def add_vertex(self, node):

self.graph_dict[node.value] = node

def add_edge(self, from_node, to_node, weight = 0):

self.graph_dict[from_node.value].add_edge(to_node.value, weight)

self.graph_dict[to_node.value].add_edge(from_node.value, weight)

def explore(self):

print("Exploring the graph....\n")

#FILL IN EXPLORE METHOD BELOW

current_room = "entrance"

path_total = 0

print("\nStarting off at the {0}\n".format(current_room))

while current_room != 'treasure room':

  node = self.graph_dict[current_room]

  for connected_room,weight in node.edges.items():

    key = connected_room[0]

          

    print("enter {0} for {1}: {2} cost".format(key,connected_room,weight))

  valid_choices = [room[:1] for room in node.edges.keys()]

  print("\nYou have accumulated: {0} cost".format(path_total))

  choice = input("\nWhich room do you move to? ")

  if choice not in valid_choices:

    print("please select from these letters: {0}".format(valid_choices))

  else:

    for room in node.edges.keys():

      if choice == room[0]:

        current_room = room

        path_total += node.edges[room] 

  

    print("\n*** You have chosen: {0} ***\n".format(current_room))

print("Made it to the treasure room with {0} cost".format(path_total))

def print_map(self):

print("\nMAZE LAYOUT\n")

for node_key in self.graph_dict:

  print("{0} connected to...".format(node_key))

  node = self.graph_dict[node_key]

  for adjacent_node, weight in node.edges.items():

    print("=> {0}: cost is {1}".format(adjacent_node, weight))

  print("")

print("")

def build_graph():

graph = Graph()

MAKE ROOMS INTO VERTICES BELOW…

entrance = Vertex(“entrance”)

ante_chamber = Vertex(“ante-chamber”)

kings_room = Vertex(“kings_room”)

grand_gallery = Vertex(“grand gallery”)

treasure_room = Vertex(“treasure_room”)

ADD ROOMS TO GRAPH BELOW…

graph.add_vertex(entrance)

graph.add_vertex(ante_chamber)

graph.add_vertex(kings_room)

graph.add_vertex(grand_gallery)

graph.add_vertex(treasure_room)

ADD EDGES BETWEEN ROOMS BELOW…

graph.add_edge(entrance,ante_chamber,7)

graph.add_edge(entrance,kings_room,3)

graph.add_edge(ante_chamber,kings_room,1)

graph.add_edge(grand_gallery,ante_chamber,2)

graph.add_edge(grand_gallery,kings_room,2)

graph.add_edge(treasure_room,ante_chamber,6)

graph.add_edge(treasure_room,grand_gallery,4)

DON’T CHANGE THIS CODE

graph.print_map()

return graph