Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

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.

For the value N = 35

if the first player starts by choosing 1

The best selection for the first player to win is 1 2 3 5 7 8 9 (at the end N = 0)

While the second player can also win if the choice is following this sequence 1 4 7 8 9 6 (at the end N = 0)

So the best sequence is the second one (1 4 7 8 9 6). As a result, the second player wins

What is the criterion for choosing the best sequence?

It wouldnâ€™t hurt if this definition of a winning move would be included in the statement of this puzzle.