DSA Stone Game

The problem

The Stone Game is a contest over a row of piles. Two players take turns. On each turn the player takes the pile at one end of the row, left or right, and adds its value to their score.

Both players play to finish ahead. The answer in this article is the margin, the first player's final score minus the second player's final score. A positive margin means the first player wins, and a negative margin means the first player loses.

cases = [
    ([5, 3, 4, 5], 1),
    ([7, 90, 5, 1], 79),
    ([3, 7, 2, 3], 5),
    ([6, 2, 9], 5),
    ([1, 5, 2], -2),
    ([2, 2], 0),
]
for piles, expected in cases:
    print("piles", piles, "first player margin:", expected)

The last two rows set the scale. Equal piles can tie, and the row with piles 1, 5 and 2 is a loss for the first player even with perfect play.

Intuition: always take the larger end

The first idea takes the larger of the two end piles on every turn. The rule is simple. It also hands the opponent the pile the mover really needed to protect.

The row 7, 90, 5, 1 shows the failure at full size. The big pile sits one step in from the left end. Grabbing an end at random can expose it to the opponent.

def greedy_margin(piles):
    piles = list(piles)
    scores = [0, 0]
    turn = 0
    while piles:
        if piles[0] >= piles[-1]:
            scores[turn] += piles.pop(0)
        else:
            scores[turn] += piles.pop()
        turn = 1 - turn
    return scores[0] - scores[1]

print("greedy margin on [7, 90, 5, 1]:", greedy_margin([7, 90, 5, 1]))
print("greedy margin on [5, 3, 4, 5]:", greedy_margin([5, 3, 4, 5]))

The greedy margin is deeply negative on the first row. Taking the small pile at the right end first would have kept the 90 within reach. Looking one move ahead is not enough, so the article scores whole ranges instead.

Brute force: score every range by recursion

The brute force scores a range directly. The mover tries the left end and the right end. Each try hands the smaller range to the opponent, so the opponent's margin on that range is subtracted.

A lead is the mover's score minus the other player's score on one range. One number captures both players. A counter records how often ranges are rescored.

calls = 0

def brute(piles, i, j):
    global calls
    calls += 1
    if i == j:
        return piles[i]
    take_left = piles[i] - brute(piles, i + 1, j)
    take_right = piles[j] - brute(piles, i, j - 1)
    return max(take_left, take_right)

print("margin:", brute([5, 3, 4, 5], 0, 3), "calls:", calls)
calls = 0
print("margin:", brute([7, 90, 5, 1], 0, 3), "calls:", calls)

Four piles already take 15 calls. The middle ranges are rescored on many paths. The answers are right, and the repetition is the cost.

The optimal solution: a table of leads over ranges

The state is one range of piles, and its table entry holds the best lead the player to move can force on that range. That one state is the whole method.

A single pile gives a lead equal to its own value. Longer ranges combine two shorter ones. Taking the left pile gains its value minus the lead the opponent then holds on the rest.

def stone_margin(piles):
    n = len(piles)
    if n == 0:
        return 0
    table = [[0] * n for _ in range(n)]
    for i in range(n):
        table[i][i] = piles[i]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            take_left = piles[i] - table[i + 1][j]
            take_right = piles[j] - table[i][j - 1]
            table[i][j] = max(take_left, take_right)
    return table[0][n - 1]

cases = [
    ([5, 3, 4, 5], 1),
    ([7, 90, 5, 1], 79),
    ([3, 7, 2, 3], 5),
    ([6, 2, 9], 5),
    ([1, 5, 2], -2),
    ([2, 2], 0),
]
for piles, expected in cases:
    margin = stone_margin(piles)
    print("piles", piles, "-> margin", margin, "expected:", expected, "match:", margin == expected)

Every case matches, including the loss and the tie. The sign of the full-range entry is the verdict, and its size is the winning or losing gap.

Walkthrough: piles 5, 3, 4, 5

The walk fills the table by range length. Single piles come first. Each longer range then reads its two shorter neighbours.

piles = [5, 3, 4, 5]
n = len(piles)
table = [[0] * n for _ in range(n)]
for i in range(n):
    table[i][i] = piles[i]
print("length 1 leads:", [table[i][i] for i in range(n)])
for length in range(2, n + 1):
    row = []
    for i in range(n - length + 1):
        j = i + length - 1
        table[i][j] = max(piles[i] - table[i + 1][j], piles[j] - table[i][j - 1])
        row.append(table[i][j])
    print("length", length, "leads:", row)
print("full range lead:", table[0][n - 1])

The full range lead is 1. The first player takes one end, the roles swap on the range of three, and the subtraction in each step is what keeps the single number honest.

Complexity

The table holds one entry per range, and each entry does constant work, so the time is O(n^2) for n piles. The table itself holds one entry per range, so the space is O(n^2).

def count_calls(n):
    calls = 0
    def rec(i, j):
        nonlocal calls
        calls += 1
        if i >= j:
            return 0
        rec(i + 1, j)
        rec(i, j - 1)
        return 0
    rec(0, n - 1)
    return calls

for n in [4, 6, 8]:
    ranges = n * (n + 1) // 2
    print("piles", n, "- table entries:", ranges, " recursive calls:", count_calls(n))

The entry count grows with the square of the pile count. The recursive call count grows far faster, which is why the table wins.

Edge cases and pitfalls

One pile is a free win by its own value. Two equal piles tie at margin zero. An empty row scores zero by the guard in the code.

The classic mistake stores two scores per range. Two scores double the state and invite swapped-player errors. The lead folds both scores into one difference, and the subtraction on each handover does the swapping.

def stone_margin(piles):
    n = len(piles)
    if n == 0:
        return 0
    table = [[0] * n for _ in range(n)]
    for i in range(n):
        table[i][i] = piles[i]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            table[i][j] = max(piles[i] - table[i + 1][j], piles[j] - table[i][j - 1])
    return table[0][n - 1]

print("one pile:", stone_margin([7]))
print("two equal piles:", stone_margin([4, 4]))
print("empty row:", stone_margin([]))
print("a loss:", stone_margin([1, 5, 2]))
print("all equal:", stone_margin([3, 3, 3, 3]))

The all-equal row ties as well. Equal piles give the second player a matching reply to every take.