using System;
using System.Diagnostics;
using Combinatorics.Collections;
using System.Collections.Generic;
using static System.Console;
using System.Threading.Tasks;
using System.Threading;

namespace komvo
{
    class Program
    {
        public static double[,] Matrix;
        public static bool End;
        public static bool EnabledPerm = false, EnabledAlg = false, EnabledAlgPar = false;

        public static int[] routesCPar;
        public static double[] routesResultsPar;
        public static int[][] routesCPars; 
        public static int index;
        public static Thread CountThreads;

        static void Main(string[] args)
        {
            GetEnables();
        Beginig:

            routesResultsPar = new double[10];
            routesCPars = new int[10][];
            index = 0;

            List<Point> Points = new List<Point>();
            Random random = new Random();
            int pCount = 0;

        Retry:
            string elems = ReadLine();
            //WriteLine($"Elems: {elems}");
            try
            {
                if (elems == "w") { GetEnables(); goto Retry; }
                else
                {
                    pCount = Convert.ToInt32(elems);
                    if (pCount < 4) { WriteLine("Слишком маленькое число"); goto Retry; }
                }
            }
            catch
            {
                Write("Введите натуральное число: ");
                goto Retry;
            }

            for(int i = 0; i < pCount; i++)
            {
                int x = random.Next(80);
                int y = random.Next(70);
                Points.Add(new Point { X = x, Y = y });
                WriteLine("Точка {0} [{1};{2}]", i + 1, x, y);
            }
            WriteLine("\n");

            int matr = Points.Count;
            Matrix = new double[matr, matr];

            for (int i = 0; i < Points.Count; i++)
                for (int j = i; j < Points.Count - 1; j++)
                    Matrix[i, j + 1] = Matrix[j + 1, i] =
                        Math.Sqrt(Math.Pow(Points[j + 1].X - Points[i].X, 2) + Math.Pow(Points[j + 1].Y - Points[i].Y, 2));


            for (int i = 0; i < matr; i++)
            {
                for (int j = 0; j < matr; j++) Write("{0:00.00} ", Matrix[i, j]);
                WriteLine();
            }



            //-------------------------------------------------------------------------------------------------
            #region Permuts

            if (!EnabledPerm) goto EndOfPerm;

            Stopwatch stopwatchPERM = new Stopwatch();
            stopwatchPERM.Start();

            List<ResultRoute> resroutesPerm = new List<ResultRoute>();
            int[] toSwap = new int[Points.Count - 1];
            for (int i = 0; i <= toSwap.Length - 1; i++) toSwap[i] = i + 2;

            bool first = true;
            double opLength = 0, prevResult = 0;
            string opRoute = string.Empty;

            Permutations<int> perm = new Permutations<int>(toSwap);
            foreach(IList<int> p in perm)
            {
                int[] route = new int[Points.Count - 1];
                for (int i = 0; i < toSwap.Length; i++) route[i] = p[i];
                prevResult = CountLength(Matrix, route);
                //WriteLine(opLength);

                if (first)
                {
                    opLength = prevResult;
                    foreach (int i in route) opRoute += i + ";";
                    first = false;
                    resroutesPerm.Add(new ResultRoute(opLength, opRoute));
                }
                else if(opLength > prevResult)
                {
                    opLength = prevResult;
                    opRoute = string.Empty;
                    foreach (int i in route) opRoute += i + ";";

                    resroutesPerm.Clear();
                    resroutesPerm.Add(new ResultRoute(opLength, opRoute));
                }
                else if(opLength == prevResult)
                {
                    opRoute = string.Empty;
                    foreach (int i in route) opRoute += i + ";";
                    resroutesPerm.Add(new ResultRoute(opLength, opRoute));
                }
            }
            stopwatchPERM.Stop();

            WriteLine("\n\nPerms");
            WriteLine("1;{1}1 - оптимальный маршрут длинной {0:00.00}\nИз {2} маршрутов при {3} точках\nПосчитано за {4} \n\n",
                opLength, opRoute, Fact(Points.Count - 1), Points.Count, stopwatchPERM.Elapsed);
            //WriteLine($"Count = {resroutesPerm.Count}");
        EndOfPerm:


            #endregion


            //-------------------------------------------------------------------------------------------------
            #region Alg


            if (!EnabledAlg) goto ExitFromAlg;

            Stopwatch stopwatchNAl = new Stopwatch();
            stopwatchNAl.Start();
            int[] routesC = new int[Points.Count - 1];
            for (int i = 0; i < routesC.Length; i++) routesC[i] = i + 2;

            routesC[routesC.Length - 1]--;

            End = false;
            bool firstIt = true;
            double routeLen = 0;
            string routeName = string.Empty;
            int routesCount = 0;

            for (int numb = 0; numb < Math.Pow(Points.Count - 1, Points.Count - 1); numb++)
            {
                routesC[routesC.Length - 1] += 1;
                Adjustment(ref routesC);
                if (!End)
                {
                    if (CheckDoubles(routesC))
                    {
                        //Write($"{CountLength(Matrix, routesC):00.00} ;");
                        routesCount += 1;
                        if (firstIt)
                        {
                            routeLen = CountLength(Matrix, routesC);
                            foreach (int i in routesC) routeName += i + ";";
                            firstIt = false;
                        }
                        else
                        {
                            if (routeLen > CountLength(Matrix, routesC))
                            {
                                routeLen = CountLength(Matrix, routesC);
                                routeName = string.Empty;
                                foreach (int i in routesC) routeName += i + ";";
                            }
                        }
                    }
                }
                else { goto EndOfAlg; }
            }
            stopwatchNAl.Stop();

        EndOfAlg:
            WriteLine("Algoritm");
            WriteLine($"1;{routeName}1 - оптимальный маршрут длинной {routeLen:00.00}\n" +
                $"Из {routesCount} маршрутов при {Points.Count} точках\nПосчитано за {stopwatchNAl.Elapsed} \n\n");

            ExitFromAlg:

            #endregion


            //-------------------------------------------------------------------------------------------------
            #region AlgParall

            if (!EnabledAlgPar) goto EndOfAlgParExiting;

            Stopwatch stopwatchNAlPar = new Stopwatch();
            stopwatchNAlPar.Start();
            routesCPar = new int[Points.Count - 1];
            for (int i = 0; i < routesCPar.Length; i++) routesCPar[i] = i + 2;

            routesCPar[routesCPar.Length - 1]--;

            End = false;
            string routeNamePar = string.Empty;

            for (int numb = 0; numb < Math.Pow(Points.Count - 1, Points.Count - 1); numb++)
            {
                routesCPar[routesCPar.Length - 1] += 1;
                Adjustment(ref routesCPar);
                if (!End)
                {
                    if (CheckDoubles(routesCPar))
                    {
                        if (CountThreads != null)
                            if (CountThreads.IsAlive) CountThreads.Join();

                        routesCPars[index] = new int[routesCPar.Length];
                        routesCPar.CopyTo(routesCPars[index], 0);

                        index++;
                        if (index > 9) index = 0;

                        //Write($"\n{index} : ");
                        //foreach (int i in routesCPars[index]) Write($"{i};  ");
                        CountThreads = new Thread(() => CountLengthParall());
                        CountThreads.Start();

                        //if (CountThreads1 == null)
                        //{
                        //    CountThreads1 = new Thread(() => CountLengthParall());
                        //    CountThreads1.Start();
                        //}
                        //else if (!CountThreads1.IsAlive)
                        //{
                        //    CountThreads1 = new Thread(() => CountLengthParall());
                        //    CountThreads1.Start();
                        //}                       
                        //else
                        //{
                        //    CountThreads1.Join();
                        //    CountThreads1 = new Thread(() => CountLengthParall());
                        //    CountThreads1.Start();
                        //}
                    }
                }
                else { goto EndOfAlgPar; }
            }
            stopwatchNAlPar.Stop();

        EndOfAlgPar:

            CountThreads.Join();
            double ddd = routesResultsPar[0];
            for(int i = 0; i < 10; i++)
            {
                if (ddd > routesResultsPar[i] & routesResultsPar[i] != 0) ddd = routesResultsPar[i];
            }

            WriteLine("Paralle Alg");
            //foreach (double d in routesResultsPar) Write($"{d:00.00};  "); WriteLine();
            WriteLine($"Result: {ddd:00.00}; Time: {stopwatchNAlPar.Elapsed}");

            EndOfAlgParExiting:

            #endregion


            Write("Ещё раз? (y/n) ");
            Exiting:
            char answer = ReadKey().KeyChar;
            switch (answer)
            {
                case 'y':
                    Write("\nВведите количество точек больше 3 (w  для изменения алгоритммов): ");
                    goto Beginig;
                case 'n':
                    goto End;
                default:
                    goto Exiting;
            }

        End:
            WriteLine("\nРабота окончена");
            Thread.Sleep(1000);
        }

        public static void Adjustment(ref int[] route)
        {
            for (int i = route.Length - 1; i >= 0; i--)
            {
                if (route[i] > route.Length + 1)
                {
                    if (i == 0) { End = true; /*WriteLine("\nEnded");*/ break; }
                    else
                    {
                        route[i] = 2;
                        route[i - 1] += 1;
                    }
                }
            }
        }

        public static double CountLength(double[,] mtr, int[] route)
        {
            double result = 0;

            for (int j = 0; j < route.Length - 1; j++)
            {
                if (j == 0) result += mtr[0, route[j] - 1];
                else if (j == route.Length - 1)
                {
                    result += mtr[route[j - 1] - 2, route[j] - 2];
                    result += mtr[0, route[j] - 2];
                }
                else
                {
                    result += mtr[route[j - 1] - 2, route[j] - 2];
                }
            }
            return result;
        }

        public static void CountLengthParall()
        {
            double result = 0;
            int indexL = index - 1;
            if (indexL == -1) indexL = 9;
            //WriteLine($"Index: {index}");
            int[] localRoute = routesCPars[indexL];

            for (int j = 0; j < localRoute.Length - 1; j++)
            {
                if (j == 0) result += Matrix[0, localRoute[j] - 1];
                else if (j == localRoute.Length - 1)
                {
                    result += Matrix[localRoute[j - 1] - 2, localRoute[j] - 2];
                    result += Matrix[0, localRoute[j] - 2];
                }
                else
                {
                    result += Matrix[routesCPars[indexL][j - 1] - 2, routesCPars[indexL][j] - 2];
                }
            }

            if(routesResultsPar[index] == 0 || routesResultsPar[index] > result) routesResultsPar[index] = result;
            //index++;
            //if (index > 9) index = 0;
        }

        public static bool CheckDoubles(int[] array)
        {
            int count = array.Length;
            //for (int i = 0; i < count; i++) Write(array[i] + " "); WriteLine();
            for(int i = 0; i < count; i++)
            {
                for(int j = i + 1; j < count; j++)
                {
                    //WriteLine($"{array[i]}[{i}] == {array[j]}[{j}] = {array[i] == array[j]}");

                    if (array[i] == array[j])
                    {
                        return false;
                    }
                }
            }
            return true;
        }

        public static bool YesOrNo(char ch)
        {
            switch (ch)
            {
                case 'y':
                    return true;
                case 'n':
                    return false;
                default:
                    return false;
            }
        }

        public static void GetEnables()
        {

        GetEnables:
            Write("\nКакие алгоритмы включить (например yny: Perm: Enbled, Alg: Disabled, AlgPar: Enabled)? : ");

            char[] check = ReadLine().ToCharArray();

            for (int i = 0; i < check.Length; i++)
            {
                if (i == 0) EnabledPerm = YesOrNo(check[i]);
                if (i == 1) EnabledAlg = YesOrNo(check[i]);
                if (i == 2) EnabledAlgPar = YesOrNo(check[i]);
            }
            //EnabledAlgPar = false;

            WriteLine($"Permutation Alg Enabled = {EnabledPerm}\nFull Alg Enabled = {EnabledAlg}\nFull Alg Parallel Enabled = {EnabledAlgPar}");

            if (EnabledPerm == EnabledAlg & EnabledAlg == EnabledAlgPar & EnabledAlgPar == false) { WriteLine("Неверно введены параметры"); goto GetEnables; }
            Write("\nВведите количество точек больше 3 (w  для изменения алгоритммов): ");
        }

        public class ResultRoute
        {
            double length;
            string route;
            public ResultRoute(double len, string route)
            {
                length = len;
                this.route = route;
            }
        }

        public partial struct Point
        {
            public int X { get; set; }
            public int Y { get; set; }
        }

        static int Fact(int a) => a <= 1 ? 1 : a * Fact(a - 1);
    }
}