using System;

using System.Collections.Generic;

using System.Linq;

​

namespace TaskExam

{

​

    internal class TaskSolver

    {

​

        public static void Main(string[] args)

        {

            TestGenerateWordsFromWord();

            TestMaxLengthTwoChar();

            TestGetPreviousMaxDigital();

            TestSearchQueenOrHorse();

            TestCalculateMaxCoins();

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

        }

​

​

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

        #region Task1

        public static List<string> GenerateWordsFromWord(string word, List<string> wordDictionary)

        {

            IEnumerable<char> letters = word.Where(p=> true);

​

            List<char> tmpList = new List<char>(letters);

​

            IOrderedEnumerable<string> res = new List<string>(wordDictionary

                .Where(s =>

                {

                    bool isContain = true;

                    foreach (var ch in s)

                    {

                        if (tmpList.Contains(ch))

                        {

                            tmpList.Remove(ch);

                        }

                        else

                        {

                            isContain = false;

                            break;

                        }

                    }

​

                    tmpList = new List<char>(letters);

                    return isContain;

                }))

                .OrderBy(p => p);

​

            return res.ToList();

        }

​

        #endregion

            /// задание 2) Два уникальных символа

        #region Task2

        public static int MaxLengthTwoChar(string word)

        {

            int maxLength = 0;

            List<string> combinations = new List<string>();

​

            List<char> allLeters = new List<char>();

            foreach (char ch in word)

            {

                if (!allLeters.Contains(ch))

                {

                    allLeters.Add(ch);

                }

            }

            FillSet(ref combinations,ref allLeters, allLeters.Count);

​

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

            {

                string altWord = "";

                foreach (char ch in word)

                {

                    if ((ch == combinations[i][0]) || (ch == combinations[i][1]))

                        altWord+=ch;

                }

​

                if ((isAlternativeString(altWord)) && (altWord.Length > maxLength))

                    maxLength = altWord.Length;

​

​

            }

​

            return maxLength;

        }

​

        public static void FillSet(ref List<string> set, ref List<char> Letters, int n)

        {

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

            {

                for (int j = i + 1; j < n; j++)

                {

                    set.Add((Letters[i].ToString() + Letters[j].ToString()));

                }

            }

        }

​

        public static bool isAlternativeString(string str)

        {

            int n = str.Length;

            for (int i = 0; i < n-1; i++)

            {

                if (str[i] == str[i + 1])

                    return false;

            }

            return true;

        }

        #endregion

​

        /// задание 3) Предыдущее число

        #region Task3

        public static long GetPreviousMaxDigital(long value)

        {

            List<char> chars = value.ToString().Select(p => p).ToList();

            int l = chars.Count;

            for (int i = l-2; i >= 0; i--)

            {

                int t = -1;

                int ind = -1;

                for (int j = i + 1; j < l; j++)

                {

                    if ((chars[j] > t) && (chars[j] < chars[i]))

                    {

                        t = chars[j];

                        ind = j;

                    }

                }

​

                if (t != -1)

                {

                    (chars[i],chars[ind]) = (chars[ind], chars[i]);

                    chars.Sort(i + 1, l - i - 1, Comparer<char>.Create((x,y) => (y-x)));

                    break;

                }

            }

​

            string str = "";

​

            foreach (char ch in chars)

            {

                str += ch;

            }

            long s = Int64.Parse(str);

            if (s == value || (str[0] == '0'))

                return -1;

            return s;

        }

        #endregion

        /// задание 4) Конь и Королева

        #region Task4

        public static List<int> SearchQueenOrHorse(char[][] gridMap)

        {

            int cX = 0; 

            int cY = 0;

            int endX = 0, endY = 0;

            int yLen = gridMap.GetLength(0);

            int xLen = gridMap[0].GetLength(0);

            int[,] intGridMap = new int[yLen,xLen];

​

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

            {

​

                for (int j = 0; j < xLen; j++)

                {

                    if (gridMap[i][j] == 's')

                    {

                        cX = j;

                        cY = i;

                    }

                    else if(gridMap[i][j] == 'e')

                    {

                        endX = j;

                        endY = i;

                    }

                    if(gridMap[i][j] != 'x')

                    {

                        intGridMap[i,j] = 100000;

                    }

                    else

                    {

                        intGridMap[i, j] = -1;

                    }

                }

            }

​

            int[,] intGridMap2 = (int[,])intGridMap.Clone();

​

            HorseMove(ref intGridMap,cX,cY, xLen,yLen,1);

​

            QueenMove(ref intGridMap2,cX,cY, xLen,yLen,1);

            int res1 = intGridMap[endY,endX];

            int res2 = intGridMap2[endY,endX];

​

            if (res1 == 100000)

                res1 = -1;

            if (res2 == 100000)

                res2 = -1;

            return new List<int>{res1, res2};

        }

        public static int QueenMove(ref int[,] gridMap, int x, int y, int xL, int yL, int counter)

        {

            int tX, tY;

            tX = x + 1;

            tY = y + 1;

            while ((tY < yL) && (tX < xL) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    QueenMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

​

                tX++;

                tY++;

            }

​

            tX = x;

            tY = y + 1;

            while ((tY < yL) && (tX < xL) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    QueenMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

​

                tY++;

            }

            tX = x + 1;

            tY = y;

            while ((tY >= 0) && (tX < xL) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    QueenMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

​

                tX++;

            }

            tX = x;

            tY = y - 1;

            while ((tY >= 0) && (tX >= 0) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    QueenMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

​

                tY--;

            }

            tX = x - 1;

            tY = y - 1;

            while ((tY >= 0) && (tX >= 0) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    QueenMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

​

                tX--;

                tY--;

            }

            tX = x - 1;

            tY = y;

            while ((tY >= 0) && (tX >= 0) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    QueenMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

​

                tX--;

            }

            tX = x + 1;

            tY = y - 1;

            while ((tY >= 0) && (tX < xL) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    QueenMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

​

                tX++;

                tY--;

            }

            tX = x - 1;

            tY = y + 1;

            while ((tY < yL) && (tX >= 0) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    QueenMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

​

                tX--;

                tY++;

            }

​

            return -1;

        }

​

        public static int HorseMove(ref int[,] gridMap, int x, int y, int xL, int yL, int counter)

        {

            int tX, tY;

            tX = x + 2;

            tY = y + 1;

            if ((tY < yL) && (tX < xL) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    HorseMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

            }

​

            tX = x + 1;

            tY = y + 2;

            if ((tY < yL) && (tX < xL) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    HorseMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

            }

            tX = x - 1;

            tY = y - 2;

            if ((tY >= 0) && (tX >= 0) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    HorseMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

            }

            tX = x - 2;

            tY = y - 1;

            if ((tY >= 0) && (tX >= 0) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    HorseMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

            }

            tX = x + 1;

            tY = y - 2;

            if ((tY >= 0) && (tX < xL) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    HorseMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

            }

            tX = x + 2;

            tY = y - 1;

            if ((tY >= 0) && (tX < xL) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    HorseMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

            }

            tX = x - 1;

            tY = y + 2;

            if ((tY < yL) && (tX >= 0) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    HorseMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

            }

            tX = x - 2;

            tY = y + 1;

            if ((tY < yL) && (tX >= 0) && (gridMap[tY,tX] != -1))

            {

                int num = gridMap[tY,tX];

​

                if (num > counter)

                {

                    gridMap[tY,tX] = counter;

                    HorseMove(ref gridMap,tX, tY, xL, yL, counter+1);

                }

            }

​

            return -1;

        }

        #endregion

​

        /// задание 5) Жадина

        #region Task5

        public static long CalculateMaxCoins(int[][] mapData, int idStart, int idFinish)

        {

            const int INF = -5;

            List<List<KeyValuePair<int, int>>> connections = new List<List<KeyValuePair<int, int>>>();

​

​

            for (int i = 0; i < mapData.GetLength(0); i++)

            {

                while ((connections.Count < mapData[i][0]+1) || (connections.Count < mapData[i][1]+1))

                {

                    connections.Add(new List<KeyValuePair<int, int>>());

                }

                connections[mapData[i][0]].Add(new KeyValuePair<int, int>(mapData[i][1],mapData[i][2]));     

                connections[mapData[i][1]].Add(new KeyValuePair<int, int>(mapData[i][0],mapData[i][2]));

            }

​

            int len = connections.Count;

​

            int[] weights = new int[len];

​

            bool[] marks = new bool[len];

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

            {

                weights[i] = INF;

            }

            weights[idStart] = 0;

            marks[idFinish] = true;

​

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

            {

                int v = -1;

                for (int j = 0; j < len; j++)

                {

                    if (!marks[j] && ((v == -1) || ((float)1/weights[j] > (float)1/weights[v])))

                    {

                        v = j;

                    }

                }

                if((v == -1) || (weights[v] == INF))

                    break;

                marks[v] = true;

​

                for (int j = 0; j < connections[v].Count; j++)

                {

                    int to = connections[v][j].Key;

                    int ln = connections[v][j].Value;

​

                    if ((weights[to] < 0) || ((float)1/(weights[v] + ln)) < ((float)1/weights[to]))

                    {

                        weights[to] = (weights[v] + ln);

                    }

                }

            }

​

​

​

​

            int n = weights[idFinish];

            if (n <= 0)

                n = -1;

            return n;

        }

​

​

        #endregion

​

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

        #region Tests

        private static void TestGenerateWordsFromWord()

        {

            var wordsList = new List<string>

            {

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

                "рог", "морг", "огр", "мор", "порог", "бра", "раб", "зубр"

            };

            AssertSequenceEqual( GenerateWordsFromWord("арбуз", wordsList), new []{ "бра", "зубр", "раб"} );

            AssertSequenceEqual( GenerateWordsFromWord("лист", wordsList), new List<string>() );

            AssertSequenceEqual( GenerateWordsFromWord("маг", wordsList), new List<string>() );

            AssertSequenceEqual( GenerateWordsFromWord("погром", wordsList), new List<string>{ "гром", "мор", "морг", "огр", "порог", "рог", "ром"} );

        }

        private static void TestMaxLengthTwoChar()

        {

            AssertEqual(MaxLengthTwoChar("beabeeab"), 5);

            AssertEqual(MaxLengthTwoChar("eqerarbereqevfdsarqerjwujfsbvvzxffsakfjkeapqefrkzxcvdaafqpdvsavkjzdafdafakkczoasdfcvzxckrfqwerivxcblgdfgw"), 6);

            AssertEqual(MaxLengthTwoChar("а"), 0);

            AssertEqual(MaxLengthTwoChar("ab"), 2);

        }

        private static void TestGetPreviousMaxDigital()

        {

            AssertEqual(GetPreviousMaxDigital(21), 12l);

            AssertEqual(GetPreviousMaxDigital(531), 513l);

            AssertEqual(GetPreviousMaxDigital(1027), -1l);

            AssertEqual(GetPreviousMaxDigital(2071), 2017l);

            AssertEqual(GetPreviousMaxDigital(207034), 204730l);

            AssertEqual(GetPreviousMaxDigital(135), -1l);

            AssertEqual(GetPreviousMaxDigital(9320125), 9315220l);

            AssertEqual(GetPreviousMaxDigital(9123456789), 8997654321l);

            AssertEqual(GetPreviousMaxDigital(1205731),1205713l);

            AssertEqual(GetPreviousMaxDigital(135295723912632228), 135295723912628322l);

        }

        private static void TestSearchQueenOrHorse()

        {

            char[][] gridA =

            {

                new[] {'s', '#', '#', '#', '#', '#'},

                new[] {'#', 'x', 'x', 'x', 'x', '#'},

                new[] {'#', '#', '#', '#', 'x', '#'},

                new[] {'#', '#', '#', '#', 'x', '#'},

                new[] {'#', '#', '#', '#', '#', 'e'},

            };

            AssertSequenceEqual(SearchQueenOrHorse(gridA), new []{3, 2});

            char[][] gridB =

            {

                new[] {'s', '#', '#', '#', '#', 'x'},

                new[] {'#', 'x', 'x', 'x', 'x', '#'},

                new[] {'#', 'x', '#', '#', 'x', '#'},

                new[] {'#', '#', '#', '#', 'x', '#'},

                new[] {'x', '#', '#', '#', '#', 'e'},

            };

            AssertSequenceEqual(SearchQueenOrHorse(gridB), new []{-1, 3});

            char[][] gridC =

            {

                new[] {'s', '#', '#', '#', '#', 'x'},

                new[] {'x', 'x', 'x', 'x', 'x', 'x'},

                new[] {'#', '#', '#', '#', 'x', '#'},

                new[] {'#', '#', '#', 'e', 'x', '#'},

                new[] {'x', '#', '#', '#', '#', '#'},

            };

            AssertSequenceEqual(SearchQueenOrHorse(gridC), new []{2, -1});

            char[][] gridD =

            {

                new[] {'e', '#'},

                new[] {'x', 's'},

            };

​

            AssertSequenceEqual(SearchQueenOrHorse(gridD), new []{-1, 1});

            char[][] gridE =

            {

                new[] {'e', '#'},

                new[] {'x', 'x'},

                new[] {'#', 's'},

            };

​

            AssertSequenceEqual(SearchQueenOrHorse(gridE), new []{1, -1});

            char[][] gridF =

            {

                new[] {'x', '#', '#', 'x'},

                new[] {'#', 'x', 'x', '#'},

                new[] {'#', 'x', '#', 'x'},

                new[] {'e', 'x', 'x', 's'},

                new[] {'#', 'x', 'x', '#'},

                new[] {'x', '#', '#', 'x'},

            };

​

            AssertSequenceEqual(SearchQueenOrHorse(gridF), new []{-1, 5});

            char[][] gridG =

            {

                new[] {'#', '#', '#', '#', '#', '#', '#', '#', '#', 'x', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},

                new[] {'#', '#', '#', '#', '#', '#', '#', 'x', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},

                new[] {'#', '#', '#', '#', '#', '#', '#', 'x', 'x', '#', 'x', '#', '#', '#', '#', '#', '#', '#', '#', '#'},

                new[] {'#', 's', '#', '#', '#', '#', '#', 'x', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},

                new[] {'#', '#', '#', '#', '#', '#', 'x', 'x', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},

                new[] {'#', '#', '#', '#', '#', 'x', 'x', '#', '#', '#', '#', 'x', '#', '#', '#', '#', '#', '#', '#', '#'},

                new[] {'#', '#', '#', '#', '#', 'x', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},

                new[] {'#', '#', '#', '#', '#', 'x', 'x', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},

                new[] {'#', '#', '#', '#', '#', '#', 'x', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},

                new[] {'#', '#', '#', '#', '#', '#', 'x', '#', '#', '#', '#', '#', '#', '#', 'x', 'x', 'x', 'x', 'x', 'x'},

                new[] {'#', '#', '#', '#', 'x', 'x', 'x', '#', '#', '#', '#', '#', '#', '#', 'x', '#', '#', '#', '#', 'x'},

                new[] {'#', '#', '#', '#', 'x', '#', '#', '#', '#', '#', '#', '#', '#', '#', 'x', 'e', '#', '#', '#', '#'},

                new[] {'#', '#', '#', '#', 'x', 'x', '#', '#', '#', '#', '#', '#', '#', '#', 'x', '#', '#', '#', '#', '#'},

                new[] {'x', 'x', 'x', 'x', 'x', 'x', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', 'x', '#', '#', '#'},

​

            };

​

            AssertSequenceEqual(SearchQueenOrHorse(gridG), new []{8, 6});

        }

        private static void TestCalculateMaxCoins()

        {

            var mapA = new []

            {

                new []{0, 1, 1},

                new []{0, 2, 4},

                new []{0, 3, 3},

                new []{1, 3, 10},

                new []{2, 3, 6},

            };

            AssertEqual(CalculateMaxCoins(mapA, 0, 3), 11l);

​

            var mapB = new []

            {

                new []{0, 1, 1},

                new []{1, 2, 53},

                new []{2, 3, 5},

                new []{5, 4, 10}

            };

            AssertEqual(CalculateMaxCoins(mapB, 0, 5), -1l);

            var mapC = new []

            {

                new []{0, 1, 1},

                new []{0, 3, 2},

                new []{0, 5, 10},

                new []{1, 2, 3},

                new []{2, 3, 2},

                new []{2, 4, 7},

                new []{3, 5, 3},

                new []{4, 5, 8}

            };

            AssertEqual(CalculateMaxCoins(mapC, 0, 5), 19l);

            var mapD = new []

            {

                new []{0, 1, 1},

                new []{0, 3, 2},

                new []{0, 5, 10},

                new []{1, 2, 1},

                new []{2, 3, 7},

                new []{2, 4, 1},

                new []{3, 5, 3},

                new []{4, 5, 2}

            };

            AssertEqual(CalculateMaxCoins(mapD, 0, 5), 12l);

        }

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

        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]}");

                }

            }

        }

        #endregion

    }

}