A good friend of mine had the challenge of trying to build a schedule using all available times and classes through a spreadsheet... by hand. He asked me if I could build a program to generate valid schedules, and with search algorithms being one of my favorite things to do, I accepted the task.
At first glance through my research, I believed this to be an Interval Scheduling problem; however, since the courses have unique timespans on multiple days, I needed a better way to represent my data. Ultimately I constructed a graph where the vertices are the sections of a class and the neighbors are compatible sections. This allowed me to use a DFS-like algorithm to find schedules.
I have never asked for a code review since I am yet to take CS classes, but I would like to know where I stand with my organization, usage of data structures, and general approaches. One thing I also want an opinion on is commenting, something I rarely do and one day it will come back to haunt me. This is actually the first time I wrote docstrings, which I hope you will find useful in understanding the code.
Anyways, I exported a spreadsheet of the valid courses into a .csv file. Below is the Python code I wrote to parse the file and generate schedules:
scheduler.py
import csv
from collections import defaultdict
from enum import Enum
class Days(Enum):
"""
Shorthand for retrieving days by name or value
"""
Monday = 0
Tuesday = 1
Wednesday = 2
Thursday = 3
Friday = 4
class Graph:
"""
A simple graph which contains all vertices and their edges;
in this case, the class and other compatible classes
:param vertices: A number representing the amount of classes
"""
def __init__(self, vertices):
self.vertices = vertices
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
class Section:
"""
Used to manage different sections of a class
Includes all times and days for a particular section
:param section_str: A string used to parse the times at which the class meets
Includes weekday, start time, and end time
Format as follows: Monday,7:00,9:30/Tuesday,3:30,5:30/Wednesday,5:30,6:50
:param class_name: The name used to refer to the class (course)
:param preferred: Preferred classes will be weighted more heavily in the search
:param required: Search will force this class to be in the schedule
"""
def __init__(self, section_str, class_name='Constraint', preferred=False, required=False):
self.name = class_name
self.preferred = preferred
self.required = required
self.days = []
for course in section_str.rstrip('/').split('/'):
d = {}
data = course.split(',')
day_mins = Days[data[0]].value * (60 * 24)
d['start_time'] = self.get_time_mins(data[1]) + day_mins
d['end_time'] = self.get_time_mins(data[2]) + day_mins
self.days.append(d)
"""
Parses a time into minutes since Monday at 00:00 by assuming no class starts before 7:00am
:param time_str: A string containing time in hh:mm
:returns: Number of minutes since Monday 00:00
"""
@staticmethod
def get_time_mins(time_str):
time = time_str.split(':')
h = int(time[0])
if h < 7:
h += 12
return 60 * h + int(time[1])
"""
A (messy) method used to display the section in a readable format
:param start_num: minutes from Monday 00:00 until the class starts
:param end_num: minutes from Monday 00:00 until the class ends
:returns: A string representing the timespan
"""
@staticmethod
def time_from_mins(start_num, end_num):
# 1440 is the number of minutes in one day (60 * 24)
# This is probably the least clean part of the code?
day = Days(start_num // 1440).name
start_hour = (start_num // 60) % 24
start_min = (start_num % 1440) - (start_hour * 60)
start_min = '00' if start_min == 0 else start_min
start_format = 'am'
end_hour = (end_num // 60) % 24
end_min = (end_num % 1440) - (end_hour * 60)
end_min = '00' if end_min == 0 else end_min
end_format = 'am'
if start_hour > 12:
start_hour -= 12
start_format = 'pm'
time = f'{day} {start_hour}:{start_min}{start_format} => '
if end_hour > 12:
end_hour -= 12
end_format = 'pm'
time += f'{end_hour}:{end_min}{end_format}'
return time
"""
Checks to see if two time ranges overlap each other
:param other: Another section object to compare
:returns: boolean of whether the sections overlap
"""
def is_overlapping(self, other):
for range_1 in self.days:
for range_2 in other.days:
if range_1['end_time'] > range_2['start_time'] and range_2['end_time'] > range_1['start_time']:
return True
return False
def __repr__(self):
strs = []
for day in self.days:
strs.append(self.time_from_mins(day['start_time'], day['end_time']))
return '\n'.join(strs)
class Scheduler:
"""
This class powers the actual search for the schedule
It makes sure to fill all requirements and uses a
search algorithm to find optimal schedules
:param graph: Instance of a Graph object
:param num_courses: A constraint on the number of courses that the schedule should have
:param num_required: A number to keep track of the amount of required classes
"""
def __init__(self, graph, num_courses=5, num_required=1):
self.graph = graph.graph
self.paths = []
self.num_courses = num_courses
self.num_required = num_required
self.schedule_num = 1
"""
A recursive search algorithm to create schedules
Nodes are Section objects, with their neighbors being compatible courses
:param u: The starting node in the search
:param visited: A boolean list to keep track of visited nodes
:param path: List passed through recursion to keep track of the path
:returns: None (modifies object properties for use in __repr__ below)
"""
def search(self, u, visited, path):
num_courses = self.num_courses
visited[u] = True
path.append(u)
if len(self.paths) > 1000:
return
if len(path) == num_courses and len([x for x in path if x.required is True]) == self.num_required:
self.paths.append(list(path))
else:
for section in self.graph[u]:
if visited[section] == False and not any((x.is_overlapping(section) or (x.name == section.name)) for x in path):
self.search(section, visited, path)
path.pop()
visited[u] = False
def __repr__(self):
out = ''
for section in self.paths[self.schedule_num - 1]:
out += f'{section.name}\n{"=" * len(section.name)}\n{repr(section)}\n\n'
return out
def main():
"""
Setup all data exported into a .csv file, and prepare it for search
"""
data = {}
# Parse csv file into raw data
with open('classes.csv') as csvfile:
csv_data = csv.reader(csvfile, dialect='excel')
class_names = []
for j, row in enumerate(csv_data):
for i, item in enumerate(row):
if j == 0:
if i % 3 == 0: # I believe there is a better way to read by columns
name = item.strip('*')
class_names.append(name)
# Preferred classes are labelled with one asterisk, required with two
preferred = item.count('*') == 1
required = item.count('*') == 2
data[name] = {
'sections_raw': [],
'sections': [],
'preferred': preferred,
'required': required
}
else:
class_index = i // 3
data_ = data[class_names[class_index]]
data_['sections_raw'].append(item)
# Create Section objects which can be compared for overlaps
for _class in data: # Personally class is more natural for me than course or lecture, but I could replace it
sections_raw = data[_class]['sections_raw']
sections = []
cur_str = ''
# Section strings are always in groups of three (class name, start time, end time)
for i in range(0, len(sections_raw), 3):
if sections_raw[i] != '':
for x in range(3):
cur_str += sections_raw[i + x] + ','
cur_str += '/'
else:
if cur_str != '':
sections.append(Section(cur_str, _class, data[_class]['preferred'], data[_class]['required']))
cur_str = ''
else:
if cur_str != '':
sections.append(Section(cur_str, _class, data[_class]['preferred'], data[_class]['required']))
cur_str = ''
data[_class]['sections'] = sections
# A friend asked me to prevent the scheduler from joining classes at specific times
# I used my Section object as a constraint through the is_overlapping method
constraint = Section('Monday,4:00,6:00/' +
'Tuesday,7:00,9:30/Tuesday,3:30,5:30/' +
'Wednesday,4:00,6:00/' +
'Thursday,7:00,9:30/Thursday,3:30,5:30/' +
'Friday,7:00,10:00')
section_data = []
# Here we extract the compatible courses given the constraint
for x in data.values():
for s in x['sections']:
if not s.is_overlapping(constraint):
section_data.append(s)
graph = Graph(len(section_data))
for section in section_data:
graph.graph[section] = []
start = None
# Now we populate the graph, not allowing any incompatible edges
for section in section_data:
if start is None:
start = section
for vertex in graph.graph:
if not section.is_overlapping(vertex) and section.name != vertex.name:
graph.add_edge(vertex, section)
scheduler = Scheduler(graph)
visited = defaultdict(bool)
scheduler.search(u=start, visited=visited, path=[]) # We use our search algorithm with courses as nodes
# The scheduler doesn't actually weight the preferred classes, so we sort all our valid schedules using
# the lambda function and reverse the order to show schedules with preferred classes first
scheduler.paths = sorted(scheduler.paths, key=
lambda path: (len([p for p in path if p.preferred])),
reverse=True)
return scheduler
if __name__ == '__main__':
# The scheduler object is created, and now we need a way for the user to view one of their schedules
scheduler = main()
n = int(input(f'There are {len(scheduler.paths)} found.\nWhich schedule would you like to see?\n#: '))
if not 1 <= n <= len(scheduler.paths):
print(f'Enter a number between 1-{scheduler.paths}.')
else:
scheduler.schedule_num = n
print(scheduler)
The .csv file is generated from a spreadsheet that uses the following layout (visualizing it will help with understanding how I parse it):
classes.csv
SPAN 201,Start,End,POLS 110*,Start,End,ENVS 130,Start,End,ACT 210,Start,End,FSEM**,Start,End,QTM 100*,Start,End
Tuesday,9:00,9:50,Tuesday,1:00,2:15,Tuesday,11:30,12:45,Monday,1:00,2:15,Tuesday,10:00,11:15,Monday,4:00,5:15
Thursday,9:00,9:50,Thursday,1:00,2:15,Thursday,11:30,12:45,Wednesday,1:00,2:15,Thursday,10:00,11:15,Wednesday,4:00,5:15
Friday,9:00,9:50,,,,,,,,,,,,,Friday,9:00,9:50
,,,,,,,,,Monday,2:30,3:45,Monday,1:00,2:15,,,
Tuesday,10:00,10:50,,,,,,,Wednesday,2:30,3:45,Wednesday,1:00,2:15,Monday,4:00,5:15
Thursday,10:00,10:50,,,,,,,,,,,,,Wednesday,4:00,5:15
Friday,10:00,10:50,,,,,,,Monday,4:00,5:15,Monday,10:00,10:50,Friday,11:00,11:50
,,,,,,,,,Wednesday,4:00,5:15,Wednesday,10:00,10:50,,,
Tuesday,12:00,12:50,,,,,,,,,,Friday,10:00,10:50,Monday,4:00,5:15
Thursday,12:00,12:50,,,,,,,Tuesday,8:30,9:45,,,,Wednesday,4:00,5:15
Friday,12:00,12:50,,,,,,,Thursday,8:30,9:45,,,,Friday,1:00,1:50
,,,,,,,,,,,,,,,,,
Tuesday,1:00,1:50,,,,,,,Tuesday,10:00,11:15,,,,Tuesday,8:30,9:45
Thursday,1:00,1:50,,,,,,,Thursday,10:00,11:15,,,,Thursday,8:30,9:45
Friday,1:00,1:50,,,,,,,,,,,,,Friday,10:00,10:50
,,,,,,,,,Tuesday,1:00,2:15,,,,,,
Tuesday,2:00,2:50,,,,,,,Thursday,1:00,2:15,,,,Tuesday,8:30,9:45
Thursday,2:00,2:50,,,,,,,,,,,,,Thursday,8:30,9:45
Friday,2:00,2:50,,,,,,,,,,,,,Friday,12:00,12:50
,,,,,,,,,,,,,,,,,
Tuesday,3:00,3:50,,,,,,,,,,,,,Tuesday,8:30,9:45
Thursday,3:00,3:50,,,,,,,,,,,,,Thursday,8:30,9:45
Friday,3:00,3:50,,,,,,,,,,,,,Friday,2:00,2:50
,,,,,,,,,,,,,,,,,
Monday,10:00,10:50,,,,,,,,,,,,,Tuesday,10:00,11:15
Wednesday,10:00,10:50,,,,,,,,,,,,,Thursday,10:00,11:15
Friday,10:00,10:50,,,,,,,,,,,,,Friday,11:00,11:50
,,,,,,,,,,,,,,,,,
Monday,9:00,9:50,,,,,,,,,,,,,Tuesday,10:00,11:15
Wednesday,9:00,9:50,,,,,,,,,,,,,Thursday,10:00,11:15
Friday,9:00,9:50,,,,,,,,,,,,,Friday,1:00,1:50
,,,,,,,,,,,,,,,,,
Monday,2:00,2:50,,,,,,,,,,,,,Monday,2:30,3:45
Wednesday,2:00,2:50,,,,,,,,,,,,,Wednesday,2:30,3:45
Friday,2:00,2:50,,,,,,,,,,,,,Friday,10:00,10:50
,,,,,,,,,,,,,,,,,
Monday,3:00,3:50,,,,,,,,,,,,,Monday,2:30,3:45
Wednesday,3:00,3:50,,,,,,,,,,,,,Wednesday,2:30,3:45
Friday,3:00,3:50,,,,,,,,,,,,,Friday,2:00,2:50
,,,,,,,,,,,,,,,,,
Monday,4:00,4:50,,,,,,,,,,,,,,,
Wednesday,4:00,4:50,,,,,,,,,,,,,,,
Friday,4:00,4:50,,,,,,,,,,,,,,,
