Handing out the allotments

A council has more applicants than allotment plots, and an applicant will not take a plot they cannot walk to. The clerk wants the letting sheet as full as it will go.

The problem

Plots are numbered from 0. wanted[i] lists the plots applicant i will accept. A plot goes to one applicant and an applicant gets one plot; an applicant who names no acceptable plot gets nothing.

Report the largest number of applicants that can hold a plot at the same time.

Input. wanted — a list of lists of plot numbers, one list per applicant.

Output. The greatest number of applicants that can be placed.

Example.

wanted = [[0, 1], [0], [1, 2]]   ->  3

Applicant 1 will take only plot 0. Give plot 0 to applicant 0 and the sheet stops at two — unless applicant 0 moves to plot 1, which leaves plot 2 for applicant 2 and all three placed.

A second example, where the plots run out:

wanted = [[0], [0], [0]]   ->  1

Three applicants and one plot between them. No amount of moving people helps, because there is nowhere for anyone to move to.

Constraints.

• 1 <= len(wanted) <= 200 applicants, and plot numbers below 200
• each applicant's list holds distinct plot numbers and may be empty
• a plot nobody names simply stays vacant

Hints

Approach

Brute force

Try every way of handing the plots out and keep the fullest sheet. With A applicants and P plots there are up to (P + 1)^A assignments: ten applicants over ten plots is already 2.6·10¹⁰, and the register holds 200 of each.

The insight

Take the applicants one at a time, and when every plot one of them wants is taken, ask each holder to move: if the chain of requests ends at a vacant plot, everyone in the chain shifts along by one and the newcomer is placed.

That chain is an augmenting path, and it never costs a placement — each person in it gives up one plot and receives another, so the number placed rises by exactly one. Asking after a plot at most once per applicant stops the chain circling, and nobody already placed is ever left without a plot. That is why handling the applicants in any single pass reaches the largest sheet: a placement is only ever moved, never undone.

Algorithm

1. Keep taken, a map from plot to the applicant holding it.
2. For each applicant in turn, start a search with a fresh set of plots already asked after.
3. For a wanted plot not yet asked after, mark it asked. Take it if it is vacant, or if the applicant holding it can move by the same search.
4. Count the applicants the search places.

Complexity

Time O(A · E) — one search per applicant, and a search follows each applicant-plot pair at most once: 200 × 40000 = 8·10⁶ at the top of the range. Space O(A + P) for the map and the asked-after set.

Solution

"""Handing out the allotments — augmenting paths, one applicant at a time."""


def can_place(newcomer, wanted, taken):
    """Seat this applicant, moving current holders along if that frees a plot."""
    tried = set()                     # asked once per newcomer, so the chain cannot loop
    # One frame per link in the chain of "can you move?" requests: the applicant
    # asked, and how many of their plots have been put to them so far. Keeping the
    # chain on this stack rather than in call frames means its depth costs nothing.
    stack = [[newcomer, 0]]
    while stack:
        applicant, asked = stack[-1]
        if asked == len(wanted[applicant]):
            stack.pop()               # this holder cannot move; whoever asked tries elsewhere
            continue
        stack[-1][1] = asked + 1
        plot = wanted[applicant][asked]
        if plot in tried:
            continue
        tried.add(plot)
        if plot in taken:
            stack.append([taken[plot], 0])   # occupied: ask the holder to move
            continue
        # A vacant plot ends the chain, so every frame on it takes the plot it
        # just asked after — each holder shifts along by one and nobody is unplaced.
        for holder, step in stack:
            taken[wanted[holder][step - 1]] = holder
        return True
    return False


def solve(wanted):
    taken = {}                        # plot -> the applicant holding it
    placed = 0
    for applicant in range(len(wanted)):
        if can_place(applicant, wanted, taken):
            placed += 1               # a placed applicant is never unplaced, only moved
    return placed


# Each applicant wants the plot before them and their own, so seating the last
# one walks a request chain through all 200 — the search keeps its own stack.
_CHAIN = [[0]] + [[i - 1, i] for i in range(1, 200)]

TESTS = [
    (([[0, 1], [0], [1, 2]],), 3),
    (([[0], [0], [0]],), 1),                  # three applicants, one plot between them
    (([[], [0]],), 1),                        # an applicant who can work no plot
    (([[0, 1], [0, 1]],), 2),
    (([[0], [0, 1], [1, 2], [2, 3]],), 4),    # each applicant after the first asks a holder to move
    (([[0], [0, 1], [1, 2], [2]],), 3),       # four applicants, three plots
    (([[]],), 0),
    (([[i] for i in range(200)],), 200),      # 200 applicants, a plot each
    ((_CHAIN,), 200),
]

Pitfalls

• Letting plots first come, first served. The first example places two applicants, and the clerk never learns the third could have been placed.
• Sharing one asked-after set across applicants. Plots asked after on an earlier applicant's behalf are skipped, and placements that exist are missed.
• Freeing a holder's plot before the chain succeeds. A holder who cannot move keeps what they have; releasing the plot first loses a placement instead of gaining one.

Variants

• Two cabinets — the other two-sided question: splitting a list in two rather than pairing it up.
• BFS and DFS — the search underneath, and where the seen set belongs.