2015年11月14日土曜日

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

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

問117「赤タイル, 緑タイル, そして青タイル」
黒い正方形のタイルと, 
2 ユニットの長さの赤のタイル, 
3 ユニットの長さの緑のタイル, 
4 ユニットの長さの青のタイルから選んで組み合わせて, 
5 ユニットの長さの 1 列をタイルで敷く方法はちょうど 15 通りある.


長さ 50 ユニットの 1 列をタイルで敷く方法は何通りあるか.

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






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






私の回答例は以下の通りです。
def e(n, m, d):
	if n not in d:
		d[n] = sum([e(n-i, m, d) for i in xrange(1, m+1)])
	return d[n]

def f(n, m):
	d = {0:0}
	for i in xrange(1, m+1): d[i] = e(i, i-1, d)+1
	return e(n, m, d)

n = 50
m = 4
s = f(n, m)
print s



4個以下の長さのブロック4種類を使って一列にタイルを敷きます。
パターン数辞書dに使うタイルの分の初期化をして求めます。

1.関数e(n, m, d):
・全体がn個で、m個以下のブロックからできているパターン数を返します。
・dは全体がn個の場合のパターン数の辞書(連想配列)です。
 1度計算した値はこの辞書に格納して重複して計算しないようにします。
・全体がn個になる場合のパターン数は、
 ループ変数iが1からmまで1つずつ変化しながら、全体がn-i個の状態の直後にi個ブロックを1つ置く場合のパターン数の累積値です。

2.関数f(n, m)
・全体がn個で、m個以下のブロックからできているパターン数を返します。
・まず、パターン数辞書の初期状態を準備します。
 キー=0の場合、パターン数は0です。
・d[n] = e(i, i-1, d)+1
 0<キーi<mの場合、パターン数は全体がi個で、i-1個以下の長さのブロックからできているパターン数とi個ブロック1つだけ置くパターン数1の和です。
・ここまででパターン数辞書の初期状態が準備できたら、
 関数e(n, m, d)が求める値なので、これを求めて返します。





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

2015年10月11日日曜日

プロジェクトオイラー 問116(別解)

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

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

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

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

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

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

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

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






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






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

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

def f(n, t):
	s = 0
	for m in t:
		d = dd(m)
		s += e(m, n, d) -1
	return s

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



前回の解法は、問114、115を参考に続けて考えたため、終端のブロックが1個かm個かによって関数end1()とendm()として関数を分けていましたが、1個ブロックもm個ブロックもその後にどちらを置いてもいいので本質的に違いはありません。
そこで、
関数end1()とendm()を統合して、終端のブロック数に関係しない関数e()として別解を作成しました。

1.関数e(m, n, d)
・全体がn個で、1個とm個のブロックからできているパターン数を返します。
・dは全体がn個の場合のパターン数の辞書(連想配列)です。
 1度計算した値はこの辞書に格納して重複して計算しないようにします。
・全体がn個になる場合のパターン数は、
 全体がn-1個の後に1個ブロックを1つ置く場合と
 全体がn-m個の後にm個ブロックを1つ置く場合の2系統あるので、この和になります。

2.関数dd(n)
・n個ブロックを使用する場合のパターン数辞書の初期状態を返します。
 1個ブロックとn個ブロックの両方があることを考慮します。
・具体的には以下のとおりです。
 キー=nの場合、1個ブロックn個連続またはm個ブロック1個の場合なのでパターン数は2、
 0<キー<nの場合、1ブロックが連続しているパターンだけなのでパターン数は1、
 キー=0の場合、パターン数は0となります。

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



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

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

2015年8月23日日曜日

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

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

問115「ブロックの組み合わせ方の数え上げ その2」
注意: これは Problem 114 をより難しくした問題である.

長さ n ユニットからなる 1 列上に, 最低 m ユニットの長さを持つ赤ブロックが置かれている. 
ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい).

敷き詰め計数関数 F(m, n) は 1 列に敷き詰める方法が何通りかを表すとする.
例えば, F(3, 29) = 673135 であり, F(3, 30) = 1089155 である.
m = 3 の時, n = 30 がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.
同様に, m = 10 では F(10, 56) = 880711, F(10, 57) = 1148904 であることがわかり, つまり n = 57 がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.
m = 50 のとき, この敷き詰め計数関数が初めて 1,000,000 を超える最小の n の値を求めよ.






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






私の回答例は以下の通りです。
def endb(m, n, bd, rd):
	if n not in bd:
		bd[n] = endb(m, n-1, bd, rd) + endr(m, n-1, bd, rd)
	return bd[n]

