プロジェクトオイラー 問９８

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問９８「アナグラム平方数」
CARE という単語の各文字をそれぞれ 1, 2, 9, 6 に置き換えることによって, 
平方数 1296 = 362 ができる. 注目すべきことに, 同じ数字の置換をつかうことにより, アナグラムの RACE も平方数 9216 = 962 をつくる. 
CARE (と RACE) を平方アナグラム単語対と呼ぼう. 先頭のゼロは許されず, 
異なる文字が同じ数字をもつこともないとする.

約 2,000 個の一般的な英単語を含む 16K のテキストファイルwords.txt 

(右クリックして "名前をつけてリンク先を保存") を用いて, 
平方アナグラム単語対をすべて求めよ (回文となる単語はそれ自身のアナグラムとはみなさない).

そのような対のメンバーから作られる最大の平方数は何か?

注: 作られるアナグラムは, すべて与えられたテキストファイルに含まれている.






注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def f(sIn):
	import itertools
	W = {}
	pIn = open(sIn)
	for s in pIn.read().replace('"', '').split(","):
		t = "".join(sorted(s))
		W[t] =W.get(t, [])+[s]
	pIn.close()
	pIn = None
	
	for k,v in W.items():
		if len(v)<2: W.pop(k)
		
	N, m = {}, max([len(s) for s in W])
	for i in xrange(int((10**m)**.5)+1):
		s = str(i*i)
		t = "".join(sorted(s))
		N[t] = N.get(t, [])+[s]
	
	for k,v in N.items():
		if len(v)<2: N.pop(k)
		
	nm = 0
	for s in W:
		for wp in itertools.permutations(W[s], 2):
			
			for t in N:
				if len(s)!=len(t): continue
				if len(set(s))!=len(set(t)): continue
				
				for np in itertools.permutations(N[t], 2):
					p = dict([(u, v) for (u, v) in zip(wp[0], np[0])])
					if "".join([p[u] for u in wp[1]])!=np[1]: continue
					i = int(max(np))
					if nm<i: nm, wpm, npm = i, wp, np
					
	return nm,wpm,npm,int(nm**.5)
	
sIn = os.path.join(os.path.dirname(__file__), "p098_words.txt")
s = f(sIn)
print s

１．関数f(sIn)
・単語ファイルsInを読み込んで、問題に合う最大平方数nm、その場合の単語ペアwpmと二乗値ペアnpm、最大平方数の＋の平方根を返します。

・単語辞書Wとして、キーにソート済み構成文字、値にそのアナグラム単語のリストを持つ辞書を作成します。
　アナグラムにならない単語、つまり単語辞書で値リストの要素数が２つ未満の場合は単語辞書からpop関数で削除します。
・同様に二乗値の方も、
　二乗値辞書Nとして、キーにソート済み構成数字、値にそのアナグラム二乗値のリストを持つ辞書を作成します。
　ただし、候補単語の最大文字列長mから最大桁数を計算し、二乗値辞書にはその桁数以下の値を対象にします。
　またアナグラムにならない二乗値、つまり二乗値辞書で値リストの要素数が２つ未満の場合は二乗値辞書からpop関数で削除します。

・単語辞書の値から、アナグラム単語ペアを順列（順番が変われば別扱いとした全組合せ）で作り出します。
　アナグラム単語が２つならば2P2=2通り、３つならば3P2=6通りのペアを作り出します。
・同様に二乗値の方も、アナグラム二乗値ペアを作り出します。
・単語と二乗値とで、桁数と構成文字種類数が同じ場合に比較していきます。
　桁数はlen関数で取得し、構成文字種類数はset関数で構成文字をユニークにしてからlen関数で個数を取得します。

　
・単語ペアwpと二乗値ペアnpのそれぞれ1つ目の値から、文字と数字の一字対応辞書pを作成します。
　この一字対応辞書で単語ペアの2つ目を翻訳して二乗値ペアの2つ目になるかをチェックします。
　チェックNGの場合は次の候補値へ進みます。
　単語ペアと辞書ペアを順列で作り出しているのは、一字対応辞書を作成元をペア1つ目に固定して、
　そのチェック対象をペア2つ目に固定しているためです。
　順番無関係の組合せcombinationではなく、順番が関係する順列permutationsを使用するのはこのためです。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
(18769, ('BOARD', 'BROAD'), ('17689', '18769'), 137)