prolog勉強１８日目 六望星のフィリップイットスターを解くプログラム - c21coterie @ ウィキ

Ｐｒｏｌｏｇ勉強１８～19日目。
このページは小学校の算数までしかできないと創価学会の方に噂を流されている堀江伸一こと私の勉強日記です。
あのカス野郎とかひたすら気持ち悪いとか、色々悪いうわさを流されてる堀江伸一です。
このような噂を流されている私ですが例えば小学校の算数までしかできないかどうかはこのページを読んで噂どおりかはご自分で判断して下さい。

例えば私はＡＯＪというプログラマ向け練習問題を扱ったサイトでSinapusu2002として登録しております。
AOJには色々な問題が掲載されており簡単な問題から非常に難しい問題まであります。
リンク先など少し難しいに分類される問題です。
奇妙な問題に見えますが本質はれっきとした数学の問題です。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0564
よく読むと結構難しそうな問題だなと感じていただけると思います。

ＡＯＪでは問題正答者のコードがどれだけ早くうごくか（どれだけ素晴らしい解法で答えたか）で正当者のランキング付けをしています。
この問題のランキングはリンク先の通りです。
http://judge.u-aizu.ac.jp/onlinejudge/problem_statistics.jsp?id=0564#
リンク先のRanking and Detailsをクリックするとこの問題の正答者ランキングが出ます。

現状sinapusu2002こと私の順位は５位ですが日付に注目してみてください。
私より上位の１位から４位までは皆2012年8月以降にランキング入りを果たしています。
私がコードを提出した２０１２年７月時点ではこの問題で最も早く動くプログラムを書いていたのは私だということがわかります。
一番早く動くプログラムですから当然他人のをカンニングして提出することは不可能。
自分で考え出した方法で問題を解いたわけです。
さて、リンク先はＡＯＪでは少し難しい問題にすぎませんが私はもう少し難しい問題も色々自力で解いています。
ここで質問です。
私は創価学会員のいうとおりの小学校の算数までしかできない人間なのでしょうか？

それはそれとしてＰｒｏｌｏｇの勉強です。
Ｐｒｏｌｏｇは論理学に基礎をおき数学証明や人工知能分野の教育目的に使われる特殊なプログラム言語です。
この言語はとにかく難しいの一言に尽きます。
Ｃ++のように結構出鱈目に書いても後で修正が出来るようなものでなく、設計から答えまで一貫して綺麗にくみ上げないといけない厳密な言語です。

数学証明や人工知能はまだ手が届かないのでもう少し敷居の低いところから勉強しているところです。
今回はリンク先パズル問題を解くコードをＰｒｏｌｏｇで書いてみました。
http://www.geocities.jp/m_hiroi/puzzle/flip_it.html

今回の挑戦は手続き的なアプローチから脱却するためのコードの書き方の模索です。
正しい答えは出てますがコードはまだまだです。

事実の定義がめんどくさいことになっていましてもう少し賢く書けそうな気がしました。
手続き的な処理なら書けるのですがＰｒｏlｏｇ的処理はまだまだみについてない感じです。

パズルをプログラムで解く理由ですが。
あるプログラム言語が実用品を記述できる能力がどれだけあるか、これは一つの問題です。
これの一つの判断材料に。
パズル(競技プログラムに出てくるような問題や数学的問題も含む)を解くプログラムをその言語で書いたとき。
どれだけ効率よく書けるかで、その言語が実用品を作る能力をどれだけもっているかある程度はかることが出来るという有名な数学者による格言があります。

逆に言えば、パズルを解く記述を書くことは色々な問題を解くテクニックの基礎になる勉強してるのと同じだといえます。

またパズルを解くプログラムを書くにはそのプログラム言語の基礎機能を組み合わせる必要があり、基礎機能を効率よく復習するのと同じ効果はあります。
そのプログラム言語の基礎機能を覚えれたかの確認にパズルはある程度向いています。
これがパズルがプログラムの勉強で出題される一つの理由です。
それとパズルだと誰でもわかるので、問題への挑戦意欲もわきやすいという利点があるようです。

%
%____A
%B_C___D_E
%_F_____G
%H_I___J_K
%____L
%C,D,F,G,I,J
change(b,w).
change(w,b).

