Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Two player coin game using Dynamic Programming | FACE Prep

Published on 10 Mar 2020

Two player coin game using Dynamic Programming is discussed here.


There is an array of coins with different worth. Two players playing this game can pick a coin from either of the left or right end. The player with maximum sum will win. Both players are optimally playing the game.


If player one wins the game print PLAYER 1 WINS else if player 2 wins print PLAYER 2 WINS if they both have equal sum at the end, print DRAW.


Strategy 1:


Array = {18, 20, 15, 30, 10, 14 }


Player 1 picks 18, now the array of coins is

20 15 30 10 14


Player 2 picks 20, now the array of coins is

15 30 10 14


Player 1 picks 15, now the array of coins is

30 10 14


Player 2 picks 30, now the array of coins is

10, 14


Player 1 picks 14, now the array of coins is

10


Player 2 picks 10.


The total value of coins picked by the second player is more (20 + 30 + 10) compared to the first player (18 + 15 + 14).


So, the second player wins.


Having made the first move, the first player is unable to succeed. So,should we make the first move or not? Does it matter?


Playing first will guarantee that the player will not lose or at least end up with a draw game. Now, consider the strategy 2 using a dynamic programming approach.


Strategy 2:


  • Count the sum of all coins that are odd-numbered. (Let the odd-numbered coins be X)
  • Count the sum of all coins that are even-numbered. (Let the even-numbered coins be Y)
  • If X > Y, take the left-most coin first. Choose all odd-numbered coins in subsequent moves.
  • If X < Y, take the right-most coin first. Choose all even-numbered coins in subsequent moves.
  • If X == Y, you will guarantee to get a tie if you stick with taking only even-numbered/odd-numbered coins.


Considering the same example,


Array = {18, 20, 15, 30, 10, 14}


  • Sum of odd coins = 18 + 15 + 10 = 43
  • Sum of even coins = 20 + 30 + 14 = 64


Since the sum of even coins is more, the first player decides to collect all even coins. He first picks 14, now the other player can only pick a coin (10 or 18). Whichever is picked by the other player, the first player again gets an opportunity to pick an even coin and block all even coins.


Program for the two player game using dynamic programming


C++

Output
Input - 5 2 1 2 1 2 Output - DRAW


Test Case 1

I/P

5

2 1 2 1 2

O/P

DRAW


Test Case 2

I/P

10

14 26 10 13 24 14 17 30 21 24

O/P

PLAYER 1 WINS


Test Case 3

I/P

5

1 36 41 20 5

O/P

PLAYER 2 WINS


Test Case 4

I/P

6

2 2 2 2 2 2

O/P

DRAW


Test Case 5

I/P

3

21 150 34

O/P

PLAYER 2 WINS


Recommended Programs




If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises