/
assignments.py
254 lines (188 loc) · 9.38 KB
/
assignments.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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
from model import connect_to_db, db, User, Attendee, Event, Table, SeatingRelationship
# db = SQLAlchemy()
def table_assignments(event_id, attendees, tables, total_seats):
''' Create table assignments '''
# dont even try to solve this if there isnt enough seats
if (total_seats < len(attendees)):
print "Not enough seats! {} attendees but only {} seats!".format(str(len(attendees)), str(total_seats))
return False
relationships = build_relationships(attendees)
clusters = build_clusters(attendees, relationships)
assignments = assign_seats(clusters, relationships, tables)
if not assignments:
print "No valid seating could be made. :("
return None
else:
# debugging
for table_id, seated_attendees in assignments.items():
print str(table_id) + " | " + str(seated_attendees)
print assignments
return assignments
def assign_seats(clusters, relationships, tables):
'''Put the attendees at tables based on their relationships'''
assignments = {}
# sort the clusters by size so we seat the biggest ones first
sorted_clusters = sorted(clusters, key=lambda cluster: -len(cluster))
# debugging
print "unsorted: " + str(clusters)
print "sorted: " + str(sorted_clusters)
success = assign_seats_recursive(assignments, sorted_clusters, relationships, tables)
if success:
return assignments
else:
return None
def assign_seats_recursive(assignments, sorted_clusters, relationships, tables):
''' Attempt to seat a cluster at a table'''
# if you have already seated all your clusters, the length will return zero,
# so then we have seated everyone
if len(sorted_clusters) == 0:
return True
# take the first cluster
cluster = sorted_clusters[0]
cluster_size = len(cluster)
#create sets of the other relationships
must_not_attendees = set()
want_attendees = set()
# create sets of ids who have a must_not and a want relationship with the attendee
for attendee_id in cluster:
if 'must_not' in relationships[attendee_id]:
must_not_attendees.update(relationships[attendee_id]['must_not'])
if 'want' in relationships[attendee_id]:
want_attendees.update(relationships[attendee_id]['want'])
attempted_tables = set()
while True:
table_id = get_table_id_to_attempt(tables, cluster_size, attempted_tables, must_not_attendees, want_attendees, assignments)
print "{} trying table {}...".format(str(attendee_id), str(table_id))
if not table_id:
print "No table found for " + str(cluster) + ", returning False"
return False
# if the table is not assigned, add it to the dictionary with an empty list
if table_id not in assignments:
assignments[table_id] = []
print "BEFORE: " + str(assignments[table_id])
# seat the cluster at the table and mark that we tried that table
assignments[table_id].extend(cluster)
attempted_tables.add(table_id)
print "AFTER: " + str(assignments[table_id])
# continue trying to seat the reamining clusters and cutting off each cluster as you go
success = assign_seats_recursive(assignments, sorted_clusters[1:], relationships, tables)
if not success:
# if the seating attempt was unsuccessful after the recursion, unseat this cluster
# by unassigning each attendee from the cluster that was seated at the table we tried
for attendee_id in cluster:
assignments[table_id].remove(attendee_id)
print "Recursion failed, unseating cluster {} for table {}".format(str(cluster), str(table_id))
else:
print "Success for cluster {} for table {}".format(str(cluster), str(table_id))
return True
def count_wants(table, assignments, want_attendees):
''' Counts the number of wanted attendees currently seated at the table'''
wants = 0
seated_attendees = assignments.get(table, [])
for want_attendee in want_attendees:
if want_attendee in seated_attendees:
wants += 1
return wants
def get_table_id_to_attempt(tables, cluster_size, attempted_tables, must_not_attendees, want_attendees, assignments):
''' Gets a table that:
-doesn't have anyone sitting at it that must not be sat with
-has enough space
-hasn't been tried
-priorities the table with the most people we want to sit with
'''
# sort the tables so the biggest ones are first
# the lambda function take number of seats at a table and subtracts the number of seats assigned at that table
# giving back the number of available seats
sorted_tables = sorted(tables.keys(), key=lambda table: -(tables[table] - len(assignments.get(table, []))))
# sort the tables so the ones with the most wants at them are first
# using a function in a lambda is cool
# https://stackoverflow.com/questions/134626/which-is-more-preferable-to-use-in-python-lambda-functions-or-nested-functions
sorted_tables = sorted(sorted_tables, key=lambda table: -count_wants(table, assignments, want_attendees))
print "tables unsorted: " + str(tables.values())
print "tables sorted: " + str(sorted_tables)
for table in sorted_tables:
# if there are not enough seats at this table, skip it
if tables[table] - len(assignments.get(table, [])) < cluster_size:
continue
# if we've already tried this table, skip it
if table in attempted_tables:
continue
# if we hate someone who is there, skip it
if not must_not_attendees.isdisjoint(assignments.get(table, [])):
continue
return table
return None
def build_clusters(attendees, relationships):
'''Builds a list of lists of attendee id clusters'''
clusters = []
for attendee_id in attendees:
attendee_relationships = relationships[attendee_id]
# get the list of must sit withs, or an empty list if no musts
must_attendees = []
if 'must' in attendee_relationships:
must_attendees = attendee_relationships['must']
in_a_cluster = False
# check all the clusters for the attendee or the attendee's musts
for cluster in clusters:
# if the attendee was already in a cluster, stop
if attendee_id in cluster:
in_a_cluster = True
break
# if the musts share an attendee with this cluster, add the attendee
# testing if two lists share an item
# https://stackoverflow.com/questions/3170055/test-if-lists-share-any-items-in-python
if not set(cluster).isdisjoint(must_attendees):
cluster.append(attendee_id)
in_a_cluster = True
# loop through the must_attendees list and if the must_attendee
# is not in the cluster, add them.
for must_attendee in must_attendees:
if must_attendee not in cluster:
cluster.append(must_attendee)
break
# if there were no musts to sit, with then none of the musts were clustered yet,
# so seat the attendee and his musts
if not in_a_cluster:
cluster = [attendee_id]
cluster.extend(must_attendees)
clusters.append(cluster)
# print out the clusters for debugging
for cluster in clusters:
print str(cluster)
return clusters
def build_relationships(attendees):
''' Builds a dictionary attendee_ids to dictionaries of relationship code to attendee id'''
relation_dict = {}
for attendee_id in attendees:
# create dictionary of attendees with their attendee_id as the key
attendee_relationship_dict = {}
# store the relationships for that attendee
# both primary attendee and secondary attendee are considered
relationships = db.session.query(SeatingRelationship).filter(
(SeatingRelationship.primary_attendee == attendee_id) | (
SeatingRelationship.secondary_attendee == attendee_id)).all()
# iterate through their relationships
for r in relationships:
relationship_code = None
relationship_attendee = None
if r.primary_attendee == attendee_id:
relationship_attendee = Attendee.query.get(r.secondary_attendee)
else:
relationship_attendee = Attendee.query.get(r.primary_attendee)
relationship_code = r.relationship_code
relationship_id = relationship_attendee.attendee_id
# add the relationship_id to the set of attendee_ids for the relationship_code
if relationship_code in attendee_relationship_dict:
attendee_relationship_dict[relationship_code].add(relationship_id)
else:
attendee_relationship_dict[relationship_code] = set([relationship_id])
# store the relationships for this attendee in the relationship_dict
relation_dict[attendee_id] = attendee_relationship_dict
# print out the relationships for debugging
for tup, val in relation_dict.items():
print str(tup) + " | " + str(val)
return relation_dict
if __name__ == "__main__":
from server import app
connect_to_db(app)
table_assignments()