/* 

  Global constraint longest_change in Picat.

  From Global Constraint Catalogue
  http://www.emn.fr/x-info/sdemasse/gccat/Clongest_change.html
  """
  SIZE is the maximum number of consecutive variables of the collection 
  VARIABLES for which constraint CTR holds in an uninterrupted way. 
  We count a change when X CTR Y holds; X and Y are two consecutive 
  variables of the collection VARIABLES.
  
  Example
  (
   4, <
      var-8,
      var-8,
      var-3,
      var-4,
      var-1,
      var-1,
      var-5,
      var-5,
      var-2>, 
   !=)

  The longest_change constraint holds since its first argument SIZE=4 is 
  fixed to the length of the longest subsequence of consecutive values of 
  the collection <8, 8, 3, 4, 1, 1, 5, 5, 2> such that two consecutive 
  values are distinct (i.e., subsequence 8 3 4 1).
  """
  
  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 = 9,
  X = new_list(N),
  X :: 1..8,

  C :: 0..N,

  X = [8, 8, 3, 4, 1, 1, 5, 5, 2],
  % C #= 4,
  
  longest_change(C, X, #!=),

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

  println(x=X),
  println(c=C),
  nl,
  fail,
  
  nl.

go => true.

%
% Let's show the hidden variables.
%
go2 ?=>
  N = 9,
  X = new_list(N),
  X :: 1..8,

  C :: 0..N,
  C #= 4,
  
  longest_change(C, X, #<, T, CumSum),  

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

  println(x=X),
  println(c=C),
  println(t=T),
  println(cumSum=CumSum),
  
  nl,
  fail,
  
  nl.

go2 => true.



%
% Longest change.
%
longest_change(C,X,Ctr) =>
  longest_change(C,X,Ctr, _T,_CumSum).

% With T and CumSum as output variables
longest_change(C,X,Ctr, T,CumSum) =>
  N = X.len,

  T = new_list(N-1), % % index (2..N)
  T :: 0..1,
  
  CumSum = new_list(N-1), % index(2..N)
  CumSum :: 0..N,
  C :: 0..N,
  
  foreach(I in 2..N)
    ctr(Ctr,X[I-1], X[I],B),
    T[I-1] #= 1 #<=> B #= 1
  end,
  
  foreach(I in 3..N)
    CumSum[I-1] #= T[I-1]*CumSum[I-2] + T[I-1]
  end,
  CumSum[1] #= 0,
  CC #= max(CumSum),
  C #= CC + 1.

ctr(#=, X,Y,B) => B :: 0..1, X #=  Y #<=> B#=1.
ctr(#!=,X,Y,B) => B :: 0..1, X #!= Y #<=> B#=1.
ctr(#>, X,Y,B) => B :: 0..1, X #>  Y #<=> B#=1.
ctr(#>=,X,Y,B) => B :: 0..1, X #>= Y #<=> B#=1.
ctr(#<, X,Y,B) => B :: 0..1, X #<  Y #<=> B#=1.
ctr(#=<,X,Y,B) => B :: 0..1, X #=< Y #<=> B#=1.