292.Nim Game

Tags: [math], [trick], [regulation], [optimal_strategy], [game], [dp], [brute_force]

Link: https://leetcode.com/problems/nim-game/\#/description

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Hint:

1. If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

Solution: Math, Trick, Regulation

class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n % 4 != 0

Revelation:

• If n <= 3, you must can win.
• If n = 4, you must lose.
• If 4 < n < 8, n = 5, 6, 7, after your turn, you must can make n = 4, so now your friend is facing n = 4, he must lose.
• If n = 8, you only can make n to 7, 6, 5, now your friend is facing n = 5, 6, or 7, he must can win.
• If 8 < n < 12, such as n = 9, 10, 11, you must can make n = 8, now your friend is facing n = 8, he must lose.
• ... Now we find the regulation, if n % 4 == 0, you must lost, your friend must win, but if n % 4 != 0, you must can win.

Note:

• Time complexity = O(1).

Time Limited Exceed: DP:

class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 3:
            return True

        f = [False for _ in xrange(n + 1)]
        f[1] = True
        f[2] = True
        f[3] = True

        for num in xrange(4, n + 1):
            this_turn_can_win = False
            for k in xrange(1, 4):
                if not f[num - k]:
                    this_turn_can_win = True
                    break

            f[num] = this_turn_can_win

        return f[n]

Revelation:

• f[num] means, if n = num, you can win or not.
• You can do num - 1, num - 2, num - 3, so we just try all these three ways, and given the remaining of the num to your friend, and try to find one scenario, your friend cannot win when he is facing this remaining num, if we find this scenario, then f[num] = True, otherwise f[num] = False. Finally return f[n].

Note:

• Time complexity = O(k * n), because k = 1, 2, or 3, so time complexity = O(n).

Time Limited Exceeded: Brute Force (recursion)

class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        # base case.
        if n <= 3:
            return True

        for k in xrange(1, 4):
            if not self.canWinNim(n - k):
                return True

        return False

Revelation:

• The function canWinNim(n) stands for that the current player tries his best to play the game, then he will win or not.
• At each your turn, try all possible ways: n - 1, n - 2, n - 3, then give these remaining n to your friend, and at your turn try to find does there exist the scenario your friend tries his best, but still lose. If you find this scenario, then return True directly. If after all trying, you still cannot find a scenario your friend have to lose, just return False, means you must lose the game.

Note:

• Time complexity = O(3^n).