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

namespace Methinks
{
    class Program
    {
        static String GOAL = "METHINKSITISAWEASEL";
        static String CHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

        public static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            
            int CAPACITY_SMALL = 300;    //容量
            int CHILDREN = 3;            //子供の数
            int INTRON = 4;                //ムダ領域
            SortedList<int, String>[] pools = new SortedList<int, String>[] {
                new SortedList<int, String>(),
                new SortedList<int, String>()
            };
            Random rand = new Random();
            
            for (int i = 0; i < CAPACITY_SMALL; i++) {
                StringBuilder sb = new StringBuilder();
                for (int n = 0; n < (GOAL.Length + INTRON); n++) {
                    sb.Append(CHARS[rand.Next(CHARS.Length)]);
                }
                AddMember(pools[0], sb.ToString());
            }

            int g = 0;
            int turn = g % 2;
            while (pools[turn].Values[0].Substring(0, GOAL.Length) != GOAL) {
                Console.WriteLine("{0}: Top = [{1}], {2}", g, pools[turn].Values[0], pools[turn].Keys[0]);

                int next = (g + 1) % 2;
                pools[next].Clear();
                for (int i = 0; i < CAPACITY_SMALL; i++) {
                    
                    for (int c = 0; c < CHILDREN; c++) {
                        int pos = rand.Next(GOAL.Length + INTRON);
                        StringBuilder child = new StringBuilder();
                        child.Append(pools[turn].Values[i].Substring(0,pos));
                        child.Append(CHARS[rand.Next(CHARS.Length)]);
                        child.Append(pools[turn].Values[i].Substring(pos+1));
                        AddMember(pools[next], child.ToString());
                    }
                }
                g++;
                turn = g % 2;
            }
                
            Console.WriteLine("{0}: Top = [{1}], {2}", g, pools[turn].Values[0], pools[turn].Keys[0]);
            Console.Write("Press any key to continue . . . ");
            Console.ReadKey(true);
        }
        static void AddMember(SortedList<int, String> pool, String member) {
            int score = GetScore(member);
            while (pool.ContainsKey(score)){
                score++;
            }
            pool.Add(score, member);
        }
        static int GetScore(String s) {
            int score = 0;
            for (int i = 0; i < GOAL.Length; i++){
                if (s[i] == GOAL[i]){
                    score--;
                }
            }
            return score * 1000;
        }
    }
}