カテゴリー: 制約論理プログラミング

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)

Problem52

ECLiPSeで解きました。
処理時間は自分のマシン(Intel(R) Core(TM) i5-3340M CPU @ 270GHz)で6.5秒くらい。
見どころ？はECLiPSeのlogical-loopで書いた順列permutationと、propiaで数値を入れ替えた制約を作っているところ
logical loop はループ用のサブ述語みたいなアホっぽい定義がなくなってコードがエレガントになるのでSWI-Prologでもぜひ正式採用してほしい。
桁のところは一般化してなく、1桁、2桁、3桁…　と手入力で増やしながら確認しました
（bb_minでそれぞれの桁での最小の数値が取れるようにしてます）。

プログラム：

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

go(Digits,[X1num,X2num,X3num,X4num,X5num,X6num]) :-
	length(X1Lst,Digits),
	X1Lst#::[0..9],
	lst2num(X1Lst,X1num),
	X1num #> 10 ^ (Digits-1),
	X2num #= X1num * 2,
	X3num #= X1num * 3,
	X4num #= X1num * 4,
	X5num #= X1num * 5,
	X6num #= X1num * 6,
	permutation(X1Lst,X2Lst) infers most,
	lst2num(X2Lst,X2num),
	permutation(X1Lst,X3Lst) infers most,
	lst2num(X3Lst,X3num),
	permutation(X1Lst,X4Lst) infers most,
	lst2num(X4Lst,X4num),
	permutation(X1Lst,X5Lst) infers most,
	lst2num(X5Lst,X5num),
	permutation(X1Lst,X6Lst) infers most,
	lst2num(X6Lst,X6num),
	labeling([X1num,X2num,X3num,X4num,X5num,X6num]).
	
lst2num(L,N):-
	(foreach(Num,L),fromto(0,In,Out,N),count(I,0,_)
		do
		Out #= In + 10^I * Num
	).

permutation(A,B):-
	(fromto(A,AIn,AOut,[]),fromto(B,[BFirst|BRest],BRest,[])
		do
		select(BFirst,AIn,AOut)
	).

実行結果（解答伏せます）：

?- bb_min(go(XXXXXXX, [N1, N2, N3, N4, N5, N6]), N1, Option).
N1 = XXXXXXXX
N2 = XXXXXXXX
N3 = XXXXXXXX
N4 = XXXXXXXX
N5 = XXXXXXXX
N6 = XXXXXXXX
Option = bb_options(continue, -1.0Inf, 1.0Inf, 1, 1, 0, 0, one, _466, _467, _468)
Yes (6.59s cpu)