can_i_win.py

'''
In the "100 game" two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.

Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.

 
 '''
 
class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        remainder = [i+1 for i in range(maxChoosableInteger)] # numbers
        @cache
        def can_win(total, remainder):
            if total >= desiredTotal:
                return False # total is already exceed the desiredTotal. Opponent won. 
            
            for num in remainder:
                if can_win(total + num, tuple([n for n in remainder if n != num])) == False: # if opponent lose, I win(return True)
                    return True
            return False 
        
        if desiredTotal == 0: 
            return True 
        if sum(remainder) < desiredTotal: # Both of two cannot win.
            return False 
        return can_win(0, tuple(remainder))