7
\$\begingroup\$

Problem:

  1. Two players pick numbers from a common pool of number to reach a combined total.
  2. The player who get to reach/cross the target value wins.
  3. 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 -

  1. Check if the highest number available in the pool >= remaining value. [yes]=> return the highest value available.

  2. 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!
\$\endgroup\$
  • 1
    \$\begingroup\$ I've noticed that no one has posted an answer about the optimality of the heuristic. Once the code has been cleared up, should @CCP post a new question for that? \$\endgroup\$ – wei2912 Oct 2 '14 at 7:22
8
\$\begingroup\$

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<Integer>();
    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.

\$\endgroup\$
  • \$\begingroup\$ Shouldn't you put System. printf() for outputting formatted strings? \$\endgroup\$ – Hungry Blue Dev Oct 1 '14 at 15:11
  • \$\begingroup\$ @ambigram_maker Whoops, forgot about that. Thanks for the notice. \$\endgroup\$ – wei2912 Oct 1 '14 at 15:38
  • \$\begingroup\$ @wei2912 Thank you for your review. I will keep in mind the suggestions. Very much appreciate your time. +1 \$\endgroup\$ – CCP Oct 1 '14 at 19:26
7
\$\begingroup\$

Only focusing on int pickANumber()

Let us take a look at the if..else...... beast with comments removed

if(tmp>=raceTo){
    pool.remove(i);
    raceTo -= tmp;
    return tmp; 
}else{
    if(leastMax > 0){
        if(tmp < leastMax){
            pool.remove(i);
            raceTo -= tmp;
            return tmp;
        }else{
            continue;
        }
    }   
    if(i-1 >= 0) {
        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;
    }
}  

to get a better overview, we will use the last part of wei1912's answer and extract the repeating part to a spearate method.

private int pickTheNumber(int poolIndex){
    int pickedValue = pool.remove(poolIndex);
    raceTo -= pickedValue;
    return pickedValue;
}  

now our if..else will look like

if(tmp>=raceTo){
    return pickTheNumber(i); 
}else{
    if(leastMax > 0){
        if(tmp < leastMax){
            return pickTheNumber(i);
        }else{
            continue;
        }
    }   
    if(i-1 >= 0) {
        if(tmp + pool.get(i-1) < raceTo){
            return pickTheNumber(i);
        }else{
            leastMax = raceTo - tmp;
            i--;
            continue;
        }
    }else{
        return pickTheNumber(i);
    }
}

mhhh, that does look a lot better. But we can still do better.

Each time we have a if with an else and if we return a value or calling continue inside the if block, we can simply skip the else. So lets refactor !

if(tmp>=raceTo){
    return pickTheNumber(i); 
}
if(leastMax > 0){
    if(tmp < leastMax){
        return pickTheNumber(i);
    }
    continue;
}   
if(i-1 >= 0) {
    if(tmp + pool.get(i-1) < raceTo){
        return pickTheNumber(i);
    }
    leastMax = raceTo - tmp;
    i--;
    continue;
}
return pickTheNumber(i);

Oh yeah, this looks neat.

Now let us rename this ugly tmp to currentValue and also let us move the declaration outside of the loop and we get

int pickANumber(){
    int currentValue = -1;
    int leastMax = -1;
    int len = pool.size();
    for(int i = len-1; i >= 0; i--){
        currentValue = pool.get(i);
        if(currentValue >= raceTo){
            return pickTheNumber(i); 
        }
        if(leastMax > 0){
            if(currentValue < leastMax){
                return pickTheNumber(i);
            }
            continue;
        }   
       if(i-1 >= 0) {
            if(currentValue + pool.get(i-1) < raceTo){
                return pickTheNumber(i);
            } 
            leastMax = raceTo - currentValue ;
            i--;
            continue;
        }
        return pickTheNumber(i);
    }
    return pickTheNumber(pool.size()-1);
}

Update
After seeing h.j.k's great answer to flatten the if statements I tried to expand on it.

h.j.k's result

