/* 

  12-pack problem in Picat.

  From Mathias Brandewinder:
  "The 12 pack-problem: combination of integers"
  http://clear-lines.com/blog/post/The-12-pack-problem-combination-of-integers.aspx
  """
  A fun problem came my way today. Imagine that you are the owner 
  of a renowned brewery in Bizzarostan, a country where beer is sold 
  only in 7-packs and 13-packs, sometimes described as the ++ packs. 
  Beer is a serious matter in Bizzarostan, and buying single bottles is 
  not tolerated by the law.

  You take great pride in doing what’s best for your customers, 
  so when a customers asks you for, say, 20 beers, you always try your 
  best to find the combination of 7-packs and 13-packs that will meet 
  your customer’s thirst, for the least amount of hard-earned money - 
  in that case, a 7-pack and a 13-pack.

  To be extra clear, the goal is to find a combination of 7- and 
  13-packs containing at least as many bottles as requested, 
  with a total number of bottles as close as possible to the amount requested.
  """

  Also see the follow up post:
  "12-pack,take one: a Sieve like approach"
  http://clear-lines.com/blog/post/12-pack-take-one-a-Sieve-like-approach.aspx
  """
  Suppose that you are given a list of integers, and a target integer. 
  Your goal is to find the closest value that is greater or equal 
  to the target, by combining integers ("packs") from the list (only 
  positive combinations are allowed). For instance, given 3 and 5, 
  the closest you can get to 16 would be 5 x 2 + 3 x 2 = 16, and the 
  closest to 17 would be 3 x 6 = 18.
  """

  Related:
  - https://mathworld.wolfram.com/CoinProblem.html
  - https://mathworld.wolfram.com/FrobeniusNumber.html
  - http://hakank.org/picat/mcnuggets_problem.pi
  - http://hakank.org/picat/frobenius_number.pi


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

*/

import cp.

main => go.

%
% Find one optimal solution.
%
go =>
  Target = 1230, 
  Given = [8,13,21,34], % list of given numbers
  Max = 1000, % Arbitrary max limit of amount
  println(given=Given),
  println(target=Target),

  n_pack_problem(Target,Given,Max, X,Total),
  println(total=Total),
  println(x=X),

  nl.

%
% Find all optimal solutions.
%
go2 =>
  Target = 1230, 
  Given = [8,13,21,34], % list of given numbers
  Max = 1000, % Arbitrary max limit of amount
  println(given=Given),
  println(target=Target),

  n_pack_problem(Target,Given,Max, _X,Total),
  println(optimal_total=Total),
  println("Find all optimal solutions:"),

  All=find_all(X2, n_pack_problem(Target,Given,Max, X2, Total)),
  foreach(A in All)
    println(A)
  end,
  println(len=All.len),
  nl.

%
% The 7 and 13 packs example described above, but here we check
% for which targets there are no exact solution.
% The last non exact solution found is for target=71,
% which is the Frobenius number of [7,13].
% 
% For more about this, see
% - https://mathworld.wolfram.com/FrobeniusNumber.html
% - http://hakank.org/picat/mcnuggets_problem.pi
% - http://hakank.org/picat/frobenius_number.pi
% - https://mathworld.wolfram.com/CoinProblem.html
% 
go3 =>
  NotExact = [],
  % Exact = [],
  Given = [7,13], % list of given numbers
  Max = 10000, % Arbitrary max limit of amount
  foreach(Target in (7+13)..100000)
    % println(target=Target),
    if n_pack_problem(Target,Given,Max, X,Total) then 
      % println(total=Total),
      % println(x=X),
      if Total != Target then
        NotExact := NotExact ++ [Target=(diff=Total-Target)]
      end
      % nl
    else
      println("Somethings is weird"=Target)
    end
  end,
  % println(exact=Exact),
  println(notExact=NotExact),
  nl.
  
n_pack_problem(Target, Given, Max, X, Total) =>
   N = Given.len,
   X = new_list(N),
   X :: 0..Max,

   Total #= sum([X[I]*Given[I] : I in 1..N]),
   Total #>= Target,
   if var(Total) then
      solve($[min(Total)],X)
   else
      solve($[],X)
   end.