/* 

  Min sum problem in Picat.

  From Alma-0, sumsum.a0:
  """
  The problem is from 
  @article{Gri82,
  Author	= { D.  Gries },
  Title		= { A Note on a Standard Strategy for Developing Loop Invariants and Loops },
  Journal	= scp,
  Volume	= 2,
  Year		= 1982,
  Pages		= {207--214}
  }

  The description follows 
  @book{AO97,
        author	= { K. R.  Apt and E. -R.  Olderog },
        title = "Verification of Sequential and Concurrent Programs",
        publisher = "Springer-Verlag",
        edition = "second",
        address = "New York",
        year = 1997
        }

  Consider an array a[1..N] of type INTEGER. By a section of a we mean a
  fragment of it of the form a[i:j] where 1 <= i <= j <= N.  The sum of
  a section a[i:j] is the sum of its elements.  A minimum-sum of
  a[1..N]$ is a section a[i:j] such that the sum of a[i:j] is minimal
  among all subsections of a[0..N].

  For example, the minimum-sum section of a[1..5]=(5,-3,2,-4,1)$ is
  $a[2:4]=(-3,2,-4)$ and its sum is -5.  The two minimum-sum sections of
  a[1..5]=(5,2,5,4,2) are $a[2:2]$ and $a[5:5]$.

  The problem is to find all mimimum-sum sections and to compute their sum.
  """

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

*/


% import util.
import cp.


main => go.


go =>
   L = [5,-3,2,-4,1],
   % L = [5,2,5,4,2],
   minsum(L,Start,End,MinSum),
   println([start=Start,end=End,minsum=MinSum]),
   println([L[K] : K in Start..End]),
   nl.


go2 =>
   N = 200,
   L = [(N div 2)-(random2() mod N) : _I in 1..N],
   println(l=L),
   time2(minsum(L,Start,End,MinSum)),
   println([start=Start,end=End,minsum=MinSum]),
   println([L[K] : K in Start..End]),

   println("\nAll optimal solutions:"),
   foreach(Range in findall([Start2,End2],minsum(L,Start2,End2,MinSum)))
      println([range=Range,[L[K] : K in Range[1]..Range[2]]])
   end,
   nl.

minsum(L,Start,End,MinSum) =>

   N = L.length,
   MaxAbs=sum([abs(L[I]) : I in 1..N]),

   % decision variables
   Start :: 1..N,
   End :: 1..N,
  
   MinSum :: -MaxAbs..MaxAbs,

   % constraints
   End #>= Start,

   MinSum #= sum([L[K]*(K #>=Start)*(K #=<End) : K in 1..N]),

   Vars = [Start,End,MinSum],
   if var(MinSum) then
     solve($[split,min(MinSum)],Vars)
   else
     solve($[split],Vars)
   end.