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