%C to E'
move_table([A,B,C,D,s,F,G,H,I,J,K,L],[A,B,s,D1,C,F,G,H,I,J,K,L]):-
	change(D,D1).


%C to H'
move_table([A,B,C,D,E,F,G,s,I,J,K,L],[A,B,s,D,E,F1,G,C,I,J,K,L]):-
	change(F,F1).


%D to B'
move_table([A,s,C,D,E,F,G,H,I,J,K,L],[A,D,C1,s,E,F,G,H,I,J,K,L]):-
        change(C,C1).

%D to K'
move_table([A,B,C,D,E,F,G,H,I,J,s,L],[A,B,C,s,E,F,G1,H,I,J,D,L]):-
	change(G,G1).


%G to A'
move_table([s,B,C,D,E,F,G,H,I,J,K,L],[G,B,C,D1,E,F,s,H,I,J,K,L]):-
	change(D,D1).


%G to L'
move_table([A,B,C,D,E,F,G,H,I,J,K,s],[A,B,C,D,E,F,s,H,I,J1,K,G]):-
	change(J,J1).


%J to E'
move_table([A,B,C,D,s,F,G,H,I,J,K,L],[A,B,C,D,J,F,G1,H,I,s,K,L]):-
	change(G,G1).
%J H'
move_table([A,B,C,D,E,F,G,s,I,J,K,L],[A,B,C,D,E,F,G,J,I1,s,K,L]):-
	change(I,I1).

%K I'
move_table([A,B,C,D,E,F,G,H,s,J,K,L],[A,B,C,D,E,F,G,H,K,J1,s,L]):-
	change(J,J1).

%B to I'
move_table([A,B,C,D,E,F,G,H,s,J,K,L],[A,s,C,D,E,F1,G,H,B,J,K,L]):-
change(F,F1). 

%L to F'
move_table([A,B,C,D,E,s,G,H,I,J,K,L],[A,B,C,D,E,L,G,H,I1,J,K,s]):-
	change(I,I1).
%F to A'
move_table([s,B,C,D,E,F,G,H,I,J,K,L],[F,B,C1,D,E,s,G,H,I,J,K,L]):-
	change(C,C1).

%
%____A
%B_C___D_E
%_F_____G
%H_I___J_K
%____L
%C,D,F,G,I,J
%
%B to L'
move_table([A,B,C,D,E,F,G,H,I,J,K,s],[A,s,C,D,E,F1,G,H,I1,J,K,B]):-
	change(I,I1),change(F,F1).
%L to E'
move_table([A,B,C,D,s,F,G,H,I,J,K,L],[A,B,C,D,L,F,G1,H,I,J1,K,s]):-
	change(G,G1),change(J,J1).
%E to B'
move_table([A,s,C,D,E,F,G,H,I,J,K,L],[A,E,C1,D1,s,F,G,H,I,J,K,L]):-
	change(C,C1),change(D,D1).


%H to A'
move_table([s,B,C,D,E,F,G,H,I,J,K,L],[H,B,C1,D,E,F1,G,s,I,J,K,L]):-
	change(C,C1),change(F,F1).
%K to A'
move_table([s,B,C,D,E,F,G,H,I,J,K,L],[K,B,C,D1,E,F,G1,H,I,J,s,L]):-
	change(D,D1),change(G,G1).
%K to H'
move_table([A,B,C,D,E,F,G,s,I,J,K,L],[A,B,C,D,E,F,G,K,I1,J1,s,L]):-
	change(I,I1),change(J,J1).

one_move(X,Y):-move_table(X,Y).
one_move(X,Y):-move_table(Y,X).

w_count([],0):-!.
w_count([X|Rest],Result):-X==w,!,w_count(Rest,Re),Result is Re +1.
w_count([_|Rest],Result):-w_count(Rest,Result).

one_print([A,B,C,D,E,F,G,H,I,J,K,L]):-
	format('____~a\n',[A]),
	format('~a_~a___~a_~a\n',[B,C,D,E]),
	format('_~a_____~a\n',[F,G]),
	format('~a_~a___~a_~a\n',[H,I,J,K]),
	format('____~a\n',[L]).

print_answer([]).
print_answer([State|Rest]):-
	print_answer(Rest),
	one_print(State),nl.


next_search(P,Limit,[State|Rest]):-
	P<Limit,
        w_count(State,WC),
	WC=:=11,
	write(P),
	!,print_answer([State|Rest]).
next_search(P,Limit,[State|Rest]):-
	P<Limit,
	one_move(State,NextState),
	P1 is P+1,
        not(member(NextState,Rest)),
	next_search(P1,Limit,[NextState,State|Rest]).

main:-between(17,19,N),
	next_search(0,N,[[s,b,b,b,b,b,b,b,b,b,b,b]]).

---

上記コードを変更して今度は最長手数のリストを表示する処理を記述。
まあまあかな。
事実の定義がやっぱり長い。

%
%____A
%B_C___D_E
%_F_____G
%H_I___J_K
%____L
%C,D,F,G,I,J
change(b,w).
change(w,b).

%C to E'
move_table([A,B,C,D,s,F,G,H,I,J,K,L],[A,B,s,D1,C,F,G,H,I,J,K,L]):-
	change(D,D1).


%C to H'
move_table([A,B,C,D,E,F,G,s,I,J,K,L],[A,B,s,D,E,F1,G,C,I,J,K,L]):-
	change(F,F1).


%D to B'
move_table([A,s,C,D,E,F,G,H,I,J,K,L],[A,D,C1,s,E,F,G,H,I,J,K,L]):-
        change(C,C1).

%D to K'
move_table([A,B,C,D,E,F,G,H,I,J,s,L],[A,B,C,s,E,F,G1,H,I,J,D,L]):-
	change(G,G1).


%G to A'
move_table([s,B,C,D,E,F,G,H,I,J,K,L],[G,B,C,D1,E,F,s,H,I,J,K,L]):-
	change(D,D1).


%G to L'
move_table([A,B,C,D,E,F,G,H,I,J,K,s],[A,B,C,D,E,F,s,H,I,J1,K,G]):-
	change(J,J1).


%J to E'
move_table([A,B,C,D,s,F,G,H,I,J,K,L],[A,B,C,D,J,F,G1,H,I,s,K,L]):-
	change(G,G1).
%J H'
move_table([A,B,C,D,E,F,G,s,I,J,K,L],[A,B,C,D,E,F,G,J,I1,s,K,L]):-
	change(I,I1).

% K I'
move_table([A,B,C,D,E,F,G,H,s,J,K,L],[A,B,C,D,E,F,G,H,K,J1,s,L]):-
	change(J,J1).

%B to I'
move_table([A,B,C,D,E,F,G,H,s,J,K,L],[A,s,C,D,E,F1,G,H,B,J,K,L]):-
	change(F,F1).

%L to F'
move_table([A,B,C,D,E,s,G,H,I,J,K,L],[A,B,C,D,E,L,G,H,I1,J,K,s]):-
	change(I,I1).
%F to A'
move_table([s,B,C,D,E,F,G,H,I,J,K,L],[F,B,C1,D,E,s,G,H,I,J,K,L]):-
	change(C,C1).

%
%____A
%B_C___D_E
%_F_____G
%H_I___J_K
%____L
%C,D,F,G,I,J
% 
%B to L'
move_table([A,B,C,D,E,F,G,H,I,J,K,s],[A,s,C,D,E,F1,G,H,I1,J,K,B]):-
	change(I,I1),change(F,F1).
%L to E'
move_table([A,B,C,D,s,F,G,H,I,J,K,L],[A,B,C,D,L,F,G1,H,I,J1,K,s]):-
	change(G,G1),change(J,J1).
%E to B'
move_table([A,s,C,D,E,F,G,H,I,J,K,L],[A,E,C1,D1,s,F,G,H,I,J,K,L]):-
	change(C,C1),change(D,D1).


%H to A'
move_table([s,B,C,D,E,F,G,H,I,J,K,L],[H,B,C1,D,E,F1,G,s,I,J,K,L]):-
	change(C,C1),change(F,F1).
%K to A'
move_table([s,B,C,D,E,F,G,H,I,J,K,L],[K,B,C,D1,E,F,G1,H,I,J,s,L]):-
	change(D,D1),change(G,G1).
