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.

コメントを残す

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

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