/*

  Towers of Hanoi Picat.

  From Rosetta code: 
  http://rosettacode.org/wiki/Towers_of_Hanoi
  """
  In this task, the goal is to solve the Towers of Hanoi problem 
  with recursion. 
  """

  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

main => go.

/*
  N=3
  Move disk 1 from pole left to pole center
  Move disk 2 from pole left to pole right
  Move disk 1 from pole center to pole right
  Move disk 3 from pole left to pole center
  Move disk 1 from pole right to pole left
  Move disk 2 from pole right to pole center
  Move disk 1 from pole left to pole center
  count=7, theoretical=7

*/
go => 
   hanoi(3),
   nl,
   nl.

/* 
   Fast couting
   N=64
   count=18446744073709551615, theoretical=18446744073709551615

   CPU time 0.0 seconds.
*/
go2 =>
   time(hanoi2(64)),
   nl.

% Showing the steps
hanoi(N) => 
   printf("N=%d\n", N),
   Count = move(N, left, center, right, 1) ,
   printf("count=%w, theoretical=%w\n", Count, 2**N-1),
   nl.

move(0, _From, _To, _Via, _Count) = 0 => true.
table
move(N, From, To, Via, Count) = Count2 => 
    Count1 = Count + move(N - 1, From, Via, To, Count),
    printf("Move disk %w from pole %w to pole %w\n", N, From, To),
    Count2 = Count1 + move(N - 1, Via, To, From,Count).


hanoi2(N) => 
   printf("N=%d\n", N),
   Count = move2(N, left, center, right, 1) ,
   printf("count=%w, theoretical=%w\n", Count, 2**N-1),
   nl.

% For fast counting
table
move2(0, _From, _To, _Via, _Count) = 0 => true.
move2(N, From, To, Via, Count) = Count2 => 
    Count1 = Count + move2(N - 1, From, Via, To, Count),
    Count2 = Count1 + move2(N - 1, Via, To, From, Count).