2013年7月31日水曜日

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

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


問79「パスコードの導出」
オンラインバンクで通常使われるsecurity methodは,パスコードからランダムに選んだ3文字をユーザーに要求するものである.
たとえば, パスコードが531278のとき,2番目, 3番目, 5番目の文字を要求されるかもしれない. このとき, 期待される答えは: 317 である.

テキストファイルkeylog.txtには, ログインに成功した50回の試行が記録されている.
3つの文字が常に順番通りに要求されるとするとき, ファイルを分析して, 
可能なパスコードのなかでもっとも短いものを見つけよ.



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






私の回答例は以下の通りです。
def f(fn):
	L0 = open(fn).read().split()
	L1 = [[[],[]] for i in xrange(10)]
	for s in L0:
		t = [int(i) for i in s]
		for i in xrange(len(t)):
			for j in xrange(len(t)):
				if i!=j: L1[t[i]][int(i<j)].append(t[j])
	L2 = [[sorted(set(t)) for t in s] for s in L1]
	L3 = [[len(s[i]) for i in [0, 1]]+[j] for j, s in enumerate(L2)]
	L4 = sorted([s for s in L3 if s[0]+s[1]])
	L5 = [str(s[-1]) for s in L4]
	return "".join(L5)

if __name__=="__main__":
	import os
	fn = os.path.join(os.path.dirname(__file__), "problem079_keylog.txt")
	print f(fn)



1.関数f(fn)
・キーログファイルfnを分析して、最小文字列長のパスコードを返します。

・リストL0は、キーログファイルの全データを格納した配列リストです。

・リストL1は、各数字の左右にくる数字のリストを要素に持つリストです。
 [数字iの左にくる数字、数字iの右にくる数字]というリストをi番目の要素に持ちます。

・リストL2は、上記リストL1の二重配列の値をユニーク化して昇順に並べます。
 set関数で集合型にすることでユニーク化し、sorted関数でソートします。
 pythonの集合型は、ハッシュ値を持ち、値変更不可、重複値を持てない配列です。

・リストL3は、左右にくるユニーク値の個数のリストを要素に持つリストです。
 [数字iの右にくるユニーク値の個数、数字iの左にくるユニーク値の個数]というリストをi番目の要素に持ちます。

・リストL4は、上記リストL3から未使用数字を除去し、各数字の左にくるユニーク値の個数が少ない順に並べたリストです。
 具体的には左右のユニーク値の個数の和が正(論理的にTrue)の要素だけをリストL3から取り出して設定します。

・リストL5は、上記のリストL4の末尾要素に該当数字が格納されているので、それを文字型にしたリストです。

・ここまで処理して上記リストL5の要素を、連結文字なしで順に連結して返します。

2.関数の外
・fn = os.path.join(os.path.dirname(__file__), "problem079_keylog.txt")
 「__file__」はこのソースコードがあるプログラムファイルそのもののフルパスです。
 os.path.dirnameでこのフォルダを取得し、ファイルパスの区切り文字を挟みながら、キーログファイル名と結合します。

・print f(fn)
 関数fの戻り値を表示します。


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

0 件のコメント:

コメントを投稿