SkyRoute Project

Link to project: https://www.codecademy.com/paths/computer-science/tracks/cspath-graph-search-algorithms/modules/cspath-basic-graph-search-algorithms/projects/skyroute-graph-search

Hello! I am on the very last steps of the project but I have a problem. It seems that if I have ANYTHING in the " stations_under_construction" list, all of my results become “closed due to maintenance”. I even calculated and tried stations which won’t possibly use the station I added to the list and it still says there is no possible route. I have worked on this for about 3 hours now and just can’t seem to figure it out. I am pasting my code below. Any advice is greatly appreciated!


from graph_search import bfs, dfs
from vc_metro import vc_metro
from vc_landmarks import vc_landmarks
from landmark_choices import landmark_choices

#Creates the string we will use throughout the program
landmark_string = “”
for letter, landmark in landmark_choices.items():
landmark_string += “{0} - {1}\n”.format(letter, landmark)

#List of closed stations
stations_under_construction = [‘Burrard’]

#----------HELPER FUNCTIONS-------------
#Handles setting selected origin and destinations
def set_start_and_end(start_point, end_point):
if start_point != None:
change_point = input("What would you like to change? You can enter ‘o’ for ‘origin’, ‘d’ for ‘destination’, or ‘b’ for ‘both’: ")
if change_point == ‘b’:
start_point = get_start()
end_point = get_end()
elif change_point == ‘o’:
start_point = get_start()
elif change_point == ‘d’:
end_point = get_end()
else:
print(“Oops, that isn’t ‘o’, ‘d’, or ‘b’…”)
set_start_and_end(start_point, end_point)
else:
start_point = get_start()
end_point = get_end()
return start_point, end_point

#Requests origin from the user
def get_start():
start_point_letter = input("Where are you coming from? Type in the corresponding letter: ")
if start_point_letter in landmark_choices:
start_point = landmark_choices[start_point_letter]
return start_point
else:
print(“Sorry, that’s not a landmark we have data on. Let’s try this again…”)
get_start()

#Requests final destination from the user
def get_end():
end_point_letter = input("Ok, where are you headed? Type in the corresponding letter: ")
if end_point_letter in landmark_choices:
end_point = landmark_choices[end_point_letter]
return end_point
else:
print(“Sorry, that’s not a landmark we have data on. Let’s try this again…”)
get_end()

#Prints a greeting
def greet():
print(“Hi there and welcome to SkyRoute!”)
print(“We’ll help you find the shortest route between the following Vancouver landmarks:\n” + landmark_string)

#Prints a goodbye statement
def goodbye():
print(“Thanks for using SkyRoute!”)

#Shows the list of landmarks again
def show_landmarks():
see_landmarks = input("Would you like to see the list of landmarks again? Enter y/n: ")
if see_landmarks == ‘y’:
print(landmark_string)

#Changes vc_metro graph to only active stations
def get_active_stations():
updated_metro = vc_metro
for station_under_construction in stations_under_construction:
for current_station, neighboring_stations in vc_metro.items():
if current_station != station_under_construction:
updated_metro[current_station] -= set(stations_under_construction)
else:
updated_metro[current_station] = set()
return updated_metro

#-----------Wrapper Function-----------
def new_route(start_point = None, end_point = None):
start_point, end_point = set_start_and_end(start_point, end_point)
shortest_route = get_route(start_point, end_point)
if shortest_route:
shortest_route_string = ‘\n’.join(shortest_route)
print(“The shortest metro route from {0} to {1} is:\n{2}”.format(start_point, end_point, shortest_route_string))
else:
print(“Unfortunately, there is currently no path between {0} and {1} due to maintenance.”.format(start_point, end_point))
again = input("Would you like to see another route? Enter y/n: ")
if again == “y”:
show_landmarks()
new_route(start_point, end_point)

def get_route(start_point, end_point):
start_stations = vc_landmarks[start_point]
end_stations = vc_landmarks[end_point]
routes =
for start_station in start_stations:
for end_station in end_stations:
#Conditional expression… learn it!
metro_system = get_active_stations() if stations_under_construction else vc_metro
if len(stations_under_construction) > 0:
possible_route = dfs(metro_system, start_station, end_station)
if possible_route is None:
return None
route = bfs(metro_system, start_station, end_station)
if route:
routes.append(route)
shortest_route = min(routes, key=len)
return shortest_route

#---------------Program----------------
def skyroute():
greet()
new_route()
goodbye()

skyroute()

Wow! I had the same problem, and (not being as careful a tester as you) didn’t know it!

Look here, in get_route()

 for start_station in start_stations:
    for end_station in end_stations:
      #Conditional expression... learn it!
      metro_system = get_active_stations() if stations_under_construction else vc_metro
      if len(stations_under_construction) > 0:
        possible_route = dfs(metro_system, start_station, end_station)
        if possible_route is None:
          return None
      route = bfs(metro_system, start_station, end_station)
      if route:
        routes.append(route)

All you need to proceed is one combination of start_station and end_station that delivers a route. But the way this is coded, if a single combination of start and stop is explored in dfs() that does not return a route, the function terminates and returns None.

There are probably many ways to correct it; I chose to set a flag called possible to False if there is any construction, then to True if any route is found. If possible winds up True, proceed to bfs(), otherwise, return None.

1 Like

Ah! I see the problem now, thanks! I am not really sure how to fix it (especially since I don’t know what a “flag” is and google results on flags have me even more confused), but at least now I have a starting point. Thank you!

Here is what I ended up with, and it seems to have worked. Since I don’t know what a “flag” is, I kind of invented what I suspect a flag might be. I just set a variable to something empty and then added any possible_route to the empty variable. If the variable was empty, it returned None, if not, it just moved on.

def get_route(start_point, end_point):
start_stations = vc_landmarks[start_point]
end_stations = vc_landmarks[end_point]
routes =
for start_station in start_stations:
for end_station in end_stations:
#Conditional expression… learn it!
metro_system = get_active_stations() if stations_under_construction else vc_metro
if len(stations_under_construction) > 0:
possible = “”
possible_route = dfs(metro_system, start_station, end_station)
possible += str(possible_route)
if not possible:
return None
route = bfs(metro_system, start_station, end_station)
if route:
routes.append(route)
shortest_route = min(routes, key=len)
return shortest_route

Hi, Joseph – I’m afraid I can’t read your code like that without a lot of guesswork about the indentations; perhaps you could change it with an edit?

I’m sorry that I used that bit of jargon, flag. Basically, a flag is a variable that you assign a default value, say True. Then, if something happens down the line (such as stations_under_construction being True), the flag is changed to False. It is a signal to other parts of the program that something has occurred. In this case, if just one route is found via dfs(), it is switched back to True.

Coding that, I got to wondering why we needed to bother with dfs() in the first place. Why not just run everything through bfs(), appending any found route to the list routes, then just check len(routes) and return None if it’s zero?

Not surprisingly, it appears that there are many ways to do it.

Hello, I am going through the SkyRoute project and was curious about task 40. It states:

  1. Inside the for loop, create a nested for loop that checks each current_station and its corresponding neighboring_stations set from the vc_metro dictionary.

I wrote the related code, a task or two from before and after are incorporated into the code section below for further context, as:

  for station_under_construction in stations_under_construction:
    for current_station, neighboring_stations in vc_metro.items():
      if current_station != station_under_contruction:
        updated_metro[current_station] -= set(stations_under_construction)
      else:
        updated_metro[current_station] = set([])

However, the neighboring stations is never used so do we need to set it and apply the .items() to the dictionary? Is there any benefit in doing this vs. not doing space saving etc?