:- module(_,_,[]).

% Towers of Hanoi: Move N disks from peg A to peg B using peg C.

hanoi_moves(N,Moves) :-
	hanoi(N,a,b,c,Moves).

hanoi(s(0),A,B,_,[move(A, B)]).
hanoi(s(N),A,B,C,Moves) :- 
    hanoi(N,A,C,B,Moves1),
    hanoi(N,C,B,A,Moves2), 
    list_append(Moves1,[move(A, B)|Moves2],Moves).

% Try:
% ?- hanoi_moves(s(s(s(0))),M).
% ?- hanoi_moves(s(s(s(0))),M), hanoi_moves(N,M).
% ?- hanoi_moves(N,M).


% Try:
% ?- hanoi_test(D).
% and hit Next for increasing numbers of disks.
% Execution time is exponential in the number of disks!

% Note: this Prolog predicate is not pure!
hanoi_test(D) :- 
    between(1,1000,D), 
    decimal_peano(D,N), 
    statistics(walltime, [_,_]),
    hanoi_moves(N,M),
    statistics(walltime, [_,T]),
    length(M,L),
    write(D), write(' disks = '),
    write(L), write(' moves in '),
    write(T), write(' mS'), nl.




% Auxiliary predicates: 
:- use_module(engine(runtime_control),[statistics/2]).
:- use_module(library(write),[write/1]).
:- use_module(engine(io_basic),[nl/0]).
:- use_module(library(lists),[length/2]).
:- use_module(engine(stream_basic),[flush_output/0]).
:- use_module(library(between)).
:- use_module(library(system),[pause/1]).

list_append([],L,L) :- 
    list(L).
list_append([X|Xs],Ys,[X|Zs]) :- 
    list_append(Xs,Ys,Zs).

list([]).
list([_|Y]) :-
    list(Y).

decimal_peano(0,0).
decimal_peano(N,s(X)) :-
    N>0,
    NN is N-1,
    decimal_peano(NN,X).