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.