METHINKS IT IS A WEASEL
Posted feedbacks - Nested
Flatten Hiddenkozima
#6288()
[
Common Lisp
]
近さのうまい定義ってそんなに自明じゃないんですね。下のプログラムではアスキーコードの差を足していますが、もっといい方法がありそうです。
文字変化のやり方も焼きなまし法を使うとかいろいろ考えられそうです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | (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個にしています。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #!/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";
|
距離関数の定義がなかったので、とりあえず一致しない文字数を距離の定義としてみました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | 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で書いてみました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 | #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]);
}
}
}
|
ごくごく素直にPythonで実装しました。増やす数(MULTIPLY)が3だと収束しなかったので、5にしてあります。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | 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: を使っています。三つでは収束しないので五つに変えました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | | ゴール 全英字 文字数 上位群 世代数 |
ゴール := '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だとなかなか収束しないですね。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | 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で。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | 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さんありがとう!!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | 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);
}
|
訂正
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #与えた文字列をランダムに一文字交換
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]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #!/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()
|
sawat
#6304()
[
JavaScript
]
他と同じく、3だと収束しないので5です。 また、ブラウザが固まらないようにsetTimeoutを使っています。Rhinoなどで実行する場合は、setTimerのところをwhileループにでもして下さい。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | 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++) |
ytakenaka
#6287()
Rating4/8=0.50
ランダムな文字からMETHINKS IT IS A WEASELを作るプログラムを作れ。
簡単に流れを書いてみます。
１：ランダムな２０文字を持つ文字列をもった３００個作ります。
２：その文字列が"METHINKSITISAWEASEL"に近いものからソートします。
３：それぞれの文字列のなか1文字を別の文字に変化させたものを３つ用意します。
４：それを２：のソートをして上位３００個残す。（９００個あるうちで上位３００個残すということです。）
５：以後３：と４：を繰り返す。
ランダムな文字変化は大文字だけでいいです。簡単にするために空白文字を外してあります。
METHINKS IT IS WEASELができたら終了。３と4の間でソートしたもので一番上位のものを毎回表示させると変化が楽しめます。:-)
Rickard Dawkinsがブラインドウォッチメイカー(現題：盲目の時計職人）の３章で書いていた有名なものです。さらに一般化してもらってもいいです。
参考
[ reply ]