Nim game

Sharktooth looses first round, enraged he poses a trickier version of the game consisting of multiple Boxes filled with apples , rules remain the same, pick a box and eat 2 or 3 apples, what should Tintin do now?

Sprague Grundy Theorem:

Calculating the grundy number of a single Box was trivial, but what if there are multiple Boxes, we need to calculate the grundy number of the whole game state not just single Box.

  • Grundy number of a game state = XOR sum of the grundy numbers of all the individual piles
  • Everytime Tintin is eating apples from a particular box, make sure after eating a particular amount of apples XOR sum of all the grundy numbers of each Box is 0, which will render sharktooth in a loosing state
  • If the initial state has a XOR sum of 0, Tintin should not go first since it's a loosing state

here's an implementation of the idea

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define FAST_CODE ios_base::sync_with_stdio(false); cin.tie(NULL);

constexpr ll MOD = 1000000007;

//to calculate Mex
ll Mex(unordered_set<ll>&S)
{
	ll Mex = 0;
	
	while (S.find (Mex) != S.end())
		Mex++;
	
	return (Mex);
}

//bottom up approach dp function to calculate grundy numbers
void nimber(ll n, vector<ll>&Grundy)
{

	Grundy[0] = 0;
	Grundy[1] = 0;

	for(ll i=2; i<=n; ++i)
	{
		unordered_set<ll> S;
		for(int j=2; j<=3; j++)
		{
			S.insert(Grundy[i-j]);	
		}

		Grundy[i] = Mex(S);
	}
}


ll Winner(ll Play, vector<ll>&Apples, vector<ll>&Grundy, ll n)
{
    ll xorSum = Grundy[Apples[0]];
 
    for (ll i=1; i<=n-1; i++)
        xorSum ^= Grundy[Apples[i]];
 
    if (xorSum!= 0)
    {
        if (Play == 1)
            return 1;
        else
            return 2;
    }
    else
    {
        if (Play == 1)
            return 2;
        else
            return 1;
    }
}
int main()
{
	FAST_CODE
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r", stdin);
		freopen("output.txt","w", stdout);
	#endif

	ll nums; // number of Apples
	cin>>nums;

	vector<ll>Apples(nums, 0); // values in each Box

	ll maxi = 0;
	for(int i=0; i<nums; ++i)
	{
		cin>>Apples[i];
		maxi = max(Apples[i], maxi);
	}

	vector<ll>Grundy(maxi+1, -1);

	nimber(maxi, Grundy);
	

	if(Winner(1, Apples, Grundy, nums) == 1) cout<<"Tintin"<<"\n";
	else cout<<"Sharktooth"<<"\n";

	for(ll g:Grundy)
	{
		cout<<g<<" ";
	}
	return 0;
	
}

 

So for boxes with apples 3, 8, 2 Tintin should go first, but for 3 8 1 Tintin shouldn't go first

Discussion

Be the first one to comment!