using System;
using System.Collections.Generic;
using System.Text;

namespace ml
{
    public class Citizen
    {
        private static int _nextId = 0;

        public int Id { get; private set; }
        public int Fitness { get; private set; }
        public string Value { get; set; }

        // Not necessary, but fun...
        public Citizen Mother { get; set; }
        public Citizen Father { get; set; }

        public Citizen()
        {
            Id = _nextId;
            _nextId++;

            Fitness = int.MaxValue;
            Value = "";

            Mother = null;
            Father = null;
        }

        public override string ToString()
        {
            return string.Format("Id: {0:D6}, Value: {1}, Fitness: {2:D4}, Mother: {3:D6}, Father: {4:D6}",
                Id, Value, Fitness, (Mother == null) ? 0 : Mother.Id, (Father == null) ? 0 : Father.Id);
        }

        public void SetFitnessToTarget(string target)
        {
            int fitness = 0;

            for (int i = 0; i < target.Length; i++)
            {
                int difference = target[i] - Value[i];
                fitness += Math.Abs(difference);
            }

            Fitness = fitness;
        }
    }

    public class Simulation
    {
        private readonly string POSSIBLE_CHARACTERS = " `1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:\"ZXCVBNM<>?";

        private List<Citizen> m_population;
        private Random m_random = new Random();
        private string m_target = "";
        private int m_populationSize = 0;
        private double m_mutationRate = 0.0;
        DateTime m_startTime;
        DateTime m_endTime;

        public Simulation(string target, int populationSize, double mutationRate)
        {
            m_target = target;
            m_populationSize = populationSize;
            m_mutationRate = mutationRate;
            m_population = new List<Citizen>(populationSize);

            Console.WriteLine("Target: {0}, Population Size: {1}, Mutation Rate: {2}", target, populationSize, mutationRate);

            // The first generation. About the same intelligence as most politicians...
            for (int i = 0; i < populationSize; i++)
            {
                Citizen c = new Citizen();
                c.Value = GenerateRandomString(target.Length);
                m_population.Add(c);
            }
        }

        void CalculateTheFitnessOfTheCitizens()
        {
            m_population.ForEach((c) => { c.SetFitnessToTarget(m_target); });
        }

        void SortThePopulationByFitness()
        {
            m_population.Sort((left, right) => left.Fitness.CompareTo(right.Fitness));
        }

        void RemoveTheWeakestCitizens()
        {
            m_population.RemoveRange(m_populationSize / 2, m_populationSize / 2);
        }

        string GenerateRandomString(int length)
        {
            StringBuilder sb = new StringBuilder(length);

            for (int i = 0; i < length; i++)
            {
                sb.Append(POSSIBLE_CHARACTERS[m_random.Next(POSSIBLE_CHARACTERS.Length)]);
            }

            return sb.ToString();
        }

        void ApplyRandomMutation(ref StringBuilder value)
        {
            value[m_random.Next(value.Length)] = POSSIBLE_CHARACTERS[m_random.Next(POSSIBLE_CHARACTERS.Length)];
        }

        void GetRandomParents(out Citizen mother, out Citizen father)
        {
            int a = m_random.Next(m_population.Count);
            int b = m_random.Next(m_population.Count);

            while (b == a) //Don't allow the same parent for both
            {
                b = m_random.Next(m_population.Count);
            }

            mother = m_population[a];
            father = m_population[b];
        }

        Citizen Mate(Citizen mother, Citizen father)
        {
            StringBuilder newValue = new StringBuilder();
            Citizen child = new Citizen();

            child.Mother = mother;
            child.Father = father;

            for (int i = 0; i < mother.Value.Length; i++)
            {
                // Determine dominant features randomly
                bool fatherIsDominant = m_random.NextDouble() < .5;

                if (fatherIsDominant)
                    newValue.Append(father.Value[i]);
                else
                    newValue.Append(mother.Value[i]);
            }

            double chanceOfMutation = m_random.NextDouble();
            if (chanceOfMutation < m_mutationRate)
                ApplyRandomMutation(ref newValue);

            child.Value = newValue.ToString();

            return child;
        }

        void MateThePopulation()
        {
            var parents = m_population;
            var children = new List<Citizen>(m_populationSize);

            for (int i = 0; i < m_populationSize; i++)
            {
                Citizen mother = null;
                Citizen father = null;

                GetRandomParents(out mother, out father);

                var child = Mate(mother, father);

                children.Add(child);
            }

            m_population = children; //Children are the future...
        }

        void PrintPaternalLineage(Citizen c)
        {
            Citizen father = c.Father;
            Console.Write("{0} ", c.Id);
            while (father != null)
            {
                Console.Write("=> {0} ", father.Id);
                father = father.Father;
            }
            Console.WriteLine();
        }

        public void Run(int maxGenerations)
        {
            Console.WriteLine("Starting simulation");
            m_startTime = DateTime.Now;

            for (int i = 0; i < maxGenerations; i++)
            {
                CalculateTheFitnessOfTheCitizens();
                SortThePopulationByFitness();

                var fittest = m_population[0];

                Console.WriteLine("[Gen {0:D5}] {1}", i, fittest);

                // Game over...
                if (fittest.Fitness == 0)
                {
                    m_endTime = DateTime.Now;
                    Console.WriteLine();
                    Console.WriteLine("Perfection reached after {0} generations. Time elapsed: {1}", i, (m_endTime - m_startTime).ToString());
                    Console.WriteLine();
                    PrintPaternalLineage(fittest);
                    break;
                }

                RemoveTheWeakestCitizens();
                MateThePopulation();
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Simulation s = new Simulation(
                target: "Genetic algorithms are cool!",
                populationSize: 2048,
                mutationRate: 0.25);

            s.Run(maxGenerations: 100);

            Console.WriteLine("Press any key...");
            Console.ReadKey();
        }
    }
}