5
\$\begingroup\$

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<n:
                x =  0 if i+1 > 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)
\$\endgroup\$
  • 4
    \$\begingroup\$ "Does choosing the best at each move give an optimal solution?", I believe the example proves that it's not an optimal solution. If you would choose the best at each move then you would end up with 8, your opponent would take 15, and then you would take 7. So you would have 8 + 7 instead of 7 + 15. \$\endgroup\$ – Simon Forsberg Apr 22 '17 at 18:20
5
\$\begingroup\$

1. Review

  1. 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.

  2. 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\$.

  3. 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))
    
  4. 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<n by iterating only over valid values of i:

    for gap in xrange(n):
        for i in xrange(n - gap):
            j = i + gap
    
  5. 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 s becomes:

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

2. 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]

3. 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.)

\$\endgroup\$
  • \$\begingroup\$ I misread your code, you can disregard my comment :) Sorry! (I should go get some coffee lol) \$\endgroup\$ – Thomas Ward Apr 26 '17 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.