/* 

  Tug-of-war problem in Picat.

  From https://www.geeksforgeeks.org/tug-of-war/
  """
  Tug of War

  Given a set of n integers, divide the set in two subsets of n/2 sizes each such that 
  the difference of the sum of two subsets is as minimum as possible. If n is even, 
  then sizes of two subsets must be strictly n/2 and if n is odd, then size of one subset must 
  be (n-1)/2 and size of other subset must be (n+1)/2.

  For example, let given set be {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, the size of set is 10. 
  Output for this set should be {4, 100, 1, 23, 20} and {3, 5, -3, 89, 54}. Both output subsets 
  are of size 5 and sum of elements in both subsets is same (148 and 148).

  Let us consider another example where n is odd. Let given set be {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}. 
  The output subsets should be {45, -34, 12, 98, -1} and {23, 0, -99, 4, 189, 4}. The sums of elements in 
  two subsets are 120 and 121 respectively.
  """


  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 =>
  println("Problem 1:"),
  problem(1, S1),
  solve_problem(S1),

  println("Problem 2:"),
  problem(2, S2),
  solve_problem(S2),
  nl.


go2 =>
  _ = random2(),
  N = 63, % 1+random2() mod 100,
  println(n=N),
  S = [ (random() mod 100) - 50 : _ in 1..N ],
  println(S),
  println(sumS=sum(S)),
  solve_problem(S),

  nl.


solve_problem(S) =>
  N = S.len, 
  tug_of_war(S, X,Y,Sizes,Z),

  println(z=Z),
  println(x=X),
  println(x1=[S[I] : I in 1..N, X[I] == 1]),
  println(x2=[S[I] : I in 1..N, X[I] == 2]),
  println(y=Y),
  println(sizes=Sizes),

  nl.


tug_of_war(S, X,Y,Sizes,Z) => 

  N = S.len,

  % decision variables
  X = new_array(N),
  X :: 1..2, % side/subset 1 and side 2

  % sum of X[1] and X[2]
  Y = new_array(2),

  Sizes = new_array(2),
  if N mod 2 == 0 then
    Sizes :: [N div 2],
    println(sizes=(N div 2))
    
  else 
    SS = [(N-1) div 2, (N+1) div 2],
    println(sizes=SS),
    Sizes :: SS
  end,
  
  % constraints
  foreach(I in 1..2)
    Y[I] #= sum( [S[J]*(X[J]#=I) : J in 1..N]),
    Sizes[I] #= sum([(X[J]#=I) : J in 1..N ])
  end,

  Z #= abs(Y[1] - Y[2]),
  Z mod 2 #= sum(S) mod 2,

  % solve 
  Vars = X ++ Y ++ Sizes,
  
  solve($[min(Z),inout,updown,report(printf("Z: %d\n", Z))], Vars).


problem(1,S) => 
  S = [3, 4, 5, -3, 100, 1, 89, 54, 23, 20].


problem(2,S) => 
  S = [23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4].