/* 

  Sequence problem in Picat.

  From Marriott, Stuckey: "Programming with Constraints", pages 31ff, 294f

  Combine the three contigs
    [a,t,c,g,g,g,c],[a,a,a,a,t,c,g],[g,c,c,a,t,t]
  to an overlapping sequence:

     AAAATCG
       ATCGGGC
            GCCATT

  i.e. the sequence AAAATCGGGCCATT


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

*/

import util.

main => go.


go =>
  sequence_problem(T,Contigs),
  println(T),
  println(contigs=Contigs),
  nl.


sequence_problem(T,ContigsFound) =>
  contigs(Contigs),
  permutation(Contigs, [C1,C2,C3]),
  not_empty(O12),
  not_empty(O23),
  concat([UC1,O12], C1),
  concat([O12,UC2,O23], C2),
  concat([O23,UC3], C3),
  concat([UC1,O12,UC2,O23,UC3], T),
  ContigsFound = [C1,C2,C3].

contigs(Contigs) => 
  Contigs = [[a,t,c,g,g,g,c],[a,a,a,a,t,c,g],[g,c,c,a,t,t]].

not_empty(L) => L = [_|_].
concat([S1],S2) ?=> S2 = S1.
concat([S1,S2|Ss],S) => 
  append(S1,T,S), concat([S2|Ss],T).