prolog勉強プロジェクトオイラー81～90 の編集履歴一覧 - c21coterie @ ウィキ

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

prolog勉強プロジェクトオイラー81～90 - (2013/09/05 (木) 20:02:31) の編集履歴(バックアップ)

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

問い84

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2084
問い84はみなさんシミュレートで解いてるようです。
この問題をグラフ上の確率分布の収束問題と考えると
今いるマス40*CCマスで出たカードの組2*2*15通り*CHマスででたカードの組み合わせ2＾8*3*7＝12902400点
の確率分布から次の状態を計算して分布の収束結果を考える必要があります。
なので収束の問題と考えると計算量が多くなりすぎますしC++のstd::mapでもギリギリ、Prologのリスト処理では話になりません。
回りを見習って単純にシミュレートすることにしました。

card_ch(0,P,5 ):-35<P,!.
card_ch(0,P,35):-25<P,!.
card_ch(0,P,25):-15<P,!.
card_ch(0,P,15):-5<P ,!.
card_ch(0,_, 5):-!     . 

card_ch(1,P,12):-28<P,!.
card_ch(1,P,28):-12<P,!.
card_ch(1,_,12):-     !.

card_ch(2,P,P1):-P1 is (P+37) mod 40,!.

card_ch(3,_,0):-!.
card_ch(4,_,10):-!.
card_ch(5,_,11):-!.
card_ch(6,_,24):-!.
card_ch(7,_,39):-!.
card_ch(8,_,5):-!. 

card_ch(9,P,P):-!.

card_cc(0,_,0):-!.
card_cc(1,_,10):-!.
card_cc(2,P,P):-!.

xai(_,_,10,3):-!.
xai(P,Sum,P1,K):-
	!,
	A is random(4)+1,
	B is random(4)+1,
	K1 is K+1,
	Sum1 is Sum+A+B,
	(A==B->xai(P,Sum1,P1,K1);
	P1 is (P+Sum1) mod 40).

card_move(P1,P2,CardCH,_,CHP,CCP,CHP1,CCP):-
	member(P1,[7,22,36]),
	!,
	CHP1 is (CHP+1) mod 16,
	nth0(CHP,CardCH,X),
	card_ch(X,P1,P2).
card_move(P1,P2,_,CardCC,CHP,CCP,CHP,CCP1):-
	member(P1,[2,17,33]),
	!,
	CCP1 is (CCP+1) mod 16,
	nth0(CCP,CardCC,X),
	card_cc(X,P1,P2).

card_move(30,10,_,_,CHP,CCP,CHP,CCP):-!.
card_move(P,P,_,_,CHP,CCP,CHP,CCP):-!.

swap([],[]):-!.
swap([[X,Y]|Rest],[[Y,X]|Result]):-!,
	swap(Rest,Result).


move(_,2000,_,_,_,_,Count,Result):-!,
	msort(Count,Result).

move(P,Deep,CardCH,CardCC,CHP,CCP,Count,Result):-
	!,
	xai(P,0,P1,0),
	card_move(P1,P2,CardCH,CardCC,CHP,CCP,CHP1,CCP1),
	Deep1 is Deep+1,
	select([P2,C],Count,Count1),
	!,
	C1 is C+1,
	move(P2,Deep1,CardCH,CardCC,CHP1,CCP1,[[P2,C1]|Count1],Result).

counts([N,0]):-
	between(0,39,N).

card_shuffle([],[]):-!.
card_shuffle(Cards,[X|Result]):-
	length(Cards,Len),
	P is random(Len),
	nth0(P,Cards,X),
	select(X,Cards,Cards1),
	!,
	card_shuffle(Cards1,Result).

test(Count,1000,_,_):-!,swap(Count,Count1),msort(Count1,Ans),write(Ans).

test(Count,Deep,CardCH,CardCC):-
	!,
	move(0,0,CardCH,
	         [0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2],
	         0,0,Count,Count1),
	Deep1 is Deep+1,
	card_shuffle(CardCH,CardCH1),
	card_shuffle(CardCC,CardCC1),
	test(Count1,Deep1,CardCH1,CardCC1).


main84:-findall(C,counts(C),Counts),
	CardCH=[0,0,1,2,3,4,5,6,7,8,9,9,9,9,9,9],
	CardCC=[0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2],
	!,
	test(Counts,0,CardCH,CardCC).

