「prolog勉強プロジェクトオイラー51～60」の編集履歴（バックアップ）一覧に戻る
プロジェクトオイラーの問題を堀江伸一がPrologで解くページ。
*問い51
http://projecteuler.net/problem=51
Prologには破壊的代入もなければ配列もstd::mapすらない。
リストで擬似的な11分木を構築して解いてみたけれど何か速度が出ない。
計算量の問題なのか、木を分解したり結合しなおしたりする作業が悪いのか？
こんな込み入ったことをするくらいなら単純な全部検証の方が早いとは思う。
まあリストで木構造を作ったらどの程度の速度が出るのか実験してみたかったというのが今回のコードです。
単純に全検証の方が早いよな絶対。
nums([a,0,1,2,3,4,5,6,7,8,9]).
notPrime(N):-N<2,!.
notPrime(N):-
sqrt(N,N1),
N2 is floor(N1),
between(2,N2,N3),
0=:=N mod N3,
!.
isPrime(N):-not(notPrime(N)).
add_a(X,[N|X]):-nums(A),
member(N,A).
add_list(List,[Y,X]):-
nums(A),
member(X,List),
member(Y,A).
create_tree(6,[0,0]):-!.
create_tree(N,Result):-
N1 is N+1,
findall(L,create_tree(N1,L),Re),
findall(L,add_list(Re,L),Result).
tree_add(_,M,[X,Y],[Re,Y1]):-
integer(X),
integer(Y),
!,
Y1 is Y+1,
((X=:=0;M<X)->
Re is M;
Re is X).
tree_add([],M,[[0,Rest]|Rest1],[[0,Result]|Rest1]):-
!,
tree_add([],M,Rest,Result).
tree_add([N|NumRest],M,[[N,Rest]|Rest1],[[N,Result]|Rest1]):-
!,
tree_add(NumRest,M,Rest,Result).
tree_add(NumList,M,[[N,Rest]|Rest1],[[N,Rest]|Result]):-
tree_add(NumList,M,Rest1,Result).
num_to_list(0,_,[]):-!.
num_to_list(N,R,[a|Result]):-
R =:= N mod 10,
N1 is N//10,
num_to_list(N1,R,Result).
num_to_list(N,R,[M|Result]):-
M is N mod 10,
N1 is N//10,
num_to_list(N1,R,Result).
check(List):-member(a,List),!.
perms(N,Result):-
between(0,9,R),
num_to_list(N,R,Result),
check(Result).
tree_adds(N,[],Tree):-!,search(N,Tree).
tree_adds(N,[L|List],Tree):-
N1 is N-1,
tree_add(L,N1,Tree,NextTree),
!,
tree_adds(N,List,NextTree).
tree_search([X,8]):-
integer(X),
!,
write([X,8]).
tree_search([[_,Rest]|Rest1]):-
member(X,[Rest,Rest1]),
tree_search(X).
search(1000000,Tree):-!,tree_search(Tree).
search(N,Tree):-
notPrime(N),
!,
N1 is N+1,
search(N1,Tree).
search(N,Tree):-
findall(L,perms(N,L),List),
N1 is N+1,
!,
tree_adds(N1,List,Tree).
main51:-create_tree(0,Tree),search(1,Tree).
*問い52
この問題は1/7の割り算を行ったとき循環するまでに1/7,2/7,3/7,4/7,5/7,6/7という割り算が一度ずつ出てきてそれらは循環している。
だから1/7の循環節が一番小さな数字で答えとなる。
問題はこの数字が最小のものであるか？
これを証明しなくてはいけないが特に思いつかないので、結局いつも通り力技となりました
num_to_list(0,[]):-!.
num_to_list(N,[X|Result]):-
X is N mod 10,
N1 is N//10,
num_to_list(N1,Result).
eq_list([],[]):-!.
eq_list([X|Rest],List):-select(X,List,Rest1),eq_list(Rest,Rest1).
set(10,16).
set(100,166).
set(1000,1666).
set(10000,16666).
set(100000,166666).
check(N):-
num_to_list(N,List),
between(2,6,R),
N1 is N*R,
num_to_list(N1,List2),
( eq_list(List,List2)->
fail;!).
main52:-
set(A,B),
between(A,B,N),
not(check(N)),
!,
write(N).
*問い53
そのまま計算して数えるだけ。
next_calc([1],[1]):-!.
next_calc([X,Y|Rest],[Z|Result]):-
Z1 is X+Y,
(1000000=<Z1 -> Z is 1000000;Z is Z1),
next_calc([Y|Rest],Result).
count100m([],0):-!.
count100m([X|Rest],Result):-
1000000=<X,!,count100m(Rest,Re),
Result is Re+1.
count100m([_|Rest],Result):-count100m(Rest,Result).
calc(100,_,Ans):-!,
write(Ans).
calc(N,List,Ans):-
N1 is N+1,
next_calc(List,NextList),
count100m(NextList,Re),
Ans1 is Ans + Re,
calc(N1,[1|NextList],Ans1).
main53:-calc(0,[1],0).
*問い54
http://sozorogusa.blogspot.jp/2012/09/project-euler-problem-54.html
この問題についてはリンク先のようにハッカーぽく書けるか、私のように素朴な低レベルコードになるかの差が出る。
ポーカーの役判定をできるだけ短く書けという問題。
これを自力でやらせてみるというのはハッカーとしてのレベルの高さを測るちょうどいいリトマス試験紙かも。
ただいまコード準備中
*問い55
この計算必ず単調増加します。
配列があれば10000～1へ調べていきます。
ある数になった時そのあと何回以内で計算が終わるか、計算が終わらないか配列にメモっておけば５０回以内で計算が終わるかのチェックで少しだけ計算量を下げることが出来ます。
そこまでしなくてもすぐに答えが出るので気にしませんでした。
rev_num(0,Sum,Sum):-!.
rev_num(N,Sum,Result):-
Sum1 is Sum *10+ (N mod 10),
N1 is N //10,
rev_num(N1,Sum1,Result).
calc(50,_):-!.
calc(T,N):-
rev_num(N,0,N1),
T1 is T+1,
N2 is N+N1,
rev_num(N2,0,N3),
(N2=:=N3->
!,fail;
calc(T1,N2)).
search(N):-
between(1,10000,N),
calc(0,N).
main55:-findall(N,search(N),List),length(List,Len),write(Len).
*問い56
そのまま計算するだけ。
keta_sum(0,0):-!.
keta_sum(N,Result):-
N1 is N//10,
M is N mod 10,
keta_sum(N1,Re),
Result is Re+M.
all_perm([Sum,A,B]):-
between(1,99,A),
between(1,99,B),
P is A^B,
keta_sum(P,Sum).
main56:-findall(L,all_perm(L),List),sort(List,List1),write(List1).
*問い57
√２の連分数展開を一項ずつ計算していく時、１０００項目までで分子の桁数が分母の桁数を超える回数を答えよ。
計算速度を稼ぐために前の項の計算結果を再利用するくらいで特に工夫はしてません。
gcd(0, B, B).
gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G).
add(U1,D1,U2,D2,U4,D4):-
U3 is U1*D2+U2*D1,
D3 is D1*D2,
gcd(U3,D3,M),
U4 is U3//M,
D4 is D3//M.
isBig(0,0):-!,fail.
isBig(_,0):-!.
isBig(U,D):-U1 is U//10,D1 is D//10,isBig(U1,D1).
calc(1000,_,_,_,_):-!,fail.
calc(_,U,D,U1,D1):-
add(U,D,1,1,U1,D1),
isBig(U1,D1).
calc(N,U,D,U2,D2):-
add(U,D,2,1,U1,D1),
N1 is N+1,
calc(N1,D1,U1,U2,D2).
search(U):-
calc(0,1,2,U,_).
main57:-findall(U,search(U),List),length(List,Len),write(Len).
*問い58
この問題はミラーラビン法というものを使うと高速に解けるらしい。
読んだけど一読しただけではよくわからなかったのでいつもの素朴な試し割で素数判定。
遅いけど一応答えは出てるからいいかな（向上心という言葉はないのかな俺？）。
notPrime(N):-N<2,!.
notPrime(N):-
sqrt(N,N1),
N2 is floor(N1),
between(2,N2,N3),
0=:=N mod N3,
!.
isPrime(N):-not(notPrime(N)).
search(_,ADD,_,PC,Count):-
PC>0,
PC1 is PC*10,
PC1<Count,
!,
Ans is ADD-1,
write([Ans,PC,Count]).
search(N,ADD,[],PC,Count1):-
!,
ADD1 is ADD+2,
search(N,ADD1,[ADD,ADD,ADD,ADD],PC,Count1).
search(N,ADD,[A1|Rest],PC,Count):-
!,
Count1 is Count+1,
N1 is N+A1,
( isPrime(N1)->
PC1 is PC+1;
PC1 is PC),
search(N1,ADD,Rest,PC1,Count1).
main58:-search(1,4,[2,2,2,2],0,1).
*問い60
この問題ただいま効率的な実装がないか思考中。
唯解くだけなら上限を設けた深さ5までの全探索でもそれなりの速度は出ると思う。
問題は物凄く早いアルゴリズムがないか、そこが知りたい。
汎用的に計算量を下げるコツを列挙してみる。
見分けがつかないものは他は消去して一つになおして整理する。
同じように扱えるものはより有利に扱えるものだけを残して計算する。
同じ計算はできるだけ省いて再利用する、同じ計算は二度と行わないようデータの処理順序に順序集合を導入する。
うーん？
この問題はまずグラフとして見る？
次に集合の問題に翻訳する。
まずグラフとして見て、素数を点とし両側結合可能なものを両側矢印でつなげる。
上限を設けて少しずつ先に延ばす戦略が有効。
例えば１０万までの素数の直積を取り、両側結合できるものの点同士を繋げる。
次にグラフを、その点と結合可能な素数を集めたA0～Anと見る（Aiは計算の都合上、その数自信もリストに含めておくと計算が楽になる）。
リストの要素が6つ以上あるものだけを選別しB0～Bｍまでとする。
Biと結合してる素数点のリストを得る関数をL(Bi)、Biの素数点をP(Bi)とする。
次にB0～Bmまでの直積をとる、Bi、BｊのL(Bi)がP(Bj)かつP(Bi)<P(Bj)のもの以外は計算しない。
直積の個々の計算はL(Bi)∧L(Bj)で素数リストが6つ以上残るものだけを残しC0～Cｋとする。
C0～CkのP(Ci)はL(Ci)=L(Bj)∧L(Bk) となる集合全てのうち最小のP(Ci)=P(Bk)となるものを採用する。
C0～CkをB0～Bmまでと同じものとみなして、この直積を取る操作を後3回繰り返して残ったリストのうち最小要素5つの計を答えとすればよい。
これが計算に使用した素数の最大値よりも小さくなればそれが答えである。
答えとならなければ素数の最大値を大きくして上記の計算を再試行すれば良い。
素数点P2,P3,P4,P5,P6と結合している素数点の共通集合がP0,P1,P2,P3,P4,P5,P6となった場合
P0とP1が結合してるかは自明ではない。
つまり結局全探索するしかないのかもしれない？
