Problem 632933 · hard · Level 06 Heuristics & Optimization

Lectures, Rooms and Tired Students

gauntlet · timetabling · simulated annealing · hard and soft constraints · incremental evaluation

A college plans one teaching week: 5 days of 5 periods, 25 slots numbered day * 5 + period (slot 0 is Monday's first period, slot 24 Friday's last). Every event (a lecture) needs a slot and a room. Write plan_week(week) that returns place, a list with one (slot, room) pair per event.

Hard rules (a timetable that breaks one is invalid):

  • a room holds at most one event per slot;
  • the room must have at least size seats, and an event with lab true needs a room with lab true;
  • an event cannot be in any slot of its away list (its lecturer is not in);
  • no student may have two events in the same slot.

Soft rules, each costing 1 penalty point per student every time it happens:

  • the student has an event in the last period of a day;
  • the student has more than two events in a row on a day (1 point for each event beyond the second in a run);
  • the student has only one event on a day.

Make the total penalty as small as you can. week is a dict: "rooms" is a list of {"seats": int, "lab": bool}, "events" a list of {"size": int, "lab": bool, "away": [slots]} (size is the number of students attending) and "students" a list with, for each student, the events they attend. The tests build their weeks with college_week(n_events, n_rooms, n_students, seed), and week_penalty(week, place) computes the penalty (it does not check the hard rules). Both are available in your code.

How this problem is scored

The checker makes its own timetable by first fit: events in index order, each in the first slot, and in that slot the first room, that keeps every hard rule. Your timetable passes if it keeps every hard rule and its penalty is no higher than first fit's. Its quality (0 to 100) is the share of the gap between first fit and the best timetable we know that you close.

Examples

Input:  week = {"rooms": [{"seats": 30, "lab": False}, {"seats": 20, "lab": True}],
                "events": [{"size": 2, "lab": False, "away": []},
                           {"size": 2, "lab": True, "away": [0, 1]},
                           {"size": 1, "lab": False, "away": []},
                           {"size": 1, "lab": False, "away": [4]}],
                "students": [[0, 1, 2], [0, 1, 3]]}
Output: [(0, 0), (2, 1), (3, 0), (3, 1)]   (penalty 0)
Explanation: event 1 needs the lab (room 1) and cannot be in slots 0 or 1. Both students
             have Monday periods 0, 2 and 3: no run of three, nothing in the last period.
             First fit gives [(0, 0), (2, 1), (1, 0), (1, 1)]: both students then have
             periods 0, 1 and 2 in a row, 1 point each, penalty 2. Moving event 3 to slot 9
             instead would cost student 1 two points: Tuesday's only event, in the last period.

Input:  week = college_week(60, 5, 120, 3)
Output: any valid timetable with a penalty no higher than first fit (267 here)

Constraints

  • Up to 120 events, 8 rooms and 250 students; each student attends 3 to 6 events
  • First fit finds a valid timetable for every test.
  • Each test must finish in well under a second in your browser. Limit your loops by a number of steps, not by the clock, and use random (the tests seed it) so the result is the same every run.

Goals

  • Keep every hard rule satisfied while searching
  • Lower a penalty made of several soft rules
  • Score a move from a few bitmask lookups instead of recomputing the timetable
Starting Python…