/* 

  Global constraint balance_modulo in Picat.

  From Global Constraint Catalogue:
  http://www.emn.fr/x-info/sdemasse/gccat/Cbalance_modulo.html
  """
  Constraint

  balance_modulo(BALANCE, VARIABLES, M)

  Purpose

  Consider the largest set S1 (respectively the smallest set S2) of variables 
  of the collection VARIABLES that have the same remainder when 
  divided by M. BALANCE is equal to the difference between the cardinality 
  of S2 and the cardinality of S1.

  Example
  (2, <6, 1, 7, 1, 5>, 3)

  In this example values 6, 1, 7, 1, 5 are respectively associated with 
  the equivalence classes 6 mod 3=0, 1 mod 3=1, 7 mod 3=1, 1 mod 3=1, 
  5 mod 3=2. Therefore the equivalence classes 0, 1 and 2 are respectively 
  used 1, 3 and 1 times. The balance_modulo constraint holds since its 
  first argument BALANCE is assigned to the difference between the maximum 
  and minimum number of the previous occurrences (i.e., 3-1).

  Usage

  An application of the balance_modulo constraint is to enforce a balanced 
  assignment of values, no matter how many distinct equivalence classes 
  will be used. In this case one will push down the maximum value of 
  the first argument of the balance_modulo constraint.
  """

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

*/

import cp.


main => go.

go ?=>
  N = 5,
  X = new_list(N),
  X :: 1..7,
  
  Bal :: 0..N,
  
  M = 3,
  
  X = [6,1,7,1,5],
  balance_modulo(Bal, X, M),
  % Bal #= 2,

  Vars = X ++ [Bal],
  solve(Vars),

  println(x=X),
  println(bal=Bal),
  nl,
  fail,
  
  nl.

go => true.

balance_modulo(Bal, X, M) =>

   Ubx = X.len,
   Counts = new_list(M), % note: this should be 0-based!
   Counts :: 0..Ubx,
   CMax :: 0..Ubx,
   CMin :: 0..Ubx,

   foreach(I in 0..M-1) 
     Counts[I+1] #= sum([(X[J] mod M) #= I : J in 1..Ubx]) 
   end,
   CMax #= max(Counts),
   min_except_0(Counts,CMin),
   Bal #= CMax - CMin.


%
% Ensure that the minumum value (> 0) is MinVal.
%
min_except_0(X,MinVal) =>
  Len = X.len,
  I :: 1..Len,
  element(I,X,MinVal),
  % between(1,Len,I),  
  % MinVal #= X[I],
  foreach(J in 1..Len)
    MinVal #=< X[J] #\/ X[J] #= 0
  end,
  MinVal #> 0.