using System;

using System.Collections.Generic;

using System.Linq;

using System.Text.RegularExpressions;

​

​

namespace TaskExam

{

    internal class TaskSolver

    {

        public static void Main(string[] args)

        {

            TestGetWordSubWords();      //completed

            TestFindPath();             //completed

            TestFormatPrettyCoins();    //completed

            FindMaxRect();              //completed

            Console.WriteLine("All Test completed!");

        }

        /// задание 1) Индекс слова

        static bool isValid(string word, Dictionary<char, int> letters)

        {

            return Regex.IsMatch(word, @"[а-яёА-ЯЁa-zA-Z]")&& word.GroupBy(c => c).ToDictionary(c => c.Key, c => c.Count()).All(x => letters.ContainsKey(x.Key) && letters[x.Key] >= x.Value);

        }

        public static List<int> GetWordSubWords(List<string> words, List<string> wordDictionary)

        {

            var kolvoWords = new List<int>();

            foreach(string word in words){

                var letters = word.GroupBy(c => c).ToDictionary(c => c.Key, c => c.Count());

                var count = 0;

                foreach(string userWord in wordDictionary)

                {

                    if(isValid(userWord, letters)) count++;

                }

                kolvoWords.Add(count);

            }

            return kolvoWords;

        }

        /// задание 2) Луноход

        class ArrayComparer : IEqualityComparer<int[]>

        {

            public bool Equals(int[] x, int[] y)

            {

                return x.SequenceEqual(y);

            }

            public int GetHashCode(int[] obj)

            {

                int heigth = 0;

                foreach (int item in obj)

                {

                    heigth = (heigth << 5) + 3 + heigth^ item.GetHashCode();

                }

                return heigth;

            }

        }

        public static int FindPath(int[][] gridMap, int sX, int sY, int eX, int eY, int energyAmount)

        {

            Queue<int[]> queue = new Queue<int[]>();

            Queue<int[]> cont = new Queue<int[]>();

            int[] tmp = new int[2];

            int energy = 0;

            queue.Enqueue(new[] { sX, sY });

            cont.Enqueue(new[] { sX, sY });

            while (queue.Count > 0)

            {

                int k = queue.Count;

                for (int i = 0; i < k; i++)

                {

                    tmp = queue.Dequeue();

                    if (tmp[0] == eX && tmp[1] == eY)

                        if (k <= energyAmount)

                            return energy;

                        else

                            return -1;

                    else

                    {

                        tmp[1]++;

                        if (tmp[1] + 1 < gridMap.Length && gridMap[gridMap.Length - tmp[1] - 1][tmp[0]] != 0 && cont.Contains(tmp, new ArrayComparer()) == false)

                        {

                            queue.Enqueue(new[] { tmp[0], tmp[1] });

                            cont.Enqueue(new[] { tmp[0], tmp[1] });

                        }

                        tmp[1]--;

                        tmp[1]--;

                        if (tmp[1] >= 0 && gridMap[gridMap.Length - tmp[1] - 1][tmp[0]] != 0 && cont.Contains(tmp, new ArrayComparer()) == false)

                        {

                            queue.Enqueue(new[] { tmp[0], tmp[1] });

                            cont.Enqueue(new[] { tmp[0], tmp[1] });

                        }

                        tmp[1]++;

                        tmp[0]--;

                        if (tmp[0] >= 0 && gridMap[gridMap.Length - tmp[1] - 1][tmp[0]] != 0 && cont.Contains(tmp, new ArrayComparer()) == false)

                        {

                            queue.Enqueue(new[] { tmp[0], tmp[1] });

                            cont.Enqueue(new[] { tmp[0], tmp[1] });

                        }

                        tmp[0]++;

                        tmp[0]++;

                        if (tmp[0] < gridMap[0].Length && gridMap[gridMap.Length - tmp[1] - 1][tmp[0]] != 0 && cont.Contains(tmp, new ArrayComparer()) == false)

                        {

                            queue.Enqueue(new[] { tmp[0], tmp[1] });

                            cont.Enqueue(new[] { tmp[0], tmp[1] });

                        }

                        tmp[0]--;

                    }

                }

                energy++;

            }

            return -1;

        }

        /// задание 3) Монетки

        public static string FormatPrettyCoins(long value, char separator)

        {

            string answer = "";

            if(value<1000)

                answer = value.ToString();

            else if(value< 100000) 

                answer = (value/1000).ToString() + " " + ((value%1000)!=0 ? (value%1000).ToString() : "000") ;

            else if(value<1000000)

                answer = (value/1000).ToString() + "K";

            else if(value<10000000)

                answer = (value/1000000).ToString() + " " + ( (value%1000000)!=0 ?((value%1000000)/1000).ToString() : "000") + "K";

            else if(value<1000000000)

                answer = (value/1000000).ToString() + "M";

            else{

                answer = (value/1000000000).ToString() + " " + ( (value%1000000000)!=0 ? ((value%1000000000)/1000000).ToString() : "000") + "M";

            }

            return answer;

        }   

        /// задание 4) Самый большой прямоугольник на гистограмме

        static bool IsEmpty<T>(Stack<T> stack) {

            return (stack.Count==0);

        } 

        public static int FindMaxRect(List<int> heights)

        {

            var stack = new Stack<int>();

            int  maxArea = 0;

            int tp;

            int area;

            int i = 0;

            int n = heights.Count()-1;

            while (i <= n) {

                if (IsEmpty(stack) ||heights[i] >= heights[stack.Peek()]) {

                    stack.Push(i++);

                }

                else {

                    tp = stack.Pop();

                    area = heights[tp] * (IsEmpty(stack) ? i : i - stack.Peek() - 1);

                    maxArea = Math.Max(maxArea, area);

                }

            }

             while (!IsEmpty(stack)) {

                tp = stack.Pop();

                area = heights[tp] * (IsEmpty(stack) ? i : i - stack.Peek() - 1);

                maxArea = Math.Max(maxArea, area);

            }

            return  maxArea;

        }

​

        /// Тесты (можно/нужно добавлять свои тесты) 

        private static void TestGetWordSubWords()

        {

            var wordsList = new List<string>

            {

                "кот", "ток", "око", "мимо", "гром", "ром", 

                "рог", "морг", "огр", "мор", "порог", 

                "cat", "tac","C"

            };

            AssertSequenceEqual( GetWordSubWords(new List<string>{"кот"}, wordsList), new []{2} );

            AssertSequenceEqual( GetWordSubWords(new List<string>{"Cat"}, wordsList), new []{1} );

            AssertSequenceEqual( GetWordSubWords(new List<string>{"cat"}, wordsList), new []{2} );

            AssertSequenceEqual( GetWordSubWords(new List<string>{"мама"}, wordsList), new []{0} );

            AssertSequenceEqual( GetWordSubWords(new List<string>{"погром", "гром"}, wordsList), new []{7, 6} );

        }

        private static void TestFindPath()

        {

            int[][] gridA =

            {

                new[] {1, 1, 1, 0, 1, 1},

                new[] {1, 1, 1, 0, 1, 1},

                new[] {1, 1, 1, 0, 0, 0},

                new[] {1, 1, 1, 1, 1, 1},

                new[] {1, 1, 1, 1, 1, 1},

                new[] {1, 1, 1, 1, 1, 1},

            };

            AssertEqual(FindPath(gridA, 0,0,2, 2, 5), 4);

            AssertEqual(FindPath(gridA, 0,0,5, 5, 30), -1);

            AssertEqual(FindPath(gridA, 0,0,0, 5, 3), -1);

        }

        private static void TestFormatPrettyCoins()

        {

            AssertEqual(FormatPrettyCoins(1, ' '), "1");

            AssertEqual(FormatPrettyCoins(10, ' '), "10");

            AssertEqual(FormatPrettyCoins(100, ' '), "100");

            AssertEqual(FormatPrettyCoins(1233, ' '), "1 233");

            AssertEqual(FormatPrettyCoins(20000, ' '), "20 000");

            AssertEqual(FormatPrettyCoins(100000, ' '), "100K");

            AssertEqual(FormatPrettyCoins(1717310, ' '), "1 717K");

            AssertEqual(FormatPrettyCoins(1000000, ' '), "1 000K");

            AssertEqual(FormatPrettyCoins(10000000, ' '), "10M");

            AssertEqual(FormatPrettyCoins(100000000, ' '), "100M");

            AssertEqual(FormatPrettyCoins(7172343310, ' '), "7 172M");

            AssertEqual(FormatPrettyCoins(10000000000, ' '), "10 000M");

        }

        private static void FindMaxRect()

        {

            AssertEqual(FindMaxRect(new List<int>{1, 2, 3, 4, 4, 4, 5, 4, 6}), 24);

            AssertEqual(FindMaxRect(new List<int>{1, 2, 3, 5, 5, 4, 2, 4, 6}), 16);

            AssertEqual(FindMaxRect(new List<int>{8, 9, 3, 5, 5, 2, 3, 4, 6, 1, 6}), 18);

        }

        /// Тестирующая система, лучше не трогать этот код

        private static void Assert(bool value)

        {

            if (value)

            {

                return;

            }

​

            throw new Exception("Assertion failed");

        }

​

        private static void AssertEqual(object value, object expectedValue)

        {

            if (value.Equals(expectedValue))

            {

                return;

            }

​

            throw new Exception($"Assertion failed expected = {expectedValue} actual = {value}");

        }

​

        private static void AssertSequenceEqual<T>(IEnumerable<T> value, IEnumerable<T> expectedValue)

        {

            if (ReferenceEquals(value, expectedValue))

            {

                return;

            }

            if (value is null)

            {

                throw new ArgumentNullException(nameof(value));

            }

            if (expectedValue is null)

            {

                throw new ArgumentNullException(nameof(expectedValue));

            }

​

            var valueList = value.ToList();

            var expectedValueList = expectedValue.ToList();

            if (valueList.Count != expectedValueList.Count)

            {

                throw new Exception($"Assertion failed expected count = {expectedValueList.Count} actual count = {valueList.Count}");

            }

​

            for (var i = 0; i < valueList.Count; i++)

            {

                if (!valueList[i].Equals(expectedValueList[i]))

                {

                    throw new Exception($"Assertion failed expected value at {i} = {expectedValueList[i]} actual = {valueList[i]}");

                }

            }

        }

​

    }

​

}