principlepythonMinor

Game winning optimal strategy

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

winninggameoptimalstrategy

Problem

Consider a row of n coins of values v1 . . . vn, where n is even. a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.

Let us understand the problem with few examples:

[8, 15, 3, 7] : The user collects maximum value as 22(7 + 15)

Does choosing the best at each move give an optimal solution?

Is there any way to improve this code?

def optimal_strategy_game(v):
    n = len(v)
    t = [[0 for x in xrange(n)] for x in xrange(n)]
    for gap in xrange(n):
        for i in xrange(n):
            j = i + gap
            if j j-1 else t[i+1][j-1]
                y = t[i+2][j] if i+2 <j else 0
                z = t[i][j-2] if i <= j-2 else 0
                t[i][j] = max(v[i]+min(x,y), v[j]+min(x,z))
    print t
    print t[0][n-1]

v = [8,15,3,7]
n = len(v)
print optimal_strategy(0,n-1,v)
optimal_strategy_game(v)

Solution

Review

-
It's usually more convenient to return a result rather than printing it. Then you can use the result in other computations, for example test cases.

-
It's not clear what the meaning of the table t is. It would be helpful to have a comment. I think that if \$i ≤ j\$ then t[i][j] gets filled in with the maximum money obtainable by a player who starts with the coins \$v_i, \dots, v_j\$.

-
There is some trouble in handling edge cases — you need to avoid an invalid lookup in the table t so instead of writing t[i+1][j-1] you have to write:

0 if i+1 > j-1 else t[i+1][j-1]

to avoid trouble in the cases i+1 == n and j == 0. What this suggests is that t would be better implemented as a mapping from pair (i, j) to money, using collections.defaultdict:

from collections import defaultdict
t = defaultdict(int)    # Map from (i,j) to max money on v[i:j+1].

Then you could look up any pair and it would default to zero even if it was out of bounds, like this:

x = t[i + 1, j - 1]
y = t[i + 2, j]
z = t[i, j - 2]
t[i, j] = max(v[i] + min(x, y), v[j] + min(x, z))

-
In this code:

for gap in xrange(n):
    for i in xrange(n):
        j = i + gap
        if j<n:

you could avoid the test

j

- 
These lines of code:

x = t[i + 1, j - 1]
y = t[i + 2, j]
z = t[i, j - 2]
t[i, j] = max(v[i] + min(x, y), v[j] + min(x, z))


are looking two steps ahead (the next player chooses the minimum of their options, and the current player chooses the maximum of theirs).

But it is simpler to look only one step ahead, like this:

s = sum(v[i:j+1])
t[i, j] = s - min(t[i + 1, j], t[i, j - 1])


How does this work? Well,

s is the sum of all the coins from i to j, so if the next player can win t[i + 1, j]

 (say), then the current player can win whatever's left.

(This is a standard trick when implementing a minimax algorithm. Instead of having different code for the even (max) and odd (min) players, use the same code for both players and negate the score at each step so that max and min swap roles.)

However, this is inefficient because of the computation of

s, which requires iterating over all the coins from i to j. But we can avoid this by precomputing a list of running totals, using itertools.accumulate

:

from itertools import accumulate
totals = [0] + list(accumulate(v))


and then the computation of

 becomes:

s = totals[j + 1] - totals[i] # sum(v[i:j+1])


Revised code



from collections import defaultdict
from itertools import accumulate

def optimal_strategy_game(coins):
    """Return the maximum possible amount of money that can be won by a
    player starting on the given row of coins.
    """
    n = len(coins)
    totals = [0] + list(accumulate(coins)) # Running totals over coins
    money = defaultdict(int) # Map from (i,j) to max money on coins[i:j+1].
    for gap in range(n):
        for i in range(n - gap):
            j = i + gap
            s = totals[j + 1] - totals[i] # s = sum(coins[i:j+1])
            money[i, j] = s - min(money[i + 1, j], money[i, j - 1])
    return money[0, n - 1]


Alternative approach



The technique here (of building a table of solutions to sub-problems) is known as dynamic programming. But code that uses dynamic programming can always be rewritten to use recursion to visit the sub-problems and memoization to avoid duplicate work. Sometimes this results in clearer code. In Python 3.2 or later, many functions are easy to memoize using the

@functools.lru_cache

 decorator:

from functools import lru_cache
from itertools import accumulate

def max_money(coins):
    """Return the maximum possible amount of money that can be won by a
    player starting on the given row of coins.
    """
    totals = [0] + list(accumulate(coins)) # Running totals over coins

    @lru_cache(maxsize=None)
    def money(start, stop):
        "Return maximum money that can be won on coins[start:stop]."
        if start >= stop:
            return 0
        else:
            s = totals[stop] - totals[start] # s = sum(coins[start:stop])
            return s - min(money(start + 1, stop), money(start, stop - 1))

    return money(0, len(coins))


(Python 2.7 lacks

lru_cache` but there's a backport.)

Code Snippets

0 if i+1 > j-1 else t[i+1][j-1]

from collections import defaultdict
t = defaultdict(int)    # Map from (i,j) to max money on v[i:j+1].

x = t[i + 1, j - 1]
y = t[i + 2, j]
z = t[i, j - 2]
t[i, j] = max(v[i] + min(x, y), v[j] + min(x, z))

for gap in xrange(n):
    for i in xrange(n):
        j = i + gap
        if j<n:

for gap in xrange(n):
    for i in xrange(n - gap):
        j = i + gap

Context

StackExchange Code Review Q#161515, answer score: 5

Revisions (0)

No revisions yet.