The mill floor load

A converted spinning mill keeps an archive on its upper floor. The floor was surveyed bay by bay, and the loading trolley has to cross it without going through the boards.

The problem

The upper floor is a rectangular grid of bays. Each bay carries a load rating in hundreds of kilograms: the heaviest load the joists under that bay will take.

The trolley is loaded at the north-west bay (0, 0) and has to reach the goods lift at the south-east bay (rows - 1, cols - 1). It rolls to any bay sharing an edge with the one it is on — north, south, east or west, never on the diagonal. Every bay on the route carries the whole trolley in turn, the loading bay and the lift bay included, so a route takes only as much load as its weakest bay allows.

Over all routes from the loading bay to the lift, report the largest possible value of the smallest rating on the route.

Input. bays — a list of lists of integers, every row the same length, each value one bay's load rating.

Output. An integer: the best achievable weakest rating.

Example.

bays = [[5, 4, 5],
        [1, 2, 6],
        [7, 4, 6]]   ->  4

Along the top row and down the east side the ratings are 5, 4, 5, 6, 6, so that route takes 4. Every other route crosses the 1 or the 2.

A second example, where the route has to weave between the rows:

bays = [[2, 2, 1, 2, 2, 2],
        [1, 2, 2, 2, 1, 2]]   ->  2

Dropping to the lower row after the first bay, back up after the fourth, and down again at the end dodges all three 1s.

Constraints.

• 1 <= rows, cols <= 300
• 0 <= bays[r][c] <= 10^9
• a one-bay floor is allowed, and then the loading bay is also the lift bay

Hints

Approach

Brute force

Walk every simple route from the loading bay to the lift, keep the weakest bay on each, and take the best. A 6 by 6 floor already has 1,262,816 such routes.

The insight

A route whose weakest bay is at least t exists exactly when the two corners lie in one component of the bays rated t or more, and lowering t only ever opens bays — so a single sweep from the strongest bay down answers every limit at once.

Dropping the limit adds bays and never removes one, so components merge and never split — the precondition union-find needs, since it supports merge and query but no delete. In descending order every open bay is rated at least as high as the one just opened, so the bay that closes the link is the weakest on the best route.

Algorithm

1. Number bay (r, c) as r * cols + c, and build a union-find over all of them with every bay closed.
2. Sort the bay numbers by rating, strongest first.
3. Open the next bay and union it with each already-open neighbour.
4. If the loading bay and the lift bay are both open and share a root, return the rating of the bay just opened. On a one-bay floor this fires immediately.

Complexity

Time O(RC log(RC)) — the sort dominates; the RC insertions and at most 2RC unions cost effectively constant time each. Space O(RC) for the parent, size and open arrays.

Solution

"""The mill floor load — open bays strongest first until the two corners join."""


def find(parent, x):
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:               # second pass flattens the path
        parent[x], x = root, parent[x]
    return root


def union(parent, size, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra == rb:
        return
    if size[ra] < size[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    size[ra] += size[rb]


def solve(bays):
    rows, cols = len(bays), len(bays[0])
    cells = rows * cols
    parent = list(range(cells))
    size = [1] * cells
    is_open = [False] * cells

    start, lift = 0, cells - 1
    strongest_first = sorted(range(cells), key=lambda i: -bays[i // cols][i % cols])

    for idx in strongest_first:
        r, c = divmod(idx, cols)
        is_open[idx] = True
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if 0 <= nr < rows and 0 <= nc < cols and is_open[nr * cols + nc]:
                union(parent, size, idx, nr * cols + nc)
        # Invariant: every open bay is rated at least bays[r][c]. So the first time
        # the corners share a root, this bay is the weakest on the best route.
        if is_open[start] and is_open[lift] and find(parent, start) == find(parent, lift):
            return bays[r][c]

    return bays[0][0]                      # unreachable: the last bay opens everything

TESTS = [
    (([[5, 4, 5],
       [1, 2, 6],
       [7, 4, 6]],), 4),
    (([[2, 2, 1, 2, 2, 2],
       [1, 2, 2, 2, 1, 2]],), 2),
    (([[3]],), 3),                          # one bay: it is both start and lift
    (([[1, 9], [9, 9]],), 1),               # the loading bay itself caps the answer
    (([[9, 9], [9, 1]],), 1),               # so does the lift bay
    (([[5, 1], [1, 5]],), 1),               # every route crosses a 1
    (([[3, 4, 6, 3, 4],
       [0, 2, 1, 1, 7],
       [8, 8, 3, 2, 7],
       [3, 2, 4, 9, 8],
       [4, 1, 2, 0, 0],
       [4, 6, 5, 4, 3]],), 3),
]

Pitfalls

• Forgetting that the corner bays count. On [[1, 9], [9, 9]] the answer is 1, not 9: the trolley is loaded on the weak bay before it moves anywhere.
• Re-running a flood fill after each bay opens. Correct, but O((RC)²) — about 8 · 10⁹ steps on a 300 by 300 floor. The union-find keeps the earlier merges.
• Opening bays weakest first. The corners still join, but the bay closing the link is then the strongest on the route, not the weakest: the first example reports 6 instead of 4.

Variants

• The trunk line survey — the same merging, counting groups at the end rather than watching for one to form.
• Union-find — the structure itself, and why the merge-only restriction is what buys the speed.