/* 

  How many ate all 4 foods in Picat.

  From MindYourDecisions
  https://www.youtube.com/watch?v=WMM0b2Sa0T4
  """
  Can you solve how many must have eaten all 4 foods?

  At an amusement park, 65% of visitors ate a donut, 80% ate a soft pretzel, 
  80% ate pizza, and 90% ate ice cream. What is the minimum percentage 
  of visitors that ate all 4 foods?
  """

  Hare is one - of many optimal - solutions:

  [65,80,80,90]
  z = 15
  0110000011110100101000111101010111111101010000110110101110111110100111011011111110111001101111111111
  1111111101011111111111111111111011111111101111101101010101101111011111111100101111101111110011010110
  1111111111111011110111100110111101001110111111111011111011110001111100101111110111111111111111101101
  1111111110101111011111111111101111110111111111011111111111111111111111111111111001011111111101111111
  .^^...................^..^.......^...^....................^........^....^...^.......^..^^....^...^..

  z = 15
  1111111111111111111110000000000000000000000000000000000011111111111111111111111111111111111111111111
  1111111111111111111001111111111111111111111111111111111111111111111111100000001010101010101010100101
  0000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111110
  1111111111111111111111111111111111111111111111111111111111111111111111111111110101010101010101011011
  ........................................................^^^^^^^^^^^^^^^.............................

 

  Cf https://math.stackexchange.com/questions/102598/100-soldiers-riddle
  """
  There are 100 soldiers. 85 lose a left leg, 80 lose a right leg, 
  75 lose a left arm, 70 lose a right arm. What is the minimum number of 
  soldiers losing all 4 limbs?
  """

  z = 10
  1111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000
  1100001001011111111001111101111111111101111101101101001111101111110111011110111111111111111111111111
  1111111111111011100110100110111101101110001011111011111011110001011110101011100110111111111111111111
  1111110110101100011111111011000010010111110110011110110100111110101101111101011001001111111111111111
  ^^..........^.........^..............^..........^.........^........^....^...........^...............

  z = 10
  1111111111111111111111111111111000000000000000111111111111111111111111111111111111111111111111111111
  1111111111111111111111111111111111111111111111111111111101010101010101010101010101010101010101011111
  1111111111111111111111110011111111111111111111111111111110101010101010101010101010101010101010100001
  0000000000000000000000001100000111111111111111111111111111111111111111111111111111111111111111111110
  ..............................................^^^^^^^^^^............................................


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

*/

import mip. % This is a MIP problem. GLPK is a little faster than Cbc. And scip is the fastest.
import util.

main => go.

go ?=> 
  Ls = [ [65,80,80,90], % ate all 4 foods
         [85,80,75,70]  % soldiers losing all 4 limbs
       ],
  member(L,Ls),
  println(L),
  min_all(L, X,Z),
  println(z=Z),
  foreach(Row in X)
    println(Row.to_list.map(to_string).join(''))
  end,
  println( [ cond( sum([ X[I,J] : I in 1..L.len]) == L.len,'^','.') : J in 1..X[1].len]),
  nl,
  fail,
  nl.

go => true.


%
% Simpler approach, based on the answer from math.stackexchange.com question op cit.
%
go2 ?=>
  Ls = [ [65,80,80,90], % ate all 4 foods
         [85,80,75,70]  % soldiers losing all 4 limbs
       ],
  member(L,Ls),
  println(l=L),
  println(100-[100-V : V in L].sum),
  nl,
  fail,
  nl.
go2 => true.

min_all(L, X,Z) =>
  Len = L.len,
  N = 100,
  X = new_array(Len,N),
  X :: 0..1,

  % decreasing(X[1]), % symmetry breaking, slightly slower for the MIP solver
  foreach(I in 1..Len)
    sum([ X[I,J] : J in 1..N]) #= L[I]
  end,
  Z #= sum([sum([X[I,J] : I in 1..Len]) #= Len : J in 1..N] ),
  solve($[min(Z)],X).