HackerRank - week code 27 - zero move nim - recursive solution - a lots of fun to practice

weekcode27_zeroMoveNim.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace zeroMoveNim
{
    class Program
    {
        static void Main(string[] args)
        {
            // For hackerRank
            RunHackerRank();

            // For my testing 
            // RunSampleTestCases(); 
        }

        private static void RunHackerRank()
        {
            IList<char> results = ProcessZeroMoveGame();
            Output(results);

        }

        private static void Output(IList<char> data)
        {
            foreach (char c in data)
            {
                Console.WriteLine(c);
            }
        }

        private static void RunSampleTestCases()
        {
            // First player 'W',   second player 'L'

            //Debug.Assert( ProcessZerorMoveNimGame(2, new int[] { 2, 2 }) == 'L');     // Second player
            //Debug.Assert( ProcessZerorMoveNimGame(2, new int[] { 1, 2 }) == 'W');     // go to first one
            //Debug.Assert( ProcessZerorMoveNimGame(3, new int[] { 1, 2, 3 }) == 'W');  // go to first  'W'
            //Debug.Assert(ProcessZerorMoveNimGame(3, new int[] { 2, 2, 4 }) == 'W');   // go to first
            Debug.Assert(ProcessZerorMoveNimGame(3, new int[] { 2, 3, 4 }) == 'L');   // go to second
        }

        private static void RunSampleTestCase1()
        {
            int result = PlayZeroMoveNim_FirstPlayerWin(2, new int[] { 2, 2 });
        }

        private static IList<char> ProcessZeroMoveGame()
        {
            IList<char> results = new List<char>();

            int nQueries = Convert.ToInt32(Console.ReadLine());

            for (int i = 0; i < nQueries; i++)
            {
                int nPiles = Convert.ToInt32(Console.ReadLine());
                int[] piles = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

                results.Add(ProcessZerorMoveNimGame_usingNimSum(nPiles, piles));
            }

            return results;
        }


        /*
         * ProcessZerorMoveNimGame_usingNimSum
         * https://en.wikipedia.org/wiki/Nim
         * 
         */
        private static char ProcessZerorMoveNimGame_usingNimSum(int nPiles, int[] piles)
        {
            int nimSum = 0; 

            for(int i = 0; i < piles.Length; i++)
            {
                nimSum = nimSum ^ piles[i]; 
            }

            if (nimSum == 0)
                return 'L';
            else
                return 'W'; 
        }

        private static char ProcessZerorMoveNimGame(int nPiles, int[] piles)
        {
            int result = PlayZeroMoveNim_FirstPlayerWin(nPiles, piles);
            if (result == 10 || result == 11)  // 10 or 11, definitely knowing who is the winner
            {
                return (result == 10) ? 'W' : 'L';
            }

            if (result == 0 || result == 1)  // first player definitely wins 
            {
                return (result == 0) ? 'W' : 'L';
            }
            else
            {
                int secondPlayer = PlayZeroMoveNim_SecondPlayerWin(nPiles, piles);
                if (secondPlayer == 1)
                {
                    return 'L';
                }
            }
            // rest - not sure - goes to first player - gambling
            return 'W';
        }

        /*
         * First player defintely wins
         * 1, 2
         * 1, 2, 3
         * 
         */
        private static int PlayZeroMoveNim_FirstPlayerWin(int nPiles, int[] piles)
        {
            // 0 - first player win, 1 - second player win

            Array.Sort(piles);

            bool goOpposite = false;
            Dictionary<int, int> dataCount = CountNumber(piles, ref goOpposite);

            int[] numbers = dataCount.Keys.ToArray();

            int newPiles = numbers.Length;
            if (numbers.Length == 0)
                return (goOpposite) ? 11 : 10;

            if (goOpposite)
            {
                if (newPiles == 1) // 2, 2, 4 - first player take 4 away, then, copy second player action, he wins
                    return 0;
                else
                {
                    // too much options ...
                }

                return 100;
            }

            bool minIs1 = numbers.Min() == 1;
            int count = numbers.Length;

            if (count == 1)
                return 0;   // 1, or 1 2, first player wins
            if (count == 2 && numbers.Max() != numbers.Min())
                return 0;

            if (count >= 3 && minIs1) // 1, 2, 3
            {
                if (count == 3)
                    return 0;

                int[] removeFirst3 = numbers.Skip(3).ToArray();
                if (PlayZeroMoveNim_SecondPlayerWin(newPiles - 3, removeFirst3) == 1)
                    return 0;
            }

            return 100;   // do not know who will win...
        }

        /*
         * second player definitely wins
         * 2, 2
         * 2, 3, 4
         * 
         */
        private static int PlayZeroMoveNim_SecondPlayerWin(int nPiles, int[] piles)
        {
            // 0 - first player win, 1 - second player win

            Array.Sort(piles);

            bool goOpposite = false;
            Dictionary<int, int> dataCount = CountNumber(piles, ref goOpposite);

            int[] numbers = dataCount.Keys.ToArray();
            if (numbers.Length == 0)
                return (goOpposite) ? 11 : 10;

            bool minIs1 = numbers.Min() == 1;
            int count = numbers.Length;

            if (goOpposite)
            {
                //count==1: first player takes away the number, then, second player cannot win. 
                //count==2: two number must be different 1, 2, first player can make it win by making it to 1, 1
                if (count <= 2)
                    return 100;

                if (count == 3 && !minIs1)  // 2, 3, 4
                    return 1;               // First player's turn, cannot make it win

                int[] removeFirst3 = numbers.Skip(3).ToArray();
                return PlayZeroMoveNim_SecondPlayerWin(numbers.Length - 3, removeFirst3);
            }
            else
            {
                if (numbers.Length == 1)
                    return 100;

                if (PlayZeroMoveNim_SecondPlayerWin(numbers.Length, numbers) == 1)
                    return 1;
            }

            return 100;
        }

        /*
         * 0, 1, 
         * the opposite 
         */
        private static int GetOpposite(int value)
        {
            if (value == 0)
                return 1;

            return 0;
        }

        private static int StaySame(int value)
        {
            return value;
        }

        /*
         *  Argue that the function will not have a bug
         *  
         * Test case 1: 
         * 2 2
         * the first player will lose, since the same player just copy the first player move, whatever he does; 
         * 
         * Test case 2:
         * 2 2 4 4 
         * Dictionary have no records
         * the first player will lost
         * 
         * Test case 3:
         * 2 2 2
         * Dictionary will have one record
         * 
         * 2
         * -- 
         * Argue that it is correct: first player will lost on 2 2, but if there is another 2, 
         * first player will take it off
         * 
         * 
         */
        private static Dictionary<int, int> CountNumber(int[] piles, ref bool goOpposite)
        {
            Dictionary<int, int> data = new Dictionary<int, int>();

            for (int i = 0; i < piles.Length; i++)
            {
                int key = piles[i];
                if (data.ContainsKey(key))
                {
                    goOpposite = true;
                    data.Remove(key);
                }
                else
                {
                    data.Add(key, 1);
                }
            }

            return data;
        }

        /*
         * 2 piles, 
         * 2 2
         * 
         * only call the function when input are checked
         */
        private static int CalculateResultSameTwoPiles(int[] piles, int result)
        {
            if (piles.Length > 0 &&
                piles.Length % 2 == 0 &&
                piles.Max() == piles.Min())
            {
                return GetOpposite(result);
            }

            return result;
        }

        /*
        * 2 piles, 
        * 1 2
        * 
        * only call the function when input are checked
        */
        private static int CalculateResultDifferentTwoPiles(int[] piles, int result)
        {
            if (piles.Length > 0 &&
                piles.Length == 2 &&
                piles.Max() > piles.Min())
            {
                return result;
            }

            return result;
        }

        /*
         * 3 piles
         * 1 2 2
         * First player will win 
         * Just take away first pile 
         * 
         */

        /*
         * 3 piles
         * 
         * 1 2 3
         * 
         * First pile number = 1, 
         * 
         * First player will win, just zero-move on first pile
         */

        /*
        * 3 piles
        * 
        * 2 3 4
        * 
        * First pile number (minimum number in all 3 piles) > 1, 
        * 
        * First player will lose, 
        * no matter first player does, 
        *  first player asks zero-move on first pile, then, second player takes first pile and leave it as 1
        *  
        */


    }
}