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

プロジェクトオイラーの問題を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

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

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

問８９「ローマ数字」
ローマ数字の記法は一つの数について沢山ある場合が存在する (FAQを見よ). 
しかし, ある数については最良の記法が必ず存在する.

例えば, 16の正しい記法を全て並べてみる.

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

最後の例は, 最小の文字数で表せるという意味で, 最も効率が良い.
11Kのテキストファイルroman.txt は1000個のローマ記法で書かれた数を含んでいる.
これらは, 正しい記法に従っている. 即ち, 大きい数から順に書かれていて, 
引き算ペアのルールにも従っている(このルールについてはFAQを見よ)
但し, 最小の文字数で表されているとは限らない.

最小形で書いたときに, 何文字節約できるかを求めよ.

注: ファイル中の全てのローマ数字には, 5つ以上の同じ文字が連続して含まれることはない.


FAQ: ローマ数字のルール

I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000

基本法則1
全ての文字は値の大きさの降順に並ぶ

基本法則2
引き算ペアについて.
例えば、4は5の1つ前なのでIVと表せる。
文字は値の大きさの降順に並べる必要があるので、
不適当に出てくる小さな値の文字は引くことを明確に示すとも言える。

X (10) + IX (9) として19=XIXと表せる. 
ただし, 8をIIXと二文字以上を引くことは許されない.

1. I, X, Cのみが引き算ペアの最初の文字として許される. 
2. IはVまたはXの前に来ることが許される 
3. XはLまたはCの前に来ることが許される 
4. CはDまたはMの前に来ることが許される






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






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

def f(sIn):
	c = ["DCCCC CM","CCCC CD", "LXXXX XC", "XXXX XL", "VIIII IX", "IIII IV"]
	L = [s.split() for s in c]
	dif = 0
	pIn = open(sIn)
	for s in pIn.readlines():
		dif += len(s)
		for k in L: s = s.replace(k[0],k[1])
		dif -= len(s)
	pIn.close()
	pIn = None
	return dif
	
import os, sys
sIn = os.path.join(os.path.dirname(__file__), "problem089_roman.txt")
s = f(sIn)
print s

節約できる文字の組み合わせをリストに定義しておきます。

ファイルを１行ずつ読んでローマ数字を取得しながら、置換前の文字数は足してから節約した表記に置換し、置換後の文字数は引いて累計していきます。

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

743

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

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

問８８「積和数」
少なくとも2つの自然数 {a1, a2, ... , ak} の集合の和かつ積として表せる自然数Nを積和数と呼ぶ：N = a1 + a2 + ... + ak = a1 × a2 × ... × ak.
例えば, 6 = 1 + 2 + 3 = 1 × 2 × 3.

ある集合の大きさ k に対して,この性質を持つ最小の N を最小積和数と呼ぼう. 
集合の大きさ k = 2, 3, 4, 5, 6 に対する最小積和数は次のとおりである.
k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6

したがって 2≦k≦6 に対して,全ての最小積和数の和は 4+6+8+12 = 30 である. 
8 は和に一度だけカウントされていることに気をつけよう.

実際, 2≦k≦12 に対する最小積和数の完全な集合は {4, 6, 8, 12, 15, 16} なので,その和は 61 である.

2≦k≦12000 に対する全ての最小積和数の和は何か?





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






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

def f(N):
	L, M, maxn = [0]*(N+1), [2], int(1+(N-1)**(0.5))
	while M[0]<=maxn:
		n = reduce(lambda x,y:x*y, M)
		k = n-sum(M)+len(M)
		if 1<k<=N and not(0<L[k]<n): L[k]=n
		if k<=N: M.append(M[-1])
		else: M = M[:-2]+[M[-2]+1]
		
	L = set(L)
	return L, sum(L)
	
n = 12000
L, s = f(n)
print s

まず、例を手計算してもう少し進めてみました。
項目数k、最小積和数n、項目のリストMとして以下の通りです。
 k   n  M
 2:  4: 2,2
 3:  6: 1,2,3
 4:  8: 1,1,2,4
 5:  8: 1,1,2,2,2
 6: 12: 1,1,1,1,2,6
 7: 12: 1,1,1,1,1,3,4
 8: 12: 1,1,1,1,1,2,2,3
 9: 15: 1,1,1,1,1,1,1,3,5
10: 16: 1,1,1,1,1,1,1,1,4,4
11: 16: 1,1,1,1,1,1,1,1,2,2,4
12: 16: 1,1,1,1,1,1,1,1,2,2,2,2

和と積が同じとのことで項目に1がたくさんあるのは明らかです。
そこで、1と1以外に分けて、1以外の要素だけに注目します。
積和数は（1以外の要素積）です。
項目数は（1の要素数）＋（1以外の要素数）です。
ここで、1の要素数は（積和数）－（1以外の要素和）なので、
項目数は（1以外の要素積）－（1以外の要素和）＋（1以外の要素数）です。

次に、1以外の要素リストを昇順に並べてみます。
 k  M
 2: 2,2
 5: 2,2,2
12: 2,2,2,2
 8: 2,2,3
11: 2,2,4
 3: 2,3
 4: 2,4
 6: 2,6
 7: 3,4
 9: 3,5
10: 4,4
以上より、以下のルールで要素リスト候補を作り出します。
・項目数が項目数上限以内ならば、末尾の要素を新要素として追加する。
・項目数が項目数上限を超過したら、末尾要素を削除しておき、新末尾値を＋１する。
　または最後から2個目の値を＋１してここまでのリストにします。

上記の要素リスト候補に対して採用可否を判定することにします。

さらに問題文では要素数kの範囲が指定されますが、
要素リストをどこまで作成するかの限界を決めるために
項目数kのときの最小積和数の上限を求めておきます。
上限のとき、[1, 1, ..., 1, p, p]になります。1の個数は(k-2)個です。
このときの積和数は積＝和なので、
p*p = k-2+p+p
p2 - 2p - (k-2) = 0
pの二次方程式として解いて、正の値をとると以下のとおりです。
p = 1+√(k-1)



１．関数f(N)
・項目数が2以上N以下の最小積和数の重複削除したリストとその和を求めます。

・L, M, maxn = [0]*(N+1), [2], int(1+(N-1)**(0.5))
　L:項目数ごとの最小積和数リスト
　M:1以外の項目リスト候補(要素は昇順)
　maxn:項目値の上限
　です。
　リストLは0クリアしておき最小積和数を設定していきます。
　
・while M[0]<=maxn:
　項目リスト候補Mの最初の値が項目値上限以内なら処理を続けます。

・n = reduce(lambda x,y:x*y, M)
　積和数nは、リストMの要素の積です。
　lambda関数で引数x,yを受け取り、その積x*yを返す無名関数を作り、
　reduce関数でリストMの要素を1つずつ累積的に上記関数に掛けていくことでリストMのすべての要素の積を求めます。

・k = n-sum(M)+len(M)
　項目数kは、（1以外の要素積－1以外の要素和=1の要素数）＋1以外の要素数　です。

・if 1<k<=N and not(0<L[k]<n): L[k]=n
　採用可否の判定です。
　要素数が2以上N以下で、積和数リストLに新規設定または現値より小さければ設定します。

・if k<=N: M.append(M[-1])
　else: M = M[:-2]+[M[-2]+1]
　次の候補を作成します。
　項目数＜項目数上限の場合、末尾の要素を追加します。
　項目数≧項目数上限値なら、末尾要素を削除しておき、新末尾値を＋１する。
　つまり、最後から2個目の値を＋１してここまでのリストとします。

・L = set(L)
　set関数でリストLの値をユニークにします。


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