/* 

  Largest possible rectangle problem in Picat.

  From Stack Overflow
  Construct the largest possible rectangle out of line segments of given lengths
  http://stackoverflow.com/questions/7294548/construct-the-largest-possible-rectangle-out-of-line-segments-of-given-lengths
  """
  I recently participated in a competition where I was asked this question. Given an 
  array with lengths what is the area of the biggest rectangle that can be made using 
  ALL the lengths. The lengths can be added but not broken in between.
  
  Example: [ 4,2,4,4,6,8 ] given this array the best we can do is make a rectangle 
  of sides 8 and 6 like this.
  
      4       4    
     - - - - - - - -
    |              |
  4 |              |
    |              | 6
    |              |
  2 |              |
    |              |
     - - - - - - - 
           8
  
  giving an area of 8 * 6 = 48.

  I am a beginner and even after a long hard think about how to do it I am unable to get 
  anywhere. I am not looking for a solution but any clue to nudge me in the right direction 
  would be appreciated.
  """

  Solutions to the three problems

    problem = 1
    s = [4,2,4,4,6,8]
    area = 48
    x = [3,3,4,4,1,2]
    sum_sides = [6,8,6,8]
    num_sides = [1,1,2,2]

    Placements:
           [6]
    [4,4]          [8]
           [4,2]


   problem = 2
   s = [2,3,5,1,8,9]
   area = 45
   x = [3,3,1,4,4,2]
   sum_sides = [5,9,5,9]
   num_sides = [1,1,2,2]

   Placements:
           [5]
   [1,8]          [9]
           [2,3]


   problem = 3
   No solution!



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

*/

import sat.

main => go.

go =>
  nolog,
  member(Problem,1..3),
  println(problem=Problem),
  problem(Problem,S),
  if rectangle_from_line_segments(S, SumSides,NumSides,X,Area) then
     print_solution(S, SumSides,NumSides,X,Area)
  else
     println("No solution!")
  end,
  nl,
  fail,
  nl.



% Find all (6) optimal solutions of problem 1.
go2 =>
  nolog,
  problem(1,S),
  rectangle_from_line_segments(S, _SumSides,_NumSides,_X,Area),
  printf("\nFound optimal area: %d\n", Area),
  println("All optimal solutions:"),

  rectangle_from_line_segments(S, SumSides,NumSides,X,Area),
  print_solution(S, SumSides,NumSides,X,Area),
  fail,
  nl.

/* 
  Random instance.
  Here is a solution for N=100.

    s = [71,32,71,74,86,24,9,6,6,39,4,52,94,17,16,35,15,83,59,9,50,27,49,88,38,5,97,24,73,14,36,43,97,6,16,82,82,76,88,87,14,91,90,60,59,57,94,25,40,4,34,89,31,34,76,20,39,72,44,11,37,79,5,85,37,72,67,18,100,6,56,13,48,46,24,6,2,17,30,41,73,15,81,55,49,56,74,39,79,17,1,67,48,5,52,84,28,70,53,27]
area = 9236
    x = [4,4,4,4,2,4,4,4,4,4,3,4,2,4,4,4,4,2,4,4,2,4,2,2,2,4,2,4,4,2,4,2,2,4,4,2,2,4,2,4,2,2,2,4,4,4,2,4,4,1,4,2,4,4,2,2,2,4,2,2,2,4,2,2,2,4,4,4,4,4,4,4,2,2,4,4,4,2,4,4,2,4,2,4,2,2,4,4,2,4,4,4,2,2,4,2,4,4,4,4]
    sum_sides = [4,2309,4,2309]
    num_sides = [1,39,1,59]

    Placements:
            [4]
    [71,32,71,74,24,9,6,6,39,52,17,16,35,15,59,9,27,5,24,73,36,6,16,76,87,60,59,57,25,40,34,31,34,72,79,72,67,18,100,6,56,13,24,6,2,30,41,15,55,74,39,17,1,67,52,28,70,53,27]          [86,94,83,50,49,88,38,97,14,43,97,82,82,88,14,91,90,94,89,76,20,39,44,11,37,5,85,37,48,46,17,73,81,49,56,79,48,5,84]
            [4]

*/
go3 =>
  nolog, 
  _ = random2(),
  N = 100,
  S = [random(1,N) : _ in 1..N],
  println(s=S),
  if rectangle_from_line_segments(S, SumSides,NumSides,X,Area) then
     print_solution(S, SumSides,NumSides,X,Area)
  else
     println("No solution!")
  end,
  nl,
  fail,
  nl.


rectangle_from_line_segments(S, SumSides,NumSides,X,Area) =>
  N = 4,
  NumSegments = S.len,

  SumSides = new_list(N),
  SumSides :: 1..sum(S),
  
  NumSides = new_list(N),
  NumSides :: 1..NumSegments,
  
  % 
  %    Sides
  %         1 
  %     - - - - - 
  %    |         |
  %    |         |
  %  4 |         | 2
  %    |         |
  %    |         |
  %     - - - - -
  %         3
  %
  % on which side should this segments be placed?
  X = new_list(NumSegments),
  X :: 1..4,

  % area
  Area :: 0..sum(S)*2,

  % For generating problems we assume that s is sorted
  % increasing(S),
  %

  % Get the sums of each side
  % (also ensure that each side get an assignment in x)
  foreach(J in 1..N) 
    SumSides[J] #= sum([S[I]*(X[I]#=J) : I in 1..NumSegments]),
    NumSides[J] #= sum([X[I]#=J : I in 1..NumSegments])
  end,

  % Ensure that the sides are of the same length

  % Upper = lower
  SumSides[1] #= SumSides[3],

  % Left = right
  SumSides[2] #= SumSides[4],

  % The area (to be maximized)
  Area #= SumSides[1] * SumSides[2],

  % Symmetry breaking
  % X[1] #= 1, % we assign first segment to first side

  % Another symmetry breaking (not coherent with the one above)
  NumSides[1] #<= NumSides[3],
  NumSides[2] #<= NumSides[4],


  Vars = SumSides ++ NumSides ++ X,
  if var(Area) then
    solve($[constr,split,max(Area)],Vars)
  else
    solve($[constr,split],Vars)  
  end.


print_solution(S, SumSides,NumSides,X,Area) =>  
  println(s=S),
  println(area=Area),
  println(x=X),
  println(sum_sides=SumSides),
  println(num_sides=NumSides),
  nl,
  NumSegments = S.len,
  T1 = [S[I] : I in 1..NumSegments, X[I] == 1],
  T4 = [S[I] : I in 1..NumSegments, X[I] == 4],
  T2 = [S[I] : I in 1..NumSegments, X[I] == 2],
  T3 = [S[I] : I in 1..NumSegments, X[I] == 3],
  println("Placements:"),
  printf("        %w\n%w          %w\n        %w\n",T1,T4,T2,T3),
  nl,
  nl.


%
% Data
%

% Original problem
problem(1,[4,2,4,4,6,8]).

% From a comment
problem(2,[2,3,5,1,8,9]). 

% from a comment: unsolvable problem
problem(3,[1,2,3,4]).