CodeChef Matches challenge I am solving some problems from CodeChef but I am stuck on the Matches problem:


  Ari and Rich are playing a pretty confusing game. Here are the rules
  of the game:
  
  
  The game is played with two piles of matches. Initially, the first pile contains N matches and the second one contains M matches.
  The players alternate turns; Ari plays first.
  On each turn, the current player must choose one pile and remove a positive number of matches (not exceeding the current number of
  matches on that pile) from it.
  It is only allowed to remove X matches from a pile if the number of matches in the other pile divides X.
  The player that takes the last match from any pile wins.
  
  
  Solve(N,M)
  
  
  If its Ari's turn and N%M==0 then Ari wins else Rich wins.
  If N%M!=0 then player try every possible moves and check if he wins any one of them in end.
  


My solution uses Dynamic Programmming, so I have used functools.lru_cache to save function results. But I am getting TLE error in some test cases.How can I further optimize the code?

from functools import lru_cache 

@lru_cache(maxsize=None)
def Solve(X,Y,Player=True):
    if X%Y==0:
        return Player
    else:
        temp=X
        X=X%Y
        if Player==Solve(max(X,Y),min(X,Y),not Player):
            return Player
        while temp!=X+Y:
            X=X+Y
            if Player==Solve(max(X,Y),min(X,Y),not Player):
                return Player
        return not Player
The whitespace needs a lot of changes to be PEP8-compliant. The capitalisation is also unconventional: functions and variables in Python usually start with a lower-case letter.



The meaning of Player is not entirely clear, and the logic is hard to follow because of that. The convention for this type of combinatorial game is to denote a position as "N" (Next player wins) or "P" (Previous player wins). So I think that Solve should be renamed position_is_N, and then the Player variable becomes unnecessary.

if condition: return doesn't need a following else:.

The loop can be tidied up considerably with range and any. I think this is equivalent:

@lru_cache(maxsize=None)
def position_is_N(x, y):
    return x % y == 0 or \
           any(not position_is_N(max(x2, y), min(x2, y))
               for x2 in range(x % y, x, y))


A comment about the constraint that x &gt;= y would be nice.




  range of both X and Y is 1 to 10^18


Consider inputs 10**18, 3 (or other similarly small y). How many times might the loop run in the worst case?

As a rule of thumb, for a challenge like this if you need to do anything more than 10**9 times your algorithm is wrong. I can only suggest that you will need a complete rewrite to pass the time limit, so you should build a table of small values and see whether you can spot and prove a pattern. The problem is probably far more about mathematics than programming.