C# - Solve Nim


The interesting puzzle was presented to me by HackerRank today. Just an atypical Game Theory algorithm located here. I don't know if it's I am just not feeling too hot, being temporarily unemployed, or just lack of experience, but I was actually stumped by the problem. A lot of developers are stumped everyday and it's even harder if you don't cut yourself a break. One thing that really gets to me, is knowing that there is a 13 year old Russian script kiddy out there that speaks 3 languages, programs in every language, plays piano, and writes better code than me. In fact, he writes better code now than I will even after a life time of practice.

So what? As I have gotten older than sting hurts less. The sting of inferiority. There is this notion that we must strive to be the best at literally everything - an irrational conclusion made by a supposedly analytical brain. It is a goal worth striving for, to hone ones self. However, if you focus only on that premise, the goal, the destination, you won't see that it's the journey which mattered. Not how good you are.

With that being said, I introduce you to the solution that I taught myself by research and code comparisons from other languages. I took what others did and I created a solution in my language. I learned something, I don't feel ashamed plucking code from others, and neither should you!

using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
    static void Main(String[] args)
    {
        int n = Convert.ToInt32(Console.ReadLine());
        string[] arr_temp = Console.ReadLine().Split(' ');
        int[] a = Array.ConvertAll(arr_temp,Int32.Parse);
        
        var nimSum = 0;
        for(int i = 0; i < n; i++) { nimSum ^= a[i]; }
        
        var sets = 0;
        if (nimSum > 0)
        {
            for(int i = 0; i < n; i++) { if((a[i]^nimSum) < a[i]) {sets++;} }    
        }
        
        Console.WriteLine(sets);
    }
}

The only two important parts are here:

        
        var nimSum = 0;
        for(int i = 0; i < n; i++) { nimSum ^= a[i]; }
        

And Here:

        
        var sets = 0;
        if (nimSum > 0)
        {
            for(int i = 0; i < n; i++) { if((a[i]^nimSum) < a[i]) {sets++;} }
        }
        

The Nim Sum

The first part is the calculation of Nim-Sum using bitwise XOR operator. There are more bitwise operations that can be learned here. Why do we calculate NimSum? Basically, Wikipedia told me to do it. The game operates in N heaps, with A[i] elements in each Heap. If I have N choices to remove x items from, how many different ways can the person who goes first win. By calculating the NimSum, we know the exact number to take for the optimum win scenario.

The Sets

Now that we know the NimSum, we now simply need to know how many containers in A such that NimSum XOR A[i] is < A[i]. This tells us we can take the NimSum from unique columns. Which means, that a unique starting point is a unique path to victory. The output here is the total sets of moves you can make, based on the optimum valued NimSum and guarantee victory.

Alternative Solutions

Involve recursion or nodes. Due to the Unit Testing restrictions on HackerRank which test fringe and exceptional cases, most of these recursion based methods fail. The restrictions are there to encourage you to find better performing solutions, not just any old solution. That means nine times out of ten its a number theory.