# Pots of gold

**Problem statement**

Pots of gold game: Two players and . There are 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 – perfect information). They get 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 , assuming also plays optimally. A starts the game.

The idea is to find an optimal strategy that makes win knowing that is playing optimally as well. How would you do that?

**Solution**

Because plays optimally, the problem of maximizing the coins collected by becomes equal to minimizing the coins collected by . Similarly because also plays optimally, the problem of maximizing the coins collected by becomes equal to minimizing the coins collected by .

Without loss of generality, assume plays first. He will have two possible choices:

- He can choose the pot at the of the line. Then chooses next. can choose either or .
- If chooses , is left with two options and .
- If chooses , is left with two options and .

outcome will be .

- He can choose the pot at the of the line. Then chooses next. can choose either or .
- If chooses , is left with two options and .
- If chooses , is left with two options and .

outcome will be .

The reason we take the is because also plays optimally. That is, chooses the pots that minimize the output for . So when chooses or , on next turn what’s left will be the minimum of what could get.

**Full code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class PotsOfGold { private static int choose(int[] pots, int start, int end) { if (start > end) { return 0; } int chooseFromStart = pots[start] + Math.min(choose(pots, start + 2, end), choose(pots, start + 1, end - 1)); int chooseFromEnd = pots[end] + Math.min(choose(pots, start + 1, end - 1), choose(pots, start, end - 2)); // Now return the maximum of the two choices. return Math.max(chooseFromStart, chooseFromEnd); } public static void main(String[] args) { int[] pots = new int[] { 4, 1, 10, 5, 0, 6, 14, 1, 1, 5 }; int result = choose(pots, 0, pots.length - 1); System.out.println(result); } } |