小屋畑ソフトウェアサービスブログページ

発見

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

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

The Boolean Constraint Solver of SWI-Prolog: System Description

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

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

2017年5月29日
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.
```
2017年5月12日

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.

2017年5月12日

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

2017年5月12日

Problem 8 数字列中の最大の積

問題

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

% problem 8
:- 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.

2017年5月12日

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.

2017年5月12日

Problem 68 Magic 5-gon ring

問題

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

変数の場所

:-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.

2017年5月12日

Problem 6 ２乗和の差

問題

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

プログラム：

% 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.

2017年5月12日

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.

2017年5月12日

Problem 44　五角数

問題

assertのハッシュとselectの順番に頼った力まかせのひどいプログラム。エレガントさのかけらもない。遅いし…

make_pent_list(10000,PentLst)の数字も小さいものから試していって見つかるまでだんだんと増やしてった（ひどい）

答えは合ってた。

:-use_module(library(clpfd)).
main:- make_pent_list(10000,PentLst), select(B,PentLst,Rest), select(A,Rest,_), A < B, Sum is A+B, p(Sum), Diff is B-A, p(Diff), write([Diff]). make_pent_list(0,[]):-!. make_pent_list(Idx,[First|Rest]):- !, First is Idx * (3*Idx - 1) / 2, assert(p(First)), Idx1 is Idx - 1, make_pent_list(Idx1,Rest). %　実行結果 % %1 ?- time(once(main)). %[5482660] %% 252,016,073 inferences, 295.203 CPU in 296.719 seconds (99% CPU, 853704 Lips) %true.

2017年5月12日