In Pots of gold game, there are two players A & B and pots of gold arranged in a line, each containing some gold coins. The players can see how many coins are there in each gold pot and each player gets alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has a higher number of coins at the end. The objective is to “maximize” the number of coins collected by A, assuming B also plays optimally and A starts the game.

**Player Opponent**

4, 6, 2, 3 3

4, 6, 2 4

6, 2 6

2 2

**9 coins 6 coins**

**Player Opponent**

6, 1, 4, 9, 8, 5 6

1, 4, 9, 8, 5 5

1, 4, 9, 8 8

1, 4, 9 9

1, 4 4

1 1

**18 coins 15 coins**

The idea is to find an optimal strategy that makes player wins knowing that opponent is playing optimally as well. The player has two choices for coin[i..j] where i and j denotes the front and rear of the line respectively.

If the player chooses front pot i, opponent is left to choose from [i+1, j].

1. if opponent chooses front pot i+1, recurse for [i+2, j]

2. if opponent chooses rear pot j, recurse for [i+1, j-1]

If the player chooses rear pot j, opponent is left to choose from [i, j-1].

1. if opponent chooses front pot i, recurse for [i+1, j-1]

2. if opponent chooses rear pot j-1, recurse for [i, j-2]

Since opponent is playing optimally as well, he will try to minimize the points collected by the player. i.e. opponent will make a choice that will leave the player with minimum coins. So the problem can be recursively defined as –

| coin[i] *(if i = j)*

*optimalStrategy*(i, j) = | max(coin[i], coin[j]) *(if i + 1 = j)*

| max (coin[i] + min(*optimalStrategy*(coin, i + 2, j),

*optimalStrategy*(coin, i + 1, j – 1)),

coin[j] + min(*optimalStrategy*(coin, i + 1, j – 1),

*optimalStrategy*(coin, i, j – 2)))

Below is C++ implementation of above approach:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <iostream> using namespace std; // Iterative function to maximize the number of coins collected by a player, // assuming that opponent also plays optimally int optimalStrategy(int coin[], int i, int j) { // base case: one pot left, only one choice possible if (i == j) return coin[i]; // if we're left with only two pots, choose one with maximum coins if (i + 1 == j) return max(coin[i], coin[j]); // if player chooses front pot i, opponent is left to choose // from [i+1, j]. // 1. if opponent chooses front pot i+1, recurse for [i+2, j] // 2. if opponent chooses rear pot j, recurse for [i+1, j-1] int start = coin[i] + min(optimalStrategy(coin, i + 2, j), optimalStrategy(coin, i + 1, j - 1)); // if player chooses rear pot j, opponent is left to choose // from [i, j-1]. // 1. if opponent chooses front pot i, recurse for [i+1, j-1] // 2. if opponent chooses rear pot j-1, recurse for [i, j-2] int end = coin[j] + min(optimalStrategy(coin, i + 1, j - 1), optimalStrategy(coin, i, j - 2)); // return maximum of two choices return max(start, end); } // Pots of Gold Game using Dynamic Programming int main() { // pots of gold arranged in a line int coin[] = { 4, 6, 2, 3 }; // number of pots (n is even) int n = sizeof(coin) / sizeof(coin[0]); cout << "Maximum coins collected by player is " << optimalStrategy(coin, 0, n - 1); return 0; } |

`Output: `

Maximum coins collected by player is 9

The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

