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.

• prijatelj: You may want to specify what you want (or think can be) improved. Run time, memory efficiency, compile time, readability, etc... Or if you want a more optimal algorithm than bruteforce.
• John Maged: I'd like a general comment on my code, point out to any possible bugs or improvement in generating the time table function (A better way than using product possibly?). Also any suggestion for a better structure for my classes.
• Gareth Rees: Are you sure about the spelling of "Wedensday" and "Thrusday"?
• John Maged: @GarethRees Those are just typos.

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

• John Maged: I've gone through your comment a couple of times, it makes a lot of sense, Friday is missing because I'm from Egypt -I don't go to college by Camel!- , Friday is the weekend day. In my original code add_course([]) or rather add_course(None) in some sense should be addable, but the problem here is I'm generating all possibilities for say, 3 groups (max) and 3 courses, but if first group only happens to be only in 2 groups, possibility 222 can't happen as the first course has no slots in that group and I have to take that course in solution.
• John Maged: Thanks a lot for your effort and notes! I'll read your notes a couple more times and go through improving my code, I'll end up making an update post if I improve it further more.