# AC Python solution Sprague–Grundy + memoization, 40 ms

• 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
``````

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

• 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.

• 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
``````

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