はてブロ@ama_ch

https://twitter.com/ama_ch

METHINKS IT IS A WEASEL

どう書くorg:METHINKS IT IS A WEASELより、yattomさんの解答を読ませて頂きました。
勝手にコメントで解説?します。解説というかメモかな。


お題:

ランダムな文字からMETHINKS IT IS A WEASELを作るプログラムを作れ。
簡単に流れを書いてみます。
1:ランダムな20文字を持つ文字列をもった300個作ります。
2:その文字列が"METHINKSITISAWEASEL"に近いものからソートします。
3:それぞれの文字列のなか1文字を別の文字に変化させたものを3つ用意します。
4:それを2:のソートをして上位300個残す。(900個あるうちで上位300個残すということです。)
5:以後3:と4:を繰り返す。
ランダムな文字変化は大文字だけでいいです。簡単にするために空白文字を外してあります。
METHINKS IT IS WEASELができたら終了。

解答:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import random

GOAL = "METHINKSITISAWEASEL"  # 求める文字列

DOMAIN = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

SET_SIZE = 300
MULTIPLY = 4

# ランダムな文字列を作る
def create_random():
    s = ""
    for i in range(len(GOAL)):
        s += random.choice(DOMAIN)
    return s

# 文字列を300個作成、リストに格納して返す
def initial_set():
    s = []
    for i in range(SET_SIZE):
        s += [create_random()]
    return s

# 引数の文字列を1文字変えて返す
def mutate(s):
    i = random.randrange(0, len(s))  # 1文字変える位置を決定
    result = s[:i] + random.choice(DOMAIN) + s[i+1:]
    return result

# リスト内の各文字列に対し、1文字違う文字列を5個ずつ作成
def mutate_set(s):
    result = []
    for e in s:
        # 1文字違う文字列を5個作る
        for i in range(MULTIPLY):
            result.append(mutate(e))
    return result

# 求める文字列と引数で、何文字違うか?
def distance(s):
    d = 0
    for c1, c2 in zip(s, GOAL):
        if c1 != c2:
            d += 1
    return d

# 求める文字列に近いものが先頭に来るようにソート
def sorted_set(s):
    work = [(distance(e), e) for e in s]  # (違う文字数, 文字列)のリストを作成
    # ソート用関数
    def mycmp(e1, e2):
        return cmp(e1[0], e2[0])  # 違うアルファベットの数でソート
    work.sort(mycmp)
    return work

def main():
    s = initial_set()  # 最初の300個を生成
    i = 0

    while True:
        new_s = mutate_set(s)  # 300個の各文字列に、1文字違う5個の文字列を生成
        # 求める文字列に近い上位300個を残す
        s = [e for (d,e) in sorted_set(new_s)[:SET_SIZE]]
        # 現状で最もゴールに近い文字列を表示
        print "%04d: %2d %s"%(i + 1, distance(s[0]), s[0])
        if s[0] == GOAL:
            break
        i += 1

if __name__=='__main__':
    main()


人が書いたソースを読むのはとても勉強になる!
すごいなぁ、アイディアが沢山。1文字変える時の処理とか、zipで違う文字数を数えたり。特に僕はまだPythonのイディオムを全然知らないから、こういう時間はなるべく沢山持ちたい。