日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。
問７９「パスコードの導出」
オンラインバンクで通常使われる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)
１．関数f(fn)
・キーログファイルfnを分析して、最小文字列長のパスコードを返します。
・リストL0は、キーログファイルの全データを格納した配列リストです。
・リストL1は、各数字の左右にくる数字のリストを要素に持つリストです。
［数字iの左にくる数字、数字iの右にくる数字］というリストをi番目の要素に持ちます。
・リストL2は、上記リストL1の二重配列の値をユニーク化して昇順に並べます。
set関数で集合型にすることでユニーク化し、sorted関数でソートします。
pythonの集合型は、ハッシュ値を持ち、値変更不可、重複値を持てない配列です。
・リストL3は、左右にくるユニーク値の個数のリストを要素に持つリストです。
［数字iの右にくるユニーク値の個数、数字iの左にくるユニーク値の個数］というリストをi番目の要素に持ちます。
・リストL4は、上記リストL3から未使用数字を除去し、各数字の左にくるユニーク値の個数が少ない順に並べたリストです。
具体的には左右のユニーク値の個数の和が正（論理的にTrue）の要素だけをリストL3から取り出して設定します。
・リストL5は、上記のリストL4の末尾要素に該当数字が格納されているので、それを文字型にしたリストです。
・ここまで処理して上記リストL5の要素を、連結文字なしで順に連結して返します。
２．関数の外
・fn = os.path.join(os.path.dirname(__file__), "problem079_keylog.txt")
「__file__」はこのソースコードがあるプログラムファイルそのもののフルパスです。
os.path.dirnameでこのフォルダを取得し、ファイルパスの区切り文字を挟みながら、キーログファイル名と結合します。
・print f(fn)
関数fの戻り値を表示します。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
73162890
