[LeetCode] 1275. Find Winner on a Tic Tac Toe Game

 Problem : https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game/

Keep tracking counters of the 3 rows / columns and the 2 diagonals.

Increase counter by 1 if it is player 'A' otherwise decrease counter by 1 for player 'B'.

Player 'A' wins if any counter equals to 3. Player 'B' wins if any counter equals to -3.

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        rows = [0] * 3
        cols = [0] * 3
        
        diag1 = 0
        diag2 = 0
        
        for i, (y, x) in enumerate(moves):
            player = 1 if i & 1 == 0 else -1
           
            rows[y] += player
            cols[x] += player

            if y == x:
                diag1 += player

            if y == 2 - x:
                diag2 += player
        
            if rows[y] == 3 or cols[x] == 3 or diag1 == 3 or diag2 == 3:
                return 'A'

            if rows[y] == -3 or cols[x] == -3 or diag1 == -3 or diag2 == -3:
                return 'B'
            
        return 'Draw' if len(moves) >= 9 else 'Pending'

[LeetCode] 464. Can I Win

 Problem : https://leetcode.com/problems/can-i-win/

The state of this game is the integers be used. Because maximal number of integer is no more than 20.  

We can use bitmask to remember the used integers. 

Also use True to represent the first player wins and use False to represent the second player wins.

Time complexity = O( 2 ** N ).   For each integer we consider whether use it or not to form a new state.  There are 2 ** N states. 

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        
        # use bitmask to remember the picked integer
        mask = 0
        
        @cache
        def helper(mask, sums, a):
            for i in range(maxChoosableInteger):
                
                # bypass if the integer (i+1) is already used
                if mask & (1 << i) != 0:
                    continue
                
                # current player wins when sums >= desiredTotal
                if sums + i + 1 >= desiredTotal:
                    return a
                
                # mark integer (i+1) is used
                mask ^= (1 << i)
                
                # because both players play optimally
                # we consider current player must chooses this routine
                # which leads to a win result for hime
                if helper(mask, sums + i + 1, not a) ==  a:
                    
                    # mark integer (i+1) is not used
                    mask ^= (1 << i)
                    
                    # current player can force a win
                    return a
                
                # mark integer (i+1) is not used
                mask ^= (1 << i)
            
            # current player cannot force a win
            return not a
        
        # it is impossible to win whe sum of all integers is less than the desiredTotal
        if maxChoosableInteger * (maxChoosableInteger + 1) // 2 < desiredTotal: return False
        
        return helper(0, 0, True)

[LeetCode] 292. Nim Game

 Problem : https://leetcode.com/problems/nim-game/

Let player A goes first.  When there is 4 stones,  player A will always lose.  Because no matter how many stone player A removes, player B can always remove the reset stones.

Because player A and B play optimally.  Both of they will try to remove stones and left 4 * N stones to its opponent.  So player A always lost, if total number of stones can be dived by 4.

class Solution:
    def canWinNim(self, n: int) -> bool:
        
        return n % 4 != 0