Two trips through the stacks

A shelving robot goes out to the sorting lift and comes back to the desk. The two legs look independent, and choosing them one at a time is what goes wrong.

The problem

A closed-stack library is a grid of bays. The returns desk is the top-left bay, the sorting lift the bottom-right, and the aisles are one-way: going out the robot moves one bay east or south per step, coming back one bay west or north.

shelves[r][c] is the number of books waiting in that bay, or -1 if the bay is closed and cannot be entered. Rolling through a bay clears it, so a bay both legs pass is empty the second time.

Plan the round trip — desk to lift, lift to desk — that clears the most books.

Input. shelves — a rectangular grid, each cell -1 or a count of books.

Output. The most books one round trip clears, or 0 if no round trip exists.

Example.

shelves = [[0,  1, 1],
           [1, -1, 1],
           [1,  1, 0]]   ->  6

The middle bay is closed, so one leg runs along the top and right, the other along the left and bottom, and between them they clear all six.

A second example, where taking the legs one at a time falls short:

shelves = [[0, 3, 2],
           [2, 2, 1],
           [0, 2, 1]]    ->  13

Top then right edge clears 7, and back through the middle another 6. The richest single leg is worth 8, and once it is cleared the best left is 3 — 11 in all.

Constraints.

• 1 <= len(shelves) <= 50 and 1 <= len(shelves[0]) <= 50
• Every row has the same length
• shelves[r][c] is -1, or an integer from 0 to 100

Hints

Approach

Brute force

Enumerate every route and pair it with every other. A 12 by 12 grid has 705,432 routes and roughly 5 x 10^11 pairs, and grids run to 50 by 50.

The insight

Reverse the return leg so both legs run desk to lift, then advance them in lockstep: after k steps both stand on the diagonal row + col = k, so a state is the step number and the two rows.

Reversal is sound because the movement rule is its own mirror. Equal step counts make double counting decidable: two legs share a bay exactly when their rows match, one comparison rather than a search through a route. With the step fixed the column is step - row, so the table is rows by rows.

Algorithm

1. If the desk or the lift is closed, answer 0.
2. Hold best[a][b]: the most books cleared with one leg on row a and the other on row b at this step. Seed best[0][0] with the desk's count and mark every other cell unreachable.
3. Per step, build a fresh table. For each pair of open bays take the largest of the four predecessors — each leg came from above or from the left — and add both bay counts, or one count when the rows are equal.
4. A pair with no reachable predecessor stays unreachable.
5. The answer is best[last][last], or 0 if it never became reachable.

Complexity

Time O((rows + cols) x rows^2) — one rows-by-rows table per step, four reads a cell: about 10^6 reads at 50 by 50. Space O(rows^2) — two layers of the table, columns recomputed from the step.

Solution

"""Two trips through the stacks — two monotone routes advanced in lockstep."""

NO_ROUTE = float("-inf")


def solve(shelves):
    if not shelves or not shelves[0]:
        return 0
    rows, cols = len(shelves), len(shelves[0])
    if shelves[0][0] == -1 or shelves[rows - 1][cols - 1] == -1:
        return 0

    # best[a][b]: most books two routes can hold when route A stands on row a and
    # route B on row b after the SAME number of moves. Both have made `step`
    # moves, so a column is never stored: it is step - row.
    best = [[NO_ROUTE] * rows for _ in range(rows)]
    best[0][0] = shelves[0][0]

    for step in range(1, rows + cols - 1):
        nxt = [[NO_ROUTE] * rows for _ in range(rows)]
        for a in range(rows):
            col_a = step - a
            if col_a < 0 or col_a >= cols or shelves[a][col_a] == -1:
                continue
            for b in range(rows):
                col_b = step - b
                if col_b < 0 or col_b >= cols or shelves[b][col_b] == -1:
                    continue
                prev = NO_ROUTE
                for was_a in (a - 1, a):          # each route arrived from above
                    for was_b in (b - 1, b):      # or from the left
                        if was_a < 0 or was_b < 0:
                            continue
                        if best[was_a][was_b] > prev:
                            prev = best[was_a][was_b]
                if prev == NO_ROUTE:
                    continue                      # no pair of routes reaches here
                gain = shelves[a][col_a]
                if a != b:
                    # equal rows at equal steps means one shelf, cleared once
                    gain += shelves[b][col_b]
                nxt[a][b] = prev + gain
        best = nxt

    return max(best[rows - 1][rows - 1], 0)

TESTS = [
    (([[0, 1, 1], [1, -1, 1], [1, 1, 0]],), 6),
    (([[0, 3, 2], [2, 2, 1], [0, 2, 1]],), 13),
    (([[1, 1, 1, 1], [1, -1, -1, 1], [1, 1, 1, 1]],), 10),
    (([[0, -1], [-1, 0]],), 0),
    (([[0, 1, -1], [1, -1, 1], [-1, 1, 0]],), 0),
    (([[2, 0, 3, 1, 1]],), 7),
    (([[1]],), 1),
    (([[-1]],), 0),
]

Pitfalls

• Planning the best leg first, then the best of what is left. On the second example that returns 11 instead of 13.
• Adding both bay counts when the rows are equal. The legs are in one bay holding one set of books. On [[2, 0, 3, 1, 1]] the doubling reports 12 where the answer is 7.
• Filling unreachable pairs with 0 rather than a sentinel below every real score. Zero reads as "reachable, nothing cleared", so the table walks through closed bays: on [[0, 1, -1], [1, -1, 1], [-1, 1, 0]], which has no route at all, that reports 2.

Variants

• Counterweight rig — another problem where the plausible greedy loses, with one number of state instead of two rows.
• Intervals and matrices — the grid recurrences this is built on, in their single-route form.