/* 

  Global constraint inflexions in Picat.

  Global constraint catalogue
  http://www.emn.fr/x-info/sdemasse/gccat/Cinflexions.html
  """
  N is equal to the number of times that the following conjunctions of 
  constraints hold:

   * Xi CTR Xi+1 /\ Xi != Xi+1,
   * Xi+1 = Xi+2 /\.../\ Xj-2 = Xj-1,
   * Xj-1 != Xj /\ Xj-1 not CTRX j.
  
  where Xk is the kth item of the VARIABLES collection and 
  1 <= i, i+2 <= j, j <= n 
  and CTR is < or > .

  Example:
  (3, <var-1, var-1, var-4, var-8, var-8, var-2, var-7, var-1>)
  
  The inflexion constraint holds since the sequence 1 1 4 8 8 2 7 1 
  contains three inflexions peaks that respectively correspond to values 
  8, 2 and 7.
  """

  Cf the Sicstus Prolog doc where an automaton is used:
  http://www.sics.se/sicstus/docs/4.0.3/html/sicstus/Combinatorial-Constraints.html

  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 = 8,
  X = new_list(N),
  X :: 1..N,

  A :: 0..N,

  X = [1,1,4,8,8,2,7,1],

  % A #= 3,

  inflexions(A, X),

  Vars = X ++ [A],
  solve(Vars),
  
  println(x=X),
  println(a=A),
  nl,
  fail,
  
  nl.

go => true.

%
% Another example: maximize the number of inflexions (which is N-2).
% Here is one solution:
%
% x = [1,3,2,5,4,7,6,8]
% a = 6
%
% x = [11,8,9,4,5,1,3,2,7,6,10]
% a = 9

go2 ?=>
  N = 9,
  X = new_list(N),
  X :: 1..N,

  A :: 0..N,

  all_different(X),

  A #= N-2,

  inflexions(A, X),

  Vars = X ++ [A],
  % solve($[max(A),ffd,split],Vars),
  solve($[ffd,split],Vars),  
  
  println(x=X),
  println(a=A),
  nl,
  fail,
  
  nl.

go2 => true.



% 
% inflexions
%
inflexions(A, X) =>
  N = X.len,
  A #= sum([
      sum([ X[K-1] #= X[K] : K in I+2..J-1]) #= sum([1 : K in I+2..J-1 ])
      #/\ % CTR is either "<" or ">"
      ( 
        ( % < and not(<)
         (X[I] #< X[I+1] #/\ X[I] #!= X[I+1])
         #/\
         (X[J-1] #!= X[J] #/\ #~(X[J-1] #< X[J]))
        )
        #\/
        ( % > and not(>)
         (X[I] #> X[I+1] #/\ X[I] #!= X[I+1])
         #/\
         (X[J-1] #!= X[J] #/\ #~(X[J-1] #> X[J]))
        )
      )
    : I in 1..N, J in I+2..N]).