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のイディオムを全然知らないから、こういう時間はなるべく沢山持ちたい。