/* 

  Subsequence sum in Picat.

  A sequence sub_seq is a subsequence of seq when all values in sub_seq are 
  exactly in the same order as in seq. 

  The minimum (maximum) subsequence sum problem is to find the minimal (maximal)
  sum and the corresponding subsequence given a specific length of a 
  subsequence.

  For the sequence [5,4,1,5,2,1] and a subsequence length of M the optimal 
  solution is
    subset_sum = 8
    subseq  = [4,1,2,1]

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

*/

import cp.

main => go.

go =>
  Seq = [5,4,1,5,2,1],
  M = 4,
  println(seq=Seq),
  println(m=M),
  
  member(Dir,[min,max]),  
  println(dir=Dir),
  subsequence_sum_solve(Seq,M,Dir, SubSeq,SubSeqSum),
  println(subset_sum=SubSeqSum),
  println('subseq '=SubSeq),
  nl,
  fail,
  nl.  


go2 =>
  _ = random2(),
  N = 1000,
  M = 14,
  Seq = [random(1,N) : _ in 1..N],
  println(seq=Seq),
  println(m=M),

  member(Dir,[min,max]),  
  println(dir=Dir),  
  subsequence_sum_solve(Seq,M,Dir, SubSeq,SubSeqSum),
  println(subset_sum=SubSeqSum),
  println('subseq '=SubSeq),
  nl,
  fail,
  nl.  

subsequence_sum_solve(Seq,M,Dir, SubSeq,SubSeqSum) =>

  SubSeq = new_list(M), 
  SubSeq :: min(Seq)..max(Seq),
  
  % SubSeqSum #>= 0,
  
  subsequence_sum(Seq,SubSeq, SubSeqSum),

  Vars = SubSeq,
  if Dir == min then
    solve($[min(SubSeqSum),ff,split],Vars)
  else
    solve($[max(SubSeqSum),ff,split],Vars)  
  end.


%
% Sums the sequence sub_seq in an sub sequence of seq
%
subsequence_sum(Seq, SubSeq,SubSeqSum) =>
  N = Seq.len,
  M = SubSeq.len,
  Offset :: 0..N-M, % offset in seq
  % identify the positions in seq for all elements in sub_seq
  foreach(I in 1..M)
    OffsetI #= Offset+I,
    element(OffsetI,Seq,SubSeq[I])
   end,
   % sum the subsequence
   SubSeqSum #= sum(SubSeq).