Nimble Game

Two people are playing Nimble.

The rules of the game are:

▶ The game is played on a line of  squares, indexed from 0 to n-1. Each square contains zero or more coins. 

For example : 

       

▶ First player start the game.

▶ The players move in alternating turns. During each move, the current player must remove exactly 1 coin from right square to left square until 0th square.

▶ The game ends when all coins are in 0th square and nobody can make a move. 

Solution: 

This game is exactly a Nim Game where one coin in k-th square is a pile of k stones. Moving a coin from k-th square to its left is equivalent to removing stones from a pile of k stones in Nim Game.

If the cell contains even number of stones then we should ignore those cells in our calculations. Because they would have no effect on the result, every move can be repeated by the opposite player. In our case the move started by First player will be repeated by Second player. Eventually First user looses. Cells that contains odd numbers have an impact to the result of the game. If we filter out the cells with odd numbered stones, then we can start converting this game to basic Nim game. If we convert then the cell index (position) becomes a number of stones in the basic Nim game. Then just apply nim game solution, which is XOR ing all values and if 0 then Second player wins, otherwise First player.

Coding Part:

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int n;

    cout << "Enter Square Number in a Box:: ";

    cin >> n;

    int a[n], xor_sum = 0;

    cout << "Enter Each Square Coin Number :: ";

    for(int i=0; i<n; i++)

    {

        cin >> a[i];

        if(a[i]%2 == 1)

            xor_sum ^= i;

    }

    if(xor_sum > 0)

        cout << "First Player Win." << "\n";

    else

        cout << "Second Player Win." << "\n";

    return 0;

}