/*
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 #=