Make delicious recipes!

Maximize coin selection to win game



Problem: Given an unsorted array of pots containing coins.
A and B play a game where they take turns and pick up a pot either from the beginning or the end of array.
If A plays first, devise a strategy to help him win the game.


Solution: A recursive solution for this can be as follows:


import java.util.*;

public class MaximizeCoinCollection 
{

    public static void main(String[] args) 
    {
        int numPots = 6;
        int[] arr = getRandomCoins(numPots);
        
        System.out.println(findMaxCoins (arr, 0, numPots-1));
    }

    // The most important part to understand here is why minimum is being chosen from the recursive calls.
    // This is so because the recursive calls the best sums A would choose for himself.
    // Since B is also playing with full efficiency, he will do his best to minimize the A's profit.
    // And so, B will choose a pot which will allow A to choose his next pot with minimum benefit.
    // For example: if B has to choose from 2,10,2,4,3, then
    // B will never choose 2 as that would expose 10 to A.
    // Since B will always offer a minimum to A, we take the minimum from the recursive calls.
    // 
    // But after recursion is done, then A will definitely maximize his profit
    // And that is where we choose maximum
    static int findMaxCoins(int[] arr, int start, int end) 
    {
        if (start > end)
            return 0;
        
        if (start == end)
            return arr[start];
        
        int a = arr[start] + Math.min(findMaxCoins(arr, start+2, end), findMaxCoins(arr, start+1, end-1));   
        int b = arr[end]   + Math.min(findMaxCoins(arr, start+1, end-1), findMaxCoins(arr, start, end-2));   
        
        return Math.max(a, b);
    }

    // Helper method to get random coins in pots
    static int[] getRandomCoins(int numPots) 
    {
        int arr[] = new int[numPots];

        for (int i=0; i<numPots; i++)
        {
            arr[i] = 1+(int)(Math.random()*numPots*2.33);
            System.out.print (arr[i]+", ");
        }

        System.out.println();
        return arr;
    }
}



Order analysis: Order of execution for the above code is exponential.
It executes 4 loops in each recursive call and recursion depth is N.
So order is O(4N)


Example executions:
Coins: 5, 2, 7, 8, 
Max Sum for A: 13



Coins: 1, 12, 3, 12, 6, 10, 
Max Sum for A: 34



Coins: 2, 8, 10, 12, 13, 3, 
Max Sum for A: 25



Coins: 7, 13, 10, 10, 14, 2, 
Max Sum for A: 31



Printing order of choosing coins:
Above will be more clear if we can also print what coins are being chosen by A.
Such a thing will also help A proceed with the game because just a max-sum is useless for A to actually play the game.


import java.util.*;

public class MaximizeCoinCollectionWithSteps 
{

    public static void main(String[] args) 
    {
        int numPots = 6;
        int[] arr = getRandomCoins(numPots);
        
        ArrayList<Integer> l = new ArrayList<Integer> ();
        int maxCoins = findMaxCoins (arr, 0, numPots-1, l);
        printAns(maxCoins, l);
    }


    // The most important part to understand here is why minimum is being chosen from the recursive calls.
    // This is so because the recursive calls the best sums A would choose for himself.
    // Since B is also playing with full efficiency, he will do his best to minimize the A's profit.
    // And so, B will choose a pot which will allow A to choose his next pot with minimum benefit.
    // For example: if B has to choose from 2,10,2,4,3, then
    // B will never choose 2 as that would expose 10 to A.
    // Since B will always offer a minimum to A, we take the minimum from the recursive calls.
    // 
    // But after recursion is done, then A will definitely maximize his profit
    // And that is where we choose maximum
    static int findMaxCoins(int[] arr, int start, int end, ArrayList<Integer> l) 
    {
        if (start > end)
            return 0;
        
        if (start == end)
        {
            l.add(arr[start]);
            return arr[start];
        }
        
        ArrayList<Integer> l1 = new ArrayList<Integer> ();
        ArrayList<Integer> l2 = new ArrayList<Integer> ();
        ArrayList<Integer> l3 = new ArrayList<Integer> ();
        ArrayList<Integer> l4 = new ArrayList<Integer> ();
        
        
        int a = arr[start] + findMaxCoins(arr, start+2, end, l1);
        int b = arr[start] + findMaxCoins(arr, start+1, end-1, l2);
        int c = arr[end]   + findMaxCoins(arr, start+1, end-1, l3);
        int d = arr[end]   + findMaxCoins(arr, start, end-2, l4);
        
        ArrayList<Integer> tmp1;
        ArrayList<Integer> tmp2;
        int min1;
        int min2;
        
        if (a < b)
        {
            tmp1 = l1;
            min1 = a;
        }
        else
        {
            tmp1 = l2;
            min1 = b;
        }
        
        
        if (c < d)
        {
            tmp2 = l3;
            min2 = c;
        }
        else
        {
            tmp2 = l4;
            min2 = d;
        }
        
        if (min1 > min2)
        {
            l.addAll(tmp1);
            l.add(arr[start]);
            return min1;
        }
        else
        {
            l.addAll(tmp2);
            l.add(arr[end]);
            return min2;
        }
    }
    
    // Helper method to print the answer
    static void printAns(int maxCoins, ArrayList<Integer> l) 
    {
        System.out.print ("Order of choosing coins: ");
        for (int i=l.size()-1; i>=0; i--)
            System.out.print (l.get(i) + ", ");
        System.out.println("\nMax sum = " + maxCoins);
    }
    

    // Helper method to get random coins in pots
    static int[] getRandomCoins(int numPots) 
    {
        int arr[] = new int[numPots];

        for (int i=0; i<numPots; i++)
        {
            arr[i] = 1+(int)(Math.random()*numPots*2.33);
            System.out.print (arr[i]+", ");
        }

        System.out.println();
        return arr;
    }
}




Example executions:


Pots: 5, 1, 6, 6, 
Order of choosing coins: 6, 5, 
Max sum = 11



Pots: 7, 12, 9, 11, 10, 13, 
Order of choosing coins: 13, 11, 12, 
Max sum = 36




Pots: 1, 5, 13, 6, 9, 11, 
Order of choosing coins: 11, 1, 13, 
Max sum = 25



Pots: 18, 9, 3, 8, 15, 9, 5, 19, 
Order of choosing coins: 19, 9, 3, 15, 
Max sum = 46








Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal