/*

  (Decomposition of) global constraint circuit in Picat.

  See Global Constraint Catalog:
  http://www.emn.fr/x-info/sdemasse/gccat/Ccircuit.html


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

*/

import util.
import cp.


main => go.

go =>   
        % find all circuits of order 5
        N = 5,
        Print = 1,
        test1(N, Print),
        test2(N, Print).


%
% Show all circuits of order 4..11 and compare with
% the built-in circuit/1 which is (unsurprisingly)
% much faster. Intrestingly the backtracks are the same.
% 
% Note: First is the statistics for my B-Prolog model
%       http://www.hakank.org/bprolog/circuit.pl
%    For N=10
%    - circuit_me/1: 3.388 seconds. Backtracks: 362879
%    - circuit/1   : 2.144 seconds. Backtracks: 362879
%    (There are 362880 different solutions of N=10,
%     i.e. one more than the number of backtracks).
%
%    For N=11:
%    - circuit_me/1: 36.062 seconds. Backtracks: 3628799
%    - circuit/1   : 23.374 seconds. Backtracks: 3628799
% 
% Then the statistics for this Picat model
%    N: 10
%    - circuit_me/1: CPU time 3.004 seconds. Backtracks: 362879
%    - circuit/1   : CPU time 1.636 seconds. Backtracks: 362879
% 
%    N: 11
%    - circuit_me/1: CPU time 31.026 seconds. Backtracks: 3628799
%    - circuit/1   : CPU time 19.449000000000002 seconds. Backtracks: 3628799
%
% So it seems that Picat is slightly faster for this problem than B-Prolog.
% (They have exactly the same number of backtracks.)
%
go2 =>
   Print = 0,
   foreach(N in 4..11)
      garbage_collect(100_000_000),
      writef("\nN: %d\n", N),
      time2(test1(N, Print)),
      time2(test2(N, Print))
   end.

go3 => 
   N = 6,
   X = new_list(N),
   X :: 1..N,
   Path = new_list(N),
   Path :: 1..N,
   circuit_path(X,Path),

   Vars = X ++ Path,
   solve(Vars),

   println(x=X),
   println(path=Path),
   nl,
   fail,
   nl.  


go4 =>   
  % find all circuits of order 5
  garbage_collect(200_000_000),
  N = 10,
  Print = 0,
  time(test2(N, Print)),
  time(test3(N, Print)).


% Using my circuit_me/1
test1(N,Print) =>
   X = new_list(N),
   X :: 1..N, 
   L = findall(X, (circuit_me(X),solve([ff],X))),
   if Print == 1 then writeln(L) end,
   writeln(len=L.length).


% Using the built-in circuit/1.
test2(N,Print) =>

   X = new_list(N),
   X :: 1..N, 
   L = findall(X, (circuit(X),solve([ff],X))),
   if Print == 1 then writeln(L) end,
   writeln(len=L.length).

% Using the built-in circuit/1 and count_all
test3(N,Print) =>

   X = new_list(N),
   X :: 1..N, 
   Count = count_all((circuit(X),solve([ff],X))),
   println(len=Count).

   
       
%
% circuit(X) succeeds for the array X if it's a circuit.
%
% This implementation use an extra array (Z) for the orbit of x[1].
%
circuit_me(X) =>
   N = length(X),
   Z = new_list(N),
   Z :: 1..N,

   %
   % The main constraint is that Z[I] must not be 1 
   % until I = N, and for I = N it must be 1.
   %
   all_different(X),
   all_different(Z),
   % all_distinct(X), % slower
   % all_distinct(Z), % slower

   % put the orbit of x[1] in in z[1..n]
   X[1] #= Z[1],
   
   % when I = N it must be 1
   Z[N] #= 1,

   % Redundant constraint. It is covered by the constraints
   % X[N] = 1 and alldifferent.
   % foreach(I in 1..N-1) Z[I] #\= 1 end,

   %
   % Get the orbit for Z.
   %
   foreach(I in 2..N)
     element(Z[I-1],X,Z[I])
   end.



circuit_path(X,Z) =>
   N = length(X),
   Z = new_list(N),
   Z :: 1..N,

   %
   % The main constraint is that Z[I] must not be 1 
   % until I = N, and for I = N it must be 1.
   %
   all_different(X),
   all_different(Z),
   % all_distinct(X), % slower
   % all_distinct(Z), % slower

   % put the orbit of x[1] in in z[1..n]
   X[1] #= Z[1],
   
   % when I = N it must be 1
   Z[N] #= 1,

   % Redundant constraint. It is covered by the constraints
   % X[N] = 1 and alldifferent.
   % foreach(I in 1..N-1) Z[I] #\= 1 end,

   %
   % Get the orbit for Z.
   %
   foreach(I in 2..N)
     element(Z[I-1],X,Z[I])
   end.