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?

Hi there guys! Awesome to read that I am not the only one having the issue. I was tracking the graph manually and I was sure that Marine Building (a) and Granville Street (l) were connected via Burrard and Granville station or via Waterfront and Vancouver City Centre. Once I included Waterfront in the list of being under construction, the program constantly returned that Marine Building and Granville street were not connected due to maintenance. It means that it did not see the connection via Burrard and Granville. Reading the comment form @patrickd314 I indeed see that the get_route() function returned None, before checking all possible start and end stations listed at the landmarks. Thus, as soon as it sees that Waterfront is not an option the function returns without checking the next options. I solved it by setting a variable in the function “possible” to False and I changed it to True if in all options a possible connection was found via DFS(). The same holds for when there is no station under construction, then the variable is being set to True as well. In the end the function returns None is possible variable has not been changed to True and return the route if it has been changed to True. Below I will paste my implementation of the altered get_route() function:

def get_route(start_point, end_point):
  start_stations = vc_landmarks[start_point]
  end_stations = vc_landmarks[end_point]
  routes = []
  possible = False
  for start_station in start_stations:
    for end_station in end_stations:
      metro_system = get_active_stations() if stations_under_construction else vc_metro
      if stations_under_construction:
        possible_route = dfs(metro_system, start_station, end_station)
        if possible_route:
          possible = True # sets variable to True as a route has been found in ALL options
          print('yay') # debugging statement, never been so happy to read 'yay'
      route = bfs(metro_system, start_station, end_station)
      if route:
        possible = True #changed to True as there are no stations in maintenance
        routes.append(route)
  if possible == False:
    return None      
  shortest_route = min(routes, key=len)
  return shortest_route

Hope this helps others that may be confused! Happy coding :wink:

1 Like

Hello guys, i wanted to upload my skyroute application code with the bonus challenges as well. If you think there’s something i can improve, let me know! Happy coding :grinning_face_with_smiling_eyes:

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

# ----- Global variables -----
landmark_string = ""
for letter, landmark in landmark_choices.items():
  landmark_string += "{0} - {1}\n".format(letter, landmark)

stations_under_construction = []

Here goes a spoiler of the second bonus challenge:

# ----- Functions -----

def update_stations_status():
  station_status = input("Which station status would you like to update to 'in construction'?: ")
  if station_status in vc_metro:
    if station_status not in stations_under_construction:
      stations_under_construction.append(station_status)
      print("The station {0} status has been updated to under construction.".format(station_status))
    else:
      stations_under_construction.remove(station_status)
  else:
    print("That is not a valid station. Let's try again...")
    update_stations_status()

#Greets user to the application
def greet_user():
  print("Hi there and welcome to SkyRoute application!")
  print("We'll help you find the shortest route between the following Vancouver landmarks:\n" + landmark_string)
  
def greet_employee():
  print("Hello there employee and welcome to SkyRoute application!")
  print("Lets update the stations status!")

# Main function

def skyroute():
  choice = input("Are you a user or an employee? Enter 'u' or 'e', respectively: ")
  if choice in ["u", "e"]:
    if choice == "u":
      skyroute_users()
    elif choice == "e":
      skyroute_employees()
  else:
    print("That's not a valid choice. Let's try again...")
    skyroute()

def skyroute_users():
  greet_user()
  new_route()
  goodbye()

def skyroute_employees():
  greet_employee()
  update_stations_status()
  goodbye()
# Sets the start_point or end_point, or both
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:
      if change_point not in ["b", "o", "d"]:
        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 

# Retrieves the start_point from landmark_choices
def get_start():
  start_point_letter = input("Where are you coming from? Type on 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()

# Retrives the end_point from landmark_choices
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()

# Gets and sets the origin and destination
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)

Here comes another spoiler, the first function of the bonus challenges:

  if start_point == end_point:
    print("You have to change either the origin and destination because you cannot choose the same for both.")
    new_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)

# Shows landmarks to user if user wishes to
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)

# Says good bye to user
def goodbye():
  print("Thanks for using SkyRoute!")

# Gets the user the best route
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:
      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 is not None:
        routes.append(route)
  
  shortest_route = min(routes, key=len)
  return shortest_route

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

skyroute()