Python MiniMax Bitwise Simple

  • 1

    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.