464 Can I Win

Can I Win

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.

 

Example 1:

**Input:** maxChoosableInteger = 10, desiredTotal = 11
**Output:** false
**Explanation:**
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

Example 2:

**Input:** maxChoosableInteger = 10, desiredTotal = 0
**Output:** true

Example 3:

**Input:** maxChoosableInteger = 10, desiredTotal = 1
**Output:** true

 

Constraints:

1 <= maxChoosableInteger <= 20
0 <= desiredTotal <= 300

class Solution:
    
    def __init__(self):
        from sortedcontainers import SortedSet
        self.dict1 = []
        self.cache = {}

    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        self.dict1 = ["0"]* (maxChoosableInteger+1)
        self.dict1[0] = "1"
        if (maxChoosableInteger * (maxChoosableInteger + 1)) // 2 < desiredTotal:
            return False
        if desiredTotal <= 0:
            return True
        return self.MoveByA(maxChoosableInteger, desiredTotal)

    def MoveByA(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        key = f"{desiredTotal}#{','.join(self.dict1)}"

        if key in self.cache:
            return self.cache[key]
        if desiredTotal <= 0:
            return False # B won

        if "0" not in self.dict1:
            print("should never occur")
            return False

        for k in range(1, maxChoosableInteger+1):
            if self.dict1[k] == "0":
                self.dict1[k] = "1"
                key1 = f"{desiredTotal}#{','.join(self.dict1)}"
                if not self.MoveByB(maxChoosableInteger, desiredTotal-k):
                    self.cache[key1] = False
                    self.dict1[k] = "0"
                    self.cache[key] = True
                    return True
                self.cache[key1] = True
                self.dict1[k] = "0"
                
        self.cache[key] = False
        return False

    def MoveByB(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        key = f"{desiredTotal}#{','.join(self.dict1)}"
        if key in self.cache:
            return self.cache[key]

        if desiredTotal <= 0:
            return False # A won

        if "0" not in self.dict1:
            print("should never occur")
            return False

        for k in range(1, maxChoosableInteger+1):
            if self.dict1[k] == "0":
                self.dict1[k] = "1"
                key1 = f"{desiredTotal}#{','.join(self.dict1)}"
                if not self.MoveByA(maxChoosableInteger, desiredTotal-k):
                    self.cache[key1] = False
                    self.dict1[k] = "0"
                    self.cache[key] = True
                    return True
                self.cache[key1] = True
                self.dict1[k] = "0"
                
        self.cache[key] = False
        return False