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

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

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

DouKaku?

METHINKS IT IS A WEASEL

Posted feedbacks - Java

Index

Feed

Other

Link

Pathtraq