Down the lock grid

A canal basin descends in a grid of lock chambers. A barge can only be worked east or south, and every chamber it enters costs minutes at the paddles.

The problem

The basin is a rectangle of chambers, rows by cols. Each chamber carries a filling time in minutes — how long the keeper needs to level it before the barge passes through. The barge starts in the north-west chamber and must reach the south-east one. Because the whole basin falls away to the south-east, only two moves are legal from any chamber: one step east, or one step south.

The trip costs the sum of the filling times of every chamber the barge occupies, including the first and the last. Find the smallest possible total.

Input. minutes — a list of rows, each a list of integers, the filling time of each chamber.

Output. The fewest total minutes on any east-or-south route from the north-west chamber to the south-east one.

Example.

minutes = [[6, 2, 9],
           [5, 3, 7],
           [8, 4, 1]]   ->  16

East, south, south, east: 6 + 2 + 3 + 4 + 1. Every other route costs more — going south first commits the barge to the 5 and then the 8 or the 3.

Example, where the cheapest first step is the wrong one:

minutes = [[1, 2, 2],
           [1, 9, 2],
           [9, 9, 2]]   ->  9

South looks better than east at the start, 1 against 2, but that route then has to cross a 9 and costs 22. Paying the extra minute up front and running east twice gives 1 + 2 + 2 + 2 + 2.

Constraints.

• 1 <= rows, cols <= 200
• 0 <= minutes[i][j] <= 500 — a chamber already at level costs nothing

Hints

Approach

Brute force

Enumerate every east-or-south route and add each up. The count is the number of ways to interleave the moves — for a 200 by 200 basin that is a number with over a hundred digits. Even a 10 by 10 basin already has 48620 routes.

The insight

The cheapest route into a chamber is the cheaper of the routes into its west and north neighbours, plus the chamber's own filling time.

Any route into a chamber enters through one of those two, and the part before that step is itself a route into the neighbour — so a cheapest route contains cheapest routes, which is the substructure the table needs. The two subproblems never interact, because a route cannot come back: moves only ever increase the row or the column.

Algorithm

1. Keep one row of running totals, best, with one entry per column.
2. The first chamber costs its own filling time.
3. Along the top row, each entry is its west neighbour plus its own time.
4. For every later row, the first column is its north neighbour plus its own time.
5. For the rest, take min(north, west) and add the chamber's own time — filling left to right, best[j - 1] is already this row and best[j] is still the row above.
6. The last entry of the last row is the answer.

Complexity

Time O(rows · cols) — every chamber is decided once, in constant work. Space O(cols), one rolling row rather than the whole table.

Solution

"""Down the lock grid — cheapest east-or-south route, held in one row."""


def solve(minutes):
    """Fewest fill minutes from the north-west chamber to the south-east one."""
    cols = len(minutes[0])
    best = [0] * cols

    for i, row in enumerate(minutes):
        for j, fill in enumerate(row):
            if i == 0 and j == 0:
                best[j] = fill
            elif i == 0:
                best[j] = best[j - 1] + fill          # top row: only ever entered from the west
            elif j == 0:
                best[j] = best[j] + fill              # left column: only ever entered from the north
            else:
                # left to right, so best[j - 1] is this row and best[j] is
                # still the row above: exactly the two ways into this chamber
                best[j] = min(best[j], best[j - 1]) + fill
    return best[-1]

TESTS = [
    (([[6, 2, 9], [5, 3, 7], [8, 4, 1]],), 16),
    (([[1, 2, 2], [1, 9, 2], [9, 9, 2]],), 9),   # the cheap first step leads to the 9s
    (([[4, 7, 2, 5]],), 18),                     # one row: every chamber is on the route
    (([[3], [8], [2]],), 13),                    # one column, same reason
    (([[7]],), 7),
    (([[0, 0], [0, 0]],), 0),
]

Pitfalls

• Choosing the cheaper next step as you go. That is greedy, not a table, and the second example returns 22 instead of 9.
• Applying min(north, west) on the boundary. On the top row there is no north neighbour; reading a zero from outside the grid makes the route look free. A single-row basin [[4, 7, 2, 5]] then reports 4 rather than 18.
• Forgetting the first chamber's own filling time. The barge occupies it, so it counts; leaving it out is silently wrong by exactly that one number.
• Sweeping the rolling row right to left. Then best[j - 1] is still the row above rather than this row, and the west neighbour is read from the wrong row.

Variants

• Squares in the mosaic — another grid table where a cell is decided from the neighbours above and to its left.
• Intervals and matrices — the boundary rules that keep grid tables free of off-by-one errors.