METHINKS IT IS A WEASEL in C# DouKaku?

ランダムな文字からMETHINKS IT IS A WEASELを作るプログラムを作れ。

簡単に流れを書いてみます。

１：ランダムな２０文字を持つ文字列をもった３００個作ります。

２：その文字列が"METHINKSITISAWEASEL"に近いものからソートします。

３：それぞれの文字列のなか1文字を別の文字に変化させたものを３つ用意します。

４：それを２：のソートをして上位３００個残す。（９００個あるうちで上位３００個残すということです。）

５：以後３：と４：を繰り返す。

ランダムな文字変化は大文字だけでいいです。簡単にするために空白文字を外してあります。

METHINKS IT IS WEASELができたら終了。３と4の間でソートしたもので一番上位のものを毎回表示させると変化が楽しめます。:-)

Rickard Dawkinsがブラインドウォッチメイカー(現題：盲目の時計職人）の３章で書いていた有名なものです。さらに一般化してもらってもいいです。

参考

http://home.pacbell.net/s-max/scott/weasel.html (JAVA アプレット)
http://en.wikipedia.org/wiki/Weasel_program

3だとなかなか収束しないですね。

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    public static class MethinksItIsLikeAWeasel
    {
        const int CANDIDATE_COUNT = 300;
        const int VALIDATION_COUNT = 3;
        const string GOAL = "METHINKSITISAWEASEL";
        static Random _rnd = new Random();

        internal static void Start()
        {
            var strs = CANDIDATE_COUNT
                .Make( () => new string( GOAL.Length.Make( () => GetChar() ).ToArray() ) )
                .ToArray();

            int g = 0;
            while( strs.First() != GOAL )
            {
                strs = strs
                    .SelectMany( str => VALIDATION_COUNT.Make( () => Replace( str ) ) )
                    .ToArray()
                    .OrderByDescending( s => CalcPoint( s ) )
                    .Take( CANDIDATE_COUNT )
                    .ToArray();
                Console.WriteLine( "{0} {1} {2}", g, CalcPoint( strs.First() ), strs.First() );
                g++;
            }
        }

        static int CalcPoint( string str )
        {
            return str.Select( ( c, i ) => c == GOAL[ i ] ? 1 : 0 ).Sum();
        }

        static string Replace( string str )
        {
            int index = _rnd.Next( str.Length );
            return str.Remove( index, 1 ).Insert( index, GetChar().ToString() );
        }

        static char GetChar()
        {
            return (char)( _rnd.Next( 26 ) + 65 );
        }

        public static IEnumerable<T> Make<T>( this int count, Func<T> func )
        {
            return Enumerable.Range( 0, count ).Select( _ => func() );
        }
    }
}

みんな言ってるけど、３じゃだめですね・・・。評価関数を工夫してどうにかしようと奮闘したけどだめでした。

遺伝子（と呼びたい）に、ムダな領域を追加すると、３でも収束します。実質、変異率を下げたのと同じことですが。

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

DouKaku?

METHINKS IT IS A WEASEL

Posted feedbacks - C#

Index

Feed

Other

Link

Pathtraq