CTU TimeTable Generator

2020/08
logo

Background

Building a good time table is hard. Actually NP hard. Doing such thing by hand is ugly and takes a lot of time. So does writing C++, but hey, that's at least somthing.
When my first semester at FIT CTU ended I finished it with pretty decent grades, so I had the option to choose my time table in the first wave. To make sure I get all classes I wanted before they fill up (and in case they did) I needed a quick way of building a time table on spot.

Development - source code

Generating all possible time tables is not hard. You just need to iterate recursively through all possible combinations of all classes.
But determining which time tables are better than others is harder. I had following requirements:

  • no classes starting at 7:30 AM
  • no classes starting at 9:15 AM when possible
  • spend less time in school in total
    • monolithic blocks of classes without time in between are better
  • keep all school days together
    • Monday + Tuesday + Wednesday is better than Thursday instead of Tuesday and so on
  • single lecture and nothing else doesn't matter, I can skip these easily
  • more lectures but nothing else doesn't really hurt too, but it's not preffered

With these requirements I was able to build a scoring algorithm.
Now I jsut had to generate all time tables, give a score to each one of them and print the best ones.

Well, in Python the app run for 20 minutes, although successfuly it took around 12 GB or RAM. Well, it works, but not really as I've imaginend. Sadly, the algoritm itself can not be much faster, but using a "faster" language with references, like C++, can.
After rewriting it in C++ the code runs for ~15 seconds. This is (probably and not only) because I don't need to make that many deep copies of many objects and with the option to easily share instances of objects the RAM usage dropped to nice 4 GB. Although still not optimal this result was someting I was looking for.

Technologies

There isn't really much to say about the Python implementation. I used purely standard library for better readability I've decided not to use many, if any, oneliners like list comprehentions and so on.

In the CPP version I used the json.hpp library to parse list of classes from FIT CTU time table API and to keep C++'s verbosity on sane levels I've decided to stick with auto (I know, not recommended), for in loops and other cool stuf we have in C++17.

Screenshots

Installation and usage

1) Spoof HTTP requests to https://timetable.fit.cvut.cz/new/api/sirius/courses/CLASS_NAME/events?... from timetable.fit.cvut.cz Using Chrome Dev tools and copy paste them to the rozvrh.json file following this structure:

{
    "FI-KSA": {"events":[...]},
    "BI-LIN": <copy pasted response from timetables>,
    ...
}

2) Compile with g++ -O3 --std=c++17 main.cpp

3) Pipe the input file to stdin of the program using cat rozvrh.json | ./a.out.