117 lines
5.3 KiB
Python
117 lines
5.3 KiB
Python
"""
|
|
Phase 2: labs.
|
|
|
|
Slightly more advanced than Phase 1 — places every lab offering's weekly
|
|
labs greedily first, against Phase 1's already-fixed placements. When a
|
|
lab can't be placed, this backtracks *recursively*: it bumps an
|
|
already-placed lab from earlier in this phase that shares the contested
|
|
resource (same instructor or same lab room), and tries to re-place the
|
|
stuck lab; if the bumped lab then can't find a new slot either, that
|
|
bumped lab is itself backtracked the same way (bump one of *its*
|
|
resource-sharing predecessors), and so on, until either everything
|
|
settles or the attempt budget is exhausted. Phase 1's sessions are never
|
|
touched — only Phase 2's own placements are ever moved.
|
|
"""
|
|
|
|
from . import grid
|
|
|
|
MAX_BACKTRACK_ATTEMPTS = 2000
|
|
|
|
|
|
def run(board, data):
|
|
"""Places every lab offering's weekly labs. Returns this phase's sessions."""
|
|
phase_start = len(board.sessions)
|
|
offerings = [o for o in data["offerings"] if not o["course"]["is_general"] and o["course"]["labs_per_week"] > 0]
|
|
|
|
placed_so_far = [] # [(offering, session), ...] placed so far in this phase
|
|
attempts = [0]
|
|
|
|
for offering in offerings:
|
|
course = offering["course"]
|
|
room_candidates = board.room_candidates(course["lab_room_id"], board.labs)
|
|
for _ in range(course["labs_per_week"]):
|
|
session = _place_lab_with_backtracking(board, offering, room_candidates, placed_so_far, attempts)
|
|
if session is None:
|
|
print(f"WARNING: could not place a lab for course {offering['course_id']} section {offering['section_id']} ({offering['batch_codes']}) even after backtracking")
|
|
else:
|
|
placed_so_far.append((offering, session))
|
|
|
|
return board.sessions[phase_start:]
|
|
|
|
|
|
def _place_lab_with_backtracking(board, offering, room_candidates, placed_so_far, attempts):
|
|
"""
|
|
Tries the plain first-fit placement first; if that fails, tries
|
|
bumping each resource-sharing predecessor (most recent first) out of
|
|
the way and recursively re-seating it, backing out cleanly if a given
|
|
bump doesn't lead anywhere. Returns the newly placed session dict, or
|
|
None if no arrangement works within the attempt budget.
|
|
"""
|
|
session = board.place_lab(offering, room_candidates, grid.DAYS)
|
|
if session is not None:
|
|
return session
|
|
|
|
# Snapshot the current candidates once — recursive calls will extend
|
|
# placed_so_far with their own successful re-seatings, but we only
|
|
# want to consider *this call's* view of what existed when we started.
|
|
candidate_room_ids = {r["room_id"] for r in room_candidates}
|
|
candidates = [
|
|
(other_offering, other_session)
|
|
for other_offering, other_session in placed_so_far
|
|
if _shares_contested_resource(offering, other_session, candidate_room_ids)
|
|
]
|
|
|
|
for other_offering, other_session in reversed(candidates):
|
|
if attempts[0] >= MAX_BACKTRACK_ATTEMPTS:
|
|
return None
|
|
attempts[0] += 1
|
|
|
|
if (other_offering, other_session) not in placed_so_far:
|
|
# Already moved by an earlier (failed) branch of this search.
|
|
continue
|
|
|
|
placed_so_far.remove((other_offering, other_session))
|
|
board.remove_session(other_session)
|
|
|
|
session = board.place_lab(offering, room_candidates, grid.DAYS)
|
|
if session is not None:
|
|
other_room_candidates = board.room_candidates(other_offering["course"]["lab_room_id"], board.labs)
|
|
new_other_session = _place_lab_with_backtracking(board, other_offering, other_room_candidates, placed_so_far, attempts)
|
|
if new_other_session is not None:
|
|
placed_so_far.append((other_offering, new_other_session))
|
|
return session
|
|
# Could not reseat the bumped lab even with recursion — undo
|
|
# our placement and put the bump back exactly as it was.
|
|
board.remove_session(session)
|
|
placed_so_far.append((other_offering, _restore_lab(board, other_offering, other_session)))
|
|
continue
|
|
|
|
# Bumping didn't free a usable slot for `offering` — restore and
|
|
# try the next candidate.
|
|
placed_so_far.append((other_offering, _restore_lab(board, other_offering, other_session)))
|
|
|
|
return None
|
|
|
|
|
|
def _restore_lab(board, offering, session):
|
|
"""Re-marks and re-adds a lab session dict exactly as it was."""
|
|
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)
|
|
|
|
|
|
def _shares_contested_resource(offering, other_session, candidate_room_ids):
|
|
"""
|
|
True if bumping other_session could plausibly free a slot offering
|
|
needs: shares the instructor, a usable lab room, or one of offering's
|
|
own batches (a batch can only be in one place at a time, so another
|
|
session competing for that batch's slot is a real contested resource
|
|
too, not just instructor/room).
|
|
"""
|
|
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"]))
|