/*

  Global constraint global contiguity in Picat.

  From Global Constraint Catalogue
  http://www.emn.fr/x-info/sdemasse/gccat/Cglobal_contiguity.html
  """
  Enforce all variables of the VARIABLES collection to be assigned to 0 or 1. 
  In addition, all variables assigned to value 1 appear contiguously.
  
  Example:
  (<0,1,1,0>)
  
  The global_contiguity constraint holds since the sequence 0 1 1 0 contains 
  no more than one group of contiguous 1.
  """


  The implementation of global contiguity below was inspired by 
  Toby Walsh's presentation "Sliding Constraints"
     http://www.cse.unsw.edu.au/~tw/samos/slide.ppt
  where he defines it in terms of the global constraint slide.


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

*/

import cp.

main => go.

go ?=>

   N = 15,
   X = new_list(N),
   X :: 0..1,

   global_contiguity(X),
   
   solve([],X),
   writeln(X), 
   fail,
   nl.

go => true.

%
% Using global_contiguity2
%
go2 ?=>

   N = 15,
   X = new_list(N),
   X :: 0..1,

   global_contiguity2(X),
   
   solve([],X),
   writeln(X), 
   fail,
   nl.

go2 => true.


%
% contiguity: all variables assigned to value 1 appear contiguously.
%
global_contiguity(X) =>

   Len = length(X),
   Y = new_list(Len),
   Y :: 0..2,
    
   increasing(Y),
   foreach({XVal,YVal} in zip(X,Y))
      BX :: 0..1,
      BY :: 0..1,
      (XVal #= 1) #<=> BX #= 1,
      (YVal #= 1) #<=> BY #= 1,
      BX #= BY
   end.


%
% Alternative version, skipping BX and BY.
%
global_contiguity2(X) =>

   Len = length(X),
   Y = new_list(Len),
   Y :: 0..2,

   increasing(Y),
   foreach(I in 1..Len)
     X[I] #= 1 #<=> Y[I]  #= 1
   end.