﻿ How to design strategy and algorithm for gold box game

# How to design strategy and algorithm for gold box game

Gold box problem (Approach)

There are ‘n’ gold boxes placed in a row, each having different number of gold coins. 2 players play a game, where the motive is to collect the maximum number of gold coins. Each player can see how many coins are present in each box, but can get a box from either end only, on his turn. Design a strategy such that Player1 wins (Assuming both players play smartly)

This problem was asked in an amazon interview. I tried this approach:

#include<stdio.h>
int max(int a, int b) {
return a>b?a:b;
}
int maxCoins(int arr[], int i, int j, int turn) {
if(i==j) {
if(turn == 1) return arr[i];
else return 0;
}
if(turn) {
return max(arr[i] + maxCoins(arr,i+1,j,0),arr[j] + maxCoins(arr,i,j-1,0));
} else {
if(arr[i]>arr[j])
return maxCoins(arr,i+1,j,1);
else
return maxCoins(arr,i,j-1,1);
}
}
int main() {
int arr[10] = {6,7,4,1,10,5,4,9,20,8}; //{2,3,4,5,6,7,8,9,10,11};
printf("%d\n",maxCoins(arr,0,9,1));
}

But I think this is not right, as player2 also plays smartly. Kindly help with what I am missing.

I got to the solution, just was close. Here is what I missed:

"The opponent intends to choose the coin which leaves the user with minimum value."

Here is updated solution:

#include<stdio.h>
int max(int a, int b) {
return a>b?a:b;
}
int min(int a, int b) {
return a<b?a:b;
}
int maxCoins(int arr[], int i, int j, int turn) {
int a,b;
if(i==j) {
if(turn == 1) return arr[i];
else return 0;
}
if(turn) {
a = arr[i] +maxCoins(arr,i+1,j,0);
b = arr[j] + maxCoins(arr,i,j-1,0);
return max(a,b);
} else {
return min(maxCoins(arr,i+1,j,1), maxCoins(arr,i,j-1,1));
}
}
int main() {
int arr[4] = {8, 15, 3, 7 };//{6,7,4,1,10,5,4,9,20,8}; //{2,3,4,5,6,7,8,9,10,11};
printf("%d\n",maxCoins(arr,0,3,1));
}