2015年9月13日日曜日

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

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

問116「赤タイル, 緑タイル, あるいは青タイル」
5 個の黒い正方形のタイルの列を, 赤(長さ 2), 緑(長さ 3), 青(長さ 4)から選んで,この色のついた長方形のタイルでいくつか置き換える.

もし赤のタイルを選んだ場合は, ちょうど 7 通りの方法がある.

もし緑のタイルを選んだ場合は, 3 通りである.

もし青のタイルを選んだ場合は, 2 通りである.

複数の色を混ぜられない場合は, 5 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は 7 + 3 + 2 = 12 通りある.

50 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は何通りあるか. 
ただし複数の色を混ぜることはできず, 少なくとも 1 個は色のついたタイルを使うこと.

注: この問題は Problem 117 に関連する






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






私の回答例は以下の通りです。
def end1(m, n, d1, dm):
	if n not in d1:
		d1[n] = end1(m, n-1, d1, dm)+endm(m, n-1, d1, dm)
	return d1[n]

def endm(m, n, d1, dm):
	if n not in dm:
		dm[n] = end1(m, n-m, d1, dm)+endm(m, n-m, d1, dm)
	return dm[n]

def dd(n):
	d = {n:1}
	for i in xrange(n): d[i] = 0
	return d

def f(n, t):
	s = 0
	for m in t:
		d1, dm = dd(1), dd(m)
		s += end1(m, n, d1, dm) + endm(m, n, d1, dm) -1
	return s

n = 50
t = 2,3,4
s = f(n, t)
print s



問114、115との違いは以下です。
a.m個ブロックも1個ブロックと同様に連続してよい。
b.最低1つは色ブロックが必要。つまり、全部黒1個のパターンは数えない。
c.黒1個ブロックの他に3色あり、3色は混ぜられない。

そこで、問115で作成した、
全体がn個で終端が黒ブロックのパターン数の関数endb()と
同終端が赤ブロックの関数endr()に基づいて、それぞれ、
全体がn個で終端が1個ブロックのパターン数を関数end1()と
同終端がm個ブロックの関数endm()として調整します。

上記aの対応で、endm()は全体個数がn-m個のときのend1()とendm()の和になります。
上記bの対応で、f()では全部が1個ブロックの場合の1パターン分、減らします。
上記cの対応で、3色別々に計算し、合計します。

1.関数end1(m, n, d1, dm)
・全体がn個で、1個とm個のブロックからできていて末尾が1個ブロックのパターン数を返します。
・問115の関数endb()の変数名を変更しただけでまったく同じ関数です。
・d1は終端が1個ブロックで全体がn個の場合のパターン数の辞書(連想配列)です。
 dmは終端がm個ブロックで全体がn個の場合のパターン数の辞書(連想配列)です。
 いずれも1度計算した値はこれらの辞書に格納して重複して計算しないようにします。
・終端に1個ブロックを置いて全体がn個になる場合のパターン数は、
 全体がn-1個で終端が1個ブロック、m個ブロックのときのパターン数の和になります。

2.関数endm(m, n, d1, dm)
・全体がn個で、1個とm個のブロックからできていて末尾がm個ブロックのパターン数を返します。
・d1、dmは関数end1のときと同様です。
・終端にm個ブロックを置いて全体がn個になる場合のパターン数は、
 全体がn-m個で終端が1個ブロック、m個ブロックのときのパターン数の和になります。

3.関数dd(n)
・n個ブロックを使用する場合のパターン数辞書の初期状態を返します。
 具体的には、キー=nの値が1で、キー<nの値が0である辞書(連想配列)を返します。

4.関数f(n, t)
・全体のブロック数nのときの求めるパターン数を返します。
 ただし、引数tは1個ブロックとともに使用するm個ブロックのmに相当する数のタプルです。
 本問では赤(長さ 2), 緑(長さ 3), 青(長さ 4)を使用するので、t=2,3,4となります。
・ループ変数mとして引数tから値を1つずつ取り出します。
・d1、dmとして、終端が1個ブロックとm個ブロックのパターン数辞書を
 関数dd()で初期化した状態で準備します。
・mの値ごとに、終端が1個ブロックの場合と終端がm個ブロックの場合の、
 それぞれのパターン数を関数end1()、関数endm()で求めて合計し、
 全部1個ブロックの場合は数えないのでそのパターン数1を引きます。
・上記を使用するm個ブロックの分だけ累積します。



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