#!/usr/local/bin/prologcgi

:-s_charset(_,utf8).
% CGI起動後に動かす述語を定義
% パラメータを取得して hanoi/2 を呼び出す。 
top_call:- get_param(seed,X),get_param(place,Y),name(X,XL),name(Y,YL),!,hanoi(XL,YL).
top_call:- output("error","error").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ハノイ本体
%% ?- hanoi("3abc","3a1a2a3").  
%% Output: seed=0bac2ab1cab3ac2bac&answer=3a1a1a2a2a3c1

hanoi([48,_,_,_],_):-                      % 収束しスタックが空なので、おしまい出力
    !,output("end","end").                 % hanoi(0,_,_,_):-!. に対応 ( "0"=48 )

    %% 収束時 "0"=48 円盤NをCへ移す操作 円盤N->C (Hは枚数=カウンタ)
hanoi([48,_,_,_,N,A,C|Stack],[H|Place]):-
    !,mkshape(N,H,C,_,49,Place,Answer),     % "1"= 49 
    output(Stack,[H|Answer]).               % Seed出力,新盤面出力

    %%%%  この節の代わりに次のものを置くと通常のハノイ出力となる
    %  hanoi([48,_,_,_,N,A,C|Stack],_):-
    %      !,write(move_disk),put(N),write(' from '),put(A),write(' to '),put(C),nl,
    %      hanoi(Stack,_).

    %% 収束時の移動情報（円盤No,先）と移動後の操作をスタックに積んで再帰
hanoi([N,A,B,C|Stack],Place):-     
	M is N-1,!,hanoi([M,A,C,B,   N,A,C,      M,B,A,C|Stack],Place).
                    % ========   ======      =======
                    % M枚をA->B, 円盤NをA->C,M枚をB->C

     %% Seed パラメータエラー
hanoi(_,Place):- output("error",Place).

%%%%%%%%%%%%%%%%%%%
%%% OutPut Utility

output(X,Y):-
    write('Content-Type: text/html; charset=utf-8'),nl,nl,
    write('seed='),puts(X),write('&answer='),puts(Y),nl.

puts([]):-!.
puts([A|B]):-put(A),puts(B).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 移動情報を元に新盤面を作る 
%% mkshape(移動円盤No,カウンタ,移動先柱,移動先高さ,高さ仮値,現在List,新List).
%% mkshape(N,H,C,Q,49,Shape,OutShape)
%%     円盤NをCへ移す,枚数はH,移す高さはQ（デフォルトは 49="1"),移動前、移動後

mkshape(_,_,_,Def,Def,[],[]):-!.              % 全円盤配置終了
mkshape(N,N,C,Q,Def,[P,S|L],[P,S,C,Q|R]):-    % 移動円盤の新位置設定
    !,M is N-1,mkshape(N,M,C,Q,Def,L,R).
mkshape(N,M,C,Q,Def,[C,S|L],[C,S,C,S|R]):-    % 移動先が仮位置以上
    S >= Def,!,Def2 is S+1,                   % 仮高さはSの上に修正
    M1 is M-1,mkshape(N,M1,C,Q,Def2,L,R).
mkshape(N,M,C,Q,Def,[P,S|L],[P,S,P,S|R]):-    % 移動先が仮位置未満
    M1 is M-1,!,mkshape(N,M1,C,Q,Def,L,R).    % または移動先でない場合
mkshape(_,_,_,_,_,_,_):-                      % Place パラメータエラー
    output("OK","error"),halt.

%% プログラム終わり
%%%%%%%%%%%%%%%%%%%

/* 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%  ハノイの塔  Flash／Prologインタフェース版  解説  %%%
%%%             2005.12.8 SOFNEC.CO.LTD  稲葉 輝      %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 問題：
N枚の円盤が大きいものから順に柱aに積み上がっている。
これを全て同じ積み重なりで柱cへ移せ。

% ルール：
柱ｂを作業用に利用してよいが小さい円盤の上に大きい円盤を置いてはならない。
また柱以外の場所へ円盤をおいてはならず、同時に一枚しか動かすことができない。

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 1)円盤の数は１〜９を限度とする。（一文字一位置とするため）
%% 2) Flash=>Prolog のパラメータ： seed,place
%%        http://www.xxxx.jp/prolog/hanoi.cgi?seed=3abc&place=3a1a2a3
%% 4) Prolog=>Flash のパラメータ： seed,answer
%%        seed=0bac2ab1cab3ac2bac&answer=3a1a1a2a2a3c1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%
%% 盤面の表現 %%
%%%%%%%%%%%%%%%%

円盤の名前を小さい順に円盤１〜円盤Nと名付ける。
円盤の置かれている高さを下から順に高さ位置１〜高さ位置Nと名付ける。


円盤１      =|=          |           |  ＜＝高さ位置３
円盤２    ===|===        |           |  ＜＝高さ位置２
円盤３   ====|====       |           |  ＜＝高さ位置１
       〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
            柱a         柱b         柱c

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%　Place：Flashから受け取る円盤配置情報　%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

ある盤面のときの静的状態を円盤数を前置きし、左から順番に全ての円盤を
次のように並べることであらわす。

　＜　円盤数,円盤Nの柱と高さ,円盤N-1の柱と高さ,円盤N-2の柱と高さ...　＞

Flash側から現在の盤面としてこの情報を受け取る。上の図では次のようになる。

3a1a2a3
 ==--==
  3 2 1 <--  順序が円盤番号に対応

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%　Answer：Prologから返す円盤の操作情報　%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

上の盤面で円盤１を柱ｃへ移動する操作( move disk1 from a3 to c1 )
のとき、他の円盤は動いていないのだから全体像は次である。

 move disk3 a1 -> a1 , move disk2 a2 -> a2 , move disk1 a3 -> c1

これを円盤数を前置きし、左から順番に全ての円盤の移動情報を
次のように並べることであらわす。

　＜　円盤数,円盤Nの現位置＋移動先,円盤N-1の現位置＋移動先,円盤N-2の現位置＋移動先...　＞

Prolog側から移動操作としてこの情報を渡す。上記操作は次のようになる。

3a1a1a2a2a3c1
 ====----====
   3   2   1    <--  順序が円盤番号に対応

%%%%%%%%%%
%% Seed %%
%%%%%%%%%%

Prolog側の遷移状態（スタック）である。

Prologは毎回起動し、結果を返して終了するので、自らのスタック状態を保持できない。
そこで、終了時にFlash側へスタック状態を渡して保存しておき、次回起動時にはそれを
そのまま受け取って前回のスタック状態を復元し次の動作を決定する。

１）　Flash ＝＞Prolog（初回）　　　Flashから円盤数＋柱の名前並び(例：3abc）を受け取る。
２）　Prolog＝＞Flash 　　　　　　　現在の引数状態（スタック）をFlashへ渡す。
３）　Flash ＝＞Prolog（２回目以降）前回渡された値をそのままPrologへ渡す。
４）　Prolog＝＞Flash（終了時）     "end"を渡す

普通のハノイの塔は必要情報をローカルスタックに積んで再帰しているが、プログラム終了時には
これが失われてしまうため、本版では引数として明示的に保持しディスク操作情報を戻すタイミング
でFlash側に渡す。

このため、”スタック技法”を用いて二重再帰を除去しローカルスタックを省く。

%%%%%%%%%%%%%%%%%%
% 普通のハノイの塔
% ?-hanoi(3,a,b,c).

 % ゼロ枚の円盤では移動がない。
hanoi(0,_,_,_):-!. 

 % N枚の円盤をAからCへ移動するには、
 % N-1枚をまずAからBへ移動しておいて
 % 　円盤NをAからCへ移動し
 % さきほどのBへ移動したN-1枚をCへ移動する

hanoi(N,A,B,C):-
	M is N-1,
	hanoi(M,A,C,B),                                  % 第一再帰（Nより上の円盤群をBへ退避移動）
	write(['Move Disk ',N,' from ',A,' to ',C]),nl,  % 底辺円盤のCへの移動
	hanoi(M,B,A,C).                                  % 第二再帰（Bへ退避した円盤群のCへの再移動）

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% スタックを用いた二重再帰の除去
% ?-hanoi([3,a,b,c]).

 % ゼロ枚の円盤でこれ以上操作がない。
hanoi([0,_,_,_]):-!.

 % ゼロ枚の円盤で収束後に底辺円盤の移動と退避円盤群を再移動する
hanoi([0,_,_,_,N,A,C|Stack]):-
	! write(['Move Disk ',N,' from ',A,' to ',C]),nl,
	hanoi(Stack).

 % 収束後に行う移動情報をスタックに積んでN-1枚の移動をおこなう
hanoi([N,A,B,C|Stack]):-
	M is N-1,hanoi([M,A,C,B, N,A,C, M,B,A,C|Stack]).
                             =====  =======
                           底辺移動,N-1の再移動

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% これに盤面情報を第二引数で追加したものが本プログラムである。
%% 移動円盤情報を現在盤面（place)に反映して移動操作盤面(answer)を生成する。
%%     ＝＞本ファイル先頭へ。

%%%%%%%%%%%%%%%%
% 動作例 
| ?-hanoi("3abc","3a1a2a3").
[Move Disk ,1, from ,a, to ,c]
0bac2ab1cab3ac2bac
3a1a1a2a2a3c1

| ?-hanoi("0bac2ab1cab3ac2bac","3a1a2c1").
[Move Disk ,2, from ,a, to ,b]
1cab3ac2bac
3a1a1a2b1c1c1

| ?-hanoi("1cab3ac2bac","3a1b1c1").
[Move Disk ,1, from ,c, to ,b]
0acb3ac2bac
3a1a1b1b1c1b2

| ?-hanoi("0acb3ac2bac","3a1b1b2").
[Move Disk ,3, from ,a, to ,c]
2bac
3a1c1b1b1b2b2

| ?-hanoi("2bac","3c1b1b2").
[Move Disk ,1, from ,b, to ,a]
0cba2bc1abc
3c1c1b1b1b2a1

| ?-hanoi("0cba2bc1abc","3c1b1a1").
[Move Disk ,2, from ,b, to ,c]
1abc
3c1c1b1c2a1a1

| ?-hanoi("1abc","3c1c2a1").
[Move Disk ,1, from ,a, to ,c]
0bac
3c1c1c2a1c3

| ?-hanoi("0bac","3c1c2c3").
end
end
*/
