Ever wondered how the timetabling algorithm of NUSMods works? Read on to find out.
Firstly start let's define the data representation of a Lesson:
Lesson = {
ClassNo: string,
DayText: string,
EndTime: string,
LessonType: string,
ModuleCode: string,
StartTime: string,
Venue: string,
WeekText: string
};
A timetable component essentially takes in an array of Lessons and does a few transformations on them to convert it into a representation that can be easily rendered.
Each day on the timetable is represented as a row in the UI and is independent of other days. With that understanding, we can start by grouping the array of Lessons by their DayText. Passing that array through the groupLessonsByDay function, we will get:
{
Monday: [LessonA, LessonB, LessonC],
Tuesday: [LessonD, ...]
};
Next, the aim is to resolve the Lesson within a day and arrange them such that if there are Lessons that overlap in time, they get pushed into an available row. If there are no available rows, a new row will be created. Each day's array of Lessons are independent, and can be processed separately by passing the array into arrangeLessonsWithinDay.
For example, given that we have 3 Lessons on Monday with the following StartTime and EndTimes:
| Lesson | StartTime | EndTime |
|---|---|---|
| 1 | 1000 | 1200 |
| 2 | 1100 | 1300 |
| 3 | 1400 | 1500 |
Initially, the arrangement for Monday is empty. A circle, O represents an unoccupied timetable cell lasting an hour, and the first ⚪️ indicates 0800 - 0900. Hence from 0800 - 1800, we have 10 circles:
⚪️⚪️⚪️⚪️⚪️⚪️⚪️⚪️⚪️⚪️
and the arrangement looks like:
[ // Only one row in this array
[] // and the row is an empty array
]
First we process Lesson 1. There are no lesson overlapping conflicts to resolve as the row is empty. We can simply add Lesson 1 to it. The two ⚪️ at 1000 and 1100 are changed to 1️⃣ to represent that they are occupied by Lesson 1.
⚪️⚪️1️⃣1️⃣⚪️⚪️⚪️⚪️⚪️⚪️
The arrangement of lessons for Monday will then look like this. Only one row with one lesson.
[
[Lesson1]
]
Next we process Lesson 2. However, Lesson 2 overlaps with the existing Lesson 1 in row 1. There are no empty rows available to consider, hence we have to add a new row within Monday to accommodate Lesson 2:
⚪️⚪️1️⃣1️⃣⚪️⚪️⚪️⚪️⚪️⚪️
⚪️⚪️⚪️2️⃣2️⃣⚪️⚪️⚪️⚪️⚪️
The arrangement of lessons after adding a new row and pushing Lesson B in:
[
[Lesson1],
[Lesson2]
]
Lastly, we process Lesson 3. Lesson 3 is able to fit into the first row:
⚪️⚪️1️⃣1️⃣⚪️⚪️3️⃣3️⃣⚪️⚪️
⚪️⚪️⚪️2️⃣2️⃣⚪️⚪️⚪️⚪️⚪️
The final arrangement of lessons for Monday:
[
[Lesson1, Lesson3],
[Lesson2]
]
We are not concerned with the ordering of the lessons within a row because it should be resolved by the components that render it. The only invariant of this representation is that no lesson within each row will overlap with each other.
arrangeLessonsForWeek applies arrangeLessonsWithinDay to each day's array of Lessons and we will get something along the lines of:
{
Monday: [
[Lesson1, Lesson3],
[Lesson2]
],
Tuesday: [
[Lesson4, Lesson5]
],
Thursday: [
[Lesson6, Lesson7, Lesson8],
[Lesson9, Lesson10]
]
}
The advantage of this data representation is that it's extremely flexible and can be consumed by different kinds of UI rendering paradigms, such as React, React Native, or even a linear timeline without boxes!
With this data representation in place, rendering the timetable is a trivial matter of iterating over the days and then over each row within that day. Combining the timetable of multiple people can be achieved by combining everyone's arrays of Lessons into one before applying the above transformations.