Problem 81 「経路の和:2方向」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2081
80要素を1行とする80行リストで実装したほうがよかったかも知れない問題。
コードが膨らんでしまった。
コードの半分が木構造の操作に使われたような気がする。
破壊的代入がないためにそれをごまかすひと手間がいたるところで発生して、コードが膨らんでいるという部分もある。
nth0を2回適用したほうがコードも短くシンプルで速度も大差ないのですが今回は木構造の勉強がしたかったということで一つ。
技術の勉強にと木構造に展開してみたけれど速くなったという実感がわかない。
破壊的代入がないから一々値を更新するたびに木の再構築を行っている。
これが遅いのかもしれないし単純に優先順位付きキューが使えない部分で遅くなっているのかもしれない。
高級言語すぎるとコンパイラやインタプリターが何をやっているかわかりづらくなるのが問題点かも。
そういうのを気にしたくないから高級化するのだが、高級化しすぎると何をしているのかわからなくなる。

%　破壊的代入がないからコードが恐ろしくめんどくさいことになっている
%　sakusya　horie shinniti
to_num([],Num,Num).
to_num([X|Rest],Num,Result):-Num1 is Num*10+(X-48),to_num(Rest,Num1,Result).

read81(List):-
     seen,
     see('e81.txt'),
     findall(X,read81oneRow(X),List).
read81oneRow(Num):-
	repeat,
	peek_code(C),
	(C== -1 ->!,fail;true),
	findall(X,read81one(X),List),
        to_num(List,0,Num).


read81one(A):-
	repeat,
	get0(A),
	((48=<A,A=<57) ->true;!,fail).
create_tree(Down,Up,[]):-
Sa is Up-Down,
Sa<2,
!.
create_tree(Down,Up,[Ls,-1,Rs]):-
M is (Down+Up)//2,
create_tree(Down,M,Ls),
create_tree(M,Up,Rs).
% 原理主義的に考えればこの述語が失敗した場合と成功した場合で処理を分けるべきだが、、、
% それをするとコードが膨らむのでやらない
tree_update(Down,Up,P,Score,[Ls,Score1,Rs],[Ls,Score1,Rs1]):-
	M is (Down+Up)//2,
	M<P,
	!,
	tree_update(M,Up,P,Score,Rs,Rs1).
tree_update(Down,Up,P,Score,[Ls,Score1,Rs],[Ls1,Score1,Rs]):-
	M is (Down+Up)//2,
	P<M,
	!,
	tree_update(Down,M,P,Score,Ls,Ls1).

tree_update(_,_,_,Score,[Ls,Score1,Rs],[Ls,Score2,Rs]):-
	!,
	((Score1== -1 ;Score<Score1)->
	Score2 is Score;
	Score2 is Score1).

tree_search(Down,Up,P,[_,_,Rs],Score1):-
	M is (Down+Up)//2,
	M<P,
	!,
	tree_search(M,Up,P,Rs,Score1).

tree_search(Down,Up,P,[Ls,_,_],Score1):-
	M is (Down+Up)//2,
	P<M,
	!,
	tree_search(Down,M,P,Ls,Score1).


tree_search(_,_,_,[_,Score,_],Score):-
	!.

get_min([],Min,Min):-!.
get_min([[Score,Row,Col]|Rest],[S1,_,_],Result):-
	Score<S1,
	!,
	get_min(Rest,[Score,Row,Col],Result).
get_min([_|Rest],Min,Result):-
	!,
	get_min(Rest,Min,Result).

one_move(Tree,ScoreTree,List,[],_):-
	!,
	search(Tree,ScoreTree,List).

one_move(Tree,ScoreTree,List,[[Dx,Dy]|Rest],[Score,Row,Col]):-
	Row1 is Row+Dy,
	Col1 is Col+Dx,
	Row1<80,
	Col1<80,
	P is Row1*80+Col1,
	tree_search(-1,6400,P,Tree,Score1),
	Score2 is Score1+Score,
	tree_search(-1,6400,P,ScoreTree,Score3),
	(Score3== -1;Score2<Score3),
	!,
	tree_update(-1,6400,P,Score2,ScoreTree,ScoreTree1),
	one_move(Tree,ScoreTree1,[[Score2,Row1,Col1]|List],Rest,[Score,Row,Col]).
one_move(Tree,ScoreTree,List,[_|Rest],Min):-
	!,
	one_move(Tree,ScoreTree,List,Rest,Min).
search(_,_,List):-
	[Top|_]=List,
	get_min(List,Top,Min),
	[_,Row,Col]=Min,
	Row==79,
	Col==79,
	!,
	write([ans,Min]).

search(Tree,ScoreTree,List):-
	[Top|_]=List,
	get_min(List,Top,Min),
	select(Min,List,List1),
	one_move(Tree,ScoreTree,List1,[[0,0],[1,0],[0,1]],Min).


first(_,_,[],Tree):-!,
	tree_search(-1,6400,0,Tree,Score),
	create_tree(-1,6400,ScoreTree),
	search(Tree,ScoreTree,[[Score,0,0]]).
first(Row,80,List,Tree):-
	!,
	Row1 is Row+1,
	first(Row1,0,List,Tree).
