/* 

  Frobenius number in Picat.

  http://mathworld.wolfram.com/FrobeniusNumber.html 
  """
  The Frobenius number is the largest value b for which the
  Frobenius equation
  a[1]*x[1] + a[2]*x[2]+...+a[n]*x[n]=b, 
  
  has no solution, where the a[i] are positive integers, b is an integer, and the 
  solutions x[i] are nonnegative integer.
  """

  See also:
  * http://mathworld.wolfram.com/CoinProblem.html
  * http://en.wikipedia.org/wiki/Coin_problem
  * http://reference.wolfram.com/language/ref/FrobeniusNumber.html
  * https://reference.wolfram.com/language/tutorial/Frobenius.html

  Given a list of integers, e.g. [6,9,20], the Frobenius number of 43 (the McNugget Number),
  means that it is possible to combine 6, 9, and 20 to get any number (integer) that is
  larger than 43.

  If the list contain 1, then any number is possible to get, and it is represented as -1 (infinity).
  Note that the approach here is brute-force using constraint modelling.


  Also see: http://hakank.org/picat/12_pack_problem.pi for related experiments.


  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.


go =>
  
  Nums = [6,9,20], % McNugget
  frobenius(Nums,Frobenius),
  println([Nums,frobenius=Frobenius]),
  nl.

go2 =>
  nolog,
  AllNums = [
             [6,9,20], % "McNugget number"
             [2,3,4],
             [1,2,3,4],             
             [4,7,12],
             [6,10,15],
             [3,7,11,13],
             [5,8,15],
             [83,89,97],
             [12, 16, 20, 27], % From http://reference.wolfram.com/language/ref/FrobeniusNumber.html
             [24, 29, 31, 34, 37, 39], % https://reference.wolfram.com/language/tutorial/Frobenius.html
             [8,13,21,34],     % See http://hakank.org/picat/12_pack_problem.pi
             [7,13],            % See http://hakank.org/picat/12_pack_problem.pi
             [5,17]            % See https://twitter.com/WWMGT/status/1409855152929054722

            ],
  foreach(Nums in AllNums) 
    % println(Nums),
    time2(frobenius(Nums,Frobenius)),
    println([Nums,frobenius=Frobenius]),
    nl
  end,

  nl.

go3 => 
  _ = random2(), 
  N = 8,
  Mod = 100,
  % We don't want 1 in the list since then F is infinity...
  Nums = [2+random() mod Mod : _ in 1..N].sort_remove_dups(),
  % while (not check_mod(Nums))
  %    Nums := [2+random() mod Mod : _ in 1..N].sort_remove_dups()
  % end,
  println(nums=Nums),
  frobenius(Nums,Frobenius),
  println(frobenius=Frobenius),
  nl.

%
% Check Nums=[N,N+1].
%
% From https://reference.wolfram.com/language/ref/FrobeniusNumber.html
%
go4 =>
  foreach(N in 1..15)
    L = [N,N+1],
    frobenius(L,F),
    println(L=F)
  end,
  nl.

%
% Note: This brute force approach needs a max number.
%
frobenius(Nums,Frobenius) =>
  Fail = -1,
  MaxC = sum(Nums)**2 div 2,
  % println(maxC=MaxC),
  foreach(I in 1..MaxC)
    if not check_sum(Nums,I) then   
      Fail := I
    end
  end,
  Frobenius = Fail.

check_sum(Nums,Num) =>
   N = Nums.length,
   X = new_list(N),
   X :: 0..Num**2,
   sum([X[I]*Nums[I]:I in 1..N]) #= Num,
   solve([updown],X).


%
% Calculate the Frobenius number of the numbers in the list Nums.
% It's a (somewhat intelligent) brute force method.
%
% frobenius_x(Nums,Frobenius) =>
%   N = Nums.length,
%   Mult :: 1..10000,
%   indomain(Mult),
%   println(mult=Mult),
%   MaxC = sum(Nums)*Mult,
%   println(maxC=MaxC),
%   Frobenius :: 1..MaxC,
%   indomain(Frobenius),
%   Vars = [],
%   foreach(I in Frobenius+1..MaxC+1)
%      X = new_list(N),
%      X :: 0..I,
%      Vars := Vars ++ X,
%      sum([X[J]*Nums[J] : J in 1..N]) #= I
%   end,
%   ( solve([ff,updown],Vars) ; fail).

% %
% % fails if any number is divisible by any other
% %
% check_mod(Nums) =>
%   Len = Nums.len, 
%   foreach(I in 1..Len, J in I+1..Len) 
%     if Nums[J] mod Nums[I] == 0 then
%       fail
%     end
%   end.