Python assignment exercise: verify pair feasibility separately from optimality

Operation contract

The exercise accepts a small owned eligibility graph and a proposed list of worker-slot tuples. Each worker and slot may occur once, and every pair must be an allowed edge. The accepted two-pair proposal uses both available slots. A duplicated slot and an ineligible edge are rejected. An empty proposal is feasible even though a larger assignment exists. That final distinction prevents a test from mistaking a valid result for an optimal result.

Failure and ownership boundary

The function validates the graph itself before looking at the proposal, including exact integer slot IDs and duplicate eligibility edges. It does not repair invalid pairs or trust a solver simply because that solver returned a list. Python bipartite matching: augment an assignment instead of taking the first free slot supplies the optimization algorithm. The independent test enumerates small alternatives to compare its pair count, while this checker focuses on feasibility.

Working program

def valid_assignment(allowed, slot_count, pairs):
    if type(allowed) is not list or len(allowed) > 8 or type(slot_count) is not int or not 0 <= slot_count <= 8 or type(pairs) is not list or len(pairs) > 8:
        raise ValueError("assignment bounds")
    for row in allowed:
        if type(row) is not list or any(type(slot) is not int or not 0 <= slot < slot_count for slot in row) or len(set(row)) != len(row):
            raise ValueError("eligibility fields")
    workers, slots = set(), set()
    for pair in pairs:
        if type(pair) is not tuple or len(pair) != 2:
            return False
        worker, slot = pair
        if type(worker) is not int or type(slot) is not int or not 0 <= worker < len(allowed) or slot not in allowed[worker] or worker in workers or slot in slots:
            return False
        workers.add(worker)
        slots.add(slot)
    return True

allowed = [[0, 1], [0]]
for proposal in ([(0, 1), (1, 0)], [(0, 0), (1, 0)], [(1, 1)], []):
    print("feasible:", valid_assignment(allowed, 2, proposal))

Output

feasible: True
feasible: False
feasible: False
feasible: True

Costs and limits

Graph validation scans E eligibility entries and verifying P pairs scans the corresponding small rows, with O(P) used-vertex storage. The eight-by-eight cap bounds this work. Removing the cap should use indexed eligibility sets and separately account for their construction; optimality checking by enumeration grows exponentially.

Common Mistakes

• A feasible empty result can still miss every possible assignment.
• Check uniqueness and eligibility, not only the number of returned pairs.

Connected lessons

Python bipartite matching: augment an assignment instead of taking the first free slot, Python collection exercise: reject repeated receipt IDs before committing state, Python refactoring: preserve rejected inputs as well as accepted results.