AC Python solution Sprague–Grundy + memoization, 40 ms


  • 2

    The problem is a Impartial game. In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nim heap of a certain size. The size is called a nimber.

    Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap.

    For details about the theorem and nimber see @stellari's post or https://en.wikipedia.org/wiki/Nimber.

    The problem then become calculate the nimber of the given 'board' and return if it is equal to zero, for any non zero nimber, player 1 wins.

    Since we will recursivly call the function nimber through out the test cases, we can use a static cache to do memoization in order to save time. If every nimber required is already known for string s then the time is just O(n) where n is the length of the string. Calculate nimber(n) from scratch is O(n^2).

    import re
    memo = [0, 0]
    
    def nimber(self, n):
        size = len(self.memo)
        if n < size:
            return self.memo[n]
        if n > size:
            self.nimber(n - 1)
        ordinals = {self.memo[i] ^ self.memo[n - 2 - i] for i in xrange(n / 2)}
        ans = 0
        while ans in ordinals:
            ans += 1
        self.memo.append(ans)
        return ans
    
    def canWin(self, s):
        ans = 0
        for n in map(len, re.split('-+', s)):
            ans ^= self.nimber(n)
        return ans != 0
    
    
    # 33 / 33 test cases passed.
    # Status: Accepted
    # Runtime: 40 ms
    

  • 0

    I just noticed that the nimbers are almost periodic, making it easy to turn this into an O(n) solution.


  • 0

    i printed out first 100 nimbers, tried to get this period yesterday, failed to find it... Turns out the period emerge after 100......it make sense that the larger nimber is periodic.


  • 0

    OK, here comes the "cheat" version using the nimber sequence......

    import re
    nimbers = [0, 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 0, 5, 2, 2, 3, 3, 0, 1, 1, 3,
               0, 2, 1, 1, 0, 4, 5, 2, 7, 4, 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4,
               5, 5, 2, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 3, 7, 4, 8, 1, 1, 2, 0, 3,
               1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 9]
    period = 34
    offset = 53
    
    def nimber(self, n):
        if n >= self.offset:
            n = self.offset + (n - self.offset) % self.period
        return self.nimbers[n]
    
    def canWin(self, s):
        ans = 0
        for n in map(len, re.split('-+', s)):
            ans ^= self.nimber(n)
        return ans != 0
    
    
    # 33 / 33 test cases passed.
    # Status: Accepted
    # Runtime: 36 ms
    # Using periodic nimber sequence
    

Log in to reply
 

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