Problem:
- Two players pick numbers from a common pool of number to reach a combined total.
- The player who get to reach/cross the target value wins.
- The problem is to find out if player-1 can enforce a strategy to win - for a given total and a pool of numbers.
My Approach:
Assuming both the players pick the optimal number from the available pool. By optimal, I mean -
Check if the highest number available in the pool >= remaining value. [yes]=> return the highest value available.
If winning is not possible, pick the highest available number (
RequiredToWin - HighestNumberInThePool) in the pool that will NOT guarantee a win in the next turn.
I just came up with 'a' solution and wrote the code. I am trying to analyze if it is optimal, in terms of time, space. Also trying to understand how I can improve my coding conventions - Global variables and the way I am using the conditional statements. I need help-review to make the code better.
/* In "the 100 game," two players take turns adding, to a running
total, any integer from 1..10. The player who first causes the running
total to reach or exceed 100 wins.
What if we change the game so that players cannot re-use integers?
For example, if two players might take turns drawing from a common pool of numbers
of 1..15 without replacement until they reach a total >= 100. This problem is
to write a program that determines which player would win with ideal play.
Write a procedure, "Boolean canIWin(int maxChoosableInteger, int desiredTotal)",
which returns true if the first player to move can force a win with optimal play.
Your priority should be programmer efficiency; don't focus on minimizing
either space or time complexity.
*/
package Puzzles;
import java.util.List;
import java.util.ArrayList;
public class The100Game{
List<Integer> pool;
int raceTo;
The100Game(int poolMax, int finalSum){
/* If (finalSum > combined sum of all numbers).
* This is an impossible problem to solve
*/
if(finalSum > ((poolMax*poolMax + poolMax)/2)){
throw new IllegalArgumentException("Expected sum cannot be achieved!");
}
raceTo = finalSum;
pool = new ArrayList<Integer>();
for(int i=0;i<poolMax;i++)
pool.add(i+1);
}
/* Autoplay the game with optimal mooves */
boolean canIWin(){
int turns = 0;
while(raceTo>0){
turns++;
System.out.println("Player"+( (turns%2==0)?"2":"1" )+" ==> "+pickANumber()+" == Remaining ["+raceTo+"]");
}
return (turns%2==1);
}
/* Pick an Optimal number, so to win
* or prevent he opponent from winning
*/
int pickANumber(){
int leastMax = -1;
int len = pool.size();
for(int i=len-1;i>=0;i--){
int tmp = pool.get(i);
if(tmp>=raceTo){
/* Winning Pick */
pool.remove(i);
raceTo -= tmp;
return tmp;
}else{
if(leastMax > 0){
/* Picking the highest number available in the pool might let the next player win.
* So picking a number < leastMax, if available - to gaurentee otherwise. */
if(tmp < leastMax){
pool.remove(i);
raceTo -= tmp;
return tmp;
}else{
continue;
}
}
if(i-1 >= 0) {
/* We know, the highest number available in the pool is < raceTo (target sum)
* Check in the pool
* if the sum of the highest number + nextHighest number >= raceTo (target sum)
* [True] => Skip both the numbers and look for a number < the LeastMax
* so the opposite player does not win.
* [False] => The highest number in the pool is the best pick
*/
if(tmp+pool.get(i-1) < raceTo){
pool.remove(i);
raceTo -= tmp;
return tmp;
}else{
leastMax = raceTo - tmp;
i--;
continue;
}
}else{
pool.remove(i);
raceTo -= tmp;
return tmp;
}
}
}
/* The raceTo sum cannot be achieved in this turn.
* There is no number available in the pool
* that can prevent a Win in the next turn.
* So we return the highest number availble in the pool.
*/
int tmp = pool.get(pool.size()-1);
pool.remove(pool.size()-1);
raceTo -= tmp;
return tmp;
}
public static void main(String[] args){
The100Game game = new The100Game(15, 105);
System.out.println("\nPlayer-"+(game.canIWin()?"1":"2")+" wins!");
}
}
Output:
-------------------------------------- Player1 ==> 15 == Remaining [90] Player2 ==> 14 == Remaining [76] Player1 ==> 13 == Remaining [63] Player2 ==> 12 == Remaining [51] Player1 ==> 11 == Remaining [40] Player2 ==> 10 == Remaining [30] Player1 ==> 9 == Remaining [21] Player2 ==> 8 == Remaining [13] Player1 ==> 5 == Remaining [8] Player2 ==> 7 == Remaining [1] Player1 ==> 6 == Remaining [-5] Player-1 wins!