private int pickANumber() {
    int leastMax = -1;
    for (int i = pool.size() - 1; i >= 0; i--) { // note: removed 'len' variable
        int currentValue = pool.get(i).intValue();
        if (currentValue >= raceTo || leastMax > 0 || i == 0
                || currentValue + pool.get(i - 1).intValue() < raceTo) {
            if (leastMax > 0 && currentValue >= leastMax) {
                continue;
            }
            return pickTheNumber(i);
        } else if (currentValue + pool.get(i - 1).intValue() >= raceTo) {
            leastMax = raceTo - currentValue;
            i--;
        }
    }
    return pickTheNumber(pool.size() - 1);
}

But it hasn't been suitable enough to get rid of the deepest if statment

            if (leastMax > 0 && currentValue >= leastMax) {
                continue;
            }

If you are interrested check the history.

But now just let us start here

if(leastMax > 0){
    if(currentValue < leastMax){
        return pickTheNumber(i);
    }
    continue;
}

Based on the fact that currentValue >= 1 for each item of pool, we can skip the check for lestMax > 0.
Because if leastMax <= 0 the condition currentValue < leastMax would never be true. So if we revert the condition which reaches the continue (leastMax > 0 && currentValue >= leastMax) to currentValue < leastMax

This will change the top most if condition to

if (currentValue >= raceTo
      || (currentValue < leastMax) {

    return pickTheNumber(i);
}  

No let us see, when the continue would be reached as we need avoid this

if(leastMax > 0){
    if(currentValue < leastMax){
        return pickTheNumber(i);
    }
    continue;
}  

as we see only if leastMax > 0 && currentValue >= leastMax

if (leastMax > 0 && currentValue >= leastMax){ continue; }

to prevent leaking the continue into the if part we will add a new condition

if (currentValue >= raceTo
      || (currentValue < leastMax) 
      || leastMax <= 0 {

    return pickTheNumber(i);
} 

the next condition to check is

   if(i - 1 >= 0) {
        if(currentValue + pool.get (i -1) < raceTo){
            return pickTheNumber(i);
        } 
        leastMax = raceTo - currentValue ;
        i--;
        continue;
    }  

we see our next condition to integrate:

if (i - 1 >= 0) which is equal to i > 0 and also currentValue + pool.get (i -1) < raceTo is true we need to pick a number.

if (currentValue >= raceTo
      || (currentValue < leastMax) 
      || (leastMax <= 0 
            && i > 0 
            && currentValue + pool.get (i -1) < raceTo){

    return pickTheNumber(i);
}

the else or better else if part is easy

 else if (leastMax <= 0 && i > 0) {
    leastMax = raceTo - currentValue;
    i--;
}  

the complete method

int pickANumber() {
    int currentValue;
    int leastMax = -1;
    int len = pool.size();
    for (int i = len - 1; i >= 0; i--) {
        currentValue = pool.get(i);

        if (currentValue >= raceTo
                || (currentValue < leastMax)
                || (leastMax <= 0
                    && (i > 0) 
                    && (currentValue + pool.get(i - 1)) < raceTo)) {

            return pickTheNumber(i);

        } else if (leastMax <= 0 && i > 0) {
            leastMax = raceTo - currentValue;
            i--;
        }
    }
    return pickTheNumber(pool.size() - 1);
}
\$\endgroup\$
  • \$\begingroup\$ int pickedValue = pool.get(poolIndex); pool.remove(poolIndex); this can be combined into the final statement, as the return value of remove is the get value. \$\endgroup\$ – h.j.k. Oct 1 '14 at 15:04
  • 1
    \$\begingroup\$ @h.j.k., Thanks. I didn't check this, as I have tested it in C# ;-) Updated my answer. \$\endgroup\$ – Heslacher Oct 1 '14 at 15:07
  • \$\begingroup\$ I wonder if the multiple if statements could be flattened. I haven't taken a close look at this part of the code to determine if there'll be any negative side effects from doing so. \$\endgroup\$ – wei2912 Oct 1 '14 at 15:43
  • \$\begingroup\$ @wei2912, I tried it 5 minutes ago and saw :-( . You can check the history. \$\endgroup\$ – Heslacher Oct 1 '14 at 15:45
  • \$\begingroup\$ @Heslacher Very much appreciate your time. I should have seen it coming - the beast/messy if/else conditions in my code. +1 \$\endgroup\$ – CCP Oct 1 '14 at 19:28
2
\$\begingroup\$

I'm going to build upon the two answers provided by @wei2912 and @Heslacher and attempt to flatten the if statements.

Let's assume we have the method pickTheNumber in @Heslacher's answer. Looking at the somewhat simplified logic:

    if(currentValue >= raceTo){
        return pickTheNumber(i); 
    }
    if(leastMax > 0){
        if(currentValue < leastMax){
            return pickTheNumber(i);
        }
        continue;
    }   
   if(i-1 >= 0) {
        if(currentValue + pool.get(i-1) < raceTo){
            return pickTheNumber(i);
        } 
        leastMax = raceTo - currentValue;
        i--;
        continue;
    }
    return pickTheNumber(i);

We can identify the four cases where we return pickTheNumber(i):

  1. currentValue >= raceTo
  2. leastMax > 0 && currentValue < leastMax^
  3. currentValue + pool.get(i - 1) < raceTo
  4. The final return

First, the final return pickTheNumber(i) is only reached when ! (i - 1 >= 0), i.e. ! (i >= 1), i.e. i = 0.

This roughly allows us to chain the four comparisons as such (note that I am also calling intValue to get around the autoboxing):

if (currentValue >= raceTo || leastMax > 0 || i == 0
        || currentValue + pool.get(i - 1).intValue() < raceTo) { ... }

Now, I put a (^) on the second condition, and you see that we only compare leastMax > 0 above. That is because according to your logic, we will continue on our loop when leastMax > 0 && ! (currentValue < leastMax), and this will bypass the comparison of the two largest numbers with raceTo too. As such, our first statement inside the 'super' if statement will be the condition to continue (note how I turn the meaning of 'not lesser' as 'greater than or equals'):

if (leastMax > 0 && currentValue >= leastMax) {
    continue;
}

Now, by right, we need to negate our first condition to make sure we only continue when it is the second condition that has been satisfied. However, if you look at the computation of leastMax, it is always positive when remaining > current, which so happens (?) to be the negation of the first condition. In other words, when the second condition is true, we already know that the first condition must be false. Explicit negation of the first condition is thus unnecessary.

The second and final statement is just to return pickTheNumber(i).

If we are not return-ing pickTheNumber(i), then that means we should check whether we need to perform the following two steps:

leastMax = raceTo - currentValue;
i--;

This will go into its own else if. The final pickANumber() method in full:

private int pickANumber() {
    int leastMax = -1;
    for (int i = pool.size() - 1; i >= 0; i--) { // note: removed 'len' variable
        int currentValue = pool.get(i).intValue();
        if (currentValue >= raceTo || leastMax > 0 || i == 0
                || currentValue + pool.get(i - 1).intValue() < raceTo) {
            if (leastMax > 0 && currentValue >= leastMax) {
                continue;
            }
            return pickTheNumber(i);
        } else if (currentValue + pool.get(i - 1).intValue() >= raceTo) {
            leastMax = raceTo - currentValue;
            i--;
        }
    }
    return pickTheNumber(pool.size() - 1);
}
\$\endgroup\$
  • \$\begingroup\$ +1 Great answer. I have expanded yours to get rid of the last if statement. \$\endgroup\$ – Heslacher Oct 2 '14 at 8:10
  • \$\begingroup\$ @Heslacher I tried to run your solution by using only currentValue < leastMax but the steps taken for the question is different... :-| This also riddled me for quite a while yesterday, before I ended with my solution. Either the more flattened form is actually the more ideal implementation (yay), or there's something we missed... \$\endgroup\$ – h.j.k. Oct 2 '14 at 14:51
  • \$\begingroup\$ I have checked it and refactored it. Now it does what it is suposed to do ;-) \$\endgroup\$ – Heslacher Oct 2 '14 at 22:27
  • \$\begingroup\$ @Heslacher now I wish I can give you +2 for your answer. :) \$\endgroup\$ – h.j.k. Oct 3 '14 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.