Project Euler Problem 59

Problem 59

全体の文字数 – 「何文字がA-Z a-zの範囲だったか」 の数値をコストとして計算し、一番コストが小さくなるものをbb_minで調べました。
あんまり効率よくないプログラムで、1900秒くらいかかりました…遅いな…
あとテキストの文字数が3の倍数というところは前もって調べてて、それをあてにしたプログラムになってます(文字数が3の倍数でないとdecryptでこける)

ソース

:-lib(ic).
:-lib(ic_sets).
:-lib(propia).
:-lib(branch_and_bound).
:-lib(csv).

go(Str,Cost,Sum) :-
csv:(csv_read("p059_cipher.txt", [InLst], Option)),
char_code('a',AscA),
char_code('z',AscZ),
[Key1,Key2,Key3]#::AscA..AscZ,
decrypt(InLst,OutLst,[Key1,Key2,Key3]),
OutLst#::0..127,
OutLst#::0..127,
letter_count(OutLst,Cnt),
length(OutLst,Len),
Cost #= Len - Cnt,
flatten([Key1,Key2,Key3,OutLst],AllVals),
labeling(AllVals),
iso_light:(atom_codes(Str,OutLst)),
mysum(OutLst,Sum).

decrypt([],[],_).
decrypt([N1,N2,N3|NRest],[D1,D2,D3|DRest],[K1,K2,K3]):-
xor(N1,K1,D1) infers most,
xor(N2,K2,D2) infers most,
xor(N3,K3,D3) infers most,
decrypt(NRest,DRest,[K1,K2,K3]).

letter_count([],0).
letter_count([First|Rest],Cnt):-
letter_count(Rest,Cnt1),
#::(First, [65..90, 97..122],Hit),
Cnt #= Cnt1+Hit.

mysum([],0).
mysum([First|Rest],Sum):-
mysum(Rest,Sum1),
Sum is Sum1 + First.

実行結果

?- bb_min(go(A, Cost, Sum), Cost, _223).
A = 復号化した文字列(伏せます)
Cost = 伏せます
Sum = 伏せます
Yes (1893.05s cpu)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>