/* 

  Cutting stock like problem in Picat.

  From https://stackoverflow.com/questions/70238640/implementing-cuttingstock-problem-in-prolog
  (This question is now removed.)
  """
  Implementing Cuttingstock Problem in Prolog

  Im trying to solve the Cuttingstock problem using constraints in prolog (CLPD). Given a number 
  L arrange a list to minimize the number of cuts needed.

  L = 100   
  K = [70,80,30,20,90,30,30,40]   
  -> [70+30,80+20,30+30+40,90] 

  I've found how one would solve the knapsack problem:

  Total = 1505,
  Prices = [215, 275, 335, 355, 420, 580],
  maplist(\P^A^M^(P*A #= M, A #>=0),Prices,Amounts,Ms),
  sum(Ms, #=, Total).

  How would I solve cuttingstock in prolog? Maybe somehow using a fold with constraints?
  """

  hakank: How is the suggested solution a cutting stock problem?
    L = 100   
    K = [70,80,30,20,90,30,30,40]   
    -> [70+30,80+20,30+30+40,90] 
  Shouldn't the cuts be between the elements in the list? This seems more like a
  knapsack problem, as is indicated by the latter comment in the question: 
  "arrange a list".
  But perhaps I don't understand what K represents....

  * go/0
    This model give the suggested solution, or another optimal solution.

      k = [70,80,30,20,90,30,30,40]
      Z:110
      Z:10
      z = 10
      x = [1,2,3,2,4,1,3,3]
      y = [100,100,100,90,0,0,0,0]
      1 = [70,30] = 100
      2 = [80,20] = 100
      3 = [30,30,40] = 100
      4 = [90] = 90

  * go2/0 
    Solves a problem that is more similar to the cutting stock problem:
      Given a stock with some integer marks on it (not necessary in 
      order), we want to cut it in parts where the sum of the marks is 
      as close to L (but not less) as possible?
  
    Here is a solution to an "ordered marks stock":

       k = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]
       Z:165
       Z:65
       z = 65
       x = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,4,4,4,4]
       y = [120,111,120,114,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

       1 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] = 120
       2 = [16,17,18,19,20,21] = 111
       3 = [22,23,24,25,26] = 120
       4 = [27,28,29,30] = 114


    Here is a solution to a random problem instance (no order of the marks):

      k = [34,37,28,16,44,36,37,43,50,22,13,28,41,10,14,27,41,27,23,37,12,19,18,30,33,31,13,24,18,36]
      Z:342
      Z:242
      Z:142
      z = 142
      x = [1,1,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,6,6,6,6,6,7,7,7,7,7]
      y = [115,117,128,120,128,112,122,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

      1 = [34,37,28,16] = 115
      2 = [44,36,37] = 117
      3 = [43,50,22,13] = 128
      4 = [28,41,10,14,27] = 120
      5 = [41,27,23,37] = 128
      6 = [12,19,18,30,33] = 112
      7 = [31,13,24,18,36] = 122


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

*/

import sat.
% import cp.
% import mip.
% import smt.


main => go.

go ?=>
  nolog,
  L = 100,
  K = [70,80,30,20,90,30,30,40],
  % _ = random2(),
  % K = [random(1,100) : _ in 1..30],
  % K = [84,87,78,16,94,36,87,93,50,22,63,28,91,60,64,27,41,27,73,37],
  println(k=K),
  N = K.len,

  % Assign X[I] to what "cut"/segment to select and minimize max(X)
  X = new_list(N),
  X :: 1..N,

  % Sum of the selected values for segment S
  Y = new_list(N),
  Y :: 0..L, % Cannot exceed L (knapsack rule)
  foreach(S in 1..N)
    Y[S] #= sum([K[J]*(X[J] #= S) : J in 1..N])
  end,

  % Symmetry breaking
  value_precede_chain(1..N,X),

  Z #= sum([cond(Y[I] #> 0,abs(L-Y[I]),0) : I in 1..N]),
  Z #> 0,
  
  Vars = X ++ Y,
  solve($[min(Z),degree,updown,report(printf("Z:%d\n",Z))],Vars),
  
  println(z=Z),
  println(x=X),
  println(y=Y),
  foreach(I in 1..N)
    T = [K[J] : J in 1..N, X[J] == I],
    if T != [] then
      println(I=T=sum(T))
    end
  end,
  nl,
  fail,
  nl.
go => true.

%
% A variant:
% 
% Let's say we have a ruler of 30 (M) cm long and we want
% to cut it in some parts where the sum of the values should be as
% close as possible to 100 (L) (but not less, in contrast to the
% knapsack rule in the other model).
% 
% Or more general: We have a ruler with some marks on it (not necessary in order) and
% we want to cut it in parts where the sum of the marks is as close to L (but not less)
% as possible?
%
% In which positions should we cut to get the 'waste' as small as possible?
%
% Note that we don't know how many cuts are neede.
% 
go2 ?=>
  nolog,
  L = 100,
  % M = 30,
  % K = 1..M,
  % 
  % K = [70,80,30,20,90,30,30,40],
  % _ = random2(),
  K = [random(1,50) : _ in 1..30],
  % K = [84,87,78,16,94,36,87,93,50,22,63,28,91,60,64,27,41,27,73,37],
  
  println(k=K),
  N = K.len,

  % Assign X[I] to what "cut"/segment to select and minimize max(X)
  X = new_list(N),
  X :: 1..N,

  % Sum of the selected values for segment S
  Y = new_list(N),
  Y :: [0] ++ L..L*2,

  % Symmetry breaking
  increasing(X),
  X[1] #= 1,  
  value_precede_chain(1..N,X),

  % We pick only the first possible segments
  foreach(I in 1..N-1)
    Y[I] #= 0 #=> Y[I+1] #= 0
  end,

  foreach(S in 1..N)
    Y[S] #= sum([K[J]*(X[J] #= S) : J in 1..N]),
    Y[S] #>=L #\/ Y[S] #= 0
  end,

  % The waste, to minimize
  Z #= sum([cond(Y[I] #> 0,abs(L-Y[I]),0) : I in 1..N]),
  Z #> 0,
  
  Vars = X ++ Y,
  solve($[min(Z),degree,updown,report(printf("Z:%d\n",Z))],Vars),
  
  println(z=Z),
  println(x=X),
  println(y=Y),
  nl,
  foreach(I in 1..N)
    T = [K[J] : J in 1..N, X[J] == I],
    if T != [] then
      println(I=T=sum(T))
    end
  end,
  nl,
  fail,
  nl.
go2 => true.




value_precede_chain(C, X) =>
  foreach(I in 2..C.length)
    value_precede(C[I-1], C[I], X)
  end.

% This definition is inspired by 
% MiniZinc definition value_precede_int.mzn
value_precede(S,T,X) =>
   XLen = X.length,
   B = new_list(XLen+1),
   B :: 0..1,
   foreach(I in 1..XLen)
     % Xis :: 0..1,
     Xis #= (X[I] #= S),
     (Xis #=> (B[I+1] #= 1))
     #/\ ((#~ Xis #= 1) #=> (B[I] #= B[I+1]))
     #/\ ((#~ B[I] #= 1) #=> (X[I] #!= T))
   end,
   B[1] #= 0.