/*

  Pair divides the sum in Picat
.
  From comp.lang.prolog
  """
  Date: Sat, Feb 28 2009 3:55 am
  From: Nick Wedd

  Here is a puzzle which I found surprisingly easy to program Prolog to
  generate solutions to.  If any of you teach Prolog to students, you
  might use it as an example (like the goat-wolf-cabbage thing).

  Find a set of four distinct positive integers such that, for every pair
  of them, their difference divides their sum.

  Find lots of such sets.

  As above, but sets of five distinct positive integers.
  
  As above, but sets of six ...
  """

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

*/

import cp.

main => go.

go ?=>
   nolog,
   N = 4,
   MaxVal = 100,
   problem(N,MaxVal,X,Z),
   writeln(X=Z),
   fail,
   nl.

go => true.


%
% With a MaxVal of 100
% There are no solutions for 8 or 9 (for MaxVal=100)
% 1 = 100
% 2 = 332
% 3 = 418
% 4 = 356
% 5 = 143
% 6 = 65
% 7 = 3
% 8 = 0
% 9 = 0
%
%
% With a MaxVal of 200 where are solutions for 8
% 1 = 200
% 2 = 798
% 3 = 1091
% 4 = 1023
% 5 = 486
% 6 = 250
% 7 = 32
% 8 = 4
% 9 = 0
%
go2 =>
   nolog,
   MaxVal = 200,
   foreach(N in 1..9)
     time(L = findall(_,problem(N,MaxVal,_X,_Z))),
     println(N=L.len)
   end,
   nl.

%
% Check single solutions for N=1..9
% (with "dynamic" MaxVal)
%
% [1] = 1
% [1,3] = 4
% [1,2,3] = 6
% [1,2,4,5] = 12
% [10,11,12,13,14] = 60
% [7,8,9,11,12,13] = 60
% [57,58,59,60,61,62,63] = 420
% [101,102,103,104,106,107,108,109] = 840
% 
% 
go3 => 
   foreach(N in 1..9)
     println(n=N),
     MaxVal = N*50,
     flush(stdout),
     time(problem(N,MaxVal,X,Z)),
     println(X=Z),
     nl
   end,
   nl.


problem(N, MaxVal, X, Z) =>

   X = new_list(N),
   X :: 1..MaxVal,
   % Z :: N..MaxVal*N,

   all_different(X),
   increasing(X),

   Z #= sum(X),
   Z mod N #= 0,
   foreach(I in 1..N, J in I+1..N) Z mod abs(X[I]-X[J]) #= 0 end,

   Vars = X ++ [Z],
   solve($[ffc,split], Vars).