2012年6月11日月曜日

プロジェクトオイラー Problem19

「プロジェクト オイラー」の問題をpythonでやってみます。

出典:
Project Euler(日本語翻訳サイト)
参考:
サイエンスもの置き場 プロジェクトオイラーを遊び倒すガイド(初級編)

Problem 19
次の情報が与えられている。
・1900年1月1日は月曜日である。
・9月、4月、6月、11月は30日まであり、2月を除く他の月は31日まである。
・2月は28日まであるが、うるう年のときは29日である。
・うるう年は西暦が4で割り切れる年に起こる。
  しかし、西暦が400で割り切れず100で割り切れる年はうるう年でない。
 
20世紀(1901年1月1日から2000年12月31日)で月の初めが日曜日になるのは何回あるか。


私の解答例は以下です。
-----

M = [31,28,31,30,31,30,31,31,30,31,30,31]
def uruu(y, m=3):
	if m<=2: return 0
	if y%400 and (not y%100): return 0
	elif not y%4: return 1
	else: return 0
	
def youbi(y, m):
	yy = [365+uruu(i) for i in xrange(1900, y)]
	mm = [M[i] for i in xrange(m-1)]
	s = sum(yy)+sum(mm)+uruu(y, m)+1
	return s%7
	
def f(ymd0, ymd1):
	s, t, r = str(ymd0), str(ymd1), 0
	y0, m0 = int(s[:4]), int(s[4:6])
	y1, m1 = int(t[:4]), int(t[4:6])
	for i in xrange(y0, y1+1):
		j0, j1 = {y0:m0}.get(i,  1), {y1:m1}.get(i, 12)
		for j in xrange(j0, j1+1):
			if youbi(i, j)==0: r += 1
	return r
	
print f(19010101, 20001231)
-----

・指定期間の日数の累積値を求め、7で割った余りで曜日を判定します。
・リストMは、平年の月別日数リストです。

 うるう年の影響は判定して+1することにします。
・関数を3つ使っています。


1.uruu(y, m=3)
・うるう年の追加日数です。
・2月以前はうるう年に関係なく追加日数は0です。
・%関数は割り算の余りです。
 余りがある(0以外)は論理的にTrueで、余りがない(0)は論理的にFalseです。
・問題文の通り、400で割れて100で割れない年は0、これ以外で4で割れれば1を返します。
・引数を年だけにすると、mの初期値を3月にしてあるので、うるう年かどうかの判定関数としても使用可能です。


2.youbi(y, m)
・指定年月の月初日の曜日を返します。
 曜日は0=日曜日, 1=月曜日,・・・, 6=土曜日です。
・yyは前年までの各年の年間日数のリストです。

 uruu()を年だけ引数にしてうるう年判定をしています。
・mmは最終年について、年初から前月末までの月別日数リストです。

 うるう年調整前状態です。
・sは1900年1月1日から指定月の前月末までの日数です。
 リストyyの和で前年末までの日数、

 リストmmの和で前月末までの日数、
 そして年月指定でのうるう年追加日数、

 さらに1900年1月1日が月曜日になるように調整で1加算しています。
・戻り値は、上記の累積日数を7で割った余りです。


3.f(ymd0, ymd1)
・期間の開始と終了の日づけをyyyymmdd形式の数値で受取り、その期間内の日曜日で始まる月数を返します。
・年ループ変数iと月ループ変数jの二重ループで、期間内の年月を生成し曜日を求め、日曜日ならカウントアップします。
・y0, m0 = int(s[:4]), int(s[4:6])
 開始年、開始月を一度に設定しています。
・{y0:m0}.get(i,  1)
 辞書{y0:m0}は、開始年をキーに開始月を値に持つ辞書です。
 get関数で、年iを判定して開始年y0の場合に開始月m0を返却し、辞書にキーが無い他の年は1を返します。
・j0, j1 = {y0:m0}.get(i,  1), {y1:m1}.get(i, 12)
 月ループ変数初期値j0は、開始年なら開始月m0で、それ以外の年は1月です。
 月ループ変数終了値j1は、終了年なら終了月m1で、それ以外の年は12月です。


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


(追記)
・20120715
 ソースコード部分にSyntaxHighlighterを導入。

0 件のコメント:

コメントを投稿