/* 

  Global constraint same_modulo in Picat.

  From Global Constraint Catalogue
  http://www.emn.fr/x-info/sdemasse/gccat/Csame_modulo.html
  """
  same_modulo(VARIABLES1,VARIABLES2,M)

  Purpose
  
  For each integer R in [0,M1], let N1R (respectively N2R) denote 
  the number of variables of VARIABLES1 (respectively VARIABLES2) that 
  have R as a rest when divided by M. For all R in [0,M1] we have 
  that N1R=N2R.

  Example
      (
      <1,9,1,5,2,1>,
      <6,4,1,1,5,5>,3
      )

  The values of the first collection 1,9,1,5,2,1 are respectively 
  associated with the equivalence classes 1 mod 3=1, 9 mod 3=0, 1 mod 3=1, 
  5 mod 3=2, 2 mod 3=2, 1 mod 3=1. Therefore the equivalence classes 
  0, 1, and 2 are respectively used 1, 3, and 2 times. Similarly, the values 
  of the second collection <6,4,1,1,5,5> are respectively associated 
  with the equivalence classes 6 mod 3=0, 4 mod 3=1, 1 mod 3=1, 1 mod 3=1, 
  5 mod 3=2, 5 mod 3=2. Therefore the equivalence classes 0, 1, and 2 are 
  respectively used 1, 3, and 2 times. Consequently the same_modulo 
  constraint holds. Figure 4.245.1 illustrates this correspondence. 
  """

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

*/

import cp.

main => go.

go =>
  N = 6,

  V1 = new_list(N),
  V1 :: 1..9,
  
  V2 = new_list(N),
  V2 :: 1..9,
  
  M :: 2..N,
  
  V1 = [1,9,1,5,2,1],
  V2 = [6,4,1,1,5,5],
  % M = 3,

  same_modulo(V1, V2, M,GCC),

  Vars = V1 ++ V2 ++ GCC ++ [M],
  solve(Vars),

  println(v1=V1),
  println(v2=V2),
  println(gcc=GCC),
  println(m=M),
  nl,

  fail,
  
  nl.


same_modulo(V1,V2,M,GCC) =>
  N = V1.len,  
  MM = fd_max(M),
  
  M1 = new_list(N),
  M1 :: 0..MM-1,
  M2 = new_list(N),
  M2 :: 0..MM-1,

  GCC = new_list(MM),
  GCC :: 0..N,
  
  foreach(I in 1..N)
     M1[I] #= V1[I] mod M,
     M2[I] #= V2[I] mod M
  end, 

  global_cardinality2(M1, GCC),
  global_cardinality2(M2, GCC).

global_cardinality2(A, Gcc) =>
   Len = length(A),
   Max = length(Gcc),
   Gcc :: 0..Len,
   foreach(I in 0..Max-1) count(I,A,#=,Gcc[I+1]) end.