0
\$\begingroup\$

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:

  1. The game is played with two piles of matches. Initially, the first pile contains N matches and the second one contains M matches.

  2. The players alternate turns; Ari plays first.

  3. 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.

  4. It is only allowed to remove X matches from a pile if the number of matches in the other pile divides X.

  5. The player that takes the last match from any pile wins.

Solve(N,M)

  1. If its Ari's turn and N%M==0 then Ari wins else Rich wins.
  2. 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
\$\endgroup\$
  • \$\begingroup\$ Can you give an example input for which it takes too long? \$\endgroup\$ – Peter Taylor May 9 at 14:26
  • \$\begingroup\$ @PeterTaylor the test cases are not visible.But the range of X and Y is 1 to 10^18 \$\endgroup\$ – ADITYA JOSHI May 9 at 14:50
  • \$\begingroup\$ Rolled back major code edit. See meta on what you can do after you receive an answer. \$\endgroup\$ – Peter Taylor May 9 at 16:44
0
\$\begingroup\$

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 >= 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.

\$\endgroup\$
  • \$\begingroup\$ Player denote turn of player. If Player=True then its Ari's turn else Rich \$\endgroup\$ – ADITYA JOSHI May 9 at 15:12
  • \$\begingroup\$ I stand by my observation that it's not clear. ari_moves_next would be clearer, although then the function should be called something like ari_wins. \$\endgroup\$ – Peter Taylor May 9 at 15:25
  • \$\begingroup\$ I have changed my code to more readable form \$\endgroup\$ – ADITYA JOSHI May 9 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.