ksun.mc
BAN USERHere 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.
Your optimalPick function is not actually always optimal.
- ksun.mc August 14, 2014For 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.