PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 79 / パスコードの導出

オンラインバンクで通常使われるsecurity methodはパスコードからランダムに選んだ3文字をユーザーに要求するものである。

たとえばパスコードが531278のとき,2番目,3番目,5番目の文字を要求されるかもしれない。このとき期待される答えは 317 である。

テキストファイル keylog.txt にはログインに成功した50回の試行が記録されている。

3つの文字が常に順番通りに要求されるとするとき,ファイルを分析して可能なパスコードのなかでもっとも短いものを見つけよ。

Problem 79 - Project Euler

解法1 下調べ+α

keylog.txt の中身は myList0 のようになっていました。問題文には「50回の試行」とありますが,重複分を除いた実際のデータ数は33です。

C[n,3]≧33 を解いて,パスコードは7文字以上とわかります。

Mathematica で処理しやすいように myList0 からダブりを除いて,桁ごとに区切ります。これが myList1 です。

myList1 に Tally を使って各数字の登場回数を調べると,4と5が一度もあらわれないことがわかります。パスコードが8文字だとすると,0~9から4と5を除いた8文字を1回ずつ使っているはずです。

次に各位の登場回数を調べました。たとえば7は百の位に最も多く13回も登場する一方で十の位,一の位には一度も登場していません。パスコードの首位の数字はおそらく7です。同じように考えると,パスコードは
「73 (1,2,6の順列) 890」
の形だろうと推測できます。そして,myList1 を見ると 1,2,6 の並び順がわかるので,解答は「73162890」だろうと予想できます。登場回数が多いからと言って並び順が上だ下だとは言い切れませんが,一応答えは出ました。

解法2 実際に3桁取り出して比較

次は真面目に解きます。8桁の数から3桁取り出して作った数の集合を myList2 として,これが myList1 を部分集合として含むものを探しました。

3桁取り出すうまい方法が思いつかなかったので,「0を5個,1を3個並べたマスクを作って,IntegerDigits[n] と成分ごとに掛け算する」という泥臭いことをやっています。この掛け算に続いて DeleteCases で0を除くと1倍した項だけが残ります。

f と g で数字を置き換えているのは,4と5を使わないことがわかっていることに加えて,「0倍した結果0になった」と「はじめから0だった」を区別するためです。

使う数字を1から8までに変更することによって予想されるパスコードは1から8までの数の順列になり,Permutations[Range[8]] で生成できます。部分集合の条件をパスしたら g で元の数に直して終了です。2.2秒で終わってホッとしました。


解法3 有向グラフ

解法1をもう少し自動化することを考えました。

この問題を紙と鉛筆で解けと言われたら,123→「1>2>3」のように1つ1つの数を不等式に直して連結していきます。これを Mathematica でやるとしたらどうなるか考えました。「i が j の前にある」を表にすることも考えたのですが,これだと表を解釈する手間が生じて解法1と大差ありません。そこで考えたのが有向グラフです。
123→{{1->2},{2->3},{1->3}}
のように変換するとグラフが描けます。

f:id:variee:20170422194457p:plain

結果は一目瞭然で,答えは「73162890」です。