first(Row,Col,[Score|List],Tree):-
	!,
	Col1 is Col+1,
	P is Row*80+Col,
	tree_update(-1,6400,P,Score,Tree,Tree1),
	first(Row,Col1,List,Tree1).

test:-create_tree(-1,6400,Tree),read81(List),
	first(0,0,List,Tree).

問い82

問い81と大差ないので特に書くことなし

%
%sakusyahorie shinniti
to_num([],Num,Num).
to_num([X|Rest],Num,Result):-Num1 is Num*10+(X-48),to_num(Rest,Num1,Result).

read82(List):-
    seen,
    see('e81.txt'),
    findall(X,read82oneRow(X),List).
read82oneRow(Num):-
	repeat,
	peek_code(C),
	(C== -1 ->!,fail;true),
	findall(X,read82one(X),List),
        to_num(List,0,Num).


read82one(A):-
	repeat,
	get0(A),
	((48=<A,A=<57) ->true;!,fail).
create_tree(Down,Up,[]):-
	Sa is Up-Down,
	Sa<2,
	!.
create_tree(Down,Up,[Ls,-1,Rs]):-
	M is (Down+Up)//2,
	create_tree(Down,M,Ls),
	create_tree(M,Up,Rs).
%
% 
tree_update(Down,Up,P,Score,[Ls,Score1,Rs],[Ls,Score1,Rs1]):-
	M is (Down+Up)//2,
	M<P,
	!,
	tree_update(M,Up,P,Score,Rs,Rs1).
tree_update(Down,Up,P,Score,[Ls,Score1,Rs],[Ls1,Score1,Rs]):-
	M is (Down+Up)//2,
	P<M,
	!,
	tree_update(Down,M,P,Score,Ls,Ls1).

tree_update(_,_,_,Score,[Ls,Score1,Rs],[Ls,Score2,Rs]):-
	!,
	((Score1== -1 ;Score<Score1)->
	Score2 is Score;
	Score2 is Score1).

tree_search(Down,Up,P,[_,_,Rs],Score1):-
	M is (Down+Up)//2,
	M<P,
	!,
	tree_search(M,Up,P,Rs,Score1).

tree_search(Down,Up,P,[Ls,_,_],Score1):-
	M is (Down+Up)//2,
	P<M,
	!,
	tree_search(Down,M,P,Ls,Score1).


tree_search(_,_,_,[_,Score,_],Score):-
	!.

get_min([],Min,Min):-!.
get_min([[Score,Row,Col]|Rest],[S1,_,_],Result):-
	Score<S1,
	!,
	get_min(Rest,[Score,Row,Col],Result).
get_min([_|Rest],Min,Result):-
	!,
	get_min(Rest,Min,Result).

one_move(Tree,ScoreTree,List,[],_):-
	!,
	search(Tree,ScoreTree,List).

one_move(Tree,ScoreTree,List,[[Dx,Dy]|Rest],[Score,Row,Col]):-
	Row1 is Row+Dy,
	Col1 is Col+Dx,
	-1<Row1,
	Row1<80,
	Col1<80,
	P is Row1*80+Col1,
	tree_search(-1,6400,P,Tree,Score1),
	Score2 is Score1+Score,
	tree_search(-1,6400,P,ScoreTree,Score3),
	(Score3== -1;Score2<Score3),
	!,
	tree_update(-1,6400,P,Score2,ScoreTree,ScoreTree1),
	one_move(Tree,ScoreTree1,[[Score2,Row1,Col1]|List],Rest,[Score,Row,Col]).
one_move(Tree,ScoreTree,List,[_|Rest],Min):-
	!,
	one_move(Tree,ScoreTree,List,Rest,Min).
search(_,_,List):-
	[Top|_]=List,
	get_min(List,Top,Min),
	[_,_,Col]=Min,
	Col==79,
	!,
	write([ans,Min]).

search(Tree,ScoreTree,List):-
	[Top|_]=List,
	get_min(List,Top,Min),
	select(Min,List,List1),
	one_move(Tree,ScoreTree,List1,[[0,-1],[1,0],[0,1]],Min).


tree_first_set(Tree,ScoreTree,80,List):-
	!,
	search(Tree,ScoreTree,List).
tree_first_set(Tree,ScoreTree,Row,List):-
	Row1 is Row+1,
	P is Row*80,
tree_search(-1,6400,P,Tree,Score),
	tree_update(-1,6400,P,Score,ScoreTree,ScoreTree1),
	tree_first_set(Tree,ScoreTree1,Row1,[[Score,Row,0]|List]).


first(_,_,[],Tree):-!,
	create_tree(-1,6400,ScoreTree),
	tree_first_set(Tree,ScoreTree,0,[]).

first(Row,80,List,Tree):-
	!,
	Row1 is Row+1,
	first(Row1,0,List,Tree).
