## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Pots of gold

Sharing is caring!

Problem statement
Pots of gold game: Two players $A$ and $B$. 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 $A$, assuming $B$ also plays optimally. A starts the game.

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

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

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

1. He can choose the pot at the $start$ of the line. Then $B$ chooses next. $B$ can choose either $start+1$ or $end$.
1. If $B$ chooses $start+1$, $A$ is left with two options $start+2$ and $end$.
2. If $B$ chooses $end$, $A$ is left with two options $start+1$ and $end-1$. $\rightarrow$ $A's$ outcome will be $pots[start] + minimum(choose(start + 2, end), choose(start + 1, end - 1))$.
2. He can choose the pot at the $end$ of the line. Then $B$ chooses next. $B$ can choose either $start$ or $end-1$.
1. If $B$ chooses $start$, $A$ is left with two options $start+1$ and $end-1$.
2. If $B$ chooses $end-1$, $A$ is left with two options $start$ and $end-2$. $\rightarrow$ $A's$ outcome will be $pots[end] + minimum(choose(start + 1, end-1), choose(start, end - 2))$.

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

Full code

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);
}
}