CODEWITHSUNDEEP
pythonbit-manipulation
Rik
Rik

Reputation: 1987

Using bitwise storage of bools in a DP problem

I working on this leetcode and I was wondering how to use bitwise manipulation. The reason being, when I use lru_cache I get the error that isUsed is not hashable. Instead of a bool array for isUsed, what is the best practice to use an int and bitwise operations instead of a bool 

def canIWin(self, n: int, target: int) -> bool:
    @lru_cache(None)
    def isWin(isUsed, target):
        # print(isUsed,target)
        if target<=0:
            return False
        for i in reversed(range(1,n+1)):
            if not isUsed[i-1]:
                if i>=target:
                    return True
                isUsed[i-1] = True
                if not isWin(isUsed[::], target-i):
                    return True
                isUsed[i-1] = False

        return False

    if target <2:
        return True
    if n*(n+1)/2<target:
        return False
    return isWin([False]*n,target)

Upvotes: 2

Views: 42

Answers (2)

Rik
Rik

Reputation: 1987

You can either use tuple or use a bitset. The easiest way to use a tuple is to convert it to an array and convert it back, however it is faster slice the array of values and pass that rather than pass an array of booleans.

Here are the three methods:

  1. Tuple Slice no boolean array (388 ms) This is the fastest because you can exit early by checking the last item
  2. Use bitset (532 ms)
  3. Converting from list to tuple (624 ms)

Tuple Slice:

def canIWin(self, n: int, target: int) -> bool:
    @lru_cache(None)
    def isWin(nums, target):
        if target <= 0:
            return False
        n = len(nums)
        if nums[-1] >= target:
            return True
        for i in range(n):
            if not isWin(nums[:i] + nums[i + 1:], target - nums[i]):
                return True
        return False
    if target < 2:
        return True
    if (n + 1) * n / 2 < target:
        return False
    return isWin(tuple(range(1, n + 1)), target)

Bitset:

def canIWin(self, n: int, target: int) -> bool:
    isNthBitSet = lambda x, n: (x & (1 << n) != 0)
    setNthBit = lambda x, n: x | (1 << n)
    @lru_cache(None)
    def isWin(isUsed, target):
        if target <= 0:
            return False
        for i in reversed(range(n)):
            if not isNthBitSet(isUsed, i):
                if not isWin(setNthBit(isUsed, i), target - i - 1):
                return True
    return False
if target < 2:
    return True
if n * (n + 1) / 2 < target:
    return False
return isWin(0, target)

List to Tuple:

def canIWin(self, n: int, target: int) -> bool:
    @lru_cache(None)
    def isWin(isUsed, target):
        isUsed = list(isUsed)
        if target <= 0:
            return False
        for i in reversed(range(1, n + 1)):
            if not isUsed[i - 1]:
                if i >= target:
                    return True
                isUsed[i - 1] = True
                if not isWin(tuple(isUsed[::]), target - i):
                    return True
                isUsed[i - 1] = False
        return False
    if target < 2:
        return True
    if n * (n + 1) / 2 < target:
        return False
    return isWin(tuple([False] * n), target)

Upvotes: 0

L3viathan
L3viathan

Reputation: 27333

As kaya3 mentioned in their comment, instead of using an integer bitset, you can just use a tuple instead of a list, since they are immutable and hashable. Setting a bit in a tuple is a bit more complicated, so it's probably easier to convert the tuple into a list once you're inside the function.

If you really want to use a bitset, you have to do some ANDing, ORing, and XORing with powers of 2:

Setting a bit at index i in a bitset of length n:

bitset = bitset | 2**(n-1-i)

Resetting a bit:

bitset = bitset & (2**n-1) ^ 2**(n-1-i)

Upvotes: 1

Related Questions