HackerRank: Stone Piles

https://www.hackerrank.com/challenges/stone-piles/problem

There are N piles of stones where the ith pile has xi stones in it. Alice and Bob play the following game:

1. Alice starts, and they alternate turns.
2. In a turn, a player can choose any one of the piles of stones and divide the stones in it into any number of unequal piles such that no two of the newly created piles have the same number of stones. For example, if there 8 stones in a pile, it can be divided into one of these set of piles:{1, 2, 5}, {1, 3, 4}, {1, 7}, {2, 6} or {3, 5}.
3. The player who cannot make a move (because all the remaining piles are indivisible) loses the game.

Given the starting set of piles, who wins the game assuming both players play optimally (that means they will not make a move that causes them to lose the game if some better, winning move exists)?

Constraints

1<= N <= 50;
1<= xi <= 50;

Notes:

If you never hear about Sprague-Grundy Theorem, this question seems very complicated.

(It seems not easy to cover this in a single blog, so I would recommend to google the above theory before reading the following, ...)

Let look at some simple cases:

if there is only 1 pile of stones.

if the number of stone is 1 or 2, the previous player wins. So this kind of state is called as P-position, relative to the current player.

if the number is 3. Then the current player can divide it into 1 & 2. And the next player cannot make any more move based on the rule. So the current player win. And this kind of stat is called as N-position.

if the number is 4: then the current player can only choose to divide it into 1 & 3. And the second player can continue to divide 3 into 1 and 2. Then the first player has no way to go. So the previous (or the second) player win, and 4 is called as a P-position.

Then how about 5?

The current can either split it into 1 and 4, or 2 and 3. If the current player chooses the first one, then he/she will win. So it can be defined as a N-position. However,  if the current player chooses 2 and 3, he/she will loose...

If there is only one pile, the the current player will definitely choose the first way in order to win, but how about there are more than piles?

This question has been investigated in details, so I just list the results below without proof (since it is not easy to proof..., maybe I will spend some time later on this.)

There are two steps:

1): we need to find the equivalent Grundy number for each pile of stone;

2): we need to consider the binary forms of the Grundy number of each pile.

For each binary digit position, we need to count the total number of "1". If there is at least one position with odd number of "1"s, then the current player will win; otherwise, it is a P-position, and the the current player cannot win. And this can be done easily using "XOR" bitwise operation.

See the code below:

class Solution {
public:
    string Nim(vector<int>& stones) {
        int res = 0;
        for(auto &a : stones) res ^= go(a);//SG Theorem
        return res? "ALICE" : "BOB";
    }
private:
    int calGruNum(int val) {//calculate Grundy Numbers
        //val > 0
        if(val < 3 || val == 4 || val == 8) return 0;
        if(val == 3) return 1;
        if(val < 8) return val - 3;
        return val - 4;
    }
};