Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
For player A : he can pick up coin in first place or last place, for each of these case player B can further pick from first or last place from remaining coins. But for A to win/maximize coins, coins collected by B should be minimum while that of A should be maximized.
If A selects coin[i], then B can choose coin[i+1] or coin[array_size]
If A selects coin[array_last], then B can choose coin[i] or coin[array_last-1]
We will simulate such that every function call will start from A's turn. This will give us the given recursive function.
Add DP to it by using map (or you can use 2-D array too)
map<pair<int, int>, int, PairCmp> DP_map;
typedef pair<int, int> Key;
// Before that, you need to implement a comparison operator for pair<int, int>, say
struct PairCmp {
bool operator() (const Key& p1, const Key& p2) const {
if (p1.first < p2.first)
return true;
else if (p1.first = p2.first)
return p1.second < p2.second;
else
return false;
}
int max_coin( int *coin, int start, int end ):
if start > end:
return 0
if (DP_map.find(Key(start, end)) != DP_map.end())
return DP_map[Key(start, end)];
int a = coin[start] + min( max_coin( coin, start+2,end ), max_coin( coin, start+1,end-1 ) )
int b = coin[end] + min( max_coin( coin, start+1,end-1 ), max_coin( coin, start,end-2 ) )
int ret = max(a, b);
DP_map[Key(start, end)] = ret;
return ret;
}
this solution does not scale. what happens if n is too large? recursion is practically impossible.
this problem is similar to the problem of finding 'perfect' chess strategy. Only that it is a reduced version. At each turn you only have to consider 2 choices, where as in chess it is many.
when n is large, the best you can do is some kind of 'look-ahead' algorithm to make sure by kth move you are not in a worse off position.
The reason for the min function being used is that the opponent B is also going to want to maximize B's winning when picking the gold pot, essentially leaving A with
the minimum of the two options to choose from in the next round.
Quick question: most (if not all) of the answers above follow this guideline: "for each move I make, calculate the minimum possible profit of the opponent, and select the move that yields the greatest profit", i.e.:
F(a,b) = max(min(F(a+2, b), F(a+1, b-1)), min(F(a, b-2), F(a+1,b-1)))
But shouldn't it be the other way around? "for each possible move I make, calculate the *maximum* possible profit of the opponent, and choose the move that yields minimum losses"? i.e.:
F(a,b) = min(max(F(a+2, b), F(a+1, b-1)), max(F(a, b-2), F(a+1, b-1)))
??
the thing is, you calculate the max profit of the opponent. suppose you take it from the front, your opponent can choose from F(a+2, b), F(a+1, b-1) , and since the opponent plays optimally, he/she would choose max(F(a+2, b), F(a+1, b-1)), which left you min(F(a+2, b), F(a+1, b-1));
same logic, if you choose from the end, your opponent can choose from F(a, b-2), F(a+1,b-1), and he/she would choose max(F(a, b-2), F(a+1,b-1)), which left you min(F(a, b-2), F(a+1,b-1))
so you actually need the max left-over so you max whatever your opponent left to you, which is the first formula above.
Say we start with an even number of pots
1 2 3 4 5 6 ... 2*n
Player A can choose the pots in such a way that he has X = 1st + 3rd + + (2n-1)th pots' gold and the player B has Y = 2nd + 4th + ... + (2n)th or vice versa. Since player A can choose whether to end up with X or Y, player A always wins.
In case the number of pots is odd, player B can follow the same strategy right after player A makes first move, so the result depends on the exact amount of gold in the pots, so no 100% winning strategy in this case.
This is right, but the question asks for _the_ optimal winning solution (i.e. which maximizes the sum assuming best play from both sides). What you have here is _a_ winning position.
Very nice proof though...
It may not be the case as the pot can be picked from either end of the line. So 1st , 2nd , 3rd pot is possible as well.
It seems the question ask for __a__ winning strategy for player A, and not for __the__ winning position for player A, actually it may happen that player A has no way to win the game if player B plays optimally.
@Mihail: If the question was asking for _a_ winning strategy, why even talk about maximizing and optimal solutions?
If it was as you say, this will become a purely mathematical problem, and an AHA question, not suitable for a tech-interview.
On the other hand, trying to maximize/finding optimal will be a good algorithmic problem.
this is nice Mihail!
When n is even, it is true who ever moves first can choose the odd-pot series or the even-pot series, so whoever moves first wins.
When n is odd, whoever first is guaranteed to lose unless the first pot can be big enough to offset the difference between odd-pot series and even-pot series!
hugh.hn, if the post is a strategy, it's not a winning one. Consider a four-pot game with the following pots:
6, 3, 1, 4
The first player can indeed choose to receive the first and third pots, but it results in a tie. The player can win, however, by choosing to receive the first and second pots.
Obviously, this is reqursion/dynamic problem. So we need formula.
Let's say, that F(i, j) - is max possible coins that 'first' player can collect on board with packets from i to j. And by 'first' player I mean player whos turn now.
F(0, n-1) - will be the answer.
Ok, now for F(i, j), first player can take v[i] or v[j].
x = v[i] + (Sum[i+1, j ] - F(i+1, j ) );
y = v[j] + (Sum[ i , j-1] - F( i, j-1) );
And he will collent x or y coints. Of course he will choose the maximum option:
F(i, j) = MAX(x, y);
Why (Sum[i+1, j ] - F(i+1, j ) )? Thats simply. After the first player took the coins, the turn passes to the second. And he also wnat to win. And now he is the first player but on the board (i+1, j) or (i, j-1). The Sum is fixed, so all that he will not take - is our coins.
_________________________________________________
But do we really need to calculate Sum? No!
Lets go deeper! in recursion : ) I skip here computing. In two words:
If we 'open' F(i+1, j ) and F( i, j-1) - sum will be reduced and using that
-Max[-a, -b] == Min[a, b]
and we will get:
a = F(i+2, j); b = F(i+1, j-1); c = F(i, j-2);
x = v[i] + MIN(a, b); y = v[j] + MIN(b, c);
F(i, j) = MAX(x, y);
On each iteration size of board will be reduced on 2.
_________________________________________________
To avoid re-computation, we need to store all done computation:
ArrayInfo optimal_subset_sum; //optimal_subset_sum( i, j ) = F(i, j)
ArrayInfo can be simply int[n][n]. if you don't care about the amount of memory used.
But we'll get to that later.
First, we need to initialize the smallest boards answers. There are two different situation.
If N is odd, then F(i, j) = F(i, i) = v[i]
for(int i=0; i+1<n; ++i)
optimal_subset_sum(i, i+1) = data[i];
If N is even, then F(i, j) = F(i, i+1) = MAX(v[i], v[i+1])
for(int i=0; i+1<n; ++i)
optimal_subset_sum(i, i+1) = MAX(data[i], data[i+1]);
And now, we increasing the size of the board for 2 and calculate answers for all possible boards:
for(int k = smallest_lenght + 2; k<=n; k+=2)
for(int i=0, j=k-1; j<n; ++i, ++j)
{
int a = optimal_subset_sum( i+2, j );
int b = optimal_subset_sum( i+1, j-1 );
int c = optimal_subset_sum( i, j-2 );
int x = data[i] + MIN(a, b); int y = data[j] + MIN(b, c);
optimal_subset_sum(i, j) = MAX(x, y);
}
_________________________________________________
Returning to the ArrayInfo.
There is only 1 sub-board starting fron i=n-1. (n-1, n-1)
There are only 2 sub-board starting fron i=n-2. (n-2, n-2) and (n-2, n-1)
...
Additionaly, we have only odd or only even lenght sub-boards, because we reduce it on 2 each time.
So we don't need N*N space. We can impliment ArrayInfo such way:
class ArrayInfo
{
public:
ArrayInfo(size_t n)
{
data = new int*[n]();
for(int i=0; i<n; ++i)
{
data[i] = new int[(n-1-i)/2+1]();
for(int j=i; j<n; ++j)
data[i][j] = -1;
}
}
int& operator() (int i, int j)
{
return data[i][(j-i)/2];
}
private:
int** data;
};
And it will used
Sum[(N-i-1)/2 + 1, { i, 0, N-1 } ] = N*(3+N)/4 = n^2/4 + 3*n/4
that's in 4 time less.
working code: http://ideone.com/ZzbMRt
A C++ solution
The strategy here is to consider the best displacement in favor of yourself. In other words, consider the profit of the left two choices and the right two choices, which we will call a distance. We choose a side by grabbing the side with the smallest distance.
As for the code, it is done using sliding incides that slowly come together. Note the corner cases and edge cases.
int goldGame(const std::vector<int>& pots)
{
// Corner case - No pots of gold
if (pots.size() == 0) return 0;
// Prepare indices
int left = 0;
int right = pots.size() - 1;
// Gold accumulated
int gold = 0;
// Loop until done grabbing gold
while (left != right)
{
// Player A goes
gold += grab(left, right, pots);
// Player B goes (toss the value)
grab(left, right, pots);
}
// Edge case - We had an even number of pots therefore player A
// gets the last pot
if (pots.size() % 2 != 0)
gold += grab(left, right, pots);
return gold;
}
int grab(int& left, int& right, const std::vector<int>& pots)
{
// Edge case - One pot left to choose from
if (left == right) return pots[left];
// Calculate distance on left side and right side
int leftDist = pots[left + 1] - pots[left];
int rightDist = pots[right - 1] - pots[right];
// Choose the lower distance to grab
if (leftDist < rightDist) return pots[left++];
return pots[right--];
}
int gold_pots(int *arr, int n)
{
int i;
int **A = (int **)malloc(sizeof(int *) * n);
int **B = (int **)malloc(sizeof(int *) * n);
for (i = 0; i < n; ++n) {
A[i] = (int *)malloc(sizeof(int) * (n + 1));
B[i] = (int *)malloc(sizeof(int) * (n + 1));
memset(A[i], 0, sizeof(int) * (n + 1));
memset(B[i], 0, sizeof(int) * (n + 1));
A[i][1] = arr[i];
}
for (int length = 2; length <= n; ++length) {
for (i = 0; i <= n - length; ++i) {
// arr[i] ... a[i + lenght - 1]
if (arr[i] + B[i+1][length - 1] > arr[i + length - 1] + B[i][length -1]) {
A[i][length] = arr[i] + B[i+1][length - 1];
B[i][length] = A[i+1][length - 1];
} else {
A[i][length] = arr[i + length - 1] + B[i][length -1];
B[i][length] = A[i][length -1];
}
}
}
int best_first_player = A[0][n];
int best_sond_player = B[0][n];
for (i = 0; i < n; ++i) {
free(A[i]);
free(B[i]);
}
free(A);
free(B);
return best_first_player;
}
Here is a java program that solves this question and has a simulation of the moves (prints out players moves and coin sums along with remaining gold pots)
The main answer to this question is in the maxCoins function at the bottom. It's a little bit cluttered because I'm returning a MaxCoinResults object instead of just an int (has additional info stored in it such as the choice that was made (start or end).
I'm doing a recursive function and caching results (so DP). Similar to a lot of other suggested answers:
import java.util.HashMap;
public class GoldPot {
private static int numSimulationsToRun = 3;
private static int numGoldPots = 10;
private static int maxCoinsPerPot = 10;
private static enum Choice{First,End,NA};
private static enum Player{A,B};
private static Player currentTurn;
public static void main(String[] args) {
runSimulations();
}
private static void runSimulations(){
for(int i=0; i<numSimulationsToRun; i++){
System.out.println("SIMULATION -- " + i + " --\n---------------------------");
int[] goldPots = getRandomGoldPots();
int start,end;
start =0;
end = goldPots.length-1;
currentTurn = Player.A;
MaxCoinResult maxCoinResult = maxCoins(goldPots,start,end, new HashMap<String,MaxCoinResult>());
System.out.println("Initial Coins:" + printGoldPots(goldPots,start,end));
System.out.println("Expected A Winnings:" + maxCoinResult.coinMaxSum);
//Simulate each turn and print results
String playerName;
String choiceStr;
int playerASum = 0;
int playerBSum = 0;
do{
playerName = currentTurn == Player.A ? "Player A" : "Player B";
choiceStr = maxCoinResult.choice == Choice.First ? "first" : "last";
if(currentTurn == Player.A){
playerASum += maxCoinResult.immediateCoinValue;
}
else{
playerBSum += maxCoinResult.immediateCoinValue;
}
System.out.println(playerName + " chooses the " + choiceStr + " coin with a value of:" + maxCoinResult.immediateCoinValue);
int currentPlayerSum = (currentTurn == Player.A) ? playerASum : playerBSum;
System.out.println(playerName + " now has a sum of " + currentPlayerSum);
//update pointers according to coin chosen
if(maxCoinResult.choice == Choice.First){
start++;
}
else{
end--;
}
currentTurn = currentTurn == Player.A ? Player.B : Player.A; //Switch turns
System.out.println("RemainingCoins:" + printGoldPots(goldPots,start,end));
//Get new results
maxCoinResult = maxCoins(goldPots,start,end, maxCoinResult.cachedResults);
}while(start <= end);
System.out.println("Final Results \n-------------");
System.out.println("Player A:" + playerASum);
System.out.println("Player B:" + playerBSum);
System.out.println("END GAME.\n\n");
}
}
public static String printGoldPots(int[] arr, int start, int end){
StringBuilder sb = new StringBuilder();
if(start > end) return "";
sb.append(arr[start]);
for(int i=start+1; i<=end; i++){
sb.append("," + arr[i]);
}
return sb.toString();
}
private static int[] getRandomGoldPots(){
int[] goldPots = new int[numGoldPots];
for(int i=0; i<numGoldPots; i++){
goldPots[i]= (int) Math.ceil(Math.random()*maxCoinsPerPot);
}
return goldPots;
}
//Simple class for result - holds choice made, max value, and initial value of choice
//Also storing cached results so that I can pass it back into maxCoins when running simulations
private static class MaxCoinResult{
int immediateCoinValue;
int coinMaxSum;
Choice choice = null;
HashMap<String,MaxCoinResult> cachedResults;
MaxCoinResult(int coinMaxSum,Choice choice,int immediateCoinValue,
HashMap<String,MaxCoinResult> cachedResults){
this.coinMaxSum = coinMaxSum;
this.immediateCoinValue = immediateCoinValue;
this.choice = choice;
this.cachedResults = cachedResults;
}
}
private static MaxCoinResult maxCoins(int[] coins, int start,int end, HashMap<String,MaxCoinResult> cachedResults){
//Base Case - 0 coins remaining
if(start > end){
MaxCoinResult result = new MaxCoinResult(0,Choice.NA,0, cachedResults);
return result;
}
String cacheKey = start + ":" + end;
//If result for start/end pair has already been cached, just return it
if(cachedResults.containsKey(cacheKey)){
return cachedResults.get(cacheKey);
}
// 3 Possibilities of remaining coins after both players move
// Recursively find max of possible remainders
//1). Both Players Choose Front
//2). 1 Player Chooses Front and 1 Player Chooses End
//3). Both Players choose End
int maxCoins2F = maxCoins(coins,start+2,end,cachedResults).coinMaxSum;
int maxCoins1F1E = maxCoins(coins,start+1,end-1,cachedResults).coinMaxSum;
int maxCoins2E = maxCoins(coins,start,end-2,cachedResults).coinMaxSum;
// 4 Possible outcomes, assuming we haven't limited them yet by the fact that B is going to make
// The optimal move on next turn
int AMaxSumAFBF = coins[start] + maxCoins2F; //A & B Choose Front
int AMaxSumAFBE = coins[start] + maxCoins1F1E; //A Chooses Front, B Chooses End
int AMaxSumAEBF = coins[end] + maxCoins1F1E; //A Chooses End, B Chooses Front
int AMaxSumAEBE = coins[end] + maxCoins2E; //A & B Choose End
// Get the max results of whether A takes First or End, now taking into account the knowledge that
// B will counter with the best move to minimize A's winnings
int AMaxSumAF = Math.min(AMaxSumAFBF, AMaxSumAFBE);
int AMaxSumAE = Math.min(AMaxSumAEBF, AMaxSumAEBE);
//Make a choice based on whether First Or end Sum is greater
Choice choice = AMaxSumAF > AMaxSumAE ? Choice.First : Choice.End;
int immediateCoinValue = (choice == Choice.First) ? coins[start] : coins[end];
int maxSum = (choice == Choice.First) ? AMaxSumAF : AMaxSumAE;
MaxCoinResult result = new MaxCoinResult(maxSum, choice,immediateCoinValue,cachedResults);
//Cache result
cachedResults.put(cacheKey, result);
//Finally return the result of A's best move
return result;
}
}
Here is some sample output:
SIMULATION -- 2 --
---------------------------
Initial Coins:5,5,10,5,9,9,3,9,5,1
Expected A Winnings:33
Player A chooses the first coin with a value of:5
Player A now has a sum of 5
RemainingCoins:5,10,5,9,9,3,9,5,1
Player B chooses the last coin with a value of:1
Player B now has a sum of 1
RemainingCoins:5,10,5,9,9,3,9,5
Player A chooses the first coin with a value of:5
Player A now has a sum of 10
RemainingCoins:10,5,9,9,3,9,5
Player B chooses the first coin with a value of:10
Player B now has a sum of 11
RemainingCoins:5,9,9,3,9,5
Player A chooses the first coin with a value of:5
Player A now has a sum of 15
RemainingCoins:9,9,3,9,5
Player B chooses the last coin with a value of:5
Player B now has a sum of 16
RemainingCoins:9,9,3,9
Player A chooses the last coin with a value of:9
Player A now has a sum of 24
RemainingCoins:9,9,3
Player B chooses the last coin with a value of:3
Player B now has a sum of 19
RemainingCoins:9,9
Player A chooses the last coin with a value of:9
Player A now has a sum of 33
RemainingCoins:9
Player B chooses the last coin with a value of:9
Player B now has a sum of 28
RemainingCoins:
Final Results
-------------
Player A:33
Player B:28
END GAME.
Maybe 32 / 29 ?
var pots = [5,5,10,5,9,9,3,9,5,1];
var playerA,
playerB = 0;
playerA = Math.max(calcLeft(pots), calcRight(pots));
function calc(pots) {
var left = [...pots];
var right = [...pots];
left.shift();
right.pop();
return Math.min(
Math.max(calcLeft(left), calcRight(left)),
Math.max(calcLeft(right), calcRight(right)),
);
}
function calcLeft(pots) {
if (!pots.length) {
return 0;
}
var coins = pots.shift();
return coins + calc(pots);
}
function calcRight(pots) {
if (!pots.length) {
return 0;
}
var coins = pots.pop();
return coins + calc(pots);
}
var pots = [5,5,10,5,9,9,3,9,5,1];
var playerA,
playerB = 0;
playerA = Math.max(calcLeft(pots), calcRight(pots));
function calc(pots) {
var left = [...pots];
var right = [...pots];
left.shift();
right.pop();
return Math.min(
Math.max(calcLeft(left), calcRight(left)),
Math.max(calcLeft(right), calcRight(right)),
);
}
function calcLeft(pots) {
if (!pots.length) {
return 0;
}
var coins = pots.shift();
return coins + calc(pots);
}
function calcRight(pots) {
if (!pots.length) {
return 0;
}
var coins = pots.pop();
return coins + calc(pots);
}
Many people A always win, this is not the case. It depends on the randomness of the gold distribution, we can only maximize.
Here is a test run with 100 pots each time, and run 10000 times.
B consistently wins around 35% of the time, I did 10 different runs, so that's 100,000 times.
The actual % depends many variables, including, number of integers, and the random range of each integer.
Here is a prove: 1 3 1, A loses no matter what.
Here is the full code you can run it yourself, have fun.
static int count = 0;
public static void main(String[] args)
{
for (int j = 0; j < 10000; j++)
{
List<Integer> a = new ArrayList<Integer>();
Random r = new Random();
for (int i = 0; i < 100; i++)
{
int temp = r.nextInt(5) + 1;
a.add(temp);
System.out.print(temp);
}
System.out.println();
game(new LinkedList<Integer>(a), 0, 0);
}
System.out.println("b wins " + count / 10000d * 100 + "%");
}
public static void game(LinkedList<Integer> ll, int a, int b)
{
if (ll == null)
return;
if (ll.size() == 0)
printResult(a, b);
else if (ll.size() == 1)
printResult(a + ll.poll(), b);
else if (ll.size() == 2)
{
int head = ll.poll();
int tail = ll.poll();
if (head >= tail)
printResult(a + head, b + tail);
else
printResult(a + tail, b + head);
} else
{
a = optimalPick(ll, a);
b = optimalPick(ll, b);
game(ll, a, b);
}
}
public static int optimalPick(LinkedList<Integer> ll, int playerGold)
{
int gain1 = ll.peekFirst() - (Math.max(ll.peekLast(), ll.get(1)));
int gain2 = ll.peekLast() - (Math.max(ll.peekFirst(), ll.get(ll.size() - 2)));
if (gain1 > gain2)
return playerGold + ll.pollFirst();
else
return playerGold + ll.pollLast();
}
public static void printResult(int a, int b)
{
System.out.println("A has " + a);
System.out.println("B has " + b);
if(b > a)
count++;
}
Your optimalPick function is not actually always optimal.
For example consider:
5,7,20,24,6,3
According to your optimal pick function
5 - max (7, 3) = -2
3 - max (6, 5) = -3
So A would choose the pot with 5 coins.
Then according to your algorithm, B would choose 3 next. Because:
(7 - 20 )= -13 < (3 - 6) = -3
But if you think for a second it would be a better move for B to choose the pot with 7 coins (because if A chooses the pot with 20 coins on B's next turn, then B can then take the pot with 24 coins).
So if A chose 5 at the beginning, and B chose 7, depending on what A did on their next turn this game would end up:
A = 5 + 3 + 24 = 32 OR 5 + 20 + 6 = 31
B = 7 + 20 + 6 = 33 OR 7 + 24 + 3 = 34
As you can see B won in both instances.
It actually would have been optimal for A to choose the pot with 3 coins in the beginning. With both players playing optimally the results would have been:
A = 3 + 24 + 7 = 34
B = 6 + 5 + 20 = 31
This is an example of why you need to recurse deeper to get the optimal solution rather than just peak at the next move.
You are right however, that with an odd number of pots B has a chance of winning depending on how the coins are set up.
But if there are an even # of coins I believe A has an optimal strategy that will help him/her to win or tie every time.
I tried the code for min max rule above but did not get a correct answer. Please let me know what's wrong
package careercup.com;
public class PotOfGold {
public static void main(String args[]) {
int[] coinPots = {4,10,29,12,26,7,21};
int start =0;
int end = coinPots.length -1;
int aCoin =0;
int bCoin =0;
int bestIndex;
while(end >= start) {
bestIndex = findBestCoinPot(coinPots, start,end);
aCoin = aCoin+ coinPots[bestIndex];
if(bestIndex == start){
start = start+1;
System.out.println("start aCoin" + aCoin + "Best "+coinPots[bestIndex]);
} else {
end = end-1;
System.out.println("end aCoin" + aCoin+ "Best "+coinPots[bestIndex]);
}
if(end >= start) {
bestIndex = findBestCoinPot(coinPots, start,end);
bCoin = bCoin+ coinPots[bestIndex];
if(bestIndex == start){
start = start+1;
System.out.println("start bCoin" + bCoin+ "Best "+coinPots[bestIndex]);
} else {
end = end-1;
System.out.println("End bCoin" + bCoin+ "Best "+coinPots[bestIndex]);
}}
}
System.out.println(" aCoin Final " + aCoin);
System.out.println(" bCoin Final " + bCoin);
}
private static int findBestCoinPot(int[] coinPots, int start, int end) {
// TODO Auto-generated method stub
int chooseCoina;
int chooseCoinb;
chooseCoina = coinPots[start] + Math.min(Math.max(coinPots[start+2],coinPots[end]),Math.max(coinPots[start+1],coinPots[end-1]));
chooseCoinb = coinPots[end] + Math.min(Math.max(coinPots[start+1],coinPots[end-1]),Math.max(coinPots[start],coinPots[end-2]));
if(chooseCoina > chooseCoinb) {
return start;
} else {
return end;
}
}
}
After hours of head scratching was still not able to understand the min logic that is used in the most accepted answer. But came up with my own in Python that is quite straightforward to understand.
#!/usr/bin/env python
def my_func(my_list, start, end):
if start > end:
return 0
value = DP_state.get((start, end), False)
if value:
return value
a = my_list[start]
b = my_list[end]
# - For the 'a' case
if my_list[start + 1] < my_list[end]:
res_a = a + my_func(my_list, start + 1, end - 1)
else:
res_a = a + my_func(my_list, start + 2, end)
# - For the 'b' case
if my_list[start] < my_list[end-1]:
res_b = b + my_func(my_list, start, end - 2)
else:
res_b = b + my_func(my_list, start + 1, end - 1)
if res_a > res_b:
DP_state[(start, end)] = res_a
return res_a
else:
DP_state[(start, end)] = res_b
return res_b
DP_state = dict()
print my_func([5, 3, 7, 10, 6, 9], 0, 5)
I'm taking AI right now and we just covered minimax, which seems perfect for this scenario.The algorithm assumes your opponent is playing optimally in a zero sum game. Even better if you use with alpha beta pruning and likely a depth limit to reduce the number of paths you have to explore.
int[] i = { 5, 25, 4, 8, 32, 6 };
System.out.println(startGame('a', i, 0, i.length - 1, new ArrayList<>()));
private static List<Integer> startGame(char startWith, int[] coins, int start, int end, List coinsCollectedByA) {
if (start >= end) {
if (startWith == 'a') {
coinsCollectedByA.add(coins[end]);
}
return coinsCollectedByA;
}
int coinCollected = ((coins[start] + coins[end - 1]) > (coins[start + 1] + coins[end])) ? coins[start]
: coins[end];
if (((coins[start] + coins[end - 1]) > (coins[start + 1] + coins[end]))) {
start++;
} else {
end--;
}
if (startWith == 'a') {
coinsCollectedByA.add(coinCollected);
startWith = 'b';
} else {
startWith = 'a';
}
return startGame(startWith, coins, start, end, coinsCollectedByA);
}
java code using DP, also gives the moves
public class PotOfGold {
static int[] arr;
static int playerInd = 0;
public static void main(String args[]){
arr = new int[]{3, 4, 5, 7, 12, 13, 6, 1};
int len = arr.length;
Strategy strategy = maxGold(0, len-1);
System.out.println(strategy.sum);
System.out.println(strategy.moves);
}
static Map<String, Strategy> map = new HashMap();
private static Strategy maxGold(int start, int end) {
//System.out.println(start+" "+end);
Strategy strategy;
if(start > end){
strategy = new Strategy();
strategy.sum = 0;
strategy.moves = "";
return strategy;
}
String key = start+"-"+end;
if(map.containsKey(key)){
return map.get(key);
}
Strategy strategy1 = new Strategy(min(maxGold(start+2, end), maxGold(start+1, end-1)), arr[start]);
Strategy strategy2 = new Strategy(min(maxGold(start+1, end-1), maxGold(start, end-2)), arr[end]);;
strategy = max(strategy1, strategy2);
map.put(key, strategy);
return strategy;
}
public static Strategy min(Strategy strategy1, Strategy strategy2){
if(strategy1.compareTo(strategy2) < 0){
return strategy1;
}
return strategy2;
}
public static Strategy max(Strategy strategy1, Strategy strategy2){
if(strategy1.compareTo(strategy2) >= 0){
return strategy1;
}
return strategy2;
}
}
class Strategy implements Comparable{
int sum;
String moves;
Strategy(){
}
Strategy(Strategy strategy1, int val){
sum = val+strategy1.sum;
moves = val+" "+strategy1.moves;
}
@Override
public int compareTo(Object o) {
Strategy strategy1 = (Strategy)o;
return this.sum - strategy1.sum;
}
I might be over simplifying but I used a deque and just popped the end that had the highest value.
[1,9,3,4,2,5,6,2]
def solution():
a=[]
b=[]
lst = input('Enter here --> ')
d = deque()
d.extend(lst)
while len(d)>0:
if len(d)>0:
if d[0]>d[len(d)-1]:
a.append(d.popleft())
else:
a.append(d.pop())
if len(d)>0:
if d[0]>d[len(d)-1]:
b.append(d.popleft())
else:
b.append(d.pop())
print 'Player A ', sum(a), ' ', a
print 'Player B ', sum(b), ' ', b
solution()
I got the same results as other people.
here i write a code which prints first number is number of gold coins collect by A and second one is for B when A plays optimally
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define mod 1000000007
#define pii pair<int,int>
vector<vector<pii>> dp(1001,vector<pii>(1001,pii{0,0}));
int A[1001];
void solve(int l,int r) {
if(l>r)
return ;
if(dp[l][r].first!=0||dp[l][r].second!=0)
return ;
solve(l+1,r);solve(l,r-1);
pii a=dp[l+1][r];
pii b=dp[l][r-1];
if(a.second+A[l]>=b.second+A[r]) {
dp[l][r]={a.second+A[l],a.first};
}
else {
dp[l][r]={b.second+A[r],b.first};
}
return ;
}
int32_t main() {
int N; cin>>N;
for(int i=1;i<=N;i++) {
cin>>A[i];
}
solve(1,N);
cout<<dp[1][N].first<<" "<<dp[1][N].second;
}
#include <iostream>
using namespace std;
int min(int i, int j)
{
return (i<j)?i:j;
}
int max(int i, int j)
{
return (i>j)?i:j;
}
int find_max_coins(int pots[], int start, int end)
{
if(start > end)
return 0;
else
return max(
(pots[start] + min(find_max_coins(pots, start+1, end-1), find_max_coins(pots, start+2, end) ) ),
(pots[end] + min(find_max_coins(pots, start+1, end-1), find_max_coins(pots, start, end-2) ) )
);
}
int main()
{
int pots[] = {1,2,3,4,5};
cout << find_max_coins(pots, 0, 4) << endl;
return 0;
}
int maxCoins(vector<int> coins , int start , int end ,int sum[] ,map<pair<int,int>,int>& visit )
{
if(start > end)
return 0;
if(start == end)
return coins[start];
if(end == start +1)
return max(coins[start],coins[end]);
if(visit.get(make_pair(start,end))!=visit.end())
return visit.get(make_pair(start,end));
int pickFirst = maxCoins(coins,start+1,end);
int pickSecond = maxCoins(coins , start , end -1);
int sumCoins = sum[end+1] - sum[start+1] ;
int value = sumCoins - min(pickFirst,pickSecond);
visit.insert(make_pair(make_pair(start,end),value));
return value;
}
Not necessary that A Win... Consider the below example.....
in any case A will lose...
Ex 1: 26, 70 ,11
Ex 2: 26,25,78,12,17
BR,
Asheesh Goyal
IMO in such games it is a norm to assume that number of moves made by both players is the same and no one is at advantage by having extra moves. The fact that you have odd number of pots violates this essential condition. My small thought. Any comments?
we should assume A and B both want to win. In example (26, 1, 70 ,11) there is no way an 'A' can win. For 'A' to win B has to choose (11,1) or (26,1). But given problem statement that B also wants to win, he will definitely select (1,70). There is no way 'A' can restrict 'B' from selecting '1,70'.
@sagar: In the case of (26, 1, 70, 11), A can win as follows:
1. A selects 26
2. Now B has to select either 1 or 11 from (1, 70, 11).
3. B selects either 11 or 1.
4. A selects 70.
5. B gets the other one.
So A can make a decision which forces B to not be able to choose 70. I think you probably read the question wrong.
Guys I need bit more explanation here.
As per the given question, player's don't have any benefit or restriction. I mean, how can a player A choose ?? as it is certain he must have to pick a pot and that too present in a certain position.. Is there any option for him to skip a pot if he did not wish to collect it ?? How can the decision is been generated ? without that the game is straight forward and is totally depends upon arrangement of pots rather than player
- If number of pots of gold is odd: There's no optimal strategy that makes A win knowing that B is playing optimally as well. (Ex: [1,3,1]);
- Else: Player A must always pick the pot which produces the larger result for the equation (Number - Immediate Neighbor).
Ex:
pots = [1,1,10,15,1,2]
A: picks pot[5] (2-1 > 1-1);
B: picks pot[0] (1-1 > 1-15);
So on...
DP implementation in C lang. for recursive algo. stated by Cerberuz
===================================================
// utility function
int max(int a, int b) {
if( a > b )
return a;
else
return b;
}
// utility function
int min(int a, int b) {
if( a < b )
return a;
else
return b;
}
// DP version
int max_coin_DP (int * coin, int n) {
int L, i, j;
int maxStart, maxEnd, result;
int ** maxArr = NULL;
maxArr = (int **) calloc(1+n, sizeof(int *));
for(L=0; L<=n; ++L) {
// for L=0, maxArr[0][i]=0;
maxArr[L] = (int *) calloc(n, sizeof(int));
}
// for L=1
for(i=0; i<=(n-1); ++i) {
maxArr[1][i] = coin[i];
}
// for L=2
for(i=0; i<=(n-2); ++i) {
maxArr[2][i] = max(coin[i], coin[i+1]);
}
// for L>=3
for(L=3; L<=n; ++L) {
for(i=0; i<n; ++i) {
j=(i+L-1);
maxStart = coin[i] + min(maxArr[i+2][j], maxArr[i+1][j-1]);
maxEnd = coin[j] + min(maxArr[i+1][j-1], maxArr[i][j-2]);
maxArr[i][j] = max(maxStart, maxEnd);
}
}
result=maxArr[n][0]; // final result
for(L=0; L<=n; ++L) {
free(maxArr[L]);
}
free(maxArr);
return(maxStart);
}
int getMaxCoins(int * coin, int n, int player) {
int start=0;
int end=(n-1);
if(player==1)
return (max_coin_DP(coin, n));
if(player==2)
return ( max(max_coin_R(coin, 1+start, end), max_coin_R(coin, start, end-1)) );
return (-1);
}
I hope the code is self explanatory in the meaning.
max_coin_R() method is a recursive method:
// This is a recursive version, alternatively it can be done using DP.
int max_coin_R( int * coin, int start, int end ) {
int a, b;
if (start > end)
return 0;
a = coin[start] + min( max_coin_R(coin, start+2,end), max_coin_R(coin, start+1, end-1) );
b = coin[end] + min( max_coin_R(coin, start+1 ,end-1), max_coin_R(coin, start, end-2) );
return max(a,b);
}
dp:
int max_coin(vector<int> pots)
{
vector<vector<int>> dp_table;
int pot_num=pots.size();
dp_table.resize(pot_num);
for(int i=0;i<pot_num;i++)
{
dp_table[i].resize(pot_num);
for(int j=0;j<i;j++)
dp_table[i][j]=0;
}
for(int k=0;k<pot_num;k++)
{
for(int i=0;i<pot_num;i++)
{
int j=i+k;
if(j>=pot_num)
continue;
double pots1,pots2;
if(i+2<pots.size() && j-1>=0)
pots1=pots[i]+min(dp_table[i+2][j],dp_table[i+1][j-1]);
else
pots1=pots[i];
if(i+1<pots.size() && j-2>=0)
pots2=pots[j]+min(dp_table[i+1][j-1],dp_table[i][j-2]);
else
pots2=pots[j];
dp_table[i][j]=max(pots1,pots2);
}
}
return dp_table[0][pot_num-1];
}
Python Recursive algorithm with Caching.
def strategy(pots):
cache = {}
def s(i, j):
# Given: pots from i to j
# Assuming rational players, return this tuple
# to represent your strategy:
# only, L, R
# how much gold in this pot
# 1st player bounty
# 2nd player bounty
# rest of the game
if i == j:
return ('only', pots[i], pots[i], 0, None)
if (i,j) in cache:
return cache[(i,j)]
l_next = s(i+1, j)
r_next = s(i, j-1)
_, _, l1, l2, _ = l_next
_, _, r1, r2, _ = r_next
l_outcome = pots[i] + l2
r_outcome = pots[j] + r2
if l_outcome > r_outcome:
result = ('L', pots[i], l_outcome, l1, l_next)
else:
result = ('R', pots[j], r_outcome, r1, r_next)
cache[(i,j)] = result
return result
return s(0, len(pots)-1)
pots = [6, 2, 3, 4, 7]
print pots
print strategy(pots)
#include <iostream>
#include <vector>
int choose(int* head, int* tail, char& choice)
{
if (head > tail)
return 0;
int middle = choose(head + 1, tail - 1, choice); // memoization
int head_first = *head + std::min(middle, choose(head + 2, tail, choice));
int tail_first = *tail + std::min(middle, choose(head, tail - 2, choice));
choice = head_first >= tail_first ? 'H' : 'T';
return std::max(head_first, tail_first);
}
int main()
{
std::vector<int> v = { 10, 2, 6, 10, 4, 7, 100, 100 };
char choice;
int i = choose(&v.data()[0],
&v.data()[0] + v.size() - 1,
choice);
std::cout << choice << " gives you " << i
<< " pieces of gold" << std::endl;
return 0;
}
public static class PotsOfGold
{
/// <summary>
/// Computes the optimal strategy where a player can pick pots from the beginning or end of the array
/// </summary>
/// <param name="pots">Array of pots each having gold value</param>
/// <returns>Indices that should be chosen</returns>
public static Stack<int> Compute(int[] pots, out int totalValue)
{
return Compute(pots, 0, pots.Length - 1, null, out totalValue);
}
/// <summary>
/// Computes optimal strategy to pick pots, given that the other player is also playing optimally
/// </summary>
/// <param name="pots">Array of pot gold values</param>
/// <param name="startIndex">Next left pot to pick</param>
/// <param name="endIndex">Next right pot to pick</param>
/// <param name="cache">Cache - without it, the algorithm is exponential</param>
/// <param name="totalValue">The difference between next player's value and the one of his opponents</param>
/// <returns>Stack of indices to pick next</returns>
private static Stack<int> Compute(int[] pots, int startIndex, int endIndex, Dictionary<string, Tuple<int[], int>> cache, out int totalValue)
{
if (startIndex == endIndex)
{
totalValue = pots[startIndex];
return new Stack<int>(new int[] {startIndex });
}
else
{
if (cache == null)
{
cache = new Dictionary<string,Tuple<int[],int>>();
}
string cacheKey = string.Format("{0}_{1}", startIndex, endIndex);
if (cache.ContainsKey(cacheKey))
{
var cachedValue = cache[cacheKey];
totalValue = cachedValue.Item2;
return new Stack<int>(cachedValue.Item1);
}
else
{
int lPotValue = pots[startIndex];
int rPotValue = pots[endIndex];
int lCost;
int rCost;
Stack<int> lStrategy = Compute(pots, startIndex + 1, endIndex, cache, out lCost);
Stack<int> rStrategy = Compute(pots, startIndex, endIndex - 1, cache, out rCost);
// this is where we strategy is chosen
// what's better take pot from the left or from the right
if (lPotValue - lCost > rPotValue - rCost)
{
// take left
lStrategy.Push(startIndex);
totalValue = lPotValue - lCost;
cache[cacheKey] = new Tuple<int[], int>(lStrategy.ToArray(), totalValue);
return lStrategy;
}
else
{
// take right
rStrategy.Push(endIndex);
totalValue = rPotValue - rCost;
cache[cacheKey] = new Tuple<int[], int>(rStrategy.ToArray(), totalValue);
return rStrategy;
}
}
}
}
}
I believe that this does the trick... simple recursion using golang, could be optimized to suit various requirements...
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
type Pot struct {
value int
choice *Choice
}
type Choice struct {
scoreA, scoreB int
leftPot, rightPot *Pot
}
func main() {
out := bufio.NewWriter(os.Stdout)
potvals, err := getPots(out)
if err != nil {
out.WriteString(fmt.Sprintln("ERROR: ", err))
out.Flush()
return
}
buildSolveAndPrintChoiceTree(potvals,out);
}
func getPots(out *bufio.Writer) ([]int, error) {
out.WriteString(fmt.Sprintln("type a space separated list of pot values and hit 'enter' key, or just hit 'enter' key to use default game"))
out.Flush()
scanner := bufio.NewScanner(os.Stdin)
if scanner.Scan() {
fmt.Println(scanner.Text()) // Println will add back the final '\n'
pots := strings.Split(scanner.Text(), " ")
// Assign cap to avoid resize on every append.
potvals := make([]int, 0, len(pots))
for _, p := range pots {
// Empty line occurs at the end of the file when we use Split.
if len(p) == 0 {
continue
}
// Atoi better suits the job when we know exactly what we're dealing
// with. Scanf is the more general option.
n, err := strconv.Atoi(p)
if err != nil {
return nil, err
}
potvals = append(potvals, n)
}
if len(potvals) > 0{
return potvals, nil
}
}
//default values for testing
potvals := make([]int, 4)
potvals[0] = 3
potvals[1] = 8
potvals[2] = 7
potvals[3] = 3
out.WriteString(fmt.Sprintln("using default testing game: ",potvals))
out.Flush()
return potvals, nil
}
func buildSolveAndPrintChoiceTree(potvals []int,out *bufio.Writer){
mychoice := buildChoiceTree(potvals)
solveChoiceTree(mychoice)
printSolvedChoiceTree(mychoice, out)
out.Flush()
}
/*recursively build a funny binary tree sort of thing from input*/
func buildChoiceTree(potvals []int) *Choice {
thelen := len(potvals)
choice := new(Choice)
choice.leftPot = new(Pot)
choice.leftPot.value = potvals[0]
if thelen > 1 {
choice.rightPot = new(Pot)
choice.rightPot.value = potvals[thelen-1]
choice.leftPot.choice = buildChoiceTree(potvals[:1])
choice.rightPot.choice = buildChoiceTree(potvals[:thelen-1])
}
return choice
}
func solveChoiceTree(tree *Choice) int {
scoreA, _ := solveChoiceTreeR(tree, true)
return scoreA
}
func solveChoiceTreeR(tree *Choice, turnA bool) (int, int) {
//terminal node
if tree.rightPot == nil {
if turnA {
tree.scoreA = tree.leftPot.value
tree.scoreB = 0
} else {
tree.scoreA = 0
tree.scoreB = tree.leftPot.value
}
} else {
//we're at a choice with two viable pots leading to new choices
scoreAL, scoreBL := solveChoiceTreeR(tree.leftPot.choice, !turnA)
scoreAR, scoreBR := solveChoiceTreeR(tree.rightPot.choice, !turnA)
if turnA {
//A's turn; trim nonoptimal choice for a
scoreAL += tree.leftPot.value
scoreAR += tree.rightPot.value
if scoreAL >= scoreAR {
//trim off right from tree
tree.rightPot = nil
tree.scoreA = scoreAL
tree.scoreB = scoreBL
} else {
tree.leftPot = nil
tree.scoreA = scoreAR
tree.scoreB = scoreBR
}
} else {
//B's turn; trim nonoptimal choice for a
scoreBL += tree.leftPot.value
scoreBR += tree.rightPot.value
if scoreBL >= scoreBR {
//trim off right from tree
tree.rightPot = nil
tree.scoreA = scoreAL
tree.scoreB = scoreBL
} else {
tree.leftPot = nil
tree.scoreA = scoreAR
tree.scoreB = scoreBR
}
}
}
return tree.scoreA, tree.scoreB
}
func printSolvedChoiceTree(tree *Choice, out *bufio.Writer) {
printSolvedChoiceTreeR(tree, out, true)
out.WriteString(fmt.Sprintln("Final score (Player A vs Player B): (", tree.scoreA, " vs ", tree.scoreB, ")"))
}
func printSolvedChoiceTreeR(tree *Choice, out *bufio.Writer, turnA bool) {
if turnA {
if tree.leftPot != nil {
out.WriteString(fmt.Sprintln("Player A chooses the L pot: ", tree.leftPot.value, " (", tree.scoreA, " vs ", tree.scoreB, ")"))
if tree.leftPot.choice != nil {
printSolvedChoiceTreeR(tree.leftPot.choice, out, !turnA)
}
} else {
if tree.rightPot != nil {
out.WriteString(fmt.Sprintln("Player A chooses the R pot: ", tree.rightPot.value, " (", tree.scoreA, " vs ", tree.scoreB, ")"))
if tree.rightPot.choice != nil {
printSolvedChoiceTreeR(tree.rightPot.choice, out, !turnA)
}
}
}
} else {
if tree.leftPot != nil {
out.WriteString(fmt.Sprintln("Player B chooses the L pot: ", tree.leftPot.value, " (", tree.scoreA, " vs ", tree.scoreB, ")"))
if tree.leftPot.choice != nil {
printSolvedChoiceTreeR(tree.leftPot.choice, out, !turnA)
}
} else {
if tree.rightPot != nil {
out.WriteString(fmt.Sprintln("Player B chooses the R pot: ", tree.rightPot.value, " (", tree.scoreA, " vs ", tree.scoreB, ")"))
if tree.rightPot.choice != nil {
printSolvedChoiceTreeR(tree.rightPot.choice, out, !turnA)
}
}
}
}
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//Note : turn 1 -> A's turn, turn 2 -> B's turn
int collectCoins(int turn, int coins[], int front_index, int back_index){
//if there is only one item
if(front_index == back_index){
//A turn
if(turn == 1){
return coins[front_index];
}
else
{
return 0;
}
}
//A turn
if(turn == 1){
return max(coins[front_index] + collectCoins(2, coins, front_index+1, back_index),
coins[back_index] + collectCoins(2, coins, front_index, back_index-1));
}
else
{
//B turn
//takes out the element that is biggest in either side
if(coins[front_index] >= coins[back_index]){
return collectCoins(1, coins, front_index+1, back_index);
}
else
{
return collectCoins(1, coins, front_index, back_index-1);
}
}
}
int main()
{
int coins[] = {10, 100, 1000, 15, 25, 200, 45, 70, 100};
cout << collectCoins(1, coins, 0, 8) << endl;
return 0;
}
Please check if this is correct. Thanks! :D
A - input array.
S(x,y) - sum of element from x to y. We can get it for O(1) with O(n) preproccesing using 2 array. Of course, with solution with Max of two Min of two F(...) is a bit faster (no need to calculate sum), but as for me - this is simple to understand.
F(x, x) := A[x]
F(x, y) := Max( A[x] + S(x+1, y) - F(x+1, y), A[y] + S(x, y-1) - F(x, y-1) )
We get first or last: A[x] or A[y]
Then see how many can get opponent in new array: F(x+1, y) or F(x, y-1)
Because of constant amount of points: S(x+1, y) - F(x+1, y) or S(x, y-1) - F(x, y-1)
HERE ARE A SIMULATION:
public static void main(String [] args){
System.out.println();
int coins[] = new int[]{100,1,20,30,40,10,20,30,90};
for(int i = 0 ; i < coins.length; i++)
System.out.print(coins[i] + " , ");
System.out.println();
playGame(coins);
System.out.println("Recursive call result: : " + max_coin(coins,0,coins.length-1));
}
public static void playGame(int array[])
{
// taking the first one.
int sum = array[0];
int sumB = 0;
int i = 1;
int j = array.length-1;
String paths = "" + array[0] + " + ";
String pathsB ="";
while(i<j){
// Time for Player B
if(array[i] > array[j])
{
pathsB += array[i] + " + ";
sumB += array[i];
i++;
}else{
pathsB += array[j] + " + ";
sumB += array[j];
j--;
}
// Time for player A
if(i>j)break;
if(array[i] > array[j])
{
paths += "" + array[i] + " + ";
sum += array[i];
i++;
}else{
paths += "" + array[j] + " + ";
sum += array[j];
j--;
}
}
System.out.println("Taking the first one:");
if(sumB>sum){
System.out.println("B WINS ");
}else{
System.out.println("A WINS " );
}
System.out.println("PLAYER A " + paths + " = " + sum);
System.out.println("PLAYER B " + pathsB + " = " +sumB);
// Start by taking the last one
sum = array[array.length-1];
i = 0;
j = array.length-2;
paths = "" + array[array.length-1] + " + ";
while(i<j){
// Time for Player B
if(array[i] > array[j])
{
pathsB += array[i] + " + ";
sumB += array[i];
i++;
}else{
pathsB += array[j] + " + ";
sumB += array[j];
j--;
}
// Time for player A
if(i>j)break;
if(array[i] > array[j])
{
paths += "" + array[i] + " + ";
sum += array[i];
i++;
}else{
paths += "" + array[j] + " + ";
sum += array[j];
j--;
}
}
System.out.println("Taking the Last one:");
if(sumB>sum){
System.out.println("B WINS");
}else{
System.out.println("A WINS");
}
System.out.println("PLAYER A " + paths + " = " + sum);
System.out.println("PLAYER B " + pathsB + " = " + sumB);
}
public static int max_coin( int coin[], int start, int end ){
if (start > end)
return 0;
int a = coin[start] + Math.min( max_coin( coin, start+2,end ), max_coin( coin, start+1,end-1 ) );
int b = coin[end] + Math.min( max_coin( coin, start+1,end-1 ), max_coin( coin, start,end-2 ) );
return Math.max(a,b);
}
mafafito@mafafito-Aspire-4752:~/programming$ java Amazon
100 , 1 , 20 , 30 , 40 , 10 , 20 , 30 , 90 ,
Taking the first one:
A WINS
PLAYER A 100 + 30 + 10 + 30 + 1 + = 171
PLAYER B 90 + 20 + 40 + 20 + = 170
Taking the Last one:
B WINS
PLAYER A 90 + 30 + 10 + 30 + 1 + = 161
PLAYER B 90 + 20 + 40 + 20 + 100 + 20 + 40 + 20 + = 350
Recursive call result: : 171
Oh. you are not taking about my code.
about the upvoting thing, of course I know it does not work. ( or at least it shouldn't work) But I wonder, how do you know that I did try anyway?
we are all in love with ourselves
that's what careercup is for
broken egos finding a playground to repair egos
import com.google.common.collect.Maps;
import java.util.Map;
public class PotsOfGold {
private static int [] pots = new int[1000];
public static void main(String[] args) {
double sqrt = Math.sqrt(pots.length);
for(int i=0;i<pots.length;i++){
pots[i]= (int)(Math.random()*sqrt);
}
long start = System.currentTimeMillis();
System.out.println(takeBrute(0, pots.length - 1));
System.out.println("brute took "+(System.currentTimeMillis()-start));
start = System.currentTimeMillis();
System.out.println(takeAlgo());
System.out.println("algo took "+(System.currentTimeMillis()-start));
}
private static int takeAlgo() {
if (pots.length==1) return pots[0];
if (pots.length==2) return Math.max(pots[0],pots[1]);
if (pots.length%2==0){
int sumEven = sum(0, pots.length-1, 0),
sumOdd = sum(0, pots.length-1, 1);
return Math.max(sumEven, sumOdd);
}else{
int takeHead = pots[0]+Math.min(sum(1, pots.length-1, 0),sum(1, pots.length-1, 1));
int takeTail = pots[pots.length-1]+Math.min(sum(0, pots.length-2, 0),sum(0, pots.length-2, 1));
return Math.max(takeHead, takeTail);
}
}
private static int sum(int headIndex,int tailIndex, int oddOrEven){
int sum = 0;
for(int i=headIndex;i<=tailIndex;i++){
if (i%2==oddOrEven){
sum+=pots[i];
}
}
return sum;
}
private static final Map<String,Integer> cache = Maps.newHashMap();
private static int takeBrute(int headIndex, int tailIndex) {
if (headIndex>tailIndex) return 0;
if (headIndex==tailIndex) return pots[headIndex];
if (headIndex+1==tailIndex) return Math.max(pots[headIndex],pots[tailIndex]);
String key = headIndex+" "+tailIndex;
Integer ret = cache.get(key);
if (ret!=null) return ret;
int takeHH = takeBrute(headIndex + 2, tailIndex);
int takeHT = takeBrute(headIndex + 1, tailIndex - 1);
int takeTT = takeBrute(headIndex, tailIndex-2);
int takeHead = pots[headIndex] + Math.min(takeHT, takeHH);
int takeTail = pots[tailIndex] + Math.min(takeTT, takeHT);
ret = Math.max(takeHead, takeTail);
cache.put(key, ret);
return ret;
}
}
Output for 1k pots :
7726
brute took 454
7711
algo took 0
N.B. The fast algo is pretty damn close and very fast but it's not accurate. Times are in milliseconds.
If you need the values as well
{{
def mc(l):
if len(l) <= 2:
return sorted(l, reverse=True)
v1 = mc(l[1:])
v2 = mc(l[:-1])
if (l[0] + sum(v1[i] for i in range(1, len(v1), 2))) > \
(l[-1] + sum(v2[i] for i in range(1, len(v2), 2))):
return [l[0]] + v1
else:
return [l[-1]] + v2
def wsa(l):
v = mc(l)
return [v[i] for i in range(len(v)) if i % 2 == 0]
print wsa([13, 25, 20, 12, 3])
}}
google search for minimax algorithm. That's the answer to this problem. Given all the information, one can say that person who plays first will ALWAYS win...
Consider the pot's structure
1 3 1
Player A ends up with 2, and player B with 3 no matter how player A performs.
This is a recursive version, alternatively it can be done using DP.
- Cerberuz February 12, 2013