Project Euler Problem 52

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)

コメントを残す

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

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