METHINKS IT IS A WEASEL
Posted feedbacks - D
問題文そのまま。
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 | private import std.stdio, std.string, std.algorithm, std.random, std.contracts;
const target = "METHINKSITISAWEASEL";
const capacity = 300;
const children = 5;
Random rand;
static this() {
rand = Random(unpredictableSeed);
}
void main() {
auto strings = new string[capacity];
foreach(ref s; strings) s = randomString;
int generation;
do {
auto temp = new string[strings.length * children];
foreach(i, ref s; temp) s = changeChar(strings[i/children]);
schwartzSort!(distance)(temp);
strings = temp[0..capacity];
writefln("[%s] %s (%s)", ++generation, strings[0], distance(strings[0]));
} while(strings[0] != target);
writefln("Now, we have %s!", target);
}
char randomChar() {
alias UniformDistribution!(int, "[]") Dist;
return Dist('A', 'Z').next(rand);
}
string randomString() {
auto result = new char[target.length];
foreach(ref c; result) c = randomChar;
return assumeUnique(result);
}
string changeChar(string str) {
alias UniformDistribution!(int) Dist;
auto result = str.dup;
result[Dist(0, result.length).next(rand)] = randomChar;
return assumeUnique(result);
}
int distance(string str) {
int d;
assert(str.length == target.length);
foreach(i; 0..target.length) {
if(str[i] != target[i]) ++d;
}
return d;
}
|
ytakenaka
#6287()
Rating4/8=0.50
ランダムな文字からMETHINKS IT IS A WEASELを作るプログラムを作れ。
簡単に流れを書いてみます。
１：ランダムな２０文字を持つ文字列をもった３００個作ります。
２：その文字列が"METHINKSITISAWEASEL"に近いものからソートします。
３：それぞれの文字列のなか1文字を別の文字に変化させたものを３つ用意します。
４：それを２：のソートをして上位３００個残す。（９００個あるうちで上位３００個残すということです。）
５：以後３：と４：を繰り返す。
ランダムな文字変化は大文字だけでいいです。簡単にするために空白文字を外してあります。
METHINKS IT IS WEASELができたら終了。３と4の間でソートしたもので一番上位のものを毎回表示させると変化が楽しめます。:-)
Rickard Dawkinsがブラインドウォッチメイカー(現題：盲目の時計職人）の３章で書いていた有名なものです。さらに一般化してもらってもいいです。
参考
[ reply ]