Skip to content

Instantly share code, notes, and snippets.

@Junuxx
Last active March 2, 2023 16:20
Show Gist options
  • Save Junuxx/9e6ec7709d3b780eeac6 to your computer and use it in GitHub Desktop.
Save Junuxx/9e6ec7709d3b780eeac6 to your computer and use it in GitHub Desktop.
Solution for a StackOverflow scheduling problem
'''
Created on 26 jan. 2016
@author: Jeroen Kools
Based on the following StackOverflow question:
https://stackoverflow.com/questions/35002027/maximizing-a-combination-of-a-series-of-values#comment57732451_35002027
- 18 students
- 12 dates
- Each student must do tasks/presentations A, B and three Cs in any order
- No more than 2 As and no more than 2 Bs on a date
- Each student rates how much they like each date
- Each date should have at least 1 A, 1 B, 1 C
- Students should be assigned to at most 1 presentation per date (assumed)
- Maximize student happiness while fulfilling all other constraints
'''
import random
nStudents = 18
nDates = 12
violations = 0
student_prefs = []
students = []
dates = []
# random.seed(1) # keep random seed for student preferences the same
"""
spread_weight: How important it is to stick to the number of presentations per day constraints.
A high value, above 5, tries hard to avoid too many or not enough presentations of a type on a date,
but cares less about students' preferences. A value below 1 gives more importance to students' wishes,
and will only use the number of already scheduled presentations as a tiebreaker.
There is a separate value for C, since there's no hard limit to daily Cs.
"""
spread_weight = 10
spread_weight_C = 10
class Date:
count = 1
def __init__(self):
self.reset()
self.count = Date.count
Date.count += 1
def __str__(self):
return "[Date %s - A: %s, B: %s, C: %s" % (self.count, self.students["A"], self.students["B"],
[self.students["C1"], self.students["C2"], self.students["C3"]])
def __repr__(self):
return str(self.count)
def reset(self):
self.students = {"A": [], "B": [], "C1": [], "C2": [], "C3": []}
def is_available(self, task, student_nr, relax_max=False):
"""
Check if a student is eligible to be scheduled for a certain presentation type at a certain date
Fails if the student is already scheduled for a presentation on that date, or if there are already too
many presentation of that type on that date
"""
# does the student already have a task this day?
for task in self.students.keys():
if student_nr in self.students[task]: return False
if task in "AB" and (len(self.students["A"] + self.students["B"]) < 3 or relax_max):
if task == "A" and len(self.students["A"]) < 2: return True
if task == "B" and len(self.students["B"]) < 2: return True
elif "C" in task:
return True
else: return False
def set_student(self, task, student_nr):
"""Schedule a student for a task on this day"""
self.students[task].append(student_nr)
def has_student(self, student_nr):
"""If a certain student is scheduled for a task on this day, return which task. Otherwise return an empty string"""
for task in self.students:
if student_nr in self.students[task]:
return task
return ""
def tasks_scheduled(self, tasks=["A", "B", "C1", "C2", "C3"]):
return sum([len(self.students[task]) for task in tasks])
class Student:
count = 1
def __init__(self):
self.reset()
self.prefs = []
self.count = Student.count
Student.count += 1
def __str__(self):
return "[Student %03i - A: %s, B: %s, C: %s, Prefs: %s]" % \
(self.count, repr(self.dates["A"]), repr(self.dates["B"]),
[repr(self.dates["C1"]), repr(self.dates["C2"]), repr(self.dates["C3"])], self.prefs)
def reset(self):
self.dates = {"A": None, "B": None, "C1": None, "C2": None, "C3": None}
def rand_list(low, high, nr):
# Generate a list of nr random integers between low and high, inclusive
result = []
for _i in range(nr):
result.append(random.randint(low, high))
return result
def setup():
# Initializes students and dates objects
# TODO: Change the first few lines below here to use actual students' preferences instead of random numbers
for _i in range(nStudents):
l = rand_list(1, 5, 12)
l = [int(round(x)) for x in l]
student = Student()
student.prefs = l
students.append(student)
for _i in range(nDates):
date = Date()
dates.append(date)
def reset():
for student in students:
student.reset()
for date in dates:
date.reset()
global violations
violations = 0
def print_students():
for student in students:
print student
print
def get_favorite_day(student, lowest_acceptable=1, spread_weight=0.1, tasks_to_spread=["A", "B", "C1", "C2", "C3"]):
"""Sort dates by students' preference, with an optional preference for dates with fewer presentations scheduled"""
date_nr_pref = zip(range(nDates), student.prefs)
date_nr_pref = sorted(date_nr_pref,
key=lambda x: x[1] - spread_weight * dates[x[0]].tasks_scheduled(tasks_to_spread),
reverse=True)
return [x[0] for x in date_nr_pref if x[1] >= lowest_acceptable]
def available(date, task):
pass
# For each student, assign to their most preferred, available A date
def fill(task, lowest_acceptable, spread_weight=0.1, tasks_to_spread="ABC"):
random_order = range(nStudents)
random.shuffle(random_order)
for i in random_order:
student = students[i]
if student.dates[task]:
continue
preferred = get_favorite_day(student, lowest_acceptable, spread_weight, tasks_to_spread)
for date_nr in preferred:
date = dates[date_nr]
if date.is_available(task, student.count, lowest_acceptable == 1):
print " Set student %i's task %s to date %s, which they rated a %i" % (student.count, task, date.count, student.prefs[date.count - 1])
date.set_student(task, student.count)
student.dates[task] = date
break
setup()
print "Generated preferences:"
print_students()
print "===================\n"
start_at = 5
while start_at >= 1:
lowest_acceptable = start_at
while lowest_acceptable > 0:
print "* Lowest_acceptable =", lowest_acceptable
fill("A", lowest_acceptable, spread_weight, "AAB")
fill("B", lowest_acceptable, spread_weight, "ABB")
if lowest_acceptable == 1:
fill("C1", lowest_acceptable, spread_weight_C, ["C1", "C2", "C3"])
fill("C2", lowest_acceptable, spread_weight_C, ["C1", "C2", "C3"])
fill("C3", lowest_acceptable, spread_weight_C, ["C1", "C2", "C3"])
lowest_acceptable -= 1
for date in dates:
if not date.students["C1"] and not date.students["C2"] and not date.students["C3"]:
violations += 1
print "Violation! No C on date %i" % date.count
if not len(date.students["A"] + date.students["B"]) <= 3:
violations
violations += 1
print "---> Violation! Too many A/Bs on day %i <---" % (date.count)
if violations > 0 and start_at > 1:
start_at -= 1
print "Trying again, start_at lowered to", start_at
reset()
else:
break
print "\n===================\n"
print_students()
for date in dates:
print date
first_col_width = 8
other_col_width = 5
total_width = (nDates * (other_col_width + 1) + first_col_width)
print "\n\n" + str.center("Date", total_width)
print "=" * total_width
print str.ljust("Student", first_col_width - 1) + " |" + "".join([str.center(str(x), other_col_width) + "|" for x in range(1, nDates + 1)])
print "=" * total_width
for student in students:
print str.center(str(student.count), first_col_width - 1) + \
" |" + "".join([ str.center(date.has_student(student.count), other_col_width) + \
"|" for date in dates])
print "=" * total_width
actual_sum = 0
top_5_sum = 0
for student in students:
top_5 = get_favorite_day(student, 1, 0)[:5]
for date_index in top_5:
top_5_sum += student.prefs[date_index]
actual_sum += student.prefs[student.dates["A"].count - 1] + \
student.prefs[student.dates["B"].count - 1] + \
student.prefs[student.dates["C1"].count - 1] + \
student.prefs[student.dates["C2"].count - 1] + \
student.prefs[student.dates["C3"].count - 1]
print "Total student satisfaction: %i/%i = %.2f%%" % (actual_sum, top_5_sum, 100 * actual_sum / top_5_sum)
print "Constraint violations: ", violations
print "Initial target value set to", start_at
@kescobo
Copy link

kescobo commented Jan 27, 2016

Can I do a PR on a gist? I added the real student responses here (rows are dates, columns are students - there's 19 now because they added a student to the class last minute).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment