6
\$\begingroup\$

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

Spreadsheet with class data

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,,,,,,,,,,,,,,,
\$\endgroup\$
1
  • \$\begingroup\$ Is there any reason for putting the docstrings above methods and not inside 'em? Looks really weird this way \$\endgroup\$ – Grajdeanu Alex Apr 11 '19 at 5:21
0
\$\begingroup\$

one thing is sure, there's too much logic going on in your main. your main should be clean, i.e. presenting only functions or methods and minimal logic, as, at a glance we can figure out what's going on when the main function is called

the blocks of code handle way too much related logics, break them up!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.