Splitting the ripening shelf

Two buyers empty a shelf from its ends, one wheel at a time. Taking the heavier end each turn is the obvious plan, and it loses.

The problem

A ripening cellar has one long shelf of cheese wheels, packed tight. wheels gives their weights in kilos, left to right, and they are wedged so firmly that only the wheel at the far left or the far right of what remains lifts out.

Two buyers take turns, the first starting. On your turn you take one end wheel and keep it; the shelf shrinks and the other buyer chooses from the new ends. Both see the whole shelf and both play to maximise their own kilos.

Report the first buyer's total minus the second's under perfect play, negative if the first buyer finishes behind.

Input. wheels — a list of integers, weights left to right.

Output. The first buyer's kilos minus the second buyer's, under optimal play.

Example.

wheels = [7, 2, 9, 4]   ->  10

The first buyer takes the 7. Whichever end the second takes, the 9 is exposed next, so the first buyer gets 7 + 9 = 16 against 2 + 4 = 6.

A second example, where taking the heavier end first loses:

wheels = [3, 9, 1, 2]   ->  7

Take the 3 and the second buyer takes the 9: the first buyer finishes 5 kilos behind. Take the 2 instead and the 9 is still there next turn — 2 + 9 = 11 against 3 + 1 = 4.

Constraints.

• 1 <= len(wheels) <= 500
• 1 <= wheels[i] <= 10^4

An aside: with an even number of wheels and an odd total the first buyer can always finish ahead, by claiming every odd position or every even position, whichever weighs more. That fixes the sign, not the margin.

Hints

Approach

Brute force

Recurse on both moves at every turn: two branches per wheel, 2^n leaves, and n reaches 500. The same shelf block is reached by a huge number of different move orders, and each one is re-solved from scratch.

The insight

Track the margin, not the two totals: one function lead(i, j) — the most the buyer to move can finish ahead by on wheels i through j — covers both buyers at once.

The game is zero-sum, so one buyer's lead is the other's negated, and taking a wheel only swaps who moves: lead(i, j) is max(wheels[i] - lead(i+1, j), wheels[j] - lead(i, j-1)). The state is the surviving block, always contiguous because both buyers take from the ends, so there are just n * (n + 1) / 2 of them.

Algorithm

1. Make an n by n table lead, and set lead[i][i] = wheels[i].
2. For each span length from 2 up to n, and each left end i, let j = i + span - 1.
3. Take the left: wheels[i] - lead[i+1][j]. Take the right: wheels[j] - lead[i][j-1].
4. Store the larger of the two in lead[i][j].
5. Return lead[0][n-1].

Complexity

Time O(n^2) — 125,000 blocks at n = 500, each settled with two lookups. Space O(n^2) for the table; a rolling row over span lengths brings that down to O(n) if the shelf gets longer.

Solution

"""Splitting the ripening shelf — interval DP on the lead the buyer to move can force."""


def solve(wheels):
    """First buyer's kilos minus the second buyer's, when both take ends optimally."""
    n = len(wheels)
    # lead[i][j] = the most the buyer whose turn it is can finish ahead by,
    # counting only wheels i..j. One table serves both buyers because the roles
    # swap every turn: whatever lead the other forces on the rest is subtracted.
    lead = [[0] * n for _ in range(n)]
    for i in range(n):
        lead[i][i] = wheels[i]
    for span in range(2, n + 1):
        for i in range(n - span + 1):
            j = i + span - 1
            take_left = wheels[i] - lead[i + 1][j]
            take_right = wheels[j] - lead[i][j - 1]
            lead[i][j] = max(take_left, take_right)
    return lead[0][n - 1]

TESTS = [
    (([7, 2, 9, 4],), 10),
    (([3, 9, 1, 2],), 7),
    (([2, 4, 8, 1, 9, 3],), 11),
    (([6, 6],), 0),
    (([10, 1],), 9),
    (([5],), 5),
    (([4, 4, 4, 4],), 0),
]

Pitfalls

• Taking the heavier end each turn. On [3, 9, 1, 2] greedy finishes 5 kilos behind when the answer is 7 ahead. Greedy gets the first move right on many shelves, which is exactly what makes it hard to catch.
• Adding the sub-result instead of subtracting it. wheels[i] + lead[i+1][j] models one buyer taking everything: [7, 2, 9, 4] returns 22, the whole shelf.
• Filling the table by left index instead of by span length. lead[i][j] reads lead[i+1][j], which is not written yet when i ascends, so [7, 2, 9, 4] returns 7 instead of 10.

Variants

• Starting the ridge relay — the same fill-in-a-safe-order rule, on a line rather than a triangle.
• Quilt of squares — the same branching search, but no two branches meet, so no table helps.