Python MiniMax Bitwise Simple


  • 1
    A

    Python solution based on MiniMax Strategy. Dic represents whether each state is a Win state or not. If any of the children states are a loose state then the parent state becomes a Win state.
    The variable "choices" is the bitwise representation of the choices available. The worst case time complexity should be O(N!) but some pruning has been done to speed up things when possible.

    def canIWin(self, maxChoosableInteger, desiredTotal):
        if desiredTotal==0: return True
        if maxChoosableInteger*(maxChoosableInteger+1)/2 < desiredTotal:return False
            
        choices,temp = 0,0
        while temp < maxChoosableInteger:
            choices |= (1<<temp)
            temp +=1
        
        dic ={}
        def solve(choice, total):
            if (choice,total) in dic: return dic[ (choice,total) ]
            if total <= 0: return False
            tempChoice,childAns = choice, True
            for i in xrange( maxChoosableInteger ):
                if tempChoice & 1:
                    childAns = childAns and solve( choice ^ (1<<i), total-i-1)
                tempChoice >>=1
                if not tempChoice or not childAns: break
            
            dic[ (choice,total) ] = not childAns
            return not childAns
        
        return solve( choices, desiredTotal)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.