Solution for a StackOverflow scheduling problem

class_projects.py

'''
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

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).