194 lines
8.9 KiB
Python
194 lines
8.9 KiB
Python
"""
|
|
Phase 3: remaining (non-general) theory courses — batch by batch, with
|
|
recursive multi-bump backtracking.
|
|
|
|
Processes batches in sorted batch_code order. Each batch must be fully
|
|
placed with zero conflicts before moving to the next batch. If a batch's
|
|
courses can't all be placed, this backtracks into *earlier, already-
|
|
completed Phase 3 batches*: it bumps sessions that share a contested
|
|
resource (same instructor, same room, or same batch) with the stuck
|
|
offering out of the way — trying combinations of more than one bumped
|
|
session where a single bump isn't enough — then reseats every bumped
|
|
session afterward (recursively backtracking again if a reseat itself gets
|
|
stuck), until either everything settles or the attempt budget is
|
|
exhausted.
|
|
|
|
Phase 1 and Phase 2 sessions are never touched — only sessions this phase
|
|
itself placed for earlier batches are ever reopened.
|
|
"""
|
|
|
|
from . import grid
|
|
|
|
MAX_BACKTRACK_ATTEMPTS = 5000
|
|
MAX_SIMULTANEOUS_BUMPS = 3
|
|
|
|
|
|
def run(board, data):
|
|
"""
|
|
Places every remaining (non-general) theory offering's weekly
|
|
lectures, batch by batch. Returns this phase's sessions.
|
|
"""
|
|
phase_start = len(board.sessions)
|
|
offerings = [o for o in data["offerings"] if not o["course"]["is_general"]]
|
|
|
|
# placed_so_far: flat list of (offering, session) for every session
|
|
# this phase has placed so far (across all completed batches) — the
|
|
# pool backtracking is allowed to bump from.
|
|
placed_so_far = []
|
|
attempts = [0]
|
|
|
|
for batch in sorted(data["batches"], key=lambda b: b["batch_code"]):
|
|
batch_code = batch["batch_code"]
|
|
batch_offerings = [o for o in offerings if batch_code in o["batch_codes"]]
|
|
# Place the most slot-constrained offerings first (long-lecture
|
|
# courses can only ever use slot 0, so they have the fewest
|
|
# options) — this way flexible 90-min courses fill in around them
|
|
# instead of greedily grabbing slot 0 first and starving a
|
|
# long-lecture course that has nowhere else to go.
|
|
batch_offerings.sort(key=lambda o: 0 if o["course"]["lecture_duration_minutes"] == 120 else 1)
|
|
|
|
for offering in batch_offerings:
|
|
course = offering["course"]
|
|
room_candidates = board.room_candidates(course["lecture_room_id"], board.classrooms)
|
|
for _ in range(course["lectures_per_week"]):
|
|
session = _place_lecture_with_backtracking(board, offering, room_candidates, placed_so_far, attempts)
|
|
if session is None:
|
|
print(
|
|
f"WARNING: could not place a lecture for course {offering['course_id']} "
|
|
f"section {offering['section_id']} (batch {batch_code}) even after backtracking"
|
|
)
|
|
else:
|
|
placed_so_far.append((offering, session))
|
|
|
|
return board.sessions[phase_start:]
|
|
|
|
|
|
def _place_lecture_with_backtracking(board, offering, room_candidates, placed_so_far, attempts):
|
|
"""
|
|
Tries the plain first-fit placement first; if that fails, tries
|
|
bumping *combinations* of resource-sharing predecessors out of the way
|
|
(starting with one at a time, then pairs, up to MAX_SIMULTANEOUS_BUMPS
|
|
together) until `offering` fits, then reseats every bumped session
|
|
(recursively backtracking again if a reseat itself gets stuck).
|
|
Returns the newly placed session dict, or None if no arrangement works
|
|
within the attempt budget.
|
|
"""
|
|
session = board.place_lecture(offering, room_candidates, grid.DAYS)
|
|
if session is not None:
|
|
return session
|
|
|
|
candidate_room_ids = {r["room_id"] for r in room_candidates}
|
|
usable_slot_indices = {grid.LONG_LECTURE_SLOT_INDEX} if offering["course"]["lecture_duration_minutes"] == 120 else set(grid.TEACHING_SLOT_INDICES)
|
|
candidates = [
|
|
(other_offering, other_session)
|
|
for other_offering, other_session in placed_so_far
|
|
if _shares_contested_resource(offering, other_session, candidate_room_ids, usable_slot_indices)
|
|
]
|
|
# Most recently placed first — later placements are more likely to be
|
|
# "loose" (easier to reseat) than earlier, already-settled ones.
|
|
candidates.reverse()
|
|
|
|
for bump_count in range(1, min(MAX_SIMULTANEOUS_BUMPS, len(candidates)) + 1):
|
|
result = _try_bump_combinations(board, offering, room_candidates, placed_so_far, attempts, candidates, bump_count)
|
|
if result is not None:
|
|
return result
|
|
if attempts[0] >= MAX_BACKTRACK_ATTEMPTS:
|
|
return None
|
|
|
|
return None
|
|
|
|
|
|
def _try_bump_combinations(board, offering, room_candidates, placed_so_far, attempts, candidates, bump_count):
|
|
"""
|
|
Tries every way of picking `bump_count` candidates (in order) to bump
|
|
simultaneously, retrying `offering`'s placement after each bump.
|
|
Returns the newly placed session on success (with all bumped sessions
|
|
reseated), or None if no combination of this size works.
|
|
"""
|
|
from itertools import combinations
|
|
|
|
for combo in combinations(range(len(candidates)), bump_count):
|
|
if attempts[0] >= MAX_BACKTRACK_ATTEMPTS:
|
|
return None
|
|
|
|
chosen = [candidates[i] for i in combo]
|
|
if any((o, s) not in placed_so_far for o, s in chosen):
|
|
# One of these was already moved by an earlier failed branch.
|
|
continue
|
|
|
|
bumped = []
|
|
for other_offering, other_session in chosen:
|
|
attempts[0] += 1
|
|
placed_so_far.remove((other_offering, other_session))
|
|
board.remove_session(other_session)
|
|
bumped.append((other_offering, other_session))
|
|
|
|
session = board.place_lecture(offering, room_candidates, grid.DAYS)
|
|
if session is not None:
|
|
if _reseat_all(board, placed_so_far, attempts, bumped):
|
|
return session
|
|
# Reseating some bumped session failed even with recursion —
|
|
# undo our placement and restore everything bumped this round.
|
|
board.remove_session(session)
|
|
for other_offering, other_session in bumped:
|
|
placed_so_far.append((other_offering, _restore_session(board, other_offering, other_session)))
|
|
continue
|
|
|
|
# This combination didn't free a usable slot — restore everything
|
|
# bumped this round and try the next combination.
|
|
for other_offering, other_session in bumped:
|
|
placed_so_far.append((other_offering, _restore_session(board, other_offering, other_session)))
|
|
|
|
return None
|
|
|
|
|
|
def _reseat_all(board, placed_so_far, attempts, bumped):
|
|
"""
|
|
Reseats every (offering, session) in `bumped` (each currently removed
|
|
from the board), backtracking recursively if needed. All-or-nothing:
|
|
on any failure, every session reseated so far in this attempt is
|
|
removed again and `bumped` remains fully un-seated (the caller is
|
|
responsible for restoring them to their original slots).
|
|
"""
|
|
reseated = []
|
|
for other_offering, other_session in bumped:
|
|
other_room_candidates = board.room_candidates(other_offering["course"]["lecture_room_id"], board.classrooms)
|
|
new_session = _place_lecture_with_backtracking(board, other_offering, other_room_candidates, placed_so_far, attempts)
|
|
if new_session is None:
|
|
for reseated_offering, reseated_session in reseated:
|
|
placed_so_far.remove((reseated_offering, reseated_session))
|
|
board.remove_session(reseated_session)
|
|
return False
|
|
reseated.append((other_offering, new_session))
|
|
placed_so_far.append((other_offering, new_session))
|
|
return True
|
|
|
|
|
|
def _restore_session(board, offering, session):
|
|
"""Re-marks and re-adds a session dict exactly as it was, at the same day/slots/room."""
|
|
room = board.data["rooms_by_id"][session["room_id"]]
|
|
for slot_index in session["slot_indices"]:
|
|
board.mark_busy(session["day"], slot_index, session["room_id"], session["instructor_code"], session["batch_codes"])
|
|
return board.add_session(
|
|
offering, session["day"], session["slot_indices"], room,
|
|
is_long_lecture=(session["duration_minutes"] == 120),
|
|
)
|
|
|
|
|
|
def _shares_contested_resource(offering, other_session, candidate_room_ids, usable_slot_indices):
|
|
"""
|
|
True if bumping other_session could plausibly free a slot `offering`
|
|
can actually use: other_session must occupy at least one slot index
|
|
`offering` is eligible for, AND share the instructor, a usable room,
|
|
or (crucially) one of offering's own batches — a batch can only be in
|
|
one place at a time, so another course competing for the *same batch's*
|
|
slot-0 time is just as real a contested resource as instructor/room.
|
|
"""
|
|
if not any(slot_index in usable_slot_indices for slot_index in other_session["slot_indices"]):
|
|
return False
|
|
if other_session["instructor_code"] == offering["instructor_code"]:
|
|
return True
|
|
if other_session["room_id"] in candidate_room_ids:
|
|
return True
|
|
return bool(set(other_session["batch_codes"]) & set(offering["batch_codes"]))
|