Dynamic Programming – Coin In a Line Game Problem

Objective: In this game, which we will call the coins-in-a-line game, an even number, n, of coins, of various denominations from various countries, are placed in a line. Two players, who we will call Alice and Bob, take turns removing one of the coins from either end of the remaining line of coins. That is, when it is a player’s turn, he or she removes the coin at the left or right end of the line of coins and adds that coin to his or her collection. The player who removes a set of coins with larger total value than the other player wins, where we assume that both Alice and Bob know the value of each coin.

Example:

coins []  =  { 6, 9, 1, 2, 16, 8}

trial 1: (players will pick the best option available for them)
coins [] = { 6, 9, 1, 2, 16, 8} , Alice picks 8
coins [] = { 6, 9, 1, 2, 16}, Bob picks 16
coins [] = { 6, 9, 1, 2}, Alice picks 6
coins [] = { 9, 1, 2}, Bob picks 9
coins [] = {1, 2}, Alice picks 2
coins [] = {1}, Bob picks 1
Alice: 8+6+2 =16 Bob: 16+9+1=26 => Alice Lost

So clearly picking up the best in each move is not good for Alice. What else Alice can do to win the game.

trial 2: (Alice thinks about Bob's move, Will discuss the strategy in solution) 
coins [] = { 6, 9, 1, 2, 16, 8} , Alice picks 6
coins [] = { 9, 1, 2, 16, 8}, Bob picks 9
coins [] = { 1, 2, 16, 8}, Alice picks 1
coins [] = 2, 16, 8}, Bob picks 8
coins [] = {2, 16}, Alice picks 16
coins [] = {2}, Bob picks 2
Alice: 6+1+16 =23 Bob: 9+8+2=19 => Alice Won

So this time Alice has won. Let's see the solution and discuss what Alice has done to win the game. 

Approach:

We will solve this problem using Dynamic programming in Bottom-up manner.

In the example above we have seen that in trail 1 Alice has lost and in trial 2 Alice has won. So clearly picking the best coin available in each move is good option for Alice.

So the question is what Alice has done differently to win in second trial. Since Alice and Bob, both are playing to win the game and both are equally clever then “Alice has to think about Bob’s move means options available for the Bob once Alice is done with the move, What Bob will pick (Bob is equally clever and tries to leave Alice with minimum values to be chosen from) and  then what Alice will chose.

So if we can clearly see that each player is making the move by keeping in mind the two moves can be made in future and pick the best of them.

Let’s make it more clear- Suppose we have coins lined up from Ci to Cj wit the values of Vi to Vj respectively.

MV(i, j)  = maximum value the Alice can collect from i'th coin to j'th coin.

In every move Alice has 2 options –

  • Either pick the ith coin (from starting)
  • OR pick the jth coin ( from the end).

Let’s discuss both the options

Alice Picks the ith coin (from starting)

 

As we can see above if Alice picks the ith coin, Ci then Bob will be left with 2 choices Ci+1 and Cj, since Bob is equally clever than Bob will pick the coin which will leave the Alice with minimum value coins.

So if Bob picks i+1th coin then it will again Alice turn and problem will be reduced to Alice has to pick a coin from i+2th to jth coin and similarly if   if Bob picks jth coin then it will again Alice turn and problem will be reduced to Alice has to pick a coin from i+1th to j-1th coin.

So Alice will collection will be

= Vi + Min{MV(i+2,j), MV(i+1, j-1)}

 Alice Picks the jth coin (from the end)

 

As we can see above if Alice picks the jth coin, Cj then Bob will be left with 2 choices Ci and Cj-1, since Bob is equally clever than Bob will pick the coin which will leave the Alice with minimum value coins.

So if Bob picks ith coin then it will again Alice turn and problem will be reduced to Alice has to pick a coin from i+1th to j-1th coin and similarly if Bob picks j-1th coin then it will again Alice turn and problem will be reduced to Alice has to pick a coin from ith to j-2th coin.

So Alice will collection will be

= Vj + Min{MV(i+1,j-1), MV(i, j-2)}

So now we need to decide whether Alice should pick ith coin or jth coin. Alice will pick the coin which ever gives the more value considering 2 moves ahead

so

MV(i, j) = Max { Vi + Min{MV(i+2,j), MV(i+1, j-1)} , Vj + Min{MV(i+1,j-1), MV(i, j-2)}}

Let’s see how the recursive equation will look like:


Complete Code:


Output:

Max value pick up by player1(Alice)- 23

Reference: http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • Venkata NTV

    Hi tutorialhorizon,

    I’m not able to see code to any of the questions…

    • tutorialhorizon

      I am able to see.. All the codes are on gist. Just check if u can see the gist code from some other sites.

  • Samrat Sreevatsa

    what happens in case of ODD number of coins?

  • Vipin Sharma

    typo : MV(i, j) = Max { Vi + Min{MV(i+2,j), MV(i+1, j-1)} , Vi + Min{MV(i+1,j-1), MV(i, j-2)}}
    Correction : MV(i, j) = Max { Vi + Min{MV(i+2,j), MV(i+1, j-1)} , Vj + Min{MV(i+1,j-1), MV(i, j-2)}}

%d bloggers like this: