CareerCup

The idea is that when you start taking coins and you have "n" coins, you can take the coin at the beginning (at index 0) and you are left with coins [1,n-1], or you can take the coin at position n-1 and you are left with coins [0,n-2]. In either case, you are left with a version of the problem where you have n-1 coins and YOUR OPPONENT STARTS.

Imagine now that you have a total of n-1 coins but your opponent is the one who will start the move. In this case there are two options, either the opponent chooses the coin at the beginning or he chooses the coin at the end. in either case you are now left with a total of n-2 coins and YOU START THE MOVE once again.

In the base case when you have once coin, If it is your turn, you pick it, if it is not your turn you gain nothing.

We can solve this problem using dynamic programming. We will basically have two 2-dimensional arrays. The first one caches the max number of coins you can take for every possible start and end in the original array of coins when YOU START. The other 2-D array caches the max number of coins you can get for every possible start and end in the original array when YOUR OPPONENT starts moving, please find the code below

import java.util.Arrays;

public class coinGame {
	
	public static int solveGame(int[][] whenIStart, int[][] whenIDontStart, int size, int [] array, int start, 
			int end, boolean IStart){
		if(start>= size || end>= size || start > end || start <0 || end <0)
			return 0;
		if(IStart){
			if(whenIStart[start][end]!=-1)
				return whenIStart[start][end];
			else{
				int optionOne = array[start] + solveGame(whenIStart, whenIDontStart, size, array, start+1, end, false);
				int optionTwo = array[end] + solveGame(whenIStart, whenIDontStart, size, array, start, end-1, false);
				int result = Math.max(optionOne, optionTwo);
				whenIStart[start][end] = result;
				return result;
			}
		}
		else{
			if(whenIDontStart[start][end]!=-1){
				return whenIDontStart[start][end];
			}
			else{
				int optionOne = solveGame(whenIStart, whenIDontStart, size, array, start+1, end, true);
				int optionTwo = solveGame(whenIStart, whenIDontStart, size, array, start, end-1, true);
				int result = Math.max(optionOne, optionTwo);
				whenIDontStart[start][end] = result;
				return result;
			}
		}
		
		
	}
	public static int solve(int[]array){
		if(array==null || array.length ==0)
			return 0;
		int[][]whenIStart = createAndFill(array.length);
		int[][]whenIDontStart = createAndFill(array.length);
		int size = array.length;
		int start = 0;
		int end = size -1;
		boolean IStart = true;
		return solveGame(whenIStart,whenIDontStart,size, array,start, 
				 end,  IStart);
		
	}
	
	public static int[][] createAndFill(int size){
		int[][]array = new int[size][size];
		for(int i =0; i<array.length; i++){
			for(int j =0; j<array[i].length; j++){
				array[i][j] = -1;
			}
		}
		return array;
	}
	
	public static void main(String[]args){
		int[]ar = {5,2,3};
		System.out.println(solve(ar));
	}

	

}

It's unclear if the game is competitive or cooperative. If it's competitive, it's unclear if player 2 plays perfectly. I will assume it is either cooperative or that player 2 plays poorly. Here is a solution that simply iterates over the possible outcomes and picks the one with the max value. Time complexity is O(2^n)). Some memozation could speed it up.

int maxGold(int a[]) {
		return maxGold(a, 0, a.length - 1, true);
	}

	int maxGold(int a[], int left, int right, boolean firstPlayer) {
		int max = _maxGold(a, left, right, firstPlayer);
		System.out.println("(" + left + "," + right + "," + firstPlayer + ") = " + max);
		return max;
	}

	int _maxGold(int a[], int left, int right, boolean firstPlayer) {
		if (left == right) {
			if (firstPlayer) {
				return a[left];
			}
			else {
				return 0;
			}
		}
		int leftMax = maxGold(a, left+1, right, !firstPlayer);
		int rightMax = maxGold(a, left, right-1, !firstPlayer);
		if (firstPlayer) {
			leftMax += a[left];
			rightMax += a[right];
		}
		return Math.max(leftMax, rightMax);
	}

The recursive solution O(2^n):

public static int getMaxGold(int[] input) {
		int N = input.length;
		int[] sum = new int[N];
		for (int i = 0; i < N; i++) {
			if (i == 0)
				sum[i] = input[i];
			else
				sum[i] = sum[i - 1] + input[i];
		}
		return getMaxGold(input, 0, N - 1, sum);
	}

	public static int getMaxGold(int[] input, int start, int end, int[] sum) {
		if (start < 0 || end > input.length || start > end)
			return 0;
		else if (start == end)
			return input[start];
		int choose1 = input[start] + sum[end] - sum[start]	- getMaxGold(input, start + 1, end, sum);
		int choose2 = input[end] + sum[end - 1] - getMaxGold(input, start, end - 1, sum);
		if (start > 0)
			choose2 = choose2 - sum[start - 1];
		return Math.max(choose1, choose2);
	}

The dp solution O(n^2):

public static int getMaxGold2(int[] input) {
		int N = input.length;
		int[] sum = new int[N];
		for (int i = 0; i < N; i++) {
			if (i == 0)
				sum[i] = input[i];
			else
				sum[i] = sum[i - 1] + input[i];
		}
		HashMap<String, Integer> map = new HashMap<>();
		return getMaxGold2(input, 0, N - 1, sum, map);
	}

	public static int getMaxGold2(int[] input, int start, int end, int[] sum,
			HashMap<String, Integer> map) {
		if (start < 0 || end > input.length || start > end)
			return 0;
		else if (start == end)
			return input[start];
		else {
			String key = start + "," + end;
			if (map.containsKey(key))
				return map.get(key);
			int choose1 = input[start] + sum[end] - sum[start] - getMaxGold2(input, start + 1, end, sum, map);
			int choose2 = input[end] + sum[end - 1] - getMaxGold2(input, start, end - 1, sum, map);
			if (start > 0)
				choose2 = choose2 - sum[start - 1];
			int result = Math.max(choose1, choose2);
			map.put(key, result);

			return result;
		}
	}

The below dynamic programming solution is relatively simple (ignores the second player altogether) and works on a few test cases. The allocation for the 0 padded solution matrix is a little strange, but saves on if statements.

#include <stdio.h>
#include <climits>
#include <iostream>

#define START_BUFFER 2
#define END_BUFFER 4
using namespace std;

int get_max(int * array, int sz)
{
	int max = INT_MIN;
	for (int i = 0; i < sz; ++i)
	{
		if (max < array[i])
		{
			max = array[i];
		}
	}
	return max;
}

void solve(int * pots, int npots, int ** allocators, int ** slns)
{
	int options[4];
	for (int start = npots-1; start >= 0; --start)
	{
		for (int end = start; end < npots; ++end)
		{
			options[0] = pots[start] + slns[start + 1][end - 1];
			options[1] = pots[start] + slns[start + 2][end];
			options[2] = pots[end] + slns[start + 1][end - 1];
			options[3] = pots[end] + slns[start][end - 2];
			slns[start][end] = get_max(options, 4);
		}
	}

}

int main(int argc, char* argv[])
{
	int npots = 6;
	// simple test
	int pots[] = { 5, 1, 5, 1, 5, 1};

	int ** allocators; int ** slns;

	// allocate with zero padding
	allocators = new int*[npots + START_BUFFER];
	slns = new int*[npots + START_BUFFER]; 
	for (int j = 0; j < npots + START_BUFFER; ++j)
	{
		allocators[j] = new int[npots + END_BUFFER];
		slns[j] = allocators[j] + START_BUFFER;
		memset(allocators[j], 0, sizeof(int)*(npots + END_BUFFER));
	}

	// solve
	solve(pots, npots, allocators, slns);
	for (int i = 0; i < npots; ++i)
	{
		for (int j = 0; j < npots; ++j)
		{
			printf(" %i ", slns[i][j]);
		}
		printf("\n");
	}

	// deallocate
	for (int i = 0; i < npots + START_BUFFER; ++i)
	{
		delete allocators[i];
	}
	delete allocators;
	delete slns;

	system("pause");
	return 0;
}

package careercup;

public class CC5707979286380544 {
	public static int getMaxGold(int[] gold,int maxGold,int turn,int startIndex,int endIndex){
		if(startIndex >endIndex||startIndex < 0||endIndex > gold.length){
			return maxGold;
		}
		if(turn == 0){
			if(gold[startIndex] > gold[endIndex]){
				maxGold+= gold[startIndex];
				return getMaxGold(gold, maxGold, 1, ++startIndex, endIndex); 
			}else{	
					maxGold+= gold[endIndex];
					return getMaxGold(gold, maxGold, 1, startIndex, --endIndex);
			}
			}else{
				
				if(gold[startIndex] > gold[endIndex]){
					
					return getMaxGold(gold, maxGold, 0, startIndex, --endIndex); 
				}else{
					
						return getMaxGold(gold, maxGold, 0, ++startIndex, endIndex);
				}
				
			}
			
			
		
		
	}
	
	public static void main(String[] args){
		int[] gold = {5,3,1,2,4};
		System.out.println(getMaxGold(gold, 0, 0, 0, gold.length-1));
	}
}

Quora has good answer for this, uses dynamic programming.

Sorry, I cannot post links here.

#include<iostream>

void recur(int a[],int ii,int jj,int P,int MaxA,int MaxB)
{
cout<<"\n Nana ::"<<ii<<"\t"<<jj;
if(ii>jj){ cout<<"\n\t\t Maximum A, B-->("<<MaxA<<","<<MaxB<<")("<<ii<<","<<jj<<")";return ;}
if(P%2==0){
cout<<"\n\t One A::"<<ii<<"\t"<<jj<<"\t MaxA,MaxB"<<MaxA<<","<<MaxB;;
recur(a,ii+1,jj,(P+1)%2,a[ii]+MaxA,MaxB); cout<<"\n\t One A1::"<<ii<<"\t"<<jj<<"\t MaxA,MaxB"<<MaxA<<","<<MaxB;
recur(a,ii,jj-1,(P+1)%2,a[jj]+MaxA,MaxB); cout<<"\n\t One A2::"<<ii<<"\t"<<jj<<"\t MaxA,MaxB"<<MaxA<<","<<MaxB;
}else if(P%2!=0){
cout<<"\n\t One B::"<<ii<<"\t"<<jj<<"\t MaxA,MaxB"<<MaxA<<","<<MaxB;
recur(a,ii+1,jj,(P+1)%2,MaxA,a[ii]+MaxB);cout<<"\n\t One B1::"<<ii<<"\t"<<jj<<"\t MaxA,MaxB"<<MaxA<<","<<MaxB;
recur(a,ii,jj-1,(P+1)%2,MaxA,a[jj]+MaxB);cout<<"\n\t One B2::"<<ii<<"\t"<<jj<<"\t MaxA,MaxB"<<MaxA<<","<<MaxB;
}
}

int main()
{
int a[]={1,2,3,4,5,6};recur(a,0,sizeof(a)/sizeof(int)-1,0,0,0);
return 0;
}

Do they know how many coins are there in each pot or not?

Just wrote solution on paper, no time to type it.
NOTICE: There are n^2 states here (begin offset multiplied by end offset) and whatever strategy led to each state has to be the best for both therefore you can assume there is only one way to get to each state.
THEREFORE: IF you don't use dynamic programming, your solution is exponential as opposed to n^2.

DP with no recursion:
(If you wonder how comes it does not look like minimax but rather min-min: switch of turn is implied by even or odd number of taken jars or by moving one cell horizontally or vertically)

public static int maxGold( int[] input ) {
  int[] sum = new int[input.length+1];
  sum[0] = 0;
  for ( int i = 0; i < input.length; i ++) sum[i+1] += sum[i] + input[i];

  int[][] takenOnSides2Gold = new int[input.length+1][input.length+1];

  for ( int taken = input.length - 1; taken >= 0; taken --) {
    for ( int takenFront = 0; takenFront <= taken; takenFront ++) {
      int takenEnd = taken - takenFront;
      takenOnSides2Gold[takenFront][takenEnd] =
        sum[input.length-takenEnd] - sum[takenFront] -  //total gold left
        Math.min(  //next move minimizes how much is taken by opponent
          takenOnSides2Gold[takenFront+1][takenEnd],
          takenOnSides2Gold[takenFront][takenEnd+1]);
    }
  }
  return takenOnSides2Gold[0][0];
}

In Python:

def each_cons(L, n):
    for j in range(len(L) - n + 1):
        yield L[j:j+n]

def coin_game(L, values={(): 0}, indices={}):
    for length in range(len(L)):
        for sliced_list in each_cons(tuple(L), length + 1):
            take_left_value = sliced_list[0] - values[sliced_list[1:]]
            take_right_value = sliced_list[-1] - values[sliced_list[:-1]]
            if take_left_value > take_right_value:
                values[sliced_list] = take_left_value
                indices[sliced_list] = 0
            else:
                values[sliced_list] = take_right_value
                indices[sliced_list] = -1
    print "list", L, "has value", values[tuple(L)], "take", indices[tuple(L)]

It can be solved with dynamic programming in O(n^2) as suggested before. Java code:

public static int solve(int[] buckets) {
        int[][][] dpValue = new int[buckets.length][buckets.length][2];
        int[] sums = new int[buckets.length];
        sums[0] = buckets[0];
        // cumulative sum to be used later in finding partial sums (from i to j).
        for (int i = 1; i < buckets.length; i++)
            sums[i] = sums[i - 1] + buckets[i];        
        for (int i = buckets.length - 1; i > -1; i--) {
            // if only one bucket left, best decision is to pick it.
            dpValue[i][i] = new int[] {buckets[i], buckets[i]};         
            for (int j = i + 1; j < buckets.length; j++) {
                // total worth of gold?
                int sumIJ = sums[j] - sums[i] + buckets[i];
                for (int k = 0; k < 2; k++) {
                    // gain the other player gets if we pick first?
                    int pickFirst = dpValue[i + 1][j][1 - k];
                    int pickLast = dpValue[i][j - 1][1 - k];
                    // total worth - best gain for other player = our gain => maximize it by minimizing the other player gain.
                    dpValue[i][j][k] = sumIJ - Math.min(pickFirst, pickLast);
                }
            }
        }
        return dpValue[0][buckets.length - 1][0];
    }

I have discussed these four scenarios: competitive/cooperative playing + known/unknown pots. The solution is to use dynamic programming to solve them. Please refer to

1. cpluspluslearning-petert.blogspot.co.uk/2014/12/dynamic-programming-maximizing-gold.html
2. cpluspluslearning-petert.blogspot.co.uk/2014/12/dynamic-programming-maximizing-gold_10.html
3. cpluspluslearning-petert.blogspot.co.uk/2014/12/dynamic-programming-maximizing-gold_14.html

Dynamic programming. O(N^2)

int MaxGold(int pots[], int s, int e)
{
	if (s > e)
		return 0;
	
	if (s == e)
		return pots[s];

	int opt1 = pots[s] + MaxGold(pots, s+2, e);
	int opt2 = pots[s] + MaxGold(pots, s+1, e-1);
	int opt3 = pots[e] + MaxGold(pots, s, e-2);
	int opt4 = pots[e] + MaxGold(pots, s+1, e-1); //Partly duplicate of opt2.

	return max(max(opt1, opt2), max(opt3, opt4));

}

Here's a cpp solution

#include<vector>
#include<unordered_set>
#include<set>
#include<algorithm>
#include<stdlib.h>
#include<iostream>
#include<utility>
#include<map>
using namespace std;
int n;
int dp[100][100];//,dp2[100][100];
int max1(int a,int b)
{
	return a>b?a:b;
}
int sum1(int *arr,int start,int end)
{
	int sum=0,i;
	for(i=start;i<=end;i++)
	{
		sum+=arr[i];
	}
	return sum;
	
}
int maxGold1(int *arr,int start,int end,bool player)
{
	if(start<0 || end>=n)
		return 0;
	//printf("for %d %d\n",start,end);
	
	if(!player)
	{
		
		dp[start][end]=maxGold1(arr,start,end,true);
		//printf("\n%d %d %d\n",start,end,dp[start][end]);
		return sum1(arr,start,end)-dp[start][end];
		
	}
	if(dp[start][end]!=-1)
		return dp[start][end];
	
	if(start==end)
	{
		dp[start][end]=arr[start];
		return arr[start];
	}
	
	dp[start][end]=max1(arr[start]+maxGold1(arr,start+1,end,false),arr[end]+maxGold1(arr,start,end-1,false));
	//printf("%d %d\n",maxGold1(arr,start+1,end,false),maxGold1(arr,start,end-1,false));
	//printf("at down %d %d %d\n",start,end,dp[start][end]);
	//getchar();
	return dp[start][end];
}
int main()
{
	int arr[]={10,20,80,30,40},i,j;
	n=5;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			dp[i][j]=-1;
			
		}
	}
	maxGold1(arr,0,n-1,true);
	printf("%d\n",dp[0][n-1]);
	
}

#Two players: a,b. calculates max coin collected by input player
#Using DP: player defines who is the 1st player,assuming you are player a
def coin_game(x,player):
    score= [[],[]]
    if player == 'a':
        curr = 0
    else:
        curr = 1
    for i in range(len(x)):
        #print(i)
        if len(x)>1:
            toPop = 0
            # Solution that only you play best 
            if curr == 0:
                if x[0]<x[-1]:
                    toPop = -1 
            else:
                if x[0]>x[-1]:
                    toPop = -1
            if len(score[curr]) == 0:
                score[curr].append(x.pop(toPop))
            else:
                score[curr].append(score[curr][-1]+x.pop(toPop))
            #########################################

            # Solution that both the player play best
            '''
            if x[0]<x[-1]:
                toPop = -1
            if len(score[curr]) == 0:
                score[curr].append(x.pop(toPop))
            else:
                score[curr].append(score[curr][-1]+x.pop(toPop))
            '''
            #########################################
            if curr == 0:
                curr = 1
            else:
                curr = 0
        else:
            score[curr].append(score[curr][-1]+x[0])
    #print (score)
    return score[0][-1]

x = [5,2,1,8,7,9,12,32,85,61]
print coin_game(x,'b')