using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
using System.Data;
using System.Diagnostics;

namespace Elitist
{
    internal class Program
    {
        private static Random random = new Random(0);
        private static int alpha = 1;
        private static int beta = 10;
        private static double rho = 0.5;
        private static double Q = 100;

        public static void Main(string[] args)
        {
            try
            {
                int numCities = 60;
                int numAnts = 4;
                int[][] dists = MakeGraphDistances(numCities);
                int[][] ants = InitAnts(numAnts, numCities);
                int[] bestTrail = Program.BestTrail(ants, dists);
                double bestLength = Length(bestTrail, dists);

                //Console.WriteLine("\nBest trail found:");
                Display(bestTrail);
                //Console.WriteLine("\nLength of best trail found: " + bestLength.ToString("F1"));
                Console.ReadLine();
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
                Console.ReadLine();
            }
        }

        private static int[][] InitAnts(int numAnts, int numCities)
        {
            int[][] ants = new int[numAnts][];
            for (int k = 0; k <= numAnts - 1; k++)
            {
                int start = random.Next(0, numCities);
                ants[k] = RandomTrail(start, numCities);
            }
            return ants;
        }

        private static int[] RandomTrail(int start, int numCities)
        {
            int[] trail = new int[numCities];
            for (int i = 0; i <= numCities - 1; i++)
                trail[i] = i;

            for (int i = 0; i <= numCities - 1; i++)
            {
                int r = random.Next(i, numCities);
                int tmp = trail[r];
                trail[r] = trail[i];
                trail[i] = tmp;
            }

            int idx = IndexOfTarget(trail, start);
            int temp = trail[0];
            trail[0] = trail[idx];
            trail[idx] = temp;
            return trail;
        }

        private static int IndexOfTarget(int[] trail, int target)
        {
            for (int i = 0; i <= trail.Length - 1; i++)
                if (trail[i] == target) return i;
            throw new Exception("Target not found in IndexOfTarget");
        }

        private static double Length(int[] trail, int[][] dists)
        {
            double result = 0.0;
            for (int i = 0; i <= trail.Length - 2; i++)
                result += Distance(trail[i], trail[i + 1], dists);
            return result;
        }

        private static int[] BestTrail(int[][] ants, int[][] dists)
        {
            double bestLength = Length(ants[0], dists);
            int idxBestLength = 0;
            for (int k = 1; k <= ants.Length - 1; k++)
            {
                double len = Length(ants[k], dists);
                if (len < bestLength)
                {
                    bestLength = len;
                    idxBestLength = k;
                }
            }
            int numCities = ants[0].Length;
            int[] bestTrail_Renamed = new int[numCities];
            ants[idxBestLength].CopyTo(bestTrail_Renamed, 0);
            return bestTrail_Renamed;
        }

        private static int[][] MakeGraphDistances(int numCities)
        {
            int[][] dists = new int[numCities][];
            for (int i = 0; i <= dists.Length - 1; i++)
                dists[i] = new int[numCities];
            for (int i = 0; i <= numCities - 1; i++)
            {
                for (int j = i + 1; j <= numCities - 1; j++)
                {
                    int d = random.Next(1, 9);
                    dists[i][j] = d;
                    dists[j][i] = d;
                }
            }
            return dists;
        }

        private static double Distance(int cityX, int cityY, int[][] dists)
        {
            return dists[cityX][cityY];
        }

        private static void Display(int[] trail)
        {
            for (int i = 0; i <= trail.Length - 1; i++)
            {
                Console.Write(trail[i] + " ");
                if (i > 0 && i % 20 == 0) Console.WriteLine("");
            }
            Console.WriteLine("");
        }
    }
}