This comment is reply for 1404 katsu: お褒めいただいて、prolog共々大変光...(マップの通り抜け). Go to thread root.
katsu #1449(2007/07/25 09:33 GMT) [ Prolog ] Rating2/2=1.00
リベンジに、Prolog改良版行きます。今度はちゃんと計算終わります。 アルゴリズムとしては、 「迷路の壁を右手で触りながら移動」 →「スタートに戻ったら失敗」 or 「最終行に届いたら成功」です。 副作用無しで美しい！とか思っていたら、 失敗時のジャンプにcatch/throwを使っちゃったのが残念至極。 始めの迷路読み込みには、DCGを使っています。 %余談ですが、GNU-prologだとL=[1|L]みたいな循環リストを処理させると、止まったりします。残念。実行例… $ cat map1 .+..... .+.+++. .+.+.+. .+++.+. .....+. $ cat map2 ..+...+ ++.+++. .+...++ ++++.+. .+..+.+ $ cat map3 .+....+.. .+++..+.. .+.++++.. .+....+.. .++++++++ ...+..+.. ......+.. $ cat map4 ++++++++++++++++ ++++++++++++++++ ++++++++++++++++ ++++++++++++++++ ++++++++++++++++ ++++++++++++++++ ++++++++++++++++ ++++++++++++++++ ++++++++++++++++ ++++++++++++++++ ................ $ cat map5 .+...........+.. .++.++++++++++.. .+...........+.. .+.+++++++++++.. .+.+.........+.. .+.+++++++++++.. ++.+.+.......+.. +..+++++++++++.. ++++............ ++++++++++++++++ ................ $ pl -sq map2.pl map1->success map2->fail map3->success map4->fail map5->fail $
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
maze(F):- load_map(F,Map,W,H), (start(Map,W,Start), catch(mouse(Map,Start,(0,1),W,H,Start), returning, fail), R=success ;R=fail), writeln(F->R). load_map(F,M,W,H):-open(F,read,S),phrase(char_file(S),M),mapsize(M,W,H). map_symbol(M,(X,Y),C):-nth1(Y,M,L),nth1(X,L,C). start([Map1|_],W,(I,1)):-between(1,W,I),nth1(I,Map1,+). dirlist(L):-L=[(0,1),(1,0),(0,-1),(-1,0)|L]. dir_try(CDir,L):-dirlist(Ls),dir_try(CDir,Ls,L). dir_try(CDir,L,L):-L=[_,CDir|_],!. dir_try(CDir,[_|Ls],L):-dir_try(CDir,Ls,L). lim_member(0,_,_):-!,fail. lim_member(_,X,[X|_]). lim_member(L,X,[X0|Xs]):-(var(X);X\=X0),L1 is L - 1,lim_member(L1,X,Xs). mouse(_,(_,H),_,_,H,_). mouse(Map,Pos,Dir,W,H,Orig):- dir_try(Dir,DirL), lim_member(4,Dir1,DirL), move(Pos,Dir1,Pos1), (Orig = Pos1 -> throw(returning);true), stay(W,H,Pos1), map_symbol(Map,Pos1,+), mouse(Map,Pos1,Dir1,W,H,Orig). move((X,Y),(Xs,Ys),(X1,Y1)):-X1 is X + Xs, Y1 is Y + Ys. stay(W,H,(X,Y)):-between(1,W,X),between(1,H,Y). mapsize(Map,W,H):-length(Map,H),Map=[L|_],length(L,W). char_file(S)-->{peek_char(S,end_of_file)},!,[]. char_file(S)-->{phrase(char_line(S),L)},[L],char_file(S). char_line(S)-->{peek_char(S,end_of_file);char_code(NL,10),peek_char(S,NL),get_char(S,_)},[],!. char_line(S)-->{get_char(S,C)},[C],char_line(S). :-maplist(maze,[map1,map2,map3,map4,map5]),halt.
Rating2/2=1.00-0+
[ reply ]
katsu
#1449()
[
Prolog
]
Rating2/2=1.00
maze(F):- load_map(F,Map,W,H), (start(Map,W,Start), catch(mouse(Map,Start,(0,1),W,H,Start), returning, fail), R=success ;R=fail), writeln(F->R). load_map(F,M,W,H):-open(F,read,S),phrase(char_file(S),M),mapsize(M,W,H). map_symbol(M,(X,Y),C):-nth1(Y,M,L),nth1(X,L,C). start([Map1|_],W,(I,1)):-between(1,W,I),nth1(I,Map1,+). dirlist(L):-L=[(0,1),(1,0),(0,-1),(-1,0)|L]. dir_try(CDir,L):-dirlist(Ls),dir_try(CDir,Ls,L). dir_try(CDir,L,L):-L=[_,CDir|_],!. dir_try(CDir,[_|Ls],L):-dir_try(CDir,Ls,L). lim_member(0,_,_):-!,fail. lim_member(_,X,[X|_]). lim_member(L,X,[X0|Xs]):-(var(X);X\=X0),L1 is L - 1,lim_member(L1,X,Xs). mouse(_,(_,H),_,_,H,_). mouse(Map,Pos,Dir,W,H,Orig):- dir_try(Dir,DirL), lim_member(4,Dir1,DirL), move(Pos,Dir1,Pos1), (Orig = Pos1 -> throw(returning);true), stay(W,H,Pos1), map_symbol(Map,Pos1,+), mouse(Map,Pos1,Dir1,W,H,Orig). move((X,Y),(Xs,Ys),(X1,Y1)):-X1 is X + Xs, Y1 is Y + Ys. stay(W,H,(X,Y)):-between(1,W,X),between(1,H,Y). mapsize(Map,W,H):-length(Map,H),Map=[L|_],length(L,W). char_file(S)-->{peek_char(S,end_of_file)},!,[]. char_file(S)-->{phrase(char_line(S),L)},[L],char_file(S). char_line(S)-->{peek_char(S,end_of_file);char_code(NL,10),peek_char(S,NL),get_char(S,_)},[],!. char_line(S)-->{get_char(S,C)},[C],char_line(S). :-maplist(maze,[map1,map2,map3,map4,map5]),halt.Rating2/2=1.00-0+