BACK
2015-01-30

ハノイの塔を勘違いしてみた

なんか教育担当することになったので、せっかくだからPrologでも教えようかとトチ狂った訳です。
で、Prologといえばハノイの塔だったので、なんとなく制作開始してみたのですが。。。

ルールが間違ってた



Wikiで見れば分かりますが、
ハノイの塔は別の棒移動&小さい順に並べるのが終了状態なのですが、
それだけじゃなくて、最初と移動中も小さい順でなければならないのでした。

で、どう勘違いしたかというと、まあ最後だけだと思ってたんです。並び順。
潰れるっちゅうねん。
いやー、要件確認って大事ですよね(死
間違ったルールで試行錯誤した挙句、とりあえずそのルールに沿ったプログラムはできました。
せっかくなので貼っておく。後で恥ずかしくなること請け合い。適当に作り始めるの悔い改めろよ、未来の俺!!(ぉ

でも恥ずかしいからhamoiにしてあります。。。
深読みしすぎるとメモリ溢れるので、制限付き。
R:ルート、L:移動した階です。Rは向きじゃなくて、棒の間の道名です。
ちなみにhanoiはHiroiさんのが4行で美しいです。That's Prolog。

hamoi(A):-hamoi(A,[],[],[],[]).
hamoi([],[],A,Log,Route):-ordered(A),reverse(Log,L),reverse(Route,R),disp(L,R).

hamoi([H|A],B,C,L,R0):-R=l,checkloop([R|R0],[H|L]),hamoi(A,[H|B],C,[H|L],[R|R0]).
hamoi([H],B,C,L,R0):-R=l,checkloop([R|R0],[H|L]),hamoi([],[H|B],C,[H|L],[R|R0]).

hamoi(A,B,[H|C],L,R0):-R=r,checkloop([R|R0],[H|L]),hamoi(A,[H|B],C,[H|L],[R|R0]).
hamoi(A,B,[H],L,R0):-R=r,checkloop([R|R0],[H|L]),hamoi(A,[H|B],[],[H|L],[R|R0]).

hamoi(A,[H|B],C,L,R0):-R=r,checkloop([R|R0],[H|L]),hamoi(A,B,[H|C],[H|L],[R|R0]).
hamoi(A,[H],C,L,R0):-R=r,checkloop([R|R0],[H|L]),hamoi(A,[],[H|C],[H|L],[R|R0]).

hamoi(A,[H|B],C,L,R0):-R=l,checkloop([R|R0],[H|L]),hamoi([H|A],B,C,[H|L],[R|R0]).
hamoi(A,[H],C,L,R0):-R=l,checkloop([R|R0],[H|L]),hamoi([H|A],[],C,[H|L],[R|R0]).

checkloop([_],_).
checkloop([Hr1|R],[Hl1|L]):-R=[Hr2|_],L=[Hl2|_],not((Hr1=Hr2,Hl1=Hl2)),length([Hl1|L],N),N=<16.

ordered(A):-ordered(A,A),!.
ordered([],_).
ordered([_],_).
ordered(_,[H1,H2]):-H1=<H2.
ordered(A,[H|L]):-L=[H1|_],H=<H1,ordered(A,L).

disp([],[]).
disp([Ha|A],[Hb|B]):-write(Ha),write(','),write(Hb),nl,disp(A,B).

BACK