using System;

using System.Linq;

using System.Collections.Generic;

​

namespace MergeTask

{

    public class MergeClass

    {

​

        private readonly record struct ItemData(string id, int level);

        private static void Merge(List<ItemData> field)

        {

            // Write your code here

        }

        // =============================================================================

        // =================================== TESTS ===================================

        // =============================================================================

        // =============================================================================

        // =============================================================================

        public static void Main(string[] args)

        {

            Console.WriteLine("Example1:");

            Console.WriteLine(string.Join(", ", new ItemData("apple", 1), new ItemData("apple", 1)));

            Console.WriteLine(" -> ");

            Console.WriteLine(new ItemData("apple", 2).ToString());

            Console.WriteLine();

            Console.WriteLine();

            Console.WriteLine("Example2:");

            Console.WriteLine(string.Join(", ", new ItemData("apple", 1), new ItemData("apple", 1), new ItemData("apple", 2),  new ItemData("home", 2), new ItemData("home", 2)));

            Console.WriteLine(" -> ");

            Console.WriteLine(string.Join(", ", new ItemData("apple", 3), new ItemData("home", 3)));

            Console.WriteLine();

            Console.WriteLine();

            Console.WriteLine("Tests are starting...");

            Console.WriteLine();

            TwoApples();

            SmallSimpleField();

            ManySameItems();

            ManySameItems2();

            SmallSimpleField();

            Console.WriteLine("Success!");

        }

​

        private static void TwoApples()

        {

            var field = new List<ItemData>{ new("apple", 1), new("apple", 1) };

            Merge(field);

            AssertSame(field, new List<ItemData> { new("apple", 2) });

        }

​

        private static void SmallSimpleField()

        {

            var field = new List<ItemData>

            {

                new("apple", 1), 

                new("apple", 1),

                new("home", 1),

                new("home", 2),

                new("home", 1),

                new("apple", 1),

            };

            Merge(field);

            AssertSame(field, new List<ItemData>

            {

                new("apple", 2),

                new("apple", 1),

                new("home", 3),

            });

        }

        private static void ManySameItems()

        {

            var field = Enumerable.Repeat(new ItemData("abc", 1), 256).ToList();

            Merge(field);

            AssertSame(field, new List<ItemData>

            {

                new("abc", 9),

            });

        }

        private static void ManySameItems2()

        {

            var field = Enumerable.Repeat(new ItemData("abc", 1), 260).ToList();

            Merge(field);

            AssertSame(field, new List<ItemData>

            {

                new("abc", 9),

                new("abc", 3),

            });

        }

        private static void LargeField()

        {

            var field = 

                    Enumerable.Repeat(new ItemData("abc", 1), 260)

                    .Concat(new ItemData []

                    {

                        new("apple", 1), 

                        new("apple", 1),

                        new("home", 1),

                        new("home", 2),

                        new("home", 1),

                        new("apple", 1),

                    })

                    .Concat(Enumerable.Repeat(new ItemData("eee", 1), 100)).ToList();

            Merge(field);

            AssertSame(field, new List<ItemData>

            {

                new("abc", 9),

                new("abc", 3),

                new("apple", 2),

                new("apple", 1),

                new("home", 3),

                new("eee", 7),

                new("eee", 6),

                new("eee", 3)

            });

        }

        private static void RandomField(int itemsTypesCount, int itemsAmount, int minItemLevel, int maxItemLevel)

        {

            var field = new List<ItemData>(itemsAmount);

            for (int i = 0; i < itemsAmount; i++) {

                field.Add(new ItemData(Random.Shared.Next(0, itemsTypesCount).ToString(), Random.Shared.Next(minItemLevel, maxItemLevel)));

            }

            var expected = new List<ItemData>(field);

            Merge(field);

            MergeFast_Test(expected);

            AssertSame(field, expected);

        }

        public static void LargeRandomField() {

            RandomField(10, 10000, 1, 12);

        }

        private static void MergeFast_Test(List<ItemData> field) {SortedDictionary<ItemData, int> itemsCount = new(new ItemComparer_Test());foreach(var item in field) {if (!itemsCount.ContainsKey(item)) {itemsCount.Add(item, 1);} else {itemsCount[item]++;}}var itemsToHandle = itemsCount.Keys.ToList();for (int i = 0; i < itemsToHandle.Count; i++) {var key = itemsToHandle[i];var mergedItem = key with { level = key.level + 1 };if (itemsCount[key] > 1){  if (itemsCount.ContainsKey(mergedItem))  {     itemsCount[mergedItem] += itemsCount[key] / 2;  }  else  {      itemsCount.Add(mergedItem, itemsCount[key] / 2);    itemsToHandle.Add(mergedItem);  }}itemsCount[key] %= 2;}field.Clear();foreach (var countData in itemsCount) {if (countData.Value == 1)  field.Add(countData.Key);}}

        private class ItemComparer_Test : IComparer<ItemData>

        {

            public int Compare(ItemData x, ItemData y)

            {

                var idComparison = string.Compare(x.id, y.id, StringComparison.Ordinal);

                if (idComparison != 0) return idComparison;

                return x.level.CompareTo(y.level);

            }

        }

        public static void GianticFieldOfSameItems() {

            var field = Enumerable.Repeat(new ItemData("abc", 1), 100000).ToList();

            var expectedField = new List<ItemData>(field);

            MergeFast_Test(expectedField);

            Merge(field);

            AssertSame(field, expectedField);

        }

        public static void SuperGianticRandomField() {

            RandomField(1000, 100000, 1, 100);

        }

​

        public static void GianticRandomField() {

            RandomField(100, 10000, 1, 100);

        }

​

        private static void AssertSame(List<ItemData> actual, List<ItemData> expected)

        {

            actual.Sort(new ItemComparer_Test());

            expected.Sort(new ItemComparer_Test());

            if (actual.Count != expected.Count)

            {

                throw new Exception("Test failed!");

            }

            for (int i = 0; i < actual.Count; i++)

            {

                if (actual[i] != expected[i])

                {

                    throw new Exception("Test failed!");

                }

            }

        }

    }

}