The 100 game - CanIWin()

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 pool;
int raceTo;

The100Game(int poolMax, int finalSum){
/* If (finalSum > combined sum of all numbers).

With regards to code quality...

Generally, you should add in a bit more whitespace to facilitate readability.

The initialization function looks fine to me. Good choice of ArrayList as a pool (and clever use of the for loop).

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();
    for (int i = 0; i < poolMax; i++) {
        pool.add(i+1);
    }
}

In canIWin(), you should make use of string formatting instead of concatenation.

/*  Autoplay the game with optimal mooves   */
boolean canIWin() {
    int turns = 0;
    while (raceTo > 0) {
        turns++;
        System.out.printf(
            "Player %d ==> %d == Remaining [%d]\n",
            (turns % 2 == 0) ? 2 : 1,
            pickANumber(),
            raceTo
        );
    }
    return turns % 2 == 1;
}

You should do the same for your main function too.

As for your pickANumber() function, you should make your if branches "flatter". Your structure of the code inside the for loop looks like this:

if () {
} else {
    if () {
        if () {
        } else {
        }
    }   
    if () {
        if () {
        } else {
        }
    } else {
    }
}

In many cases, you can replace else { continue; } by changing the structure of your if statement. I'll leave this as an exercise.

If we look closely, we can see that this particular piece of code appears very frequently.

pool.remove(i);
raceTo -= tmp;
return tmp;

This can be easily thrown into a seperate function and would make the code a lot cleaner.

EDIT: Thanks to @ambigram_maker for pointing out that I typed System.out.println instead of System.out.printf. My Java has been rusty (no pun intended) for a while.

StackExchange Code Review Q#64281, answer score: 9