# [Community Puzzle] 2-player game on a calculator

Coding Games and Programming Challenges to Code Better

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.

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 but I learned something new about how to really increase the speed

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

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

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