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

　ちょっと遅いですが...。

#! /usr/bin/ruby
    
class Text
    
    GOAL        = 'METHINKSITISAWEASEL'
    CHARACTER_SET = ('A'..'Z').to_a
    
    attr_accessor :text
    
    def create
        self.text = (1..GOAL.length).map { |_| CHARACTER_SET[rand(CHARACTER_SET.length)] }.to_s
        self
    end
    
    def update
        self.text[rand(GOAL.length)] = CHARACTER_SET[rand(CHARACTER_SET.length)]
        self
    end
    
    def rank
        self.text.split('').zip(GOAL.split('')).inject(0) { |r,s| s[0] == s[1] ? r + 1 : r }
    end
    
    def complete?
        self.rank == GOAL.length
    end
    
    def clone
        copy = super
        copy.text = self.text.clone
        copy
    end
end

class Processor
    
    POOL_SIZE    = 300
    COPY_SIZE    = 3
    
    attr_accessor :text_list
    
    def initialize
        self.text_list = (1..POOL_SIZE).map { |_| Text.new.create }.sort { |a,b| b.rank <=> a.rank }
        self
    end
    
    def process
        self.text_list = self.text_list.map { |t| (1..COPY_SIZE).map { |_| t.clone.update } }.flatten.sort { |a,b| b.rank <=> a.rank }.first(POOL_SIZE)
        self
    end
    
    def complete?
        self.text_list.first.complete?
    end
end

i = 1
processor = Processor.new
until processor.complete? do
    puts "process(#{i}): #{processor.text_list.first.text}(#{processor.text_list.first.rank})"
    processor.process
    i = i + 1
end
puts "complete(#{i}): #{processor.text_list.first.text}"

素朴に書いてみました。

Ruby-1.8.x系だと滅茶苦茶遅いですが、Ruby-1.9.1だと阿呆みたいに速くなりますね……。

TARGET = "METHINKSITISAWEASEL".split("")

class Array
  def choice
    self[rand(self.size)]
  end
end

def rand_char
  ('A'..'Z').to_a.choice
end

def gen
  (1..300).map{ (1..TARGET.size).inject(""){|r,s|r+=rand_char()} }
end

def weasel_sort(arr)
  arr.sort_by{|s| rank = 0;s.each_char.with_index{|c, i|;rank += 1 if c != TARGET[i]};rank}
end

def evolve(arr)
  arr.map{|word| (1..10).map{ t=word.dup;i = rand(word.size);t[i]=rand_char;t}}.flatten
end

def generate_passage
  rc = gen
  i = -1
  until rc[0].split("") == TARGET
    i += 1
    rc = evolve rc
    rc = weasel_sort rc
    rc = rc[0..299]
    puts "generation #{i}: ", "\t" + rc[0..5].join(" ")
  end
  return i
end

if $0 == __FILE__
  TARGET = ARGV.fetch(0, "METHINKSITISAWEASEL").upcase.split("")
  generate_passage()
end

DouKaku?

METHINKS IT IS A WEASEL

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq