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.
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, time), min(t_time, time)) if new_time <= new_time: 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) 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.