METHINKS IT IS A WEASEL 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

近さのうまい定義ってそんなに自明じゃないんですね。下のプログラムではアスキーコードの差を足していますが、もっといい方法がありそうです。

文字変化のやり方も焼きなまし法を使うとかいろいろ考えられそうです。

(defun random-char (&optional random-state)
  (code-char (+ 65 (random 26 random-state))))

(defun random-string (length &optional random-state)
  (let ((s (make-string length)))
    (dotimes (i length)
      (setf (elt s i) (random-char random-state)))
    s))

(defun modify (s &optional random-state)
  (let ((i (random (length s) random-state))
        (r (copy-seq s)))
    (setf (elt r i)
          (code-char (+ (random 3 random-state)
                        (char-code (elt s i))
                        -1)))
    r))

(defun weasel (target)
  (let ((state (make-random-state t)))
    (flet ((key (s)
             (loop for c1 across s and c2 across target
               sum (abs (- (char-code c1) (char-code c2))))))
      (do ((strings (loop repeat 300
                      as s = (random-string (length target) state)
                      collect (cons s (key s)))
                    (sort (mapcan (lambda (p)
                                    (loop repeat 3
                                      as s = (modify (car p) state)
                                      collect (cons s (key s))))
                                  strings)
                          #'< :key #'cdr))
           (i 1 (1+ i)))
          ((string= target (caar strings))
           (format t "~D: ~A (~D)~%" i (caar strings) (cdar strings))
           (format t "Finished after ~D steps.~%" i))
        (setf (cdr (nthcdr 299 strings)) nil)
        (format t "~D: ~A (~D)~%" i (caar strings) (cdar strings))))))

(weasel "METHINKSITISAWEASEL")

安直な実装。派生文字列が3つだとうまく収束しなかったので、10個にしています。

#!/usr/bin/perl

use strict;
use warnings;

my @alphabets = "A" .. "Z";
my @strings   = ();
my $goal      = "METHINKSITISAWEASEL";

sub random_int($) { int rand shift }

sub similarity($) {
    my $str   = shift;
    my $score = 0;

    for ( 0 .. length($str) - 1 ) {
        $score++ if substr( $str, $_, 1 ) eq substr( $goal, $_, 1 );
    }
    return $score;
}

sub derive_string($) {
    my $origin_string   = shift;
    my @derived_strings = ();
    for ( 1 .. 10 ) {
        my $derived_string = $origin_string;
        substr( $derived_string, random_int length $origin_string, 1 ) =
          $alphabets[ random_int @alphabets ];
        push @derived_strings, $derived_string;
    }

    return @derived_strings;
}

for ( 1 .. 300 ) {
    my $string = "";
    $string .= $alphabets[ random_int @alphabets ] for 1 .. length $goal;
    push @strings, $string;
}

my $count = 0;
until ( $strings[0] eq $goal ) {
    my @next_gen = ();
    print $count++, ": ", $strings[0], "\n";
    push @next_gen, derive_string $_ for @strings;
    @strings =
      ( map { $_->[1] }
          sort { $b->[0] <=> $a->[0] } map { [ similarity $_, $_ ] } @next_gen )
      [ 0 .. 299 ];
}

print $count, ": ", $strings[0], "\n";

距離関数の定義がなかったので、とりあえず一致しない文字数を距離の定義としてみました。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;


public class Sample177 {
    private static final char[] CHARACTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
    private static final int INITIAL_COUNT = 300;
    private static final int CREATE_COUNT = 3;


    private final Random random_ = new Random();
    private List<String> cache_ = new ArrayList<String>();

    private final String target_;
    private final Comparator<String> comparator_;


    public Sample177(String target) {
        target_ = target;
        comparator_ = new StringDistanceComparator(target);
        init();
    }
    private void init() {
        for (int count = 0; count < INITIAL_COUNT; count++) {
            cache_.add(createString(target_.length()));
        }
        Collections.sort(cache_, comparator_);
    }
    private String createString(int length) {
        StringBuilder builder = new StringBuilder(length);
        for (int index = 0; index < length; index++) {
            builder.append(CHARACTERS[random_.nextInt(CHARACTERS.length)]);
        }
        return builder.toString();
    }

    public String getTop() {
        return cache_.get(0);
    }

    public void nextStep() {
        for (String str: cache_.toArray(new String[0])) {
            for (int index = 0; index < CREATE_COUNT; index++) {
                cache_.add(changeCharacter(str));
            }
        }
        Collections.sort(cache_, comparator_);
        cache_ = cache_.subList(0, INITIAL_COUNT);
    }
    public String changeCharacter(String str) {
        StringBuilder builder = new StringBuilder(str);
        builder.setCharAt(random_.nextInt(str.length()), CHARACTERS[random_.nextInt(CHARACTERS.length)]);
        return builder.toString();
    }


    static class StringDistanceComparator implements Comparator<String> {
        private final String target_;
        public StringDistanceComparator(String target) {
            target_ = target;
        }

        @Override
        public int compare(String o1, String o2) {
            return calcDistance(o1) - calcDistance(o2);
        }
        private int calcDistance(String other) {
            int distance = 0;
            for (int index = 0, len = target_.length(); index < len; index++) {
                distance += (target_.charAt(index) == other.charAt(index))? 0 : 1;
            }
            return distance;
        }
    }


    public static void main(String[] args) {
        String target = "METHINKSITISAWEASEL";
        Sample177 sample = new Sample177(target);

        int index = 1;
        String top = sample.getTop();
        System.out.println(index++ + ":" + top);
        while (!top.equals(target)) {
            sample.nextStep();
            top = sample.getTop();
            System.out.println(index++ + ":" + top);
        }
    }
}

>近さのうまい定義ってそんなに自明じゃないんですね。下のプログラムではアスキーコードの差を足しています

そうなんですよね。うまい定義はどうするか？ってありますね。僕も作成した時はアスキーコードの差を利用したように記憶しています。:-)

お題とは外れますが、せっかくなのでGAで書いてみました。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

const char TargetString[] = "METHINKSITISAWEASEL";
const int TargetStringLength = 20;

const char AlphabetTable[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int AlphabetNum = strlen(AlphabetTable);


int getScore(char *s)
{
    //完全マッチで0が帰る。
    int score = 0;    
    for(int i = 0; i < TargetStringLength; ++i) {
        int d = TargetString[i] - s[i];
//        score -= d > 0 ? d : -d;    //差
        score -= !!d;                //ハミング距離
    }
    return score;    
}


void kousa(char *s1,char *s2)
{
    int r = rand() % TargetStringLength;
    //rの位置で交差させる
    for(int i = r; i < TargetStringLength; ++i){
        char t;
        t = s1[i];
        s1[i] = s2[i];
        s2[i] = t;
    }
}

void henni(char *s)
{
    //1文字を別の文字に変化させる
    s[rand() % (TargetStringLength - 1)] = AlphabetTable[rand() % AlphabetNum];
}

struct Gene{
    char gene[TargetStringLength];
    int result;
};

void GeneToResult(Gene *g)
{
    g->result = getScore(g->gene);
}


int compare(const void *_a,const void *_b)
{
    const Gene *a = (Gene*)_a;
    const Gene *b = (Gene*)_b;
    
    if (a->result > b->result){
        return -1;
    } else if (a->result < b->result) {
        return 1;
    }

    return 0;
}


int main()
{
    srand((unsigned int)time(NULL));

    //初期化
    const int GeneMax = 300;
    Gene genePool[GeneMax];

    for(int i = 0; i < GeneMax; ++i){
        //ランダムな文字列で埋め尽くす
        for(int j = 0; j < TargetStringLength - 1; ++j){
            genePool[i].gene[j] = AlphabetTable[rand() % AlphabetNum];
        }
        genePool[i].gene[TargetStringLength -1] = '\0';
        GeneToResult(&genePool[i]);    //スコアの取得
    }


    //進化させる
    for(int t = 0; t < 1000; t++) {
        //sort
        qsort(genePool,GeneMax,sizeof(Gene),&compare);

        //上位をprint
        printf("times = %d --------------------\n", t);
        for(int i = 0; i < 10; ++i){
            printf("Gene = %s, score = %d \n", genePool[i].gene, genePool[i].result);
        }
        getchar();

        //交叉、突然変異
        for(int i = GeneMax/2; i < GeneMax; i+=2){    //スコアの下位半分を捨てる
            char g1[TargetStringLength];
            char g2[TargetStringLength];
            strcpy(g1 , genePool[rand()%(GeneMax/2)].gene);    //適当な上位を選択
            strcpy(g2 , genePool[rand()%(GeneMax/2)].gene);
            kousa(g1, g2);    //交差
            henni(g1);        //変異
            henni(g2);
            strcpy(genePool[i].gene , g1);
            strcpy(genePool[i+1].gene , g2);
        }
        //評価
        for(int i = 0; i < GeneMax; ++i){
            GeneToResult(&genePool[i]);
        }
    }
}

お題の通りに実装すると収束しませんね。突然変異の確率が高すぎるのが良くないようです。変異する文字数を1にすれば収束しました。(変異がおこる確率をいじるとさらに早く、80世代ほどで終わります)

すいません。問題の設定が甘くて　お許しください。

ごくごく素直にPythonで実装しました。増やす数(MULTIPLY)が3だと収束しなかったので、5にしてあります。

import random

GOAL = "METHINKSITISAWEASEL"

DOMAIN = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

SET_SIZE = 300
MULTIPLY = 5

def create_random():
    s = ""
    for i in range(len(GOAL)):
        s += random.choice(DOMAIN)
    return s

def initial_set():
    s = []
    for i in range(SET_SIZE):
        s += [create_random()]
    return s

def mutate(s):
    i = random.randrange(0, len(s))
    result = s[:i] + random.choice(DOMAIN) + s[i+1:]
    return result

def mutate_set(s):
    result = []
    for e in s:
        for i in range(MULTIPLY):
            result.append(mutate(e))
    return result

def distance(s):
    d = 0
    for c1, c2 in zip(s, GOAL):
        if c1 != c2:
            d += 1
    return d

def sorted_set(s):
    work = [(distance(e), e) for e in s]

    def mycmp(e1, e2):
        return cmp(e1[0], e2[0])
    work.sort(mycmp)
    return work

def main():
    s = initial_set()
    i = 0

    while True:
        new_s = mutate_set(s)
        s = [e for (d,e) in sorted_set(new_s)[:SET_SIZE]]
        print "%04d: %2d %s"%(i + 1, distance(s[0]), s[0])
        if s[0] == GOAL:
            break
        i += 1

if __name__=='__main__':
    main()

Squeak Smalltalk で。

ソートの際の比較は、文字とその位置の一致の数を調べる #howManyMatch: を使っています。三つでは収束しないので五つに変えました。

| ゴール 全英字 文字数 上位群 世代数 |
ゴール := 'METHINKSITISWEASEL'.
文字数 := ゴール size.
全英字 := Character alphabet asUppercase.
上位群 := OrderedCollection new.
300 timesRepeat: [
    | 元文字列 |
    元文字列 := ((1 to: 文字数) collect: [:idx | 全英字 atRandom]) as: String.
    上位群 add: {元文字列 howManyMatch: ゴール. 元文字列}].
世代数 := 0.

World findATranscript:  nil.
[上位群 first last = ゴール] whileFalse: [
    | 候補群 |
    候補群 := OrderedCollection new.
    上位群 do: [:each |
        5 timesRepeat: [
            | 変異文字列 |
            変異文字列 := each last copy.
            変異文字列 at: 文字数 atRandom put: 全英字 atRandom.
            候補群 add: {変異文字列 howManyMatch: ゴール. 変異文字列}]].
    候補群 := 候補群 asArray sort: [:a :b | a first > b first].
    上位群 := 候補群 first: 300.
    Transcript cr; show: (世代数 := 世代数 + 1) -> 上位群 first].
^世代数

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

3だと収束しないので5で。

import scala.util.Sorting.stableSort
class Weasel(val target:String) {
  val rnd = new Random
  val len = target.size
  val chars = (65 to 90).map(_.asInstanceOf[char])
  def newchar = chars(rnd.nextInt(chars.size))

  def similarity(s:String) = (len /: (0 until len)){(r,i) => 
    r-(if(target(i) == s(i)){1}else{0})
  }

  def sort(lst:Seq[String]) = stableSort(lst, similarity _).toList

  def mutate(s:String) = (1 to 5).map{x=> 
    var a = s.toArray
    a(rnd.nextInt(len)) = newchar
    a.mkString("")
  }
 

  def start = {
    val lst = sort((1 to 300).map(x=>(1 to len).map(y=>newchar).mkString("")))
    def iter(ss:List[String], generation:int):unit = {
      printf("Generation %d\n%s\n%s\n\n", generation, "-"*40, ss.take(5).mkString("\n"))
      ss match {
        case head::rest if head == target => ()
        case x => 
          iter(sort(x.flatMap(mutate)).take(300), generation+1)
      }
    }
    iter(lst, 0)
  }
}

new Weasel("METHINKSITISAWEASEL").start

密かに20文字じゃなくて19文字じゃないかと。。。。ちょっと無駄なところを省いて動いています。 perlが入っていれば第一引数の任意の文字列で同じことができます。(コマンドライン|ターミナル)からも動くので遊んでみてください。正規表現で最初点数つけていたのですがまったく速度的に異常なことに.... いろいろ考えさせてもらって楽しかったですytakenakaさんありがとう!!

use strict;

my $goal = uc(@ARGV[0]) || q{METHINKSITISAWEASEL};

my @table;
     # $table[$id]->[0] 文字列
     # $table[$id]->[1] 近似スコア
my $total_calc;
     #キャッシュ数
my $cash = 3; 


$|=1; # 計算途中に結果を見たいのでバッファオフ


INIT: 
      #@tableに300個ランダムな文字列を生成
    for my $id (0..299){
     my @alpha = ("A".."Z");
      for(0..(length($goal)-1)){
        $table[$id]->[0] .= $alpha[int rand(26)];
      }
    }
    
BEGIN:
    ++$total_calc;
    
        #各項目を1文字何かに変えて$cash数分配
    for my $cnt (0..$#table){
     for(1..$cash) {
     $table[$cnt + $_ * 300] = [one_chr_enig($table[$cnt]->[0]),undef];
     }
    }
        #各項目を点数化 0 -> undef
    @table = set_score(@table);
        # 順列にソート
    @table = sort{$b->[1]<=>$a->[1]} @table;
        #@tabel の299以下の要素を切り捨てる
    $#table = 299;

        #結果出力
    print ($table[0]->[0]
              .  q{ (score) : } . $table[0]->[1]
              .  q{ (steps) : } ." $total_calc  \n"
          );
    
unless($table[0]->[1] == length($goal))
 {goto BEGIN};

    #計算結果を算出    
sub set_score {
   my @table = @_;
         for (0..$#table){
              my $str = $table[$_]->[0];
              my @pre =split//,$goal;
              my $score = undef;
                for (0..(length($goal)-1)){
                  if (substr($str, $_, 1) eq $pre[$_]){
                   ++$score;
                  }
                }
              $table[$_]->[1] = $score;
         }
  return @table;
}

    #与えた文字列をランダムに一文字交換
sub one_chr_enig {
  my @str = split//,shift;
  my @alpha = ("A".."Z");
  $str[int rand(length($goal))] =  $alpha[int rand(26)];
  return join("",@str);
}

訂正

    #与えた文字列をランダムに一文字交換
sub one_chr_enig {
  my @str = split//,shift;
  my @alpha = ("A".."Z");
  $str[int rand(length($goal))] =  $alpha[int rand(26)];
  return join("",@str);
}

よりも下記のほうが俄然早いです。

    #与えた文字列をランダムに一文字交換
sub one_chr_enig {
  my $str = shift;
  my @alpha = ("A".."Z");
  substr($str,int rand(length($goal)),1) = $alpha[int rand(26)];
  return $str;
}

収束しないのでmutationしないものも次世代に持ち越してしまうようしてしまいましたが・・・。
     ng = ng + list(g.spawn_mutant()) + [g]

#!/usr/bin/python
# -*- encoding=us-ascii -*-
#
import random


class Gene(object):
  seed = 0
  base_alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  goal = "METHINKSITISAWEASEL"
  memoize = dict()
  def generate_rnd_code(self):
    return ''.join([random.choice(self.base_alpha) for i in range(len(self.goal))])

  def __init__(self, code=None):
    if code is None:
      self.code = self.generate_rnd_code()
    else:
      self.code = code

  def score(self):
    def score(goal, target):
      if goal:
        diff = ord(goal[0]) - ord(target[0])
        return diff * diff + score(goal[1:], target[1:])
        #return abs(diff) + score(goal[1:], target[1:])
      else:
        return 0
    s = score(self.goal, self.code)
    return s
  def which_base_to_mutate(self):
    return random.randint(0, len(self.goal)-1)

  def substitute_candidates(self, base, count):
    #cand = self.base_alpha.replace(base, '')
    cand = self.base_alpha[:]
    cand=list(cand)
    cand.remove(base)
    random.shuffle(cand)
    return cand[:count]

  def spawn_mutant(self, n_children=None):
    if n_children is None:
      n_children = 3
    nth = self.which_base_to_mutate()
    old_base = self.code[nth]
    for new_base in self.substitute_candidates(old_base, n_children):
      yield Gene(code= self.code[:nth] + new_base + self.code[nth+1:])

class GeneVat(object):
  def __init__(self, mass, n_children):
    self.genes = [Gene() for i in range(mass)]
    self.n_children = n_children
    self.mass = mass

  def create_ng(self):
    ng = list()
    for g in self.genes:
      ng = ng + list(g.spawn_mutant()) + [g]
    return ng

  def filter(self, xs):
    def cmp_by_score(x, y):
      xs = x.score()
      ys = y.score()
      if xs < ys:
        return -1
      elif xs > ys:
        return 1
      else:
        assert(xs == ys)
        return 0
    xs.sort(cmp_by_score)
    return xs[:self.mass]

  def evolve(self):
    self.genes = self.filter(self.create_ng())

  def head(self):
    for g in self.genes[:5]:
      print g.score(), g.code


vat = GeneVat(300, 3)
vat.head()
i = 0
while vat.genes[0].score()!= 0:
  i += 1
  vat.evolve()
  print 'generation %i'%i
  vat.head()

他と同じく、3だと収束しないので5です。また、ブラウザが固まらないようにsetTimeoutを使っています。Rhinoなどで実行する場合は、setTimerのところをwhileループにでもして下さい。

function test() {
  var x = "METHINKSITISAWEASEL";
  var data = sort(initialData(300, x.length), x);
  var mutate = 5;
  setTimer(x, data, mutate, 0, 100);
}
function setTimer (x, data, mutateNum, count, interval) {
  setTimeout(function() {
    print(count + " " + data[0] + " " + data[0].differenceFrom(x));
    if (data[0].differenceFrom(x) == 0) {
      return;
    }
    data = mutateAndSelect(x, data, mutateNum);
    setTimer (x, data, mutateNum, count+1, interval);
  }, interval);
}

function mutateAndSelect (x, data, mutateNum) {
  var ar = new Array(data.length * mutateNum);
  for (var i=0, n=data.length; i<n; i++) {
    for (var j=0; j<mutateNum; j++) {
      ar[i*mutateNum + j] = data[i].mutate();
    }
  }
  return sort(ar, x).slice(0, data.length);
}

function sort(data, x) {
  var cache = {};
  data.sort(function (a, b) {
    var da = cache[a] || (cache[a] = a.differenceFrom(x));
    var db = cache[b] || (cache[b] = b.differenceFrom(x));
    return da - db;
  });
  return data;
}

function initialData(num, len) {
  var ar = new Array(num);
  for (var i = 0; i<num; i++) {
    ar[i] = randomString(len);
  }
  return ar;
}
function randomString(len) {
  var chars = new Array(len);
  for (var i = 0; i<len; i++) {
   chars[i] = 65 + Math.floor(26*Math.random());
  }
  return String.fromCharCode.apply(null, chars);
}

String.prototype.differenceFrom = function (str) {
  var diff = Math.abs(this.length - str.length);
  for ( var i=0, n = Math.min(this

DouKaku?

METHINKS IT IS A WEASEL

Posted feedbacks - Flatten