/*

  Decomposition of global contiguity using regular in Picat.

  Here's a variant of the global constraint global contiguity
  using (a decomposition of) the regular constraint.


  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,

   % Constraints
   global_contiguity(X),

   Vars = X,
   solve([ff], Vars),

   println('x  '=X),
   fail,
   nl.

go => true.


global_contiguity(X) =>

   N = X.length,

   % Transition function (MiniZinc style)  
   % This use the regular expression "0*1*0*" to 
   % require that all 1's (if any) in an array appear contiguously.
   % 
   Transition = [
                 [1,2], % state 1 (start) input 0 -> state 1, input 1 -> state 2 i.e. 0*
                 [3,2], % state 2: 1*
                 [3,0]  % state 3: 0*
                ],
   NStates = 3,
   InputMax = 2,
   InitialState = 1,
   AcceptingStates = [1,2,3],

   RegInput = new_list(N),
   RegInput :: 1..InputMax,  % 1..2

   % Translate X's 0..1 to RegInput's 1..2
   foreach(I in 1..N) 
      RegInput[I] #= X[I]+1  
   end,

   regular(RegInput,NStates,InputMax,Transition,InitialState, AcceptingStates).