The problem has an optimal substructure. We have seen that the problem can be broken down into smaller subproblems which can further be broken down into yet smaller subproblems, and so on. The problem also exhibits overlapping subproblems so we will end up solving the same subproblem over and over again. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are *Memo*ized rather than computed again and again. This method is illustrated below –

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <iostream> using namespace std; // maximum number of pots #define N 10 // Create a table to store solutions of subproblems int lookup[N][N]; // Function to maximize the number of coins collected by a player, // assuming that opponent also plays optimally int optimalStrategy(int coin[], int i, int j) { // base case: one pot left, only one choice possible if (i == j) return coin[i]; // if we're left with only two pots, choose one with maximum coins if (i + 1 == j) return max(coin[i], coin[j]); // if sub-problem is seen for the first time, solve it and // store its result in a lookup table if (lookup[i][j] == 0) { // if player chooses front pot i, opponent is left to choose // from [i+1, j]. // 1. if opponent chooses front pot i+1, recurse for [i+2, j] // 2. if opponent chooses rear pot j, recurse for [i+1, j-1] int start = coin[i] + min(optimalStrategy(coin, i + 2, j), optimalStrategy(coin, i + 1, j - 1)); // if player chooses rear pot j, opponent is left to choose // from [i, j-1]. // 1. if opponent chooses front pot i, recurse for [i+1, j-1] // 2. if opponent chooses rear pot j-1, recurse for [i, j-2] int end = coin[j] + min(optimalStrategy(coin, i + 1, j - 1), optimalStrategy(coin, i, j - 2)); // assign maximum of two choices lookup[i][j] = max(start, end); } // return the subproblem solution from the map return lookup[i][j]; } // Pots of Gold Game using Dynamic Programming int main() { // pots of gold arranged in a line int coin[] = { 4, 6, 2, 3 }; // number of pots (n is even) int n = sizeof(coin) / sizeof(coin[0]); cout << "Maximum coins collected by player is " << optimalStrategy(coin, 0, n - 1); return 0; } |

`Output: `

Maximum coins collected by player is 9

The time complexity of above solution is O(n^{2}) and auxiliary space used by the program is O(n^{2}).

Below is bottom-up version of above solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include <iostream> #include <cstdlib> using namespace std; int calculate(int **T, int i, int j) { if (i <= j) return T[i][j]; return 0; } // Iterative function to maximize the number of coins collected by a player, // assuming that opponent also plays optimally int optimalStrategy(int* coin, int n) { // base case: one pot left, only one choice possible if (n == 1) return coin[0]; // if we're left with only two pots, choose one with maximum coins if (n == 2) return max(coin[0], coin[1]); // create a dynamic 2D matrix to store sub-problem solutions int** T = new int*[n]; for (int i = 0; i < n; i++) T[i] = new int[n]; // Fill the matrix in diagonal manner as shown below // Iteration 0: Fill T[][] from T[0][0] to T[n-1][n-1] // Iteration 1: Fill T[][] from T[0][1] to T[n-2][n-1] // Iteration 2: Fill T[][] from T[0][2] to T[n-3][n-1] // ... // Iteration n-2: Fill T[][] from T[0][n-2] to T[1][n-1] // Iteration n-1: Fill T[][] from T[0][n-1] to T[0][n-1] for (int iteration = 0; iteration < n; iteration++) { for (int i = 0, j = iteration; j < n; i++, j++) { // if player chooses front pot i, opponent is left to choose // from [i+1, j]. // 1. if opponent chooses front pot i+1, recurse for [i+2, j] // 2. if opponent chooses rear pot j, recurse for [i+1, j-1] int start = coin[i] + min(calculate(T, i + 2, j), calculate(T, i + 1, j - 1)); // if player chooses rear pot j, opponent is left to choose // from [i, j-1]. // 1. if opponent chooses front pot i, recurse for [i+1, j-1] // 2. if opponent chooses rear pot j-1, recurse for [i, j-2] int end = coin[j] + min(calculate(T, i + 1, j - 1), calculate(T, i, j - 2)); T[i][j] = max(start, end); } } int result = T[0][n - 1]; // deallocate memory before returning using delete[] operator for (int i = 0; i < n; i++) delete[] T[i]; delete[] T; return result; } // Pots of Gold Game using Dynamic Programming int main() { // pots of gold arranged in a line int coin[] = { 4, 6, 2, 3 }; // number of pots (n is even) int n = sizeof(coin) / sizeof(coin[0]); cout << "Maximum coins collected by player is " << optimalStrategy(coin, n); return 0; } |

`Output: `

Maximum coins collected by player is 9

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply