forked from wkemmey/cpsc125_project_one
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathttr_graph.py
142 lines (134 loc) · 4.97 KB
/
ttr_graph.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
from collections import defaultdict
trains = [
['Vancouver', 'Seattle'],
['Vancouver', 'Calgary'],
['Calgary', 'Seattle'],
['Calgary', 'Winnipeg'],
['Calgary', 'Helena'],
['Helena', 'Seattle'],
['Portland', 'Seattle'],
['Portland', 'San Francisco'],
['Portland', 'Salt Lake City'],
['Salt Lake City', 'San Francisco'],
['Los Angeles', 'San Francisco'],
['Los Angeles', 'Las Vegas'],
['Los Angeles', 'Phoenix'],
['Las Vegas', 'Salt Lake City'],
['Salt Lake City', 'Helena'],
['Helena', 'Winnipeg'],
['Helena', 'Denver'],
['Salt Lake City', 'Denver'],
['Phoenix', 'Santa Fe'],
['Los Angeles', 'El Paso'],
['Phoenix', 'El Paso'],
['El Paso', 'Santa Fe'],
['Santa Fe', 'Denver'],
['Helena', 'Duluth'],
['Helena', 'Omaha'],
['Winnipeg', 'Duluth'],
['Winnipeg', 'Sault St Marie'],
['Denver', 'Omaha'],
['Denver', 'Kansas City'],
['Denver', 'Oklahoma City'],
['Santa Fe', 'Oklahoma City'],
['El Paso', 'Oklahoma City'],
['El Paso', 'Dallas'],
['El Paso', 'Houston'],
['Houston', 'Dallas'],
['Dallas', 'Oklahoma City'],
['Oklahoma City', 'Kansas City'],
['Omaha', 'Kansas City'],
['Omaha', 'Duluth'],
['Duluth', 'Sault St Marie'],
['Duluth', 'Toronto'],
['Duluth', 'Chicago'],
['Omaha', 'Chicago'],
['Dallas', 'Little Rock'],
['Oklahoma City', 'Little Rock'],
['Houston', 'New Orleans'],
['New Orleans', 'Little Rock'],
['Little Rock', 'Saint Louis'],
['Kansas City', 'Saint Louis'],
['Little Rock', 'Nashville'],
['Nashville', 'Saint Louis'],
['Saint Louis', 'Chicago'],
['Sault St Marie', 'Toronto'],
['Sault St Marie', 'Montreal'],
['Montreal', 'Toronto'],
['Montreal', 'Boston'],
['Montreal', 'New York'],
['Toronto', 'Pittsburgh'],
['Toronto', 'Chicago'],
['Boston', 'New York'],
['New York', 'Pittsburgh'],
['New York', 'Washington'],
['Pittsburgh', 'Chicago'],
['Pittsburgh', 'Saint Louis'],
['Pittsburgh', 'Nashville'],
['Pittsburgh', 'Raleigh'],
['Pittsburgh', 'Washington'],
['Washington', 'Raleigh'],
['Raleigh', 'Nashville'],
['Nashville', 'Atlanta'],
['Atlanta', 'Raleigh'],
['Raleigh', 'Charleston'],
['Atlanta', 'New Orleans'],
['Atlanta', 'Charleston'],
['Miami', 'Charleston'],
['Miami', 'Atlanta'],
['Miami', 'New Orleans']
]
tickets = [
['Los Angeles', 'New York', 21],
['Duluth', 'Houston', 8],
['Sault St Marie', 'Nashville', 8],
['New York', 'Atlanta', 6],
['Portland', 'Nashville', 17],
['Vancouver', 'Montreal', 20],
['Duluth', 'El Paso', 10],
['Toronto', 'Miami', 10],
['Portland', 'Phoenix', 11],
['Dallas', 'New York', 11],
['Calgary', 'Salt Lake City', 7],
['Calgary', 'Phoenix', 13],
['Los Angeles', 'Miami', 20],
['Winnipeg', 'Little Rock', 11],
['San Francisco', 'Atlanta', 17],
['Kansas City', 'Houston', 5],
['Los Angeles', 'Chicago', 16],
['Denver', 'Pittsburgh', 11],
['Chicago', 'Santa Fe', 9],
['Vancouver', 'Santa Fe', 13],
['Boston', 'Miami', 12],
['Chicago', 'New Orleans', 7],
['Montreal', 'Atlanta', 9],
['Seattle', 'New York', 22],
['Denver', 'El Paso', 4],
['Helena', 'Los Angeles', 8],
['Winnipeg', 'Houston', 12],
['Montreal', 'New Orleans', 13],
['Sault St Marie', 'Oklahoma City', 9],
['Seattle', 'Los Angeles', 9]
]
# this will initialize board as an empty dictionary, where each value is a set
board = defaultdict(set)
def convert_to_graph(board, trains):
for train in trains:
first_city = train[0]
second_city = train[1]
board[first_city].add(second_city)
board[second_city].add(first_city)
def find_path(board, first_city, second_city):
return True # replace this line with your code
def calculate_score(board, tickets):
score = 0
for ticket in tickets:
if find_path(board, ticket[0], ticket[1]):
score = score + ticket[2]
else:
score = score - ticket[2]
return score
# main
convert_to_graph(board, trains)
score = calculate_score(board, tickets)
print("The score is: {0}".format(score))