-
Notifications
You must be signed in to change notification settings - Fork 1
/
skyroute.py
143 lines (121 loc) · 5.83 KB
/
skyroute.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
from graph_search import bfs, dfs
from vc_metro import vc_metro
from vc_landmarks import vc_landmarks
from landmark_choices import landmark_choices
#String which joins all of the landmarks together
landmark_string = ""
#list below accounts for stations which are closed
stations_under_construction = ['Templeton', 'King Edward']
#For loops to join the landmarks together
for letter, landmark in landmark_choices.items():
landmark_string += "{0} - {1}\n".format(letter, landmark)
#print(landmark_string)- test
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)
def goodbye():
print("Thanks for using SkyRoute!")
#Requests a startpoint 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() #enables the user to try again
#Request a end point 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() #enables the user to try again
#The following function will be taking care of setting the start and destination points
def set_start_and_end(start_point, end_point):
if start_point is not 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 == 'd':
start_point = get_start()
elif change_point == 'd':
end_point = get_end()
else:
print("Please enter either '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
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)
def get_route(start_point, end_point):
#start_stations will be looking at all stations we could possibly start at given the landmark
start_stations = vc_landmarks[start_point]
#end_stations will be looking at all the end stations we could possibly end given the landmark
end_stations = vc_landmarks[end_point]
#list collecting the shortest routes
routes = []
#looping through every combination of start and end stations
for start_station in start_stations:
for end_station in end_stations:
#looking at how many stops it takes from start to finish
#landmarks are being passed in
#print("Iterating over {0} and {1}".format(start_station, end_station))#USE for Testing only
metro_system = get_active_stations() if stations_under_construction else vc_metro
#check if stations_under_construction is empty
#Checks to see if a route EXISTS using Depth First Search
if len(stations_under_construction) > 0:
possible_route = dfs(metro_system, start_station, end_station)
if possible_route is None:
return None
#Breath First Search used to find the shortest route
route = bfs(metro_system, start_station, end_station)
#if there is a route we append the shortest route to routes list we created above
if route:
routes.append(route)
#print("Routes list consists of : " + str(routes))
shortest_route = min(routes, key=len)
return shortest_route
#TEST IF get_route WORKS---------
#print(get_route('Marine Building', 'Robson Square'))
##['Waterfront', 'Vancouver City Centre']- is the shortest route
def get_active_stations():
updated_metro = vc_metro
#loop checking for any connections to and from stations which are closed
for station_under_construction in stations_under_construction:
for current_station, neighboring_station in vc_metro.items():
if current_station != station_under_construction:
#this will set substract stations under construction from updated_metro.
updated_metro[current_station] -= set(stations_under_construction)
#when the current_station is a station_under_construction
else:
updated_metro[current_station] = set([])
return updated_metro
#TEST-CASE ------Use to test if get_active_stations function works
# for active_stations, connections in active_stations.items():
# print(active_stations + '-' + str(connections))
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)
#changing the format of shortest_route.
if shortest_route is not None:
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?\n Enter y/n: ")
if again == "y":
show_landmarks()
new_route(start_point, end_point)
def skyroute():
greet()
new_route()
goodbye()
skyroute()