2015年03月11日

C#でDawkins' weasel プログラムを書く

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その76

■問題 (出題者:ytakenaka さん)
ランダムな文字からMETHINKS IT IS A WEASELを作るプログラムを作れ。
簡単に流れを書いてみます。
1:ランダムな20文字を持つ文字列をもった300個作ります。
2:その文字列が"METHINKSITISAWEASEL"に近いものからソートします。
3:それぞれの文字列のなか1文字を別の文字に変化させたものを3つ用意します。
4:それを2:のソートをして上位300個残す。(900個あるうちで上位300個残すということです。)
5:以後3:と4:を繰り返す。
ランダムな文字変化は大文字だけでいいです。簡単にするために空白文字を外してあります。
METHINKS IT IS WEASELができたら終了。3と4の間でソートしたもので一番上位のものを毎回表示させると変化が楽しめます。:-)
Rickard Dawkinsがブラインドウォッチメイカー(現題:盲目の時計職人)の3章で書いていた有名なものです。さらに一般化してもらってもいいです。
参考

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



巡回セールスマン問題を解く で示した遺伝的アルゴリズム(genetic algorithm)の簡易版といった感じですね。

「さらに一般化しても」とあるので、任意の文字列(すべて大文字)を与えられるようにしています。
でも、上記の通りコードを書いても、"METHINKSITISAWEASEL" よりも、すこし長めの文字列を与えると、僕の書き方が悪いのかいつになっても答えが求まりませんでした。

しかたないので、上記 3の処理をすこし変更しています。
示されたやり方だと、3つの子孫は、親の文字列よりも求める文字列との一致度が悪くなってしまう確率のほうが高いように思います。
そのため、自分自身も含めて3つを残すようにしています。こうすれば、生成した子孫は、求める文字列よりも類似度が親よりも悪くなることがありません。

うごかしてみると、直ぐに答えが見つかりました。

どのように文字列が変化していくのかを分かるように、途中結果を表示するようにしています。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;
using System.Linq.Expressions;

namespace Doukaku.Org {
    public  class Program  {
        public static void Main() {
            Solver solver = new Solver();
            //var s = solver.Execute("METHINKS IT IS A WEASEL");
            var s = solver.Execute("THE PEN IS MIGHTER THAN THE SWORD");
            Console.WriteLine(s);
            Console.ReadLine();
            s = solver.Execute("The quick brown fox jumps over the lazy dog".ToUpper());
            Console.WriteLine(s);
            Console.ReadLine();
        }
    }

    public class Solver {
        private const string alphabets = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
        private const int SetSize = 300;
        private const int IncreaseCount = 3;
        private readonly int CharCount = alphabets.Length;

        private string target;
        private Random rnd = new Random();

        public string Execute(string target) {
            this.target = target;
            var lines = CreateLines(target.Length);
            while (lines[0] != target) {
                lines = Survive(IncreaseLines(lines));
                Console.WriteLine("{0} {1}", lines[0], Distance(lines[0]));
            }
            return lines[0];
        }

        private IEnumerable<string> IncreaseLines(IEnumerable<string> list) {
            foreach (var s in list) {
                yield return s;   // 自分自身も残す。
                // 新たに作るのは2つの文字列。
                for (int i = 0; i < IncreaseCount - 1; i++)
                    yield return Mutate(s);
            }
        }

        // 文字列の変異
        private string Mutate(string s) {
            var ary = s.ToCharArray();
            ary[rnd.Next(target.Length)] = RnadomChar();
            return new string(ary);
        }

        // 生き延びる  上位setSize個だけを残す
        private IList<string> Survive(IEnumerable<string> list) {
            return list.OrderBy(s => Distance(s)).Take(SetSize).ToList();
        }

        // 長さlengthの文字列をsetSize個ランダムに生成する。
        private IList<string> CreateLines(int length) {
            return Enumerable.Range(1, SetSize)
                             .Select(n => MakeRandomString(length))
                             .OrderBy(s => Distance(s))
                             .ToList();
        }

        // 長さlengthの文字列をランダムに生成する。
        private string MakeRandomString(int length) {
            return Enumerable.Range(1, length)
                             .Aggregate("", (r, i) => r + RnadomChar());
        }

        // 求めたい文字列との差異を数値化して返す。0 ならば 一致。
        private int Distance(string s) {
            return s.Select((c, ix) => c == target[ix] ? 0 : 1).Sum();
        }

        // ランダムに一文字を返す。
        private char RnadomChar() {
            return alphabets[rnd.Next(CharCount)];
        }
    }
}



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52408065