Hackerrank week code 28 - value of friendship - code review, make the code more readable - study one of C# submissions

valueOfFriendship_codereview_2.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
    /* 
     * January 19, 2016
     */
    public struct Group
    {
        public int Links;
        public Stack<int> Nodes;

        /*
         * Small group will join the bigger group. 
         */
        public static void MergeSmallGroupToLargeOne(
            Group[] groups,
            int     smallGroupId,
            int     bigGroupId,
            int[]   nodeGroupId)
        {
            groups[bigGroupId].Links += groups[smallGroupId].Links + 1;

            Stack<int> destination = groups[bigGroupId].Nodes;
            Stack<int> source = groups[smallGroupId].Nodes;

            while (source.Count > 0)
            {
                int node = source.Pop();
                nodeGroupId[node] = bigGroupId;
                destination.Push(node);
            }
        }

        /*
         * Go over the calculation formula about value of friendships
         * 
         */
        public static ulong CalculateValue(Group[] sortedGroups)
        {
            ulong additionalLinks = 0;
            ulong totalValueOfFriendship = 0;
            ulong totalFriends = 0;

            // Each group is maximized in order... additionalLinks added at end
            foreach (Group group in sortedGroups)
            {
                ulong links = (ulong)(group.Nodes.Count - 1);

                ulong lookupValue = FriendshipValueCalculation.GetLookupTable()[links];
                totalValueOfFriendship += lookupValue + totalFriends * links;

                additionalLinks += (ulong)group.Links - links;

                totalFriends += links * (links + 1);
            }

            totalValueOfFriendship += additionalLinks * totalFriends;

            return totalValueOfFriendship;
        }

        /*
         * filter out empty group, check Group class member 
         * @groupCount - total groups, excluding merged groups
         * @groupIndex - total groups, including merged groups
         * 
         * check Nodes in the stack, if the stack is empty, then the group is empty. 
         */
        public static Group[] GetNonemptyGroups(int groupCount, int groupIndex, Group[] groups)
        {
            Group[] nonEmptyGroups = new Group[groupCount];

            int index = 0;
            for (int i = 1; i <= groupIndex; i++)
            {
                if (groups[i].Nodes.Count > 0)
                {
                    nonEmptyGroups[index++] = groups[i];
                }
            }

            return nonEmptyGroups;
        }
    }

    /*
     * Design talk: 
     * 1 <= n <= 100,000, n is the total students
     * 1 <= m <= 2 * 100,000, m is the total friendship
     * @groups - 
     * @groupIdMap - 
     */
    public class GroupManagement
    {
        public Group[] Components;
        public int[]   IdMap;
        public int     Index = 0;
        public int     Count = 0;

        public GroupManagement(int totalStudents)
        {
            Components = new Group[totalStudents / 2 + 1];   //
            IdMap = new int[totalStudents + 1];              // less than 2MB
            Index = 0;
            Count = 0;
        }

        /*
         * 
           1) neither in a group:  create new group with 2 nodes
           2) only one in a group: add the other
           3) both already in same group - increase Links
           4) both already in different groups... join groups
         * 
         */
        public void AddFriendshipToGroups(int id1, int id2)
        {
            int groupId1 = IdMap[id1];
            int groupId2 = IdMap[id2];

            if (groupId1 == 0 || groupId2 == 0)
            {
                if (groupId1 == 0 && groupId2 == 0)
                {
                    Index++;
                    Count++;

                    Components[Index].Links = 1;
                    Components[Index].Nodes = new Stack<int>();
                    Components[Index].Nodes.Push(id1);
                    Components[Index].Nodes.Push(id2);

                    IdMap[id1] = Index;
                    IdMap[id2] = Index;
                }
                else if (groupId1 == 0)
                {
                    // add student1 into student2's group
                    Components[groupId2].Nodes.Push(id1);
                    Components[groupId2].Links++;

                    IdMap[id1] = groupId2;
                }
                else
                {
                    // add student2 into studnet1's group
                    Components[groupId1].Nodes.Push(id2);
                    Components[groupId1].Links++;
                    IdMap[id2] = groupId1;
                }
            }
            else
            {
                if (groupId1 == groupId2)
                {
                    Components[groupId1].Links++;
                }
                else   // merge two groups 
                {
                    Count--;
                    int groupSize1 = Components[groupId1].Nodes.Count;
                    int groupSize2 = Components[groupId2].Nodes.Count;

                    if (groupSize1 < groupSize2)
                    {                        
                        Group.MergeSmallGroupToLargeOne(Components, groupId1, groupId2, IdMap);
                    }
                    else
                    {
                        Group.MergeSmallGroupToLargeOne(Components, groupId2, groupId1, IdMap);
                    }
                }
            }
        }
    }

    /*
     * descending
     */
    public class GroupComparer : Comparer<Group>
    {
        public override int Compare(Group x, Group y)
        {
            return (y.Nodes.Count - x.Nodes.Count);
        }
    }

    /*
     * add some calculation description here. 
     */
    public class FriendshipValueCalculation
    {
        public static long FRIENDSHIPS_MAXIMUM = 200000;

        public static ulong[] GetLookupTable()
        {
            ulong[] friendshipsLookupTable = new ulong[FRIENDSHIPS_MAXIMUM];  // 1.6 MB

            ulong valueOfFriendship = 0;

            for (int i = 1; i < FRIENDSHIPS_MAXIMUM; i++)
            {
                valueOfFriendship += (ulong)i * (ulong)(i + 1);
                friendshipsLookupTable[i] = valueOfFriendship;
            }

            return friendshipsLookupTable;
        }
    }

    static void Main(String[] args)
    {
        ProcessInput();
        //RunSampleTestcase();
        //RunSampleTestcase2(); 
    }

    public static void ProcessInput()
    {
        GroupComparer headComparer = new GroupComparer();

        int queries = Convert.ToInt32(Console.ReadLine());
        for (int query = 0; query < queries; query++)
        {
            string[] tokens_n = Console.ReadLine().Split(' ');
            int studentsCount = Convert.ToInt32(tokens_n[0]);
            int friendshipsCount = Convert.ToInt32(tokens_n[1]);

            GroupManagement groupManager = new GroupManagement(studentsCount);

            for (int i = 0; i < friendshipsCount; i++)
            {
                string[] relationship = Console.ReadLine().Split(' ');

                int id1 = Convert.ToInt32(relationship[0]);
                int id2 = Convert.ToInt32(relationship[1]);

                groupManager.AddFriendshipToGroups(id1, id2);
            }

            // Sort all groups from large one with more students to small one with less students
            Group[] groupsNeedSorting =
                Group.GetNonemptyGroups(
                    groupManager.Count,
                    groupManager.Index,
                    groupManager.Components);

            Array.Sort(groupsNeedSorting, headComparer);

            Console.WriteLine(Group.CalculateValue(groupsNeedSorting));
        }
    }

    /*
     *
     * Need to work on the sample test case
     * 1. student 1 and 2 become friends
     *  1-2 3 4 5,  we then sum the number of friends that each student has
     * to get 1 + 1 + 0 + 0 + 0 = 2. 
     * 2. Student 2 and 3 become friends:
     *  1-2-3 4 5, we then sum the number of friends that each student has to get
     * 2 + 2 + 2 + 0 + 0 = 6. 
     * 3. Student 4 and 5 become friends:
     * 1-2-3 4-5, we then sum the number of friends that each student has to get 
     * 2 + 2 + 2 + 1 + 1 = 8. 
     * 4. Student 1 and 3 become friends: (we hold to add 1 and 3 until 4 and 5
     *    are added to maximize the value.)
     * 1-2-3 4-5, we then sum the number of friends that each student has to get
     * 2 + 2 + 2 + 1 + 1 = 8. 
     * Total is 2 + 6 + 8 + 8 = 24.   
     */
    public static void RunSampleTestcase()
    {
        string[][] datas = new string[1][];
        datas[0] = new string[2];
        datas[0][0] = "5";
        datas[0][1] = "4";

        string[][] allFriendships = new string[1][];
        allFriendships[0] = new string[4];

        allFriendships[0][0] = "1 2";
        allFriendships[0][1] = "2 3";
        allFriendships[0][2] = "1 3";
        allFriendships[0][3] = "4 5";        

        Console.WriteLine(RunTestcase(datas, allFriendships));
    }

    public static void RunSampleTestcase2()
    {
        string[][] datas = new string[1][];
        datas[0] = new string[2];
        datas[0][0] = "5";
        datas[0][1] = "4";

        string[][] allFriendships = new string[1][];
        allFriendships[0] = new string[4];

        allFriendships[0][0] = "1 2";
        allFriendships[0][1] = "3 2";
        allFriendships[0][2] = "4 2";
        allFriendships[0][3] = "4 3";

        Console.WriteLine(RunTestcase(datas, allFriendships));
    }

    private static ulong RunTestcase(string[][] datas, string[][] allFriendships)
    {
        GroupComparer headComparer = new GroupComparer();

        int studentsCount = Convert.ToInt32(datas[0][0]);
        int friendshipsCount = Convert.ToInt32(datas[0][1]);

        GroupManagement groupManager = new GroupManagement(studentsCount);

        for (int i = 0; i < friendshipsCount; i++)
        {
            string[] relationship = allFriendships[0][i].Split(' ');

            int id1 = Convert.ToInt32(relationship[0]);
            int id2 = Convert.ToInt32(relationship[1]);

            groupManager.AddFriendshipToGroups(id1, id2);
        }

        // Get all groups large to small
        Group[] groupNeedSorting =
            Group.GetNonemptyGroups(
                groupManager.Count,
                groupManager.Index,
                groupManager.Components);

        Array.Sort(groupNeedSorting, headComparer);

        return Group.CalculateValue(groupNeedSorting); 
    }
}