Repository navigation
Expand file tree
/
Copy pathsubwayPlanning.py
More file actions
120 lines (106 loc) · 4.85 KB
/
Copy pathsubwayPlanning.py
File metadata and controls
120 lines (106 loc) · 4.85 KB
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
# -----------------
# User Instructions
#
# Write a function, subway, that takes lines as input (read more about
# the **lines notation in the instructor comments box below) and returns
# a dictionary of the form {station:{neighbor:line, ...}, ... }
#
# For example, when calling subway(boston), one of the entries in the
# resulting dictionary should be 'foresthills': {'backbay': 'orange'}.
# This means that foresthills only has one neighbor ('backbay') and
# that neighbor is on the orange line. Other stations have more neighbors:
# 'state', for example, has 4 neighbors.
#
# Once you've defined your subway function, you can define a ride and
# longest_ride function. ride(here, there, system) takes as input
# a starting station (here), a destination station (there), and a subway
# system and returns the shortest path.
#
# longest_ride(system) returns the longest possible ride in a given
# subway system.
# -------------
# Grading Notes
#
# The subway() function will not be tested directly, only ride() and
# longest_ride() will be explicitly tested. If your code passes the
# assert statements in test_ride(), it should be marked correct.
def subway(**lines):
"""Define a subway map. Input is subway(linename='station1 station2...'...).
Convert that and return a dict of the form: {station:{neighbor:line,...},...}"""
## your code here
subway_map = {}
for index in lines.keys():
station_line = lines[index].split()
for station in station_line:
station_index = station_line.index(station)
if station_index == 0:
subway_map.setdefault(station, {})[station_line[station_index+1]] = index
elif station_index == len(station_line)-1:
subway_map.setdefault(station, {})[station_line[station_index-1]] = index
else:
subway_map.setdefault(station, {})[station_line[station_index+1]] = index
subway_map.setdefault(station, {})[station_line[station_index-1]] = index
#print subway_map
return subway_map
boston = subway(
blue='bowdoin government state aquarium maverick airport suffolk revere wonderland',
orange='oakgrove sullivan haymarket state downtown chinatown tufts backbay foresthills',
green='lechmere science north haymarket government park copley kenmore newton riverside',
red='alewife davis porter harvard central mit charles park downtown south umass mattapan')
def ride(here, there, system=boston):
"Return a path on the subway system from here to there."
## your code here
#subway_system = subway(boston)
#print system
return shortest_path_search(here, lambda s: system[s], lambda s : s == there)
def longest_ride(system):
""""Return the longest possible 'shortest path'
ride between any two stops in the system."""
## your code here
#print system
stops = set(a for i in boston.values() for a in i)
return max([ride(a,b) for a in stops for b in stops], key=len)
def shortest_path_search(start, successors, is_goal):
"""Find the shortest path from start state to a state
such that is_goal(state) is true."""
if is_goal(start):
return [start]
explored = set() # set of states we have visited
frontier = [ [start] ] # ordered list of paths we have blazed
while frontier:
path = frontier.pop(0)
s = path[-1]
for (state, action) in successors(s).items():
if state not in explored:
explored.add(state)
path2 = path + [action, state]
if is_goal(state):
return path2
else:
frontier.append(path2)
return []
def path_states(path):
"Return a list of states in this path."
return path[0::2]
def path_actions(path):
"Return a list of actions in this path."
return path[1::2]
def test_ride():
assert ride('mit', 'government') == [
'mit', 'red', 'charles', 'red', 'park', 'green', 'government']
assert ride('mattapan', 'foresthills') == [
'mattapan', 'red', 'umass', 'red', 'south', 'red', 'downtown',
'orange', 'chinatown', 'orange', 'tufts', 'orange', 'backbay', 'orange', 'foresthills']
assert ride('newton', 'alewife') == [
'newton', 'green', 'kenmore', 'green', 'copley', 'green', 'park', 'red', 'charles', 'red',
'mit', 'red', 'central', 'red', 'harvard', 'red', 'porter', 'red', 'davis', 'red', 'alewife']
print "ride okay"
assert (path_states(longest_ride(boston)) == [
'wonderland', 'revere', 'suffolk', 'airport', 'maverick', 'aquarium', 'state', 'downtown', 'park',
'charles', 'mit', 'central', 'harvard', 'porter', 'davis', 'alewife'] or
path_states(longest_ride(boston)) == [
'alewife', 'davis', 'porter', 'harvard', 'central', 'mit', 'charles',
'park', 'downtown', 'state', 'aquarium', 'maverick', 'airport', 'suffolk', 'revere', 'wonderland'])
assert len(path_states(longest_ride(boston))) == 16
return 'test_ride passes'
print test_ride()