「prolog勉強プロジェクトオイラー91～100」の編集履歴（バックアップ）一覧に戻る

prolog勉強プロジェクトオイラー91～100 - (2013/09/11 (水) 20:33:55) の編集履歴(バックアップ)

---

プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。

問い91

原点が特殊処理が必要なくらいで後は点OAのベクトルを90度回して最小公倍数でその長さ割ったベクトルの定数倍になる点を数えればOK。

gcd(0, B, B).
gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G). 

min(X,Y,X):-X<Y,!.
min(_,Y,Y):-!.

point_count(_,0,1000):-!.
point_count(L,D,Result):-
	Result is L//D.

r90(0,_,1,0):-!.
r90(_,0,0,1):-!.
r90(DY,DX,DY1,DX1):-
	gcd(DY,DX,G),
	DY1 is DX//G,
	DX1 is DY//G.
 
calc_perm(Y,X,Ans,Ans1):-
	r90(Y,X,DY,DX),
	X1 is 50-X,
	Y1 is 50-Y,
point_count(X ,DX,T1),
	point_count(Y1,DY,T2),
 	point_count(X1,DX,T3),
	point_count(Y,DY,T4),
	min(T1,T2,Re1),
	min(T3,T4,Re2),
	Ans1 is Ans+Re1+Re2.

search(51,0,Ans):-!,write(Ans).
search(Y,51,Ans):-
	!,
	Y1 is Y+1,
	search(Y1,0,Ans).
search(Y,X,Ans):-
	calc_perm(Y,X,Ans,Ans1),
	X1 is X+1,
	search(Y,X1,Ans1).

main91:-search(0,1,2500).

問い92 Square digit chains

http://projecteuler.net/problem=92
この問題はC++なら配列を使えば結構な速度で答えが出る。
Prologでは遅い。
少しだけ工夫が必要だ問題の関数をｆと定義すると。
f(102345)=f(201345)
のように数字を並べ替えたものは同じ値になることとどうやら
f(1～9999999)<=567
となることを利用して計算量を下げれそうに見える。
これで試してみることにしよう。
計算を簡単にするために0012407のような0づめを許して組み合わせ数を求めることにする。
動作が遅いPrologだがほとんど瞬きする間に答えが出た。
こんなものだろう。

to_perm(N,Result):-nth0(N,[1,1,2,6,24,120,720,5040,40320],Result).
search(Num,7,Div,NowDiv,_,[Num,Result]):-
	!,
	Num>0,
	to_perm(NowDiv,NowDiv1), 
	Result is 5040//(Div*NowDiv1).
search(Num,Deep,Div,NowDiv,[N|Nums],Result):-
	NowDiv1 is NowDiv+1,
	Num1 is Num+N*N,
	Deep1 is Deep+1,
	search(Num1,Deep1,Div,NowDiv1,[N|Nums],Result).

search(Num,Deep,Div,NowDiv,[_|Nums],Result):-
	to_perm(NowDiv,NowDiv1),
	Div1 is Div*NowDiv1,
	search(Num,Deep,Div1,0,Nums,Result).

sum([],[N,P],[[N,P]]):-!.
sum([[N,P]|Rest],[N,P1],Result):-
	!,
	P2 is P+P1,
	sum(Rest,[N,P2],Result).
sum([[N,P]|Rest],[N1,P1],[[N1,P1]|Result]):-
	sum(Rest,[N,P],Result).

calc(0,Sum,Sum):-!.
calc(N,Sum,Result):-
	M is N mod 10,
	Sum1 is Sum+M*M,
	N1 is N//10,
	!,
	calc(N1,Sum1,Result).

search(1):-!,fail.
search(89):-!.
search(N):-
	calc(N,0,N1),
	search(N1).

seed(N):-
	between(1,567,N),
	search(N).

sum2([],_,Sum,Sum):-!.
sum2(_,[],Sum,Sum):-!.
sum2([[N,P]|Perm],[N|OKs],Sum,Result):-
	!,
	Sum1 is Sum+P,
	sum2(Perm,OKs,Sum1,Result).
sum2([[N,_]|Perm],[N1|OKs],Sum,Result):-
	N<N1,
	!,
	sum2(Perm,[N1|OKs],Sum,Result).
sum2(Perm,[_|OKs],Sum,Result):-
	!,
	sum2(Perm,OKs,Sum,Result).

main92:-Nums=[0,1,2,3,4,5,6,7,8,9],
	findall(P,search(0,0,1,0,Nums,P),Perm),
	msort(Perm,Perm1),
	[[N,_]|_]=Perm1,
	sum(Perm1,[N,0],Perm2),
	findall(N1,seed(N1),OKs),
	sum2(Perm2,OKs,0,Ans),write(Ans).