using System;

using System.Collections.Generic;

using System.Linq;

    public class Program

    {

        const string alphabet = "qwertyuiopasdfghjklzxcvbnm !QWERTYUIOPASDFGHJKLZXCVBNM";

        static Random rnd = new Random();

        const string target = "Hello World!";

        const int mutationChance = 20;

​

        public static void Main(string[] args)

        {

            List<Entity> entities = GenEntities(500);

            uint gen = 0;

​

            double bestFitness = -1;

            while (entities.Select(x => x.fitness).Max() != 1)

            {

                gen++;

                // Set fitness

                entities.ForEach(x => x.setFitness(target));

                // Order by fitness

                entities = entities.OrderBy(x => x.fitness).ToList();

                // Kill worst half

                const int kill = 250;

                entities.RemoveRange(0, kill);

                // Gen them again

                entities = Reproduce(entities, kill);

​

                bestFitness = entities.Select(x => x.fitness).Max();

                Console.Write(bestFitness.ToString().PadRight(25));

                Console.WriteLine(entities.Where(x => x.fitness == bestFitness).First().output);

            }

​

            Console.WriteLine("Generation: " + gen);

            Entity ThatOne = entities.Where(x => x.fitness == entities.Select(a => a.fitness).Max()).First();

            Console.WriteLine("Best Entity: {0}, {1}", ThatOne.output, ThatOne.fitness);

        }

​

        static List<Entity> GenEntities(int n = 1000)

        {

            List<Entity> list = new List<Entity>();

​

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

            {

                string s = "";

                for (int j = 0; j < target.Length; j++)

                {

                    s += alphabet[rnd.Next(alphabet.Length)];

                }

                list.Add(new Entity(s, 0));

            }

​

            return list;

        }

​

        static List<Entity> Reproduce(List<Entity> entities, int reproduceN)

        {

            List<Entity> newEntities = new List<Entity>();

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

            {

                // Choose first one

                Entity first = /*entities[rnd.Next(entities.Count)]*/ entities.Last();

                // Choose second one

                Entity second = entities[rnd.Next(entities.Count)];

​

                // Choose genetic line

                int line = rnd.Next(1, target.Length - 1);

                string output = "";

                // Combine entity info

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

                {

                    if (rnd.Next(101) < mutationChance)

                        output += alphabet[rnd.Next(alphabet.Length)];

                    else

                        output += first.output[j];

                }

                for (int j = line; j < target.Length; j++)

                {

                    if (rnd.Next(101) < mutationChance)

                        output += alphabet[rnd.Next(alphabet.Length)];

                    else

                        output += second.output[j];

                }

                newEntities.Add(new Entity(output, 0));

            }

            entities.AddRange(newEntities);

            return entities;

        }

    }

​

    class Entity

    {

        public string output = "";

        public double fitness = 0;

​

        public Entity(string output, double fitness)

        {

            this.output = output;

            this.fitness = fitness;

        }

​

        public void setFitness(string target)

        {

            int right = 0;

            for (int i = 0; i < target.Length; i++)

            {

                if (target[i] == output[i])

                    right++;

            }

            fitness = right / (double)target.Length;

        }

    }