def endr(m, n, bd, rd):
	if n not in rd:
		rd[n] = 1 + sum([endb(m, i,bd,rd) for i in xrange(n-m+1)])
	return rd[n]

def f(m, k):
	bd = {0:0, 1:1}
	rd = {m:1}
	for i in xrange(m): rd[i] = 0

	n = 0
	while endb(m, n, bd, rd)+endr(m, n, bd, rd)<=k: n += 1
	return n


m=50
k = 1000000
n = f(m, k)
print n


問114との違いは、以下の2点です。
a.赤ブロックの最小個数が3個固定だったのがm個になったこと。
b.全体の長さを固定にしてパターン数を求めていたことに対して
 パターン数の下限値から全体の長さの最小値を求めること。

そこで、問114で作成した、
全体がn個で終端が黒ブロックのパターン数の関数endb()、
同赤ブロックの関数endr()を上記aに対応できるように改良し、
求める値を返すf()も上記bに合わせて改良します。

1.関数endb(m, n, bd, rd)
・赤ブロックが最小m個、全体がn個で終端が黒ブロックのパターン数を返します。
・問114の関数endb()に引数mを追加し、呼び出す関数endr()も問114のものに引数mを追加するので、それに合わせました。
・bdは終端が黒で全体がn個の場合のパターン数の辞書(連想配列)です。
 rdは終端が赤で全体がn個の場合のパターン数の辞書(連想配列)です。
 いずれも1度計算した値はこれらの辞書に格納して重複して計算しないようにします。
・終端に黒ブロックを置いて全体がn個になる場合、
 全体がn-1個で終端が赤でも黒でも置けるので、これらのパターン数の和になります。

2.関数endr(m, n, bd, rd)
・赤ブロックが最小m個、全体がn個で終端が赤ブロックのパターン数を返します。
・問114の関数endb()に引数mを追加し、固定値2の部分をm-1に改良しました。
・bd、rdは関数endbのときと同様です。
・終端に赤ブロックを置いて全体がn個になる場合は以下の2つの場合があります。
 a.まだ何も置いていなくて長さn個の赤ブロックを置く場合
 b.端が黒でn個まで2個以上のすきまがあり、すきまの長さ+1個の赤ブロックを置く場合
  この場合、置く直前のブロックは黒ブロックの場合だけなのでendb関数を呼び出します。

 aの場合は1パターンなので赤辞書rdのキーnの初期値に1として設定します。
 bの場合はループ変数iを0からnのm個手前まで回して、長さiの黒ブロックで終わって長さn-iの赤ブロックを1つ置くパターン数を足します。

3.関数f(m, k)
・赤ブロックの最小個数mで問題の条件に合うパターン数が下限値k個を超える、全体の長さの最小値を返します。
・bd、rdは関数endbのときと同様です。
 最小の長さが、黒は1個で、赤はm個なので、黒赤それぞれでその値未満のパターン数は0で、その値で1パターンが初期値になります。
 なお、辞書rdには、キーmのとき1を固定で設定し、m未満のキーのときはfor文で回して0を設定します。
・黒赤それぞれのが終端となるパターン数の和が全パターン数です。
 全体の長さnは0から始めて1ずつ増加させながら全パターン数を計算していき、
 この全パターン数が下限値kを超えたら、そのときのnを返します。



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

2015年8月20日木曜日

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

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

問114「ブロックの組み合わせ方の数え上げ その1」
長さ 7 ユニットからなる 1 列上に, 最低 3 ユニットの長さを持つ赤ブロックが置かれている. 
ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい). 
これを敷き詰める方法は, ちょうど 17 通りある.


50 ユニットの長さの 1 列を敷き詰める方法は何通りあるか.

注意: 上の例では起こりえないが, 通常はブロックの大きさが複数混ざっていてもよい. 
例えば, 8 ユニットの長さの 1 列では, 赤(3), 黒(1), 赤(4) を使うことができる.







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






私の回答例は以下の通りです。
def endb(n, bd, rd):
	if n not in bd:
		bd[n] = endb(n-1, bd, rd) + endr(n-1, bd, rd)
	return bd[n]

def endr(n, bd, rd):
	if n not in rd:
		rd[n] = 1 + sum([endb(i,bd,rd) for i in xrange(n-2)])
	return rd[n]

def f(n):
	bd, rd = {0:0, 1:1}, {0:0, 1:0, 2:0, 3:1}
	return endb(n, bd, rd) + endr(n, bd, rd)

n=50
s = f(n)
print s



黒ブロック(長さ1個)または赤ブロック(長さ3個以上)を1つずつ置いていって個数を数えます。
ただし、赤ブロックは連続では置けないので、
順番に並べていく中で終端が赤か黒かで別々の関数にします。

1.関数endb(n, bd, rd)
・全体がn個で終端が黒ブロックのパターン数を返します。
・bdは終端が黒で全体がn個の場合のパターン数の辞書(連想配列)です。
 rdは終端が赤で全体がn個の場合のパターン数の辞書(連想配列)です。
 いずれも1度計算した値はこれらの辞書に格納して重複して計算しないようにします。
・終端に黒ブロックを置いて全体がn個になる場合、
 全体がn-1個で終端が赤でも黒でも置けるので、これらのパターン数の和になります。

2.関数endr(n, bd, rd)
・全体がn個で終端が黒ブロックのパターン数を返します。
・bd、rdは関数endbのときと同様です。
・終端に赤ブロックを置いて全体がn個になる場合は以下の2つの場合があります。
 a.まだ何も置いていなくて長さn個の赤ブロックを置く場合
 b.端が黒でn個まで2個以上のすきまがあり、すきまの長さ+1個の赤ブロックを置く場合
  この場合、置く直前のブロックは黒ブロックの場合だけなのでendb関数を呼び出します。

 aの場合は1パターンなので赤辞書rdのキーnの初期値に1として設定します。
 bの場合はループ変数iを0からnの3つ手前まで回して、長さiの黒ブロックで終わって長さn-iの赤ブロックを1つ置くパターン数を足します。

3.関数f(n)
・問題の条件で長さnで1列を敷き詰めるパターン数を返します。
・bd、rdは関数endbのときと同様です。
 最小の長さは黒が1個で赤が3個なので、黒赤それぞれでこの値未満のパターン数は0で、その値で1パターンというのが初期値になります。
・黒赤それぞれのが終端となるパターン数の和が、求めるパターン数です。


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

2015年8月17日月曜日

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

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

問113「非はずみ数」
ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき, その数を増加数 (increasing number) と呼ぶ; 例えば134468は増加数である.
同様に, 任意の桁の数が自身の右にある桁の数以上であるとき, その数を減少数 (decreasing number) と呼ぶ; 例えば66420がそうである.
増加数でも減少数でもない数を "はずみ"数 ("bouncy" number) と呼ぶ; 155349がそうである.
nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる. 例えば, 100万未満では, はずみ数でない数は12951個しかない. 同様に, 1010未満では277032個しかない.
googol数 (10100) 未満ではずみ数でないものの数を答えよ.






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






私の回答例は以下の通りです。
def g(n):
	if n<2: return 1
	else: return n*g(n-1)

def C(n, m): return g(n)//g(m)//g(n-m)

def H(n, m): return C(n+m-1, m)

def f(n):
	c = H(10, n)-H(10, 0)
	for i in xrange(1, n+1): c += H(10,i)
	c -= 10*n
	return c

n=100
s = f(n)
print s



与えられた数が大きすぎるので桁数ごとに個数を計算して合計することにします。

まず増加数です。
これは0から9までの数字10種類からi個を選ぶ重複組合せです。
重複組合せの個数は公式から以下の通りです。
 10Hi  ...(A)

図にすると、i桁の数字が以下のように表せます。「|」は仕切り棒です。
連続する0|連続する1|・・・|連続する9
つまり、i個の要素を連続する0から連続する9までの10個の部分に分けることと同じです。
重複組合せでは、仕切り棒の本数も含めた格納場所に仕切り棒を入れることを考えます
10個の部分に分けるので必要な仕切り棒は10-1で9本必要です。
つまり、i+9個の格納場所に9本の仕切り棒を格納し、仕切り棒の間には連続する数字を格納することと同じです。
なお仕切り棒が隣合う場合、その間の連続する数字は1つも無いことになります。
重複組合せの個数の式と、重複を許さない組合せの個数の式との関係は以下の通りです。
 nHm = n+m-1Cm  ...(B)
m-1は、仕切り棒の本数です。

それから、最上位が0の場合、桁数がiではなくなってしまいますが、
その個数は最上位1桁だけ0固定で他のi-1桁分は重複組合せなので、
 10Hi-1
この分を差し引くと
 10Hi - 10Hi-1
これを全桁分、つまり桁数iを1からnまで動かして和をとると、
ほとんどの項が打ち消しあって以下だけが残ります。
 10Hn - 10H0  ...(C)

次に減少数です。
減少数と同じように図にすると、i桁の数字が以下のように表せます。
連続する9|連続する8|・・・|連続する0
この重複組合せの個数は上記(A)と同じです。

さらに、増加数と減少数で重複して数えている分を差し引きます。
増加数でも減少数でもカウントしている値は、全桁同じ数字の場合なので、
各桁数ごとに10個あり、n桁以下の範囲では、
10*n  ...(D)
です。

1.g(n)
・階乗n!を返します。
問20のものを流用しました。


2.関数C(n, m)
・n個の中からm個を選ぶ組合せの個数を返します。
・公式から、n!/(m!・(n-m)!) です。

3.関数H(n, m)
・n個の中からm個を選ぶ重複組合せの個数を返します。
・上記(B)をそのまま実装しました。

4.関数f(n)
・10n未満、つまりn桁以下で、はずみ数以外の数の個数を返します。

・c = H(10, n)-H(10, 0)
 増加数の個数です。上記(C)をそのまま実装しました。

・for i in xrange(1, n+1): c += H(10,i)
 減少数の個数です。
 n桁の減少数である上記(A)をそのまま実装し、1桁からn桁の分の和を計算しました。

・c -= 10*n
 増加数と減少数の重複分を差し引きます。
 上記(D)をそのまま実装しました。




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

2015年7月5日日曜日

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

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

問112「はずみ数」
左から右までどの桁もその左の桁を下回らない数を増加数と呼ぶ. 例えば, 134468.
同様に, どの桁もその右の桁を下回らない数を減少数と呼ぶ. 例えば, 66420.
増加数でも減少数でもない正の整数をはずみ数と呼ぶことにする. 例えば, 155349.

100以下にはずみ数が無いのは明らかだが, 1000未満では半数を少し上回る525個がはずみ数である.
実際, はずみ数の割合が50%に達する最少の数は538である.
驚くべきことに, はずみ数はますます一般的になり, 21780でははずみ数の割合は90%に達する.
はずみ数の割合がちょうど99%になる最小の数を求めよ.






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






私の回答例は以下の通りです。
def f(n):
	i, b, c, r = 0, 0.0, 0.0, n/100.0
	while True:
		i += 1
		s = str(i)
		t = "".join([j for j in sorted(s)])
		u = "".join([j for j in sorted(s, reverse=True)])
		if t<s<u: b += 1
		else: c += 1
		if r<=b/(b+c): break

	return i

n=99
s = f(n)
print s



小さい数から順に各桁を昇順降順にソートした値と比較することではずみ数か判定し、件数カウントしその割合を計算しました。

1.関数f(n)
・はずみ数の割合がちょうどn%になる最小の数を返します。
・変数iは候補値、変数bははずみ数の個数、変数cははずみ数以外の個数、変数rは割合です。
・変数sで候補値を文字列にします。
  ループ変数jでひと桁ずつ取り出し、sorted関数で昇順にして再度連結した値を変数tとし、sorted関数のreverse引数をTrueにすることで降順にして再度連結した値を変数uとします。
・変数tとuはそれぞれ増加数と減少数なので、変数sがこれらの間の値であれば、はずみ数と判定します。





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

2015年6月21日日曜日

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

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

問111「重複桁を持つ素数」
重複した桁を含む 4 桁の素数を考える. 

全てが同じにならないのは明らかである: 
1111 は 11 で割り切れ, 2222 は 22 で割り切れ, 以下同様だからである. 

しかし 3 個の 1 を含む 4 桁の素数は 9 つある:
1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

n 桁の素数に対する重複した桁の最大個数を M(n, d) と表すことにしよう. 
ここで d は重複した桁とする. 
またそのような素数の個数を N(n, d) と表し, これらの素数の和を S(n, d) と表す.
よって M(4, 1) = 3 は, 重複した桁を 1 としたときの, 
4 桁の素数に対する重複した桁の最大個数である. 
そのような素数は N(4, 1) = 9 個あり, これらの素数の和は S(4, 1) = 22275 である. 
d = 0 に対しては, 重複した桁は M(4, 0) = 2 個だけ可能であることが分かるが,そのような場合は N(4, 0) = 13 個ある.

同じようにして 4 桁の素数に対して次の結果を得る.

Digit, d M(4, d) N(4, d) S(4, d)
0 2 13 67061
1 3 9 22275
2 3 1 2221
3 3 12 46214
4 3 2 8888
5 3 1 5557
6 3 1 6661
7 3 9 57863
8 3 1 8887
9 3 7 48073

d = 0 から 9 に対して, S(4, d) の総和は 273700 である.

S(10, d) の総和を求めよ.






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






私の回答例は以下の通りです。
def h(n):
	import itertools
	if n==2: return True
	if n<2 or (not n%2): return 0
	for i in itertools.islice(itertools.count(3, 2), None):
		if i*i>n: break
		if not n%i: return 0
	return n

def g(M, w):
	L = []
	for s in M:
		if s[0]=="0":
			for t in w:
				L.append(t+s)
		else:
			for i in xrange(len(s)+1):
				for t in w:
					if i==0 and t=="0": continue
					L.append(s[:i]+t+s[i:])
				
	return L

def f(n):
	SS = 0
	for d in xrange(10):
		w = [str(i) for i in xrange(10) if i!=d]
		S, M = 0, n
		while S==0:
			M -= 1
			L = [str(d)*M]
			for i in xrange(n-M): L = g(L, w)
			L = set(L)
			for t in L: S += h(int("".join(t)))
			
		SS += S
		
	return SS

n=10
s = f(n)
print s



素数を発生させて重複桁があるかチェックする方式でやってみたところ、チェック以前に10桁分の素数の発生がとても1分で終わらないことが判明しました。
そこで、やり方を逆にして、まず重複桁の値を決め、その他の値を重複桁の間や両側に付加して候補値を作り、素数チェックをするようにしました。


1.関数h(n)
・素数ならn、素数以外なら0を返します。
問58の 素数判定関数を改良しました。

・forループではxrange関数で数値を発生させていましたが、
  10桁の整数の途中からオーバーフローになるので
  itertoolsモジュールのislice関数を使うように改良しました。
  
2.関数g(M, w)
・リストMの全要素の両端や文字間に、リストwから取り出した1文字を付加した値を作りリストにまとめて返します。
  但し、後で数値化したときに桁数が減ってしまうことを避けるために、
  リストMの各要素の先頭が0の場合は左端にだけ付加し、
  付加する文字が0の場合は左端以外にだけ付加します。
  

3.関数f(n)
・n桁の素数について問題文のSの合計を返します。
・ループ変数dは重複する桁の値で、0から9の値をとります。
・リストwは重複しない桁の値で、0から9のうち、dと異なる値を持ちます。
・変数Sは、dが重複するn桁の素数の和です。
・変数Mは、重複する桁dの個数です。
・while文では変数Mを1つずつ減らしながらSを計算し0以外になれば終了します。
・変数iは、全体n桁のうちd以外の値の個数です。
・リストLは、関数gでd以外の値をi個付加した候補値のリストです。
  リストLの要素を1つずつ取り出し、連結して数値化し、関数hで素数判定します。
  素数ならば、変数Sに累積していきます。
・whileループを抜けたら、SをSSに累積して、次のdでの処理に続きます。






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

2015年5月23日土曜日

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

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

問110「ディオファントス逆数 その2」
次の等式で x, y, n は正の整数である.

1/x + 1/y = 1/n

n = 1260 では 113 の異なる解があり, この n が解の個数が 100 を超える最小の値である.

解の数が 4,000,000 を超える最小の n を求めよ.

注: この問題は Problem 108 を非常に難しくしたケースである. 総当り法で解ける範囲を超えているので, 賢い解き方が求められる.






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






私の回答例は以下の通りです。
def P(n):
	L, i = [], 1
	if n>0:
		L.append(2)
		while len(L)<n:
			i += 2
			for j in L:
				if not i%j: break
			else:
				L.append(i)
	return L

def mul(L): return reduce(lambda x,y:x*y, L)

def f(m):
	import math
	tmax = int(math.log(m*2, 3))
	p = P(tmax+1)
	nb, kb, Lb, L = 0, 0, [], []
	while len(L)<=tmax:
		L = [1]*(len(L)+1)
		M = [i*2+1 for i in L]
		k = (mul(M)+1)//2
		while k<=m:
			for i in xrange(len(L)):
				if tmax<=1 or (i<len(L)-1 and L[i]==L[i+1]):
					L[i] += 1
					for j in xrange(i):
						if L[j]>L[i]: L[j] = L[i]
					break
			else:
				L = [1]*(len(L)+1)

			M = [i*2+1 for i in L]
			k = (mul(M)+1)//2

		N = [p[i]**j for i,j in enumerate(L)]
		n = mul(N)
		if nb==0 or n<=nb: nb, kb, Lb = n, k, L
	return nb, kb, Lb

m=4000000
n, k, L = f(m)
print "n :", n
print "k :", k
print "L :", L


問108ではnを1つずつ増やしながら解の個数kを求めてkが閾値を超えたら終了というロジックで解きましたが、解の個数kが巨大な数になると、素因数分解の処理が重くて処理が終わりません。

まず、問108からわかっていることは以下のとおりです。
・解の個数kは、n2を2つの約数の積で表したパターンの個数に等しい。

・n2の約数の個数iについて、n2を素因数分解した結果に含まれる各素因数に対して、採用0個の場合も含めたパターン数は各要素数+1であり、これを全素因数の分だけ掛け合わせた積が、約数の個数iということになります。
 例:72の約数の個数は、72=23+32, べき乗の値から、(3+1)x(2+1)=12

・n2の約数の個数iとして、2つの約数の積でn2になる組合せの個数kとして、
 k = (i+1)//2  (小数以下切捨て)です。

上記からnと解の個数kの関係を、例にあるn=1260, k=113の場合を手で計算してみると以下の通りです。

n = 1260
↑積  ↓因数分解 
素数とべきリスト値の累乗リストN = [22, 32, 51, 71] = [4, 9, 5, 7]
↑小さい順の素数にべきリストLの値で累乗
べきリストL = [2, 2, 1, 1]
↓各要素の2乗
べき2乗リスト = [4, 4, 2, 2]
↓各要素に+1する
約数の個数リストM = [5, 5, 3, 3]
↓各要素の積
約数の個数 = 5*5*3*3 = 225

解の個数k = (225+1)//2 = 113

問108ではnから出発して1つずつ因数分解をしていましたが、
一見して明らかに一番取り扱い易そうなのは、上記のべきリストLです。
べきリストLを調整しつつ、kを算出してしきい値判定して、nを特定する方法でいきます。

しきい値mとして、m<kである最小のnを求めるので、
m<kを満たすkが特定されたときにnが最小であるためには、
べきリストLは、左の要素≧右の要素 ...(a)

べきリストLの要素数をtに固定すると、
nが最小になるのは、全要素が1のとき。例 [1,1, ... ,1] 1がt個ある。
べきリストLの要素数tの最大値tmaxは、全要素が1でm=kのときのtの値です。
このとき約数の個数リストMは1*2+1=3だけがtmax個ある状態で、
解の個数k = (3tmax)//2 = m(しきい値)となります。
3tmax = m*2
両辺の対数をとって、
tmax * log3 =log(m*2)
tmax = log(m*2)/log3 = log3(m*2) (小数以下切捨て)...(b)

1.関数P(n)
・小さい方からn個の素数リストを返します。
Problem108で作成した関数を流用します。詳しくはProblem108を参照。

2.関数mul(L)
・リストLの全要素の積を返します。
・reduce文で、第1引数の関数f、第2引数にリストLを設定しています。
・関数fは「lambda x,y:x*y」です。
 無名関数lambdaを使って、引数1と引数2の積を計算します。
・reduce文では関数fの第2引数にリストLの要素を順に渡し、
 関数fの第1引数に関数処理結果を設定します。
 このため、関数fでfの第1引数と第2引数を元に計算することで、累積的な処理が記述できます。
 reduce文は、累積的は処理を短く記述できますが、少しややこしい構文です。

3.関数f(m)
・1/x + 1/y = 1/n(x,y,nは正の整数)となる解の個数kが引数mを超える最小値を求め、n、k、べきリストLを返します。
・べきリストLの要素数の最大値tmaxは、上記(b)をそのまま実装します。
・素数リストpは、関数Pでtmax個の素数を準備します。

・外側のwhileループでは、べきリストの要素数がtmax以下の場合にべきリストを調整して解の候補を探します。
・べきリストLの初期値は全要素1で要素数をループの都度1つずつ増やします。

・内側のwhileループでは、解の個数kがそのしきい値m以下の場合にべきリストを調整して解の候補を探します。

・現在のべきリストに基づいて次のべきリストを調整します。
・iのforループで、べきリストの要素を右から順に見ていきます。
 まず、べきリストの最大要素数が1以下、または「右隣と同じ値」である最初の要素を+1します。
 例:[1] → [2]
 例:[4, 3, 2, 2, 1, 1] → [4, 3, 3, 2, 1, 1]
 さらに、+1した要素の左側は、L[i]にクリアします。
 例:[4, 3, 3, 2, 1, 1] → [3, 3, 3, 2, 1, 1]
 -1する前のリストは当ループが進めばまた出てきます。
 
・forループが最後まで終了したら、べきリストLの要素数を1つ増やして全要素1にクリアします。
 for文のelse句は、for文のループがbreakで途中で抜けずに最後まで終了した直後に実行する処理を記述します。
 例:[3, 2, 1] → [1, 1, 1, 1]

・このようにしてべきリストLを作成したら、チェックします。
 約数の個数リストM、解の個数kを計算します。

・解の個数kがしきい値を超えて内側のwhileループが終了したら、素数とべきリスト値の累乗リストN、そして求める値nを計算し、バックアップしてある値と比較して、最小のnの場合にバックアップするようにします。




解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
n : 9350130049860600
k : 4018613
L : [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1]

2015年5月3日日曜日

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

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

問109「ダーツ」
ダーツゲームでは, プレイヤーは 20 等分に分けられたダーツボードに 3 本のダーツを投げる. 
ダーツボードは 1 から 20 の番号がふられている.


ダーツの点数は, ダーツが刺さった領域の番号によって決まる. 
外側の赤緑の輪の外に刺さったダーツは 0 点である. 
この輪の内側の黒と白の領域はシングル (1 倍) の点数を表している. 
しかし, 外側と内側の赤緑の輪はそれぞれダブル (2 倍) とトリプル (3 倍) の点数である.

ボードの中央の 2 つの同心円はブルやブルズアイと呼ばれる. 
外側のブルは 25 点, 内側のブルはダブルの 50 点である.

ルールには多くのバリエーションがあるが, 最もポピュラーなゲームでは, 
プレイヤーは 301 または 501 点から始まり, 最も早く現在の得点を 0 点に減らしたプレイヤーが勝者となる. 
しかし, 普通は「ダブルアウト」方式でプレイをする. 
この方式では, プレイヤーは勝利するために, 
最後のダーツをダブル (ボードの中央のダブルのブルズアイを含む) に刺さなければならない. 
それ以外で現在の得点を 1 点以下に減らした場合, 
3 本のダーツに対する得点は「バースト(無効)」になる.

プレイヤーが現在の得点で終了できる場合を「チェックアウト」と呼ぶ. 
最も高いチェックアウトは 170: T20 T20 D25 (トリプルの 20 を 2 回とダブルのブル) である.

得点が 6 でチェックアウトする異なるやり方はちょうど 11 通りある.

D3   
D1 D2  
S2 D2  
D2 D1  
S4 D1  
S1 S1 D2 
S1 T1 D1 
S1 S3 D1 
D1 D1 D1 
D1 S2 D1 
S2 S2 D1 

D1 D2 と D2 D1 は, 異なるダブルで終了しているので異なるとみなすことに注意しよう. 
しかし S1 T1 D1 の組み合わせは T1 S1 D1 と同じとみなす.

さらに, 組み合わせを考える上でミスは含まないこととする; 
たとえば, D3 は 0 D3 や 0 0 D3 と同じである.

信じられないことに, 異なるチェックアウトは全部で 42336 通りある.
得点が 100 未満の異なるチェックアウトは何通りあるか.






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






私の回答例は以下の通りです。
def f(n):
	Ls = [i+1 for i in xrange(20)]+[25]
	Ld = [(i+1)*2 for i in xrange(20)]+[50]
	Lt = [(i+1)*3 for i in xrange(20)]
	La = Ls+Ld+Lt
	c = 0

	for i in Ld:
		if i<n: c += 1

	for i in La:
		for j in Ld:
			if i+j<n: c += 1

	for m, i in enumerate(La):
		for j in La[m:]:
			for k in Ld:
				if i+j+k<n: c += 1

	return c

n=100
c = f(n)
print c


何投目で終了するかの別に分けてカウントします。

1.関数f(n)
・n点未満でチェックアウトするときの、場合の数を返します。
・リストLsはシングルの得点リストです。要素は1から20までの整数と25です。
・リストLdはダブルの得点リストです。要素は1から20までの偶数と50です。
・リストLtはトリプルの得点リストです。要素は1から20までの3の倍数です。
・リストLaは全面の得点リストです。
 シングル、ダブル、トリプルのリストを単純に結合したものです。

・1投終了の場合、ダブルのリストLdです。
 この中から得点合計がn未満の場合をカウントします。

・2投終了の場合、1投目は前面リストLa、2投目はダブルのリストLdです。
 二重ループで状況を再現し、得点合計がn未満の場合をカウントします。

・3投終了の場合、
 1投目は前面リストLa、
 2投目は前面リストLaのうち1投目としてカウントしてないもの、
 つまり、リストLaから1投目で採用した位置よりも後の位置で採用します。
 3投目はダブルのリストLdです。
 三重ループで状況を再現し、得点合計がn未満の場合をカウントします。


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

2015年4月4日土曜日

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

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

問108「ディオファントス逆数 その1」
次の等式で x, y, n は正の整数である.

1/x + 1/y = 1/n

n = 4 では 3 つの異なる解がある.
1/5 + 1/20 = 1/4
1/6 + 1/12 = 1/4
1/8 + 1/8 = 1/4

解の数が 1000 を超える最小の n を求めよ.

注: この問題は Problem 110 の易しいケースである. こちらを先に解く事を強く勧める.





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






私の回答例は以下の通りです。
def P(n):
	L, i = [], 1
	if n>0:
		L.append(2)
		while len(L)<n:
			i += 2
			for j in L:
				if not i%j: break
			else:
				L.append(i)
	return L

def g(n, P):
	s, d = n, {}
	for i in P:
		while s>=i:
			if s%i: break
			else:
				while not s%i:
					d[i], s = d.get(i, 0)+1, s//i
		if s<i: break
	return d 

def f(m):
	import math
	i = int(math.log(2*m-1, 2))
	n, k, p = 1, 1, P(i)
	while k<=m:
		n += 1
		d = g(n*n, p)
		i = 1
		for j in d.values(): i *= j+1
		k = (i+1)//2
	return n, k

m=1000
n, k = f(m)
print "n :", n
print "k :", k


問題の式を変形してみます。
1/x + 1/y = 1/n
両辺にnxyを掛けて
ny  + nx  = xy
xy - nx - ny = 0 ...a

式aを2つの数の積で表して差分調整することにします。
xy, nx, nyを展開式の項として持つ式で最も簡単な式は以下の通り。
(x-n)(y-n) = xy - nx - ny + n2 ...b

式bに式aを代入して、
(x-n)(y-n) = n2 ...c

n2を2つの正の整数の積で表し、それぞれ+nすればxとyになります。
つまり、当問題でチェックすべき「解の数」は、
n2を2つの約数の積で表したパターンの個数です。

また、2つの約数の積が元の数になる組合せは、
約数を順に並べて小さい方からと大きい方からそれぞれ1つずつ採用し、
中央値がある場合は中央値を2つ採用した組合せです。
なので、n2の約数の個数i、該当する約数の組合せの個数kとして、以下の通りです。
k = (i+1)/2  (小数点以下切捨て)...d

また、約数の個数iは素因数分解した素因数ごとの採用パターン数の積です。
n2を素因数分解した結果の素因数ごとの要素数jとして、
その採用0個の場合も含めたパターン数j+1について、
全ての素因数の分の積を計算します。
この約数の個数iから、約数ペアの個数kを求め、指定値mを超えるまで処理を繰り返します。

また、素因数分解にあたり素数をいくつまで用意したらいいか検討します。
素因数分解で使用する素数の個数の上限値tについて、
この分だけ最小素数2を累乗しても約数の個数i以上となるので、
2t ≧ i
両辺の対数を取って、
tlog2 ≧ log(i)
t ≧ log(i)/log2 = log2i
式dを代入して、
t ≧ log2(2k-1)
t = log2(2k-1) (小数点以下切り捨て)...e

素因数分解の準備として、素因数分解で使用する素数の個数の上限値tの分だけ素数を用意しておきます。

1.関数P(n)
・小さい方からn個の素数リストを返します。
・リストLは素数リスト、変数iは素数候補です。
・リストLに最初の素数2を設定します。
・3以上の奇数を素数候補として、リストLにある素数で順に割り算します。
 割り算の余りが無い時点で素数候補iは素数ではないので、
 forループをbreakして次の素数候補へ処理がすすみ、
 リストLのすべての素数で割り算の余りがあれば、forループが最後まで回るのでelse句へ進んで素数リストLに素数候補iを追加します。
・上記を指定した素数の個数になるまで続けます。

2.関数g(n, P)
Problem47で作成した関数を流用します。詳しくはProblem47を参照。
・引数nを素数リストPを使って素因数分解し、
 素数をキー、キーごとの分解した個数を値とする辞書(連想配列)を返します。

3.関数f(m)
・1/x + 1/y = 1/n(x,y,nは正の整数)となる解の個数kがmを超える最小値を求め、nとkを返します。
・対数関数を使う準備としてmathモジュールをインポートし式eを実装します。
 math.log関数の引数は、真数、底の順に設定します。
 変数nは問題文の右辺1/nのn、変数kはチェック対象の解の個数です。
・whileループで、解の個数kが指定値mを超えるまで処理を繰り返します。
・変数dは関数gによるn2に対して素数リストpを使用して因数分解した結果の辞書(連想配列)です。
・ループ関数jで因数分解辞書dから、素因数の値に関係なく、素因数ごとの要素数を設定します。
 変数iに、該当する素因数の個数j個に0個採用のケースも含めたj+1を掛けてためます。
・変数kとして、式dを実装します。//関数は割り算の商(整数値)です。





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