# Naive implementation of a program to generate optimal timetable for college

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)

"""
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:
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)
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)



And example data and main:

# Algorithms
algo = Course("Algorithms")

# OS
os = Course("Operating Systems")

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.

• 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. – prijatelj Jan 25 '18 at 16:03
• 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. – John Maged Jan 25 '18 at 17:31
• Are you sure about the spelling of "Wedensday" and "Thrusday"? – Gareth Rees Jan 26 '18 at 0:25
• @GarethRees Those are just typos. – John Maged Jan 26 '18 at 16:48

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

• 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 Jan 26 '18 at 16:58
• 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. – John Maged Jan 26 '18 at 17:00