%K to H'
move_table([A,B,C,D,E,F,G,s,I,J,K,L],[A,B,C,D,E,F,G,K,I1,J1,s,L]):-
	change(I,I1),change(J,J1).

one_move(X,Y):-move_table(X,Y).
one_move(X,Y):-move_table(Y,X).

w_count([],0):-!.
w_count([X|Rest],Result):-X==w,!,w_count(Rest,Re),Result is Re +1.
w_count([_|Rest],Result):-w_count(Rest,Result).

one_print([]):-!.
one_print([A,B,C,D,E,F,G,H,I,J,K,L]):-
	format('____~a\n',[A]),
	format('~a_~a___~a_~a\n',[B,C,D,E]),
	format('_~a_____~a\n',[F,G]),
	format('~a_~a___~a_~a\n',[H,I,J,K]),
	format('____~a\n',[L]).

one_search(OldList,NowList,NextState):-
	select(NowState,NowList,_),
	one_move(NowState,NextState),
 	not(member(NextState,OldList)),
	not(member(NextState,NowList)). 

write_all([]).
write_all([State|Rest]):-write_all(Rest),one_print(State).

next_search(_,OldList,[]):-!,write_all(OldList).
next_search(P,OldList,NowList):-
	!,
	length(NowList,Len),
	write(Len),nl,
	findall(State,one_search(OldList,NowList,State),NextList),
	P1 is P+1,
	sort(NextList,NextList1),
	next_search(P1,NowList,NextList1).

main:-next_search(0,[],[[s,b,b,b,b,b,b,b,b,b,b,b],
 			[b,s,b,b,b,b,b,b,b,b,b,b],
 		        [b,b,s,b,b,b,b,b,b,b,b,b],
 			[b,b,b,s,b,b,b,b,b,b,b,b],
 			[b,b,b,b,s,b,b,b,b,b,b,b],
 			[b,b,b,b,b,s,b,b,b,b,b,b],
 			[b,b,b,b,b,b,s,b,b,b,b,b],
 			[b,b,b,b,b,b,b,s,b,b,b,b],
 			[b,b,b,b,b,b,b,b,s,b,b,b],
 			[b,b,b,b,b,b,b,b,b,s,b,b],
 			[b,b,b,b,b,b,b,b,b,b,s,b],
 			[b,b,b,b,b,b,b,b,b,b,b,s]]).

１９日目
5星陣の組み合わせ数を求めるプログラムを書いてみた。
手続き的発想からすこしＰｒｏｌｏｇ的発想に近寄れた気がする。
でも手続きの方がプログラマの自由度を高めて便利に作られている気がするのでＰｒｏｌｏｇはあまり好きにはなれないかもしれない。

sums([A0,_,A2,_,_,A5,_,_,A8,_],Sum):-Sum is A0+A2+A5+A8.
sums([_,_,_,_,A4,_,A6,A7,A8,_],Sum):-Sum is A8+A7+A6+A4.
sums([_,A1,A2,A3,A4,_,_,_,_,_],Sum):-Sum is A4+A3+A2+A1.
sums([_,A1,_,_,_,A5,_,A7,_,A9],Sum):-Sum is A1+A5+A7+A9.
sums([A0,_,_,A3,_,_,A6,_,_,A9],Sum):-Sum is A9+A6+A3+A0.

all_ok([A,A,A,A,A]).

round_ok([A0,A1,_,_,A4,_,_,_,A8,A9]):-A0<A1,A0<A4,A0<A8,A0<A9.
revers_ok([_,_,A2,A3,_,_,_,_,_,_]):-A2>A3.

selects([],_,_).
selects(_,_,[A1,A0]):-A0>A1,!,fail.
selects(_,_,[A4,_,_,_,A0]):-A0>A4,!,fail.
selects([X|Rest],List,Temp):-select(X,List,Rest1),selects(Rest,Rest1,[X|Temp]).


search(List,Result):-
	selects([A0,A1,A2,A3,A4,A5,A6,A7,A8,A9],List,[]),
	Result=[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9],
	round_ok(Result),
	revers_ok(Result),
	findall(Sum,sums(Result,Sum),SumList),
	all_ok(SumList).

main:-findall(Perm,search([1,2,3,4,5,6,8,9,10,12],Perm),List), 
length(List,Len),
	write(Len).