first(Row,Col,[Score|List],Tree):-
	!,
	Col1 is Col+1,
	P is Row*80+Col,
	tree_update(-1,6400,P,Score,Tree,Tree1),
	first(Row,Col1,List,Tree1).

test:-create_tree(-1,6400,Tree),read82(List),
	first(0,0,List,Tree).

問い83

これも81と大差なし特に書くことなし

%
%sakusyahorie shinniti
to_num([],Num,Num).
to_num([X|Rest],Num,Result):-Num1 is Num*10+(X-48),to_num(Rest,Num1,Result).

read81(List):-
    seen,
     see('e81.txt'),
     findall(X,read81oneRow(X),List).
read81oneRow(Num):-
	repeat,
	peek_code(C),
	(C== -1 ->!,fail;true),
	findall(X,read81one(X),List),
        to_num(List,0,Num).


read81one(A):-
	repeat,
	get0(A),
	((48=<A,A=<57) ->true;!,fail).
create_tree(Down,Up,[]):-
	Sa is Up-Down,
	Sa<2,
	!.
create_tree(Down,Up,[Ls,-1,Rs]):-
	M is (Down+Up)//2,
	create_tree(Down,M,Ls), 
	create_tree(M,Up,Rs).
%
%
tree_update(Down,Up,P,Score,[Ls,Score1,Rs],[Ls,Score1,Rs1]):-
	M is (Down+Up)//2,
	M<P,
	!,
	tree_update(M,Up,P,Score,Rs,Rs1).
tree_update(Down,Up,P,Score,[Ls,Score1,Rs],[Ls1,Score1,Rs]):-
	M is (Down+Up)//2,
	P<M,
	!,
	tree_update(Down,M,P,Score,Ls,Ls1).

tree_update(_,_,_,Score,[Ls,Score1,Rs],[Ls,Score2,Rs]):-
	!,
	((Score1== -1 ;Score<Score1)->
	Score2 is Score;
	Score2 is Score1).

tree_search(Down,Up,P,[_,_,Rs],Score1):-
	M is (Down+Up)//2,
	M<P,
	!,
	tree_search(M,Up,P,Rs,Score1).

tree_search(Down,Up,P,[Ls,_,_],Score1):-
	M is (Down+Up)//2,
	P<M,
	!,
	tree_search(Down,M,P,Ls,Score1).


tree_search(_,_,_,[_,Score,_],Score):-
	!.

get_min([],Min,Min):-!.
get_min([[Score,Row,Col]|Rest],[S1,_,_],Result):-
	Score<S1,
	!,
	get_min(Rest,[Score,Row,Col],Result).
get_min([_|Rest],Min,Result):-
	!,
	get_min(Rest,Min,Result).

one_move(Tree,ScoreTree,List,[],_):-
	!,
	search(Tree,ScoreTree,List).
 
one_move(Tree,ScoreTree,List,[[Dx,Dy]|Rest],[Score,Row,Col]):-
	Row1 is Row+Dy,
	Col1 is Col+Dx,
	Row1<80,
	Col1<80,
	-1<Row1,
	-1<Col1,
	P is Row1*80+Col1,
	tree_search(-1,6400,P,Tree,Score1),
	Score2 is Score1+Score,
	tree_search(-1,6400,P,ScoreTree,Score3),
	(Score3== -1;Score2<Score3),
	!,
	tree_update(-1,6400,P,Score2,ScoreTree,ScoreTree1),
	one_move(Tree,ScoreTree1,[[Score2,Row1,Col1]|List],Rest,[Score,Row,Col]).
one_move(Tree,ScoreTree,List,[_|Rest],Min):-
	!,
	one_move(Tree,ScoreTree,List,Rest,Min).
search(_,_,List):-
	[Top|_]=List,
	get_min(List,Top,Min),
	[_,Row,Col]=Min,
	Row==79,
	Col==79,
	!,
	write([ans,Min]).

search(Tree,ScoreTree,List):-
	[Top|_]=List,
	get_min(List,Top,Min),
	select(Min,List,List1),
	one_move(Tree,ScoreTree,List1,[[0,-1],[-1,0],[1,0],[0,1]],Min).


first(_,_,[],Tree):-!,
	tree_search(-1,6400,0,Tree,Score),
	create_tree(-1,6400,ScoreTree),
tree_update(-1,6400,0,Score,ScoreTree,ScoreTree1),
	search(Tree,ScoreTree1,[[Score,0,0]]).
first(Row,80,List,Tree):-
	!,
	Row1 is Row+1,
	first(Row1,0,List,Tree).
first(Row,Col,[Score|List],Tree):-
	!,
	Col1 is Col+1,
	P is Row*80+Col,
	tree_update(-1,6400,P,Score,Tree,Tree1),
	first(Row,Col1,List,Tree1).

test:-create_tree(-1,6400,Tree),read81(List),
	first(0,0,List,Tree).

c21coterie @ ウィキ