181 allocations[org] = slots |
184 allocations[org] = slots |
182 available_slots -= slots |
185 available_slots -= slots |
183 unallocated_applications_count -= org_applications_count |
186 unallocated_applications_count -= org_applications_count |
184 |
187 |
185 return allocations |
188 return allocations |
|
189 |
|
190 def preprocessingAllocation(self): |
|
191 """An algorithm that pre-processes the input before running as normal. |
|
192 """ |
|
193 |
|
194 adjusted_orgs = self.adjusted_orgs |
|
195 adjusted_slots = self.adjusted_slots |
|
196 locked_orgs = self.locked_orgs |
|
197 locked_slots = self.locked_slots |
|
198 unlocked_orgs = self.unlocked_orgs |
|
199 unlocked_applications = self.unlocked_applications |
|
200 |
|
201 total_popularity = sum(self.popularity.values()) |
|
202 |
|
203 available_slots = self.slots |
|
204 allocations = {} |
|
205 slack = {} |
|
206 |
|
207 for org in locked_orgs: |
|
208 popularity = self.popularity[org] |
|
209 mentors = self.mentors[org] |
|
210 slots = locked_slots[org] |
|
211 slots = min(slots, mentors) |
|
212 |
|
213 total_popularity -= popularity |
|
214 available_slots -= slots |
|
215 allocations[org] = slots |
|
216 |
|
217 # adjust the orgs in need of adjusting |
|
218 for org in adjusted_orgs: |
|
219 slots = adjusted_slots[org] |
|
220 |
|
221 adjustment = (float(total_popularity)/float(available_slots))*slots |
|
222 adjustment = int(math.ceil(adjustment)) |
|
223 self.popularity[org] += adjustment |
|
224 |
|
225 # adjust the popularity so that the invariants are always met |
|
226 for org in unlocked_orgs: |
|
227 popularity = self.popularity[org] |
|
228 mentors = self.mentors[org] |
|
229 |
|
230 slots = (float(popularity)/float(total_popularity))*available_slots |
|
231 slots = min(slots, self.max_slots_per_org) |
|
232 slots = max(slots, self.min_slots_per_org) |
|
233 slots = min(slots, mentors) |
|
234 |
|
235 popularity = (float(total_popularity)/float(available_slots))*slots |
|
236 |
|
237 self.popularity[org] = popularity |
|
238 |
|
239 # do the actual calculation |
|
240 for org in unlocked_orgs: |
|
241 org_applications = self.applications[org] |
|
242 org_applications_count = len(org_applications) |
|
243 |
|
244 popularity = self.popularity[org] |
|
245 raw_slots = (float(popularity)/float(total_popularity))*available_slots |
|
246 slots = int(math.floor(raw_slots)) |
|
247 |
|
248 slack[org] = raw_slots - slots |
|
249 allocations[org] = slots |
|
250 |
|
251 slots_left = available_slots - sum(allocations.values()) |
|
252 |
|
253 # add leftover slots, sorted by slack, decending |
|
254 for org, slack in sorted(slack.iteritems(), key=lambda (k,v): v, reverse=True): |
|
255 if slots_left < 1: |
|
256 break |
|
257 |
|
258 slots_left -= 1 |
|
259 allocations[org] += 1 |
|
260 |
|
261 return allocations |