[Community Puzzle] 2-player game on a calculator

Puzzles
#1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

#2

I am trying to solve this puzzle (in PHP):

In case I misunderstood the task:

  • I output every starting number, that when fully played out, the oppenent always looses.

My code works but it is too slow for the last test. I have already tried a lot of tweaks, but it still fails. Looks like I am really missing out some “shortcut”…

This is the part of the code that does most of the work:

function play ($number, $N, $level) {
    ++$level;
    $N -= $number;
    if ($N < 0 || in_array($N, NEXT_MOVES[$number])) {
        return false;
    }
    if ($N == 0 || min(NEXT_MOVES[$number]) > $N) {
        return true;
    }
    foreach (NEXT_MOVES[$number] as $nextMove) {
        if ($nextMove > $N) continue;
        if (play($nextMove, $N, $level)) return false;
    }
    return true;
}

I play the numbers in descreasing order (highest possible first). As soon as one side “wins”, I go back one “level” and try the next number. The $level variable is there for debugging purposes only.

#3

I changed it all up and replaced the function for 2 additional loops. that “worked”, but it’s not as pretty as this solution was :wink: but I learned something new about how to really increase the speed :+1:

#4

I don’t understand what makes a winning starting move…I can always find a path to a win based on the starting number and subsequent moves therefore I must not understand something. For instance in test case 2, N = 9 and the winning numbers are 1,7,8,9.

However if I pick 2, N = 7 and player two has options 1, 3, 4, 5 or 6.
–if he picks 6 I lose because N = 1 and my options are 2,3,5,8,9 all would make N negative
–if he picks 5 I win because N = 2 and my only non negative options are 1 or 2 which make him lose
–if he picks 4 I lose
–if he picks 3 I lose
–if he picks 1 we go another round with N =6 and my options are 2, 3, 5 (8,9) are losers
----I pick 5 I lose because N = 1 and he picks 1
----I pick 3 I win
----I pick 2 we go another round with 2 more outcomes 1 win each.

Based on the above I would conclude that 2 is a winner when starting at 9 can someone explain what I am missing?

1 Like
#5

In game theory we say something is a “winning move” for player 1 if for all subsequent moves by player 2, player 1 will still always win.

Therefore for N = 9, 2 is not a winning move. You said “If [player 2] picks 6 I lose”. Therefore the initial move of 2 does not guarantee a win for player 1.

However, for N = 9, 1 is an example of a winning move. Here player 2 has 3 options which are 4, 5 or 2.
1 > 4 > 1 > 2 > 1 Player 1 wins
1 > 5 > 3 Player 1 wins
1 > 2 > 6 Player 1 wins
Notice how there are no choices player 2 can make which makes player 1 lose.

2 Likes
#6

Thank you. That makes this puzzle much easier to understand.