A school has n exams to fit into k time slots, numbered 0 to k - 1 in time order. Each
student takes a few exams. A timetable is judged from the students' point of view:
- every pair of a student's exams in the same slot costs 10 points (they would have to sit both at once);
- every pair in neighbouring slots (
sands + 1) costs 1 point (no time to revise).
Write plan_exam_week(n, students, k) that returns a list slots of length n, where slots[e] is
the slot of exam e. students is a list with one entry per student: the sorted list of their
exams. Slots may hold any number of exams. Lower cost is better.
The tests build their data with enrolments(n, number_of_students, seed), and
timetable_cost(students, slots) computes the cost. Both are available in your code.
How this problem is scored
The checker makes its own timetable: exams 0, 1, 2, ... in turn go to the slot where they cost
least given the exams already placed (the lowest slot on a tie); then, exam by exam and slot by
slot, it moves an exam whenever that lowers the cost, until a whole pass changes nothing. Your
timetable passes if it costs no more than that one. Its quality (0 to 100) says how much of
the gap between that timetable and the best one we know you close.
Examples
Input: n = 20, students = enrolments(20, 150, 1), k = 6
Output: a list of 20 slot numbers from 0 to 5
the checker's timetable costs 1058; the best known costs 917
Constraints
20 <= n <= 120,150 <= len(students) <= 1400,6 <= k <= 14; each student takes 3 to 5 exams- Each test must finish in well under a second in your browser. Limit your loops by a number of
iterations, not by the clock, and use
random(the tests seed it) for random choices.
Goals
- Keep a search moving after a local optimum by always taking the best allowed move
- Use short-term memory (a tabu list) to stop the search from undoing its last moves
- Maintain a table of move costs so every candidate move is a lookup