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;
		}
	}
}