Naive implementation of a program to generate optimal timetable for college

Question

College registration for the next semester is soon, So I decided to make a naive implementation (Bruteforce) for a program to generate an optimal timetable in terms of number of work days I need to attend. Even though this problem is NP-hard, but that's no problem for the size of input of my problem (6-7 courses maximum)

Here are some things to consider about our courses system:

• Each course can be included in 2 or 3 groups
• A student can register any course from any different group, but you must register the whole course (i.e. section and lab for that course must be the from the same group as the lecture)
• One day is divided into 12 periods, Any part of a course (Lecture, section or lab) can be between 1 to 3 periods.

First, Here's CollegeSchedule.py Where I have some classes declaration

from collections import defaultdict

workdays = ('Saturday', 'Sunday', 'Monday', 'Tuesday', 'Wedensday', 'Thrusday')


class Course():

    """
    This class contains infomation about a college course such as course
    name and in which group it occurs in.
    Each course consists of a lecture and a section at least, some courses
    has extra slot for a lab.
    """

    def __init__(self, name):

        self.name = name
        self.occurances = defaultdict(list)

    def add_slot(self, group, day, periods, type_):
        S = Slot(self, group, day, periods, type_)
        self.occurances[group].append(S)

    def get_group_slots(self, group):
        if group in self.occurances:
            return self.occurances[group]
        # In the rare case where a course is only present in 2 groups only
        return None

    def __str__(self):

        result = ""
        for group, slots in self.occurances.items():
            result += "Group " + str(group) + ":\n"
            for slot in slots:
                result += slot.get_type() + "\n"
                result += "Day: " + \
                    str(slot.day) + " Group: " + str(slot.group) + \
                    " Periods: " + str(slot.periods) + "\n"

        return result


class Slot():

    """
    This class represents a slot in a timetable (part of a course), including the
    type of that part (i.e. lecture, section or lab) along with
    the periods in which that part takes place (We've 12 periods per day, each slot
    can be between 1 to 3 periods),
    Day in which that part occurs,
    group number,
    and course name.
    """

    def __init__(self, course, group, day, periods, type_):
        self.course = course.name
        self.group = group
        self.day = day
        self.periods = periods
        self.type = type_

    def get_type(self):
        return self.type

    def __str__(self):
        result = "Course: " + self.course + " Group " + \
            str(self.group) + " " + str(self.type) + \
            " Periods " + str(self.periods)
        return result

    def __repr__(self):
        return self.__str__()


class Timetable:
    """
    A very simple Timetable representation, Has a dictionary with a
    key being the day number and the value is a list of slots
    that are part of the Timetable.
    """

    def __init__(self):
        self.work_days = defaultdict(list)

    def add_course(self, course_slots):
        """
        Tries to add a whole course (Lecture, section and lab) into the timetable.
        Returns boolean indicating if adding was successful.
        """

        if not course_slots:
            return False

        for slot in course_slots:
            can_add = self.check_slot(slot)
            if not can_add:
                return False
            self.work_days[slot.day].append(slot)

        return True

    def check_slot(self, slot):
        """
        Checks if a slot can be added into the Timetable
        by checking if the slot periods intersect with any other slot
        in the same day.
        """
        day = slot.day

        if not day in self.work_days:
            return True

        for t_slot in self.work_days[day]:
            t_time = t_slot.periods
            time = slot.periods
            new_time = (max(t_time[0], time[0]), min(t_time[1], time[1]))

            if new_time[0] <= new_time[1]:
                return False

        return True

    def print_timetable(self):
        """
        Print the timetable in a sorted way.
        First sorted by days, and inside each day sorted by periods.
        """
        days_list = sorted(self.work_days)
        for day in days_list:
            print(workdays[day])
            self.work_days[day].sort(key=lambda x: x.periods[0])
            print(*self.work_days[day], sep="\n")


    def total_days(self):
        return len(self.work_days)

And here's the method generate_best_timetables which actually generates the timetables

def generate_best_timetables(courses, MAX_GROUP_NUM = 3):
    """
    Generating every possible solution to the problem, Here I am Generating
    3**N possible tuples Where 3 is the maximum number of groups and N is the number of
    courses to consider.
    Each element value in the tuple correspond to a group number - 1 (0, 1, 2), and the i-th element
    in the tuple correspond to the i-th course in the list of courses.
    i.e. for i-th element in the tuple, we try to add the tuple[i]+1 group of the i-th
    course to the timetable.
    """

    total_tt = []
    best_tt = None
    COURSES_NUM = len(courses)

    for p in product(range(MAX_GROUP_NUM), repeat=COURSES_NUM):
        tt = Timetable()
        valid = True

        for i, val in enumerate(p):
            course_slots = courses[i].get_group_slots(int(val) + 1)
            valid = tt.add_course(course_slots)
            if not valid:
                break

        if valid:
            # Store all the timetables with minimum number of work days
            if not best_tt or tt.total_days() < best_tt.total_days():
                best_tt = tt
                total_tt = [best_tt]
            elif tt.total_days() == best_tt.total_days():
                total_tt.append(tt)

    return total_tt

And example data and main:

# Algorithms
algo = Course("Algorithms")
algo.add_slot(1, 0, (1, 2), "Lecture")
algo.add_slot(1, 0, (3, 4), "Section")
algo.add_slot(1, 1, (3, 4), "Lab")

algo.add_slot(2, 0, (1, 2), "Lecture")
algo.add_slot(2, 2, (1, 2), "Section")
algo.add_slot(2, 3, (1, 2), "Lab")

# OS
os = Course("Operating Systems")
os.add_slot(1, 0, (5, 6), "Lecture")
os.add_slot(1, 0, (7, 8), "Section")
os.add_slot(1, 1, (5, 6), "Lab")

os.add_slot(2, 0, (1, 2), "Lecture")
os.add_slot(2, 4, (7, 8), "Section")
os.add_slot(2, 5, (5, 6), "Lab")

def main():
    courses = [os, algo]
    total_tt = generate_best_timetables(courses)

    for tt in total_tt:
        tt.print_timetable()
        print("Working days: ", tt.total_days())
        print("================================")

What can I improve about my program?

I know I've problem with naming variables/classes/modules and the classes structure I've right now is not the best and the way I generate the next possible timetable in generate_best_timetables using product is kinda odd, and again, Performance is not an issue with the size of my problem so I'm not really considered about it for now.

For testing now, I'm adding the courses in code manually but I'll be populating the courses list from file (maybe csv file?) or database.

I would appreciate any comments on my code.

Answer 1

Notes:

• Good use of a tuple for workdays
• Good use of defaultdict
• Decent documentation. Weird wrapping. Should follow some kind of standard.
• Good use of itertools.product

Some minor nitpicks:

• PEP 8! (line length, " for format strings, ' for all other strings, etc.)
• We prefer class Course: to class Course():
• You should never have a blank line after a line ending in :
• You should use an enum for the workdays (this will improve readability later on--I had no idea what those numbers in the course initialization meant):

class Workday(Enum):
    Saturday = 0
    Sunday = 1
    Monday = 2
    Tuesday = 3
    Wednesday = 4
    Thursday = 5
    # NOTE: Friday missing?

• In get_group_slots the in check isn't very Pythonic. Python subscribes to the try and handle the failure if it happens philosophy. Namely, indexing a nonexistent key in a dict will produce an KeyError. So that code should look like:

def get_group_slots(self, group):
    try:
        return self.occurances[group]
    except KeyError:
        return None

• Your __str__ looks very java-y. We prefer building strings by employing format strings (or f-strings if you're on Python 3.6, which I'll use in this example) and string.join (I will add that it is a little strange that you define a __str__ on Slot but don't use it):

def __str__(self):
    # This is still a bit unwieldy, but it conveys your intent a bit better 
    def str_slot(slot):
        return f'{slot.get_type()}\nDay: {slot.day} Group: {slot.group} ' \
               f'Periods: {slot.periods}'

    return '\n'.join("Group {}:\n{}".format(group, '\n'.join(map(str_slot, slots)))
                     for group, slots in self.occurances.items())

• On Slot, defining __repr__ as __str__ isn't right in this context. __repr__ should be unambiguous in its representation of your object. Generally they look like <Slot ...>. __str__ is for pretty printing (as you have defined it)
• get_type is strange. Typically in Python we don't do getters and setters. Instead use the property decorator. Although, typically most people just expose the value as a regular property (because using the property syntax is verbose)
• Since Slot is immutable, it seems like a good candidate to be a namedtuple. This comes with immutable properties and a __repr__ for free.
• "Private" properties are prefixed with _ as an indicator
• Logic issue: why does add_course([]) return False? Seems like an empty class should be addable? Which leads me to:
• Your Course is a conflation between an object and the builder pattern. It is both at the same time. This is troubling, because typically in a typed language once you are able to new an object it should be fully built (and ready to use). I shouldn't need to thing = SomeThing(); thing.setupMoreStuff(). I'd actually suggest making Course a namedtuple too. Add a @classmethod called create for building a Course with a given name and slots (and perhaps this can assert that there is at least one slot). Slot doesn't need the first course parameter, so you remove the cyclic dependency. The ideal syntax in my mind looks like:

class Course(namedtuple('Course', ('name', 'occurances'))):
    @classmethod
    def create(cls, name, slots):
        occurances = defaultdict(list)
        for slot in slots:
            occurances[slot.group].append(slot)

        return cls(name, occurances)

    # ... define __str__ ...

Slot = namedtuple('Slot', ('group', 'day', 'periods', 'type'))

# Example Usage:
algorithms_course = Course.create('Algorithms', [
    # NOTE: Why are the groups 1 indexed!!
    # Note: The periods tuple is confusing.
    Slot(1, Workday.Saturday, (1, 2), 'Lecture'),
    Slot(1, Workday.Saturday, (3, 4), 'Lecture'),
    Slot(1, Workday.Sunday, (3, 4), 'Lab'),
    Slot(2, Workday.Saturday, (1, 2), 'Lecture'),
    Slot(2, Workday.Monday, (1, 2), 'Lecture'),
    Slot(2, Workday.Tuesday, (1, 2), 'Lab'),
])

• Similarly to before the check_slot and add_course dance in Timetable isn't super pythonic. add_slot should try to add and raise a special exception like ScheduleConflictError in the event it can't be added. You can still have the two separate methods, but I'd make check_slot "private" (by prefixing with _)
• Your defining of periods as tuples makes check_slot confusing. I'd name periods namedtuples as well and add an overlaps() method. Then _check_slot() becomes one line: return any(slot.overlaps(other_slot) for other_slot in self.work_days[slot.day])
• Making periods namedtuples also gives them a default ordering that will sort by the first element then the next (which is how you want periods sorted in print_timetable). Then you can define __lt__ on Slot and then sorting the slots for printing is just sorted(self.work_days[day]) (prefer this to .sort(), which mutates the underlying list unless that's what you want)
• Again in print_timetable prefer string.join and f-strings
• In generate_best_timetables:
  • Never use UPPER_SNAKE_CASE except for constants
  • Prefer x is None to not x
  • Instead of maintaining best_tt and total_tt, I would maintain a single list. When you find ties append() to the list. When you find a better one clear() the list. I'd call this collection best_timetables. We prefer no abbreviations. You can compare total days like so: best_timetables[0].total_days():

best_timetables = deque()

# ... snip ...

if valid:
    try:
        if tt.total_days() < best_timetables[0].total_days():
            best_timetables = [tt]
        elif tt.total_days() == best_timetables[0].total_days():
            best_timetables.append(tt)
    except IndexError:
        best_timetables = [tt]

- I wouldn't use `tt`. `current_timetable` is better.
- You don't need the `int(val)`. `val` is already an int
- The `valid` flag isn't very pythonic. And if you take my advice about raising `ScheduleConflictErorr`, then you can remove it and do the much more pythonic:

best_timetables = []

for p in product(range(max_group_num), repeat=len(courses)):
    try:
        current_timetable = Timetable()

        # NOTE: Prefer zip() to indexing
        for course, val in zip(courses, p):  # NOTE: name p better, what is it?
            timetable.add_course(course.occurances[val + 1])  # NOTE: val + 1 is still unclear, better naming may help here

        try:
            if tt.total_days() < best_timetables[0].total_days():
                best_timetables = [tt]
            elif tt.total_days() == best_timetables[0].total_days():
                best_timetables.append(tt)
        except IndexError:
            best_timetables = [tt]
    except ScheduleConflictError:
        pass

- Generate your `courses` inside `main()` right before `courses`!

- This file should be called college_schedule.py not CollegeSchedule.py