プロジェクトオイラー Problem 79 「パスコードの導出」 †

Problem 79 「パスコードの導出」 †

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

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

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

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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2079
詳細はリンク先で。





解法
トポロジカルソートで片が付きます。
トポロジカルでない場合答えが複数になるのでトポロジカルになるということですかね。

e(E1,E2,_,E1,E2).
e(_,E2,E3,E2,E3):-!.

e1(Top,_,Top).
e1(_,Tail,Tail).

change_G(Datas,[Top,Tail]):-
      member([E1,E2,E3],Datas),
      e(E1,E2,E3,Top,Tail).


dells(G,Top,[Top1,Tail1]):-
      member([Top1,Tail1],G),
      not(Top=:=Top1).

search_next([],[Num]):-
      !,
      Num1 is Num-48,
      write(Num1).

search_next(G,Nums):-
      select(Top,Nums,Nums1),
      not(member([_,Top],G)),
      !,
      findall(E,dells(G,Top,E),G1),
      Top1 is Top-48,
      write(Top1),
      search_next(G1,Nums1).

numbers1(G,E):-
      member([Top,Tail],G),
      e1(Top,Tail,E).
numbers(G,Nums2):-
      findall(E,numbers1(G,E),Nums1),
      sort(Nums1,Nums2).

main79:-
      open('pe79.txt',read,IS),
      read_term(IS,Datas,[]),
      close(IS),
      findall(E,change_G(Datas,E),G),
      numbers(G,Nums),
      search_next(G,Nums).