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

C++に移植してみました。

see: 乱数の範囲を限定する

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib> // rand, RAND_MAX
#include <cassert>
#include <ctime>

const std::string goal = "METHINKS IT IS LIKE A WEASEL";

size_t random(size_t n) // [0, n)
{
    assert(n > 0);

    return static_cast<size_t>(std::rand() * (n + 1.0) / (RAND_MAX + 1.0));
}

char random_char()
{
    static const char table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";

    return table[random(sizeof(table))];
}

std::string random_string()
{
    std::string s;

    s.resize(goal.size());

    std::generate(s.begin(), s.end(), random_char);

    return s;
}

class sentence
{
public:
    explicit sentence(const std::string& s = random_string());

    const std::string& str() const
    {
        return _s;
    }

    friend bool operator<(const sentence& lhs, const sentence& rhs)
    {
        return lhs._diff < rhs._diff;
    }

private:
    std::string _s;
    size_t _diff;
};

sentence::sentence(const std::string& s) : _s(s), _diff(0)
{
    assert(s.size() == goal.size());

    for (size_t i = 0; i < s.size(); ++i)
    {
        if (s[i] != goal[i])
        {
            ++_diff;
        }
    }
}

int main()
{
    std::srand(std::time(NULL));

    const size_t count = 300;

    std::vector<sentence> v(count);

    for (size_t generation = 1; ; ++generation)
    {
        std::sort(v.begin(), v.end());

        v.erase(v.begin() + count, v.end());

        std::cout << std::setw(4) << generation << ": " << v.front().str() << std::endl;

        if (v.front().str() == goal)
        {
            break;
        }

        for (size_t i = 0; i < count; ++i)
        {
            std::string s = v[i].str();

            s[random(s.size())] = random_char();

            v.push_back(sentence(s));
        }
    }
}

最終の文字列を"METHINKS IT IS A WEASEL"にして、２：のソートをシュウォーツ変換っぽく。あとやっぱり、派生が3つだと収束しないので5つで。

see: Schwartzian transform

#include <algorithm>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string>
#include <utility>
#include <vector>

const std::string GOAL("METHINKS IT IS A WEASEL");
const std::size_t MULTI_NUM = 5;
const std::size_t INIT_SIZE = 300;

typedef std::vector<std::string> strlist_t;
typedef std::pair<std::string, std::string> keyed_t;

char
gen_char()
{
  static const std::string CANDIDATES("ABCDEFGHIJKLMNOPQRSTUVWXYZ ");
  return CANDIDATES[std::rand()%CANDIDATES.size()];
}

std::string
gen_seed()
{
  std::string seed(GOAL.size(), '\0');
  std::generate(
      seed.begin(), seed.end(),
      gen_char);
  return seed;
}

char
diff_char(const char l, const char r)
{
  return l < r ? r - l : l - r;
}

keyed_t
make_diff(const std::string& seed)
{
  std::string diff(seed.size(), '\0');
  std::transform(
      seed.begin(), seed.end(),
      GOAL.begin(),
      diff.begin(),
      diff_char);
  return std::make_pair(diff, seed);
}

bool
diff_cmp(const keyed_t& lhs, const keyed_t& rhs)
{
  return lhs.first < rhs.first;
}

std::string
extract_seed(const keyed_t& dpair)
{
  return dpair.second;
}

void
sort_seeds(strlist_t& seeds)
{
  std::vector<keyed_t> difflist;
  difflist.reserve(seeds.size());

  std::transform(
      seeds.begin(), seeds.end(),
      std::back_inserter(difflist),
      make_diff);
  std::sort(
      difflist.begin(), difflist.end(),
      diff_cmp);
  std::transform(
      difflist.begin(), difflist.end(),
      seeds.begin(),
      extract_seed);
}

int main()
{
  strlist_t seeds;
  seeds.reserve(INIT_SIZE);
  // 1:
  std::generate_n(
      std::back_inserter(seeds),
      INIT_SIZE,
      gen_seed );
  // 2:
  sort_seeds(seeds);

  std::size_t generation = 0;
  while ( 1 )
  { // 3:
    strlist_t new_seeds;
    new_seeds.reserve(INIT_SIZE*MULTI_NUM);
    for ( strlist_t::const_iterator it = seeds.begin();
        it != seeds.end(); ++it )
      for ( int i = 0; i < MULTI_NUM; ++i )
        new_seeds.push_back(
            std::string(*it)
              .replace(std::rand()%it->size(), 1, 1, gen_char()));
    seeds.swap(new_seeds);
    // 4:
    sort_seeds(seeds);
    seeds.erase(seeds.begin()+INIT_SIZE, seeds.end());

    std::cout << std::setw(4) << ++generation <<
      " : \"" << seeds.front() << "\"\n";
    if ( seeds.front() == GOAL )
      break;
  }

  return 0;
}

DouKaku?

METHINKS IT IS A WEASEL

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq