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

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

問９０「平方数を作る２つのさいころ」
立方体の6面それぞれに異なる数字(0から9)が書かれている.2番目の立方体も同様になっている.異なる位置に2つの立方体を隣り合わせることで様々な2桁の数を作ることができる.

例えば, 平方数である64も作ることができる:

事実, 両方の立方体の数字を注意深く選ぶと100以下のすべての平方数を示すことが可能である:
01, 04, 09, 16, 25, 36, 49, 64, そして 81.

例えば, これを実現する一つの方法としては {0, 5, 6, 7, 8, 9} を一方の立方体に, そして {1, 2, 3, 4, 8, 9} を他方の立方体に配置すればよい.
しかし, 6と9を逆さまに回転することを許すと
 {0, 5, 6, 7, 8, 9} と {1, 2, 3, 4, 6, 7} 
のような配列で9つすべての平方数を示す事ができる; 
そうでなければ09を得ることができない.

順番ではなくそれぞれの立方体の数字に着目して配列を区別する.

{1, 2, 3, 4, 5, 6} は {3, 6, 4, 1, 2, 5} と同じものとし
{1, 2, 3, 4, 5, 6} は {1, 2, 3, 4, 5, 9} と異なるものとする.

しかし6と9を逆さにすることを許すために, 最後の例で区別された両方の配列のかわりに, {1, 2, 3, 4, 5, 6, 9} という(要素数が７つに)拡張された配列を使用して2桁の数をつくることにする.

すべての平方数を表示し得る2つの立方体の異なる配列の組はいくつあるか.





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






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

def g(L):
	if   (6 not in L) and (9 in L): L.append(6)
	elif (6 in L) and (9 not in L): L.append(9)
	return L
	
def f():
	import itertools
	L0, c = set([i**2 for i in xrange(1,10)]), 0
	for c1 in itertools.combinations(range(10), 6):
		c1 = g(list(c1))
		for c2 in itertools.combinations(range(10), 6):
			c2 = g(list(c2))
			M0 = [i*10+j for i in c1 for j in c2]
			M1 = [j*10+i for i in c1 for j in c2]
			if not L0-set(M0+M1): c+=1

	return c/2

print f()

まず平方数リストL0と、題意に合う状態をカウントするカウンターcを初期設定します。
このとき、平方数リストは後で集合としての差を計算するのでset関数で集合型にしておきます。
ループ内で1つ目のさいころの目の組の候補c1として、
itertoolsにある順列関数combinationsを使用し、10未満の自然数から重複を許さずに6個選んだ組み合わせを順に作り出し、
さらにそのループ内で2つ目のさいころの目の組の候補c2も同様に作り出します。
このとき関数g(L)にて、6か9のどちらかがあれば、このうちの無い方を追加しておきます。
このようにして作り出したc1とc2の候補のペアがで題意に合うか判定します。

判定は上記c1,c2の２つのリストから二重ループで回してとりだしたすべての要素の組をそれぞれ10の位、1の位とした値を作り出します。
そして、set関数で集合型にして、平方数の集合からこれを引いた差集合が空であれば、すべての平方数が作り出せたことになるので、カウンタを+1します。

点Pと点Qが入れ替わった直角三角形も別としてカウントしているため、
直角三角形の個数はその半分です。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
1217