Course:CPSC312-2021/YearlyPrologue
Yearly Prologue
Authors: Bronwyn, Johann, Justin
What is the problem?
As a prolog(ue) to every academic year, you must build a timetable. There are courses you want to take, and constraints you'd like your timetable to satisfy - for example, you might not want courses starting at 8am, or you might not want to still be in class at 7pm. It's difficult to build a timetable that satisfies as many of your constraints as possible without computer assistance.
What is the something extra?
We plan to allow the user to dynamically specify certain constraints on the generated schedules. We also plan to ensure that all required sections for a course are scheduled and allow you to specify optional courses.
What did we learn from doing this?
We got our course data from an API and generated Prolog facts for each course and section. Generating these facts was relatively painless as Prolog's syntax and property triple patter makes it trivial to scrape data and extend facts about existing entities with new properties.
While creating the Prolog that would schedule the courses there were many interesting things that came up. Firstly, the importance of the order of clauses was shocking at first. It makes sense in hindsight but initially, since I was picturing this as making rules for how the world is I thought order wouldn't matter as A and B is equivalent to B and A. Which is true but sometimes one order causes an error, or causes the program to never terminate. The first of these I encountered, was when the recursive call generates something I need for an additional check. If the recursive call doesn't come first, than the item isn't generated yet and Prolog isn't smart enough to just fill it in or check if something will handle it later, instead it errors out. Sometimes order also leads to the program never finishing as the check that prevents an infinite loop is later in the clause.
Secondly, throughout our code there were several times that we would be generating a list of a different size than the list that we started with. An example of this, we will take a list of courses and then we need to generate a list of sections. These aren't necessarily the same length as some courses require multiple sections, ie a lecture and a lab. This initially would cause us problems as how we had initially implemented it there was nothing preventing us from just adding infinite sections for each course. Some of this was solved by bounding the size of the list that we are generating first (order of clauses back at it again). This initially looked to be sufficient, it would generate a correct list, except on a retry it wouldn't fail, it would just sit there infinitely adding items to the list. I needed to combine two properties into one to make sure that the list was properly bounded and would fail properly.
Thirdly, we ran into this problem that upon retry, we would get the same schedule for at least the first fifty retries. We found the findall predicate that would allow us to produce all the unique schedules and prevented us from producing identical schedules. This was also helpful for our code for determining all the terms that a section occurs during, as we ran into some problems with year long courses.
One piece that we struggled a bit with was while making our duration definition. Sometimes we would provide a start time and an end time and generate a duration, sometimes we would provide a start time and a duration and generate an end time. This would cause a problem as how we would calculate these times depending on the how the start minutes related to the end minutes. This would cause problems as generating an end time before know how to generate it wasn't possible. We, once again, tried to solve this by re-ordering the clauses. This almost worked, expect is caused problems, it caused an error when any of the arguments weren't instantiated, but when we used = the expression wouldn't get evaluated. We tried combining the two methods and that didn't work either. We ended up with the solution that is slightly hacky, where we ended up with two properties, one that generates the end time and one the generates the duration.
We also learned a lot about dealing with statefulness in UIs through assert and retract.
Limitations
One of the biggest challenges that we had to face was the increasing polynomial time complexity as the number of sections to be scheduled increased. We found that attempting to schedule more than five courses in one schedule resulted in execution times beyond what a normal user might tolerate. Sadly there was no way around this issue which ultimately proved to be limited by the NP-hard nature of calculating every possible permutation of the sections under a given set of constraints. We attempted to work around this issue using Prolog's cut operator but that could only be utilized so much. Learning about cut was really fascinating and there were a few different ways that we could take advantage of it in our code. One benefit was that each of our properties were unique for a particular section, so after getting the value for a particular property for a section, we do not want to backtrack and search for a different property that we knew didn't exist. We couldn't use it too much, because then we wouldn't generate all possible schedules, just one possible one.
We also found it hard to implement pre-requisite course requirements as a valid constraint in our system. Some courses require an explicit set of courses to be taken beforehand while others give the student a choice of a specified number of courses from a provided set. Furthermore, some courses require specialized rules for taking course (e.g. a course in CPSC with a course number of 3XX) that only added to difficulty of modeling a pre-req constraint. While each of these sub-constraints could have been modeled individually, we opted to model constraints that could be fully implemented while also not increasing the time complexity of schedule generation dramatically.