koyahata のすべての投稿

PrologでForループ

SicstusやECLiPSeではイテレータとかいうのを使ってDo-Loopが記述できるのですが、もともとECLiPSeで実現されていた論理プログラミングのループ(Logical Loop)を紹介する以下の論文を2002年にSchimpfさんという人が書いていて、これでLogical Loopが広まったようです?

Logical Loop

まだ深く読み込んでませんが、SWIにもなんかの方法で実装できるような気もする… lambdaライブラリとかを使う?

発見

CLP(B)を使ってProjectEuler の No.172を解いている記事を見つけた。

CLPFD の開発者のMarkus Triskaさんが書いている。

The Boolean Constraint Solver of SWI-Prolog: System Description

他にも No.161 に関する記載もありますね。

…しかし律儀に全数を数え上げる方法を使ってるからムチャクチャ効率悪くて、メモリ20Gbyte積んだマシン使って7時間もかかって解いてる…ダメだなこりゃ…

Probrem 185 Number Mind

Project Eulerの問題はものすごくたくさんあるし(2017.05.12現在で600問弱)自分の目的はProlog関連技術の威力を試すためにやっている側面が強く全問制覇が目標ではないので、これからはまずそれに適した問題から解いてゆこうと思う。

Probrem 185 Number Mind

この問題は「ザ・制約論理プログラミング用問題」というくらい制約論理プログラミングに向いていると感じ手を付けた。ほとんど探索の工夫をせずに問題の定義のみ書いて、ちゃんと解けている。

今回プログラムを作っていてハマってしまった箇所があり、勉強になった。
・術語内で制約論理用変数を使いそれを呼び元に返さない状態でlabelingを行うと、それらの変数がガベージコレクトされておかしくなる。
・上記のエラーメッセージはguess述語の呼び出しをかなり減らした状態から順々に増やしてゆかないと見ることができない(全て書いた状態で実行すると一晩返ってこないプログラムとなり時間をかけて正しく動いているようにも見え、プログラムが間違っているという手がかりは全く得られなかった)

上記のような手続き型言語と異なる独自の開発ノウハウが結構あるので、これからも要勉強である。

labelingのオプションでも相当速度が変わる。基本はffもしくはffcをつけるで良いと思う。

この問題は Difficulty Rating が55% で、 2017年5月12日現在で解いた人が 2273 人しかいない問題だそうで、今まで自分が解いた中では一番難しい問題のようだ。

個人的には今までチャレンジかつ正答した問題の中では 191 Prize String が一番難しく、これは1週間位組み合わせ・順列系のサイトを調べまくって解いた。自分の解き方はエレガントでなかったが、正答者のみ見れるスレッドによると動的計画法でエレガントかつ超スピードで解けるようだ。

Number Mindの問題は前述のハマり以外はとくに問題はなかった。正答者スレによるとECLiPSeとかいう(IDEのほうではない)同じく制約論理ライブラリを使って解いている人がいた。その人のコードもほぼ問題の定義のみが記述されているエレガントなものだった。自分のスピードより数十倍速いようだったので、Eclipse恐るべしと思った。いつか勉強するかも。

正答者スレを見ることにより、自分より遥かに優秀な取り組み方をしている人の使用言語やソースコードを確認できるのも Project Euler の良いところだと思う。

ソースコード:

:-use_module(library(clpfd)).

solve(Num):-
length(Num,16),
Num ins 0..9,

guess(Num,2321386104303845,0,Hits00),
guess(Num,6375711915077050,1,Hits01),
guess(Num,6913859173121360,1,Hits02),
guess(Num,3847439647293047,1,Hits03),
guess(Num,3174248439465858,1,Hits04),
guess(Num,8157356344118483,1,Hits05),
guess(Num,4895722652190306,1,Hits06),
guess(Num,4513559094146117,2,Hits07),
guess(Num,5616185650518293,2,Hits08),
guess(Num,2615250744386899,2,Hits09),
guess(Num,6442889055042768,2,Hits10),
guess(Num,2326509471271448,2,Hits11),
guess(Num,5251583379644322,2,Hits12),
guess(Num,2659862637316867,2,Hits13),
guess(Num,5855462940810587,3,Hits14),
guess(Num,9742855507068353,3,Hits15),
guess(Num,4296849643607543,3,Hits16),
guess(Num,7890971548908067,3,Hits17),
guess(Num,8690095851526254,3,Hits18),
guess(Num,1748270476758276,3,Hits19),
guess(Num,3041631117224635,3,Hits20),
guess(Num,1841236454324589,3,Hits21),

Hits=[ Hits00,Hits01,Hits02,Hits03,Hits04,
Hits05,Hits06,Hits07,Hits08,Hits09,
Hits10,Hits11,Hits12,Hits13,Hits14,
Hits15,Hits16,Hits17,Hits18,Hits19,
Hits20,Hits21],

flatten([Num,Hits],Flatten),
labeling([ff,bisect],Flatten).

guess(Num,CompareNum,HitNum,Hits):-
number_codes(CompareNum,Codes),
maplist(code_num,Codes,Nums),
%write(Nums),nl,
maplist(chk_hit,Num,Nums,Hits),
sum(Hits,#=,HitNum).

chk_hit(A,B,H):-
A#=B #<==> H.

code_num(Cd,Num):-
Num is Cd - 48.

実行結果:
?- time(solve(Num)),write(Num).
% 585,922,243 inferences, 43.774 CPU in 43.975 seconds (100% CPU, 13385202 Lips)
**********解答伏せてます**********
% 176,962,326 inferences, 13.057 CPU in 13.140 seconds (99% CPU, 13552767 Lips)
false.

Problem2 偶数のフィボナッチ数

問題


% problem 2

solve:-
fibo([2,1],Fibo),
even_sum(Fibo,Sum),
write(Sum).

even_sum([],0):-!.
even_sum([First|Rest],Sum):-
First mod 2 =:= 0,
!,
even_sum(Rest,Sum1),
Sum is First + Sum1.
even_sum([_|Rest],Sum):-
even_sum(Rest,Sum).

fibo([First|Rest],Rest):-
First >= 4000000,
!.
fibo([P1,P2|Rest],Out):-
P0 is P1 + P2,
fibo([P0,P1,P2|Rest],Out).

実行結果:
1 ?- solve.
***********************(解答伏せます)**********************
true.

Problem 9 特別なピタゴラス数

問題

CLPFDを使って解いた。こんなのでも結構時間かかっていて、CLPFD大丈夫か??と不安になった…


% problem 9

:-use_module(library(clpfd)).

solve:-
[A,B,C] ins 1..1000,
A + B + C #= 1000,
A #< B, B #< C,
A * A + B * B #= C * C,
label([A,B,C]),
write([A,B,C]).

実行結果:
1 ?- time(solve).
[XXX,XXX,XXX]
% 69,890,740 inferences, 132.578 CPU in 134.625 seconds (98% CPU, 527166 Lips)
true

Problem 8 数字列中の最大の積

問題

他にも挑戦している人がいると思うので今回から解答を伏せます。


% problem 7

:- dynamic
gvar/2.

gvar(max,0).

set_gvar(Name,X):-
nonvar(Name),retract(gvar(Name,_)),!,asserta(gvar(Name,X)).
set_gvar(Name,X):-
nonvar(Name),asserta(gvar(Name,X)).

bignum(7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450).

solve:-
gvar(max,0),
bignum(BigNumAtom),
number_chars(BigNumAtom,BigNumChars),
bignum_mul(BigNumChars).

bignum_mul([A01,A02,A03,A04,A05,A06,A07,A08,A09,A10,A11,A12,A13 | Rest]):-
!,
List = [A01,A02,A03,A04,A05,A06,A07,A08,A09,A10,A11,A12,A13],
mul_chars(List,Mul),
gvar(max,Max),
(Mul > Max->(set_gvar(max,Mul),write(Mul),nl);true),
bignum_mul([A02,A03,A04,A05,A06,A07,A08,A09,A10,A11,A12,A13 | Rest]).

mul_chars([],1):-!.
mul_chars([First|Rest],Mul):-
number_chars(FirstNum,[First]),
mul_chars(Rest,MulRest),
Mul is MulRest * FirstNum.

実行結果:
1 ?- time(solve).
***********************(解答伏せます)**********************
% 42,565 inferences, 0.047 CPU in 0.047 seconds (100% CPU, 908053 Lips)
false.

Problem 7 10001番目の素数

問題

% problem 7

% Idx は 9 のみで構成されている必要あり
solve(Idx):-
retractall(sosu),
assert(max(Idx)),
make_list(Idx,List),
eratosthenes_sieve(List,List1), % エラトステネスのふるいによる素数列挙
nth1(10001,List1,Sosu),
write(Sosu).

% 2 ~ Idx までのリストを作成
make_list(Idx,List):-
make_list_sub(Idx,List,[]).

make_list_sub(1,Ret,Ret):-!.
make_list_sub(Idx,Ret,List):-
Idx1 is Idx - 1,
make_list_sub(Idx1,Ret,[Idx | List]).

% 素数列挙 エラトステネスのふるい
eratosthenes_sieve([],[]):-!.
eratosthenes_sieve([First | Rest],[First | Rest]):-
max(Max),
First * First > Max ,
!.
eratosthenes_sieve([First | Rest], [First | Ret]):-
erase_baisu(First,Rest,Rest1),
eratosthenes_sieve(Rest1,Ret).

erase_baisu(_,[],[]):-!.
erase_baisu(Base,[First | Rest],[First | Ret]):-
First mod Base =\= 0,
!,
erase_baisu(Base,Rest,Ret).
erase_baisu(Base,[_ | Rest],Ret):-
erase_baisu(Base,Rest,Ret).
rotate_sub(Rot1,Idx1,Rot).

実行結果:
1 ?- solve(1000000).
***********************(解答伏せます)**********************
true.

Problem 68 Magic 5-gon ring

問題

CLPFDを用いて解いた。こういうのがCLPFDの得意分野だと思う。
作成時間1時間弱?

変数の場所
p_068_2


:-use_module(library(clpfd)).

main:-
List = [A,B,C,D,E,F,G,H,I,J],
List ins 1..10,
all_different(List),
A #= 10 #\/ B #= 10 #\/ C #= 10 #\/ D #= 10 #\/ E #= 10,
maplist(#<(A),[B,C,D,E]),
maplist(
sum,
[[A,F,G],[B,G,H],[C,H,I],[D,I,J],[E,J,F]],
[#=,#=,#=,#=,#=],
[Sum,Sum,Sum,Sum,Sum]),
flatten([[A,F,G],[B,G,H],[C,H,I],[D,I,J],[E,J,F]],Flatten),
setof(Flatten,label(List),Num15List),
maplist(num_chr_recursive,Num15List,Num16List),
write(Num15List),nl,nl,
write(Num16List),nl,nl,
msort(Num16List,Sorted),
write(Sorted),nl,nl,
last(Sorted,Last),
write('answer:'),nl,
write(Last).

num_chr_recursive([],[]):-!.
num_chr_recursive([FirstNum|RestNums],Ret):-
!,
num_chr_recursive(RestNums,RestChrs),
atom_chars(FirstNum,Chrs),
append(Chrs,RestChrs,Ret).

%
%実行結果
%[10] 25 ?- main.
***********************(解答伏せます)**********************
%true.
%

Problem 6 2乗和の差

問題

最初のほうのはみんな簡単ですね…歯ごたえあるやつまでとばしてやるかな…

プログラム:

% problem 6

solve:-
make_list(100,L),
calc_pow2_sum(L,PowSum),
calc_sum(L,Sum),
SumPow is Sum * Sum,
Ans is SumPow - PowSum ,
write(Ans).

calc_pow2_sum([],0):-!.
calc_pow2_sum([First|Rest],PowSum):-
FirstPow is First * First,
calc_pow2_sum(Rest,PowSumRest),
PowSum is FirstPow + PowSumRest.

calc_sum([],0):-!.
calc_sum([First|Rest],Sum):-
calc_sum(Rest,RestSum),
Sum is First + RestSum.

% 1 ~ Idx までのリストを作成
make_list(Idx,List):-
make_list_sub(Idx,List,[]).

make_list_sub(0,Ret,Ret):-!.
make_list_sub(Idx,Ret,List):-
Idx1 is Idx - 1,
make_list_sub(Idx1,Ret,[Idx | List]).

実行結果:
1 ?- solve.
***********************(解答伏せます)**********************
true.

Problem 5 最小公倍数

問題

1~20の最小公倍数を求めているだけ

プログラム:

% problem 5

solve:-
calc_lcm_all([2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],Lcm),
write(Lcm).

% すべての数字の最小公倍数を取得
calc_lcm_all([],1):-!.
calc_lcm_all([First|Rest],Lcm):-
calc_lcm_all(Rest,LcmRest),
lcm(First,LcmRest,Lcm).

% 最小公倍数
lcm(N, M, Lcm) :-
Gcd is gcd(N , M),
Lcm is (N * M) // Gcd, !.

実行結果:
[2] 9 ?- time(solve).
***********************(解答伏せます)**********************
% 79 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
true.