METHINKS IT IS A WEASEL in C DouKaku?

METHINKS IT IS A WEASEL

ランダムな文字から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

post comment

Posted feedbacks - C

お題とは外れますが、せっかくなので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]);
        }
    }
}

DouKaku?

METHINKS IT IS A WEASEL

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq