/* 

  Bowls and Oranges problem in Picat.

  From BitTorrent Developer Challenge
  http://www.bittorrent.com/company/about/developer_challenge
  """
  You have 40 bowls, all placed in a line at exact intervals of 
  1 meter. You also have 9 oranges. You wish to place all the oranges 
  in the bowls, no more than one orange in each bowl, so that there are 
  no three oranges A, B, and C such that the distance between A and B is 
  equal to the distance between B and C. How many ways can you arrange 
  the oranges in the bowls?.
  """
  
  Via http://surana.wordpress.com/2011/06/01/constraint-programming-example/

  Using count_all/1 (in go3/0) is the fastest approach.

    goal = go3
    count = 7555794
    CPU time 6.209 seconds. Backtracks: 7800656


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

*/


import cp.


main => time2(go).

% 10.847s
go => 
   N = 40, % number of bowls
   M = 9,  % number of oranges

   X = new_list(M),
   X :: 1..N, 

   all_different(X),  
   % all_distinct(X),  
   increasing_strict(X),
   % increasing2(X),
   foreach(I in 1..M, J in 1..M, K in 1..M, I < J, J < K)
        X[J]-X[I] #!= X[K]-X[J]
   end,

   % solution: 7555794,   
   All=solve_all([constr], X), % 26.1s 12882858 backtracks

   writeln(All.length).

%
% fail driven approach
% 8.27s
go2 ?=> 
   get_global_map().put(count,0),
   N = 40, % number of bowls
   M = 9,  % number of oranges

   X = new_list(M),
   X :: 1..N, 

   all_different(X),  
   % all_distinct(X),  
   increasing(X),
   % increasing2(X),
   foreach(I in 1..M, J in 1..M, K in 1..M, I < J, J < K)
        X[J]-X[I] #!= X[K]-X[J]
   end,
   % solve(X),
   solve([constr], X),
   get_global_map().put(count, get_global_map().get(count)+1),
   % println(get_global_map().get(count)),
   fail.

% print the counts
go2 =>
  println(get_global_map().get(count)),
  nl.

%
% Using count_all/1: 6.209s
%
go3 ?=>
  Count=count_all(bowl_and_oranges(_X)),
  println(count=Count),
  nl.
go3 => true.

%
% For use with count_all
%
bowl_and_oranges(X) => 
   N = 40, % number of bowls
   M = 9,  % number of oranges

   X = new_list(M),
   X :: 1..N, 

   all_different(X),  
   increasing_strict(X),
   foreach(I in 1..M, J in 1..M, K in 1..M, I < J, J < K)
        X[J]-X[I] #!= X[K]-X[J]
   end,
   solve([constr], X).   




% increasing(List) =>
%    foreach(I in 2..List.length) List[I-1] #=< List[I] end.

% increasing2([]) ?=> true.
% increasing2([_]) ?=> true.
% increasing2([X,Y|Xs]) => 
%    X #=< Y,
%    increasing2(Xs).