Solution too slow for "2-player game on a calculator" (PHP)

Puzzles
#1

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.

#2

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: