Maximize coin selection to win gameProblem: 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 |
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: