[Performance] Optimize performance by reducing search space with pruning

[voonhous]

Background

While b9ab611 is a stop-gap to terminate the traversal of the search-space prematurely for the backtracking algorithm when 10k results is reached, it might be insufficient under cases where users have selected a designated "free-time".

When a "free-time" is selected, the backtracking algorithm might have to traverse a larger search-space to find the required solution. On top of that, there might not be a solution in the search space. As such, the 10k hard limit will not be reached, causing the algorithm to run sufficiently long, causing a 503 TIMEOUT.

Example

Let's use the AY2023-2024 example for computer engineering. [source]

The number of indexes for each of the mod can be is as such:

Module	Number of Index(es)
SC1003	35
SC1005	23
SC1013	27
MH1810	71
EG1001	51
CC0003	658
CC0005	644

The search space has a size of (product of number of indexes in each module) 33,350,314,236,120 (33 trillion).

Problem

If users did not specify a "I want a free day", the page will quickly return the first 10k valid results. However, if users specifies that they want a free day, the search space will be too large and will cause a timeout before ANY valid results is returned.

Solution

Given that users have provided the blocks of free time that they want, indexes in each module can be pruned if they clash with the free time blocks that users provided. The fix should take advantage of the fact that users' provided free time is actually not DEPENDENT on any other modules<>indexes. Hence this can be done ahead of traversal.

The pruning of indexes will have a linear run time of O(N), where N is the sum of indexes of the modules provided by user.

The pruning can take place after check exam schedule. This will drastically reduce the search space required to traverse by the backtracking algo.

plan/back_end/scheduler.php

Lines 44 to 69 in e98560c

	# Put dummy data for user selected free time
	$timetable = select_free_time($timetable, $user_free_times_selection);
	$result = array("validation_result" => validate_input($input_courses, $database_course));
	if ($result["validation_result"]) {
	$result["exam_schedule_validation"] = check_exam_schedule($input_courses);
	$result["exam_schedule"] = $exam_schedule;
	}
	# Filter HW0188 based on the user major
	filter_HW0188_timetable($user_major);
	# Filter HY0001 off when generating timetable
	{
	$key = array_search('HY0001', $input_courses, true);
	if ($key !== FALSE) {
	unset($input_courses[$key]);
	}
	# "reindex" the array
	$input_courses = array_values($input_courses);
	}
	# Generate all possible timetables
	generate_timetable($input_courses, $timetable);
	$result["timetable"] = $all_timetable;
	$result["too_many_results"] = $too_many_solutions;

Impact

Basically any modules that have a large set of indexes (usually common mods) which Y1 students are suppose to take.

Difficulty

Low, need to implement a prune function to return the list of indexes for each module that does not clash with user's free time by reusing check_clash function.

[kenrick95]

@voonhous Thanks for the feedback

I might be wrong, since the codes was written almost 10 years ago, but I think we already did that? We marked the timetables' slots here as occupied before we even start with the generate_timetable

plan/back_end/scheduler.php

Line 45 in e98560c

$timetable = select_free_time($timetable, $user_free_times_selection);

though if you think you can optimize it further, feel free to send a pull request