## fizzbuzzer.com

### 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