/*

  Two coin applications in Picat.

  From "The ECLiPSe Book" pages 99f and 234 ff
  The solution in ECLiPSe is at page 236.

  """
  What is the minimum number of coins that allows one to pay _exactly_
  any amount smaller than one Euro? Recall that there are six different
  euro cents, of denomination 1, 2, 5, 10, 20, 50
  """

  There are 4 optimal solutions (8 coins):
    x=[1,2,1,2,1,1]
    x=[1,2,2,1,1,1]
    x=[2,1,1,2,1,1]
    x=[2,1,2,1,1,1]


  The other application (go2/0) is to create the denominations
  which minimize the number of coins used in this way.


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

*/

import cp.


main => go.

%
% This is faster with the cp solver ( 0.0006s) compared to the sat solver (about 8s)
%
go =>
       
   % the different coin values
   Variables = [1,2,5,10,25,50],

   N = length(Variables),

   Xs = new_list(N),
   Xs :: 0..99,

   % total number of the coins used
   NumCoins :: 0..99,
   NumCoins #= sum(Xs),
   
   % This is the "main loop":
   % Checks that all changes from 1 to 99 can be made.
   % To be honest I have forgotten exactly how
   % the ECLiPSe solution looked like.
   % Here is one way.
   foreach(J in 1..99)
       Tmp = new_list(N),
       Tmp :: 0..99,
       scalar_product(Variables,Tmp,J),
       % Ensure that we don't use more coins than in X[I]
       foreach(I in 1..N) 
          Tmp[I] #=< Xs[I] 
       end
   end,

   solve($[min(NumCoins)], Xs),

   writeln(num_coins=NumCoins),
   writeln(x=Xs),
   nl.

% scalar_product(A, X, Product) => 
%    Product #= sum([A[I]*X[I] : I in 1..A.length]).

% increasing(List) =>
%    foreach(I in 2..List.length) List[I-1] #=< List[I] end.

do_coins(J,Xs,Variables,N) =>
   Tmp = new_list(N),
   Tmp :: 0..99,
   scalar_product(Variables,Tmp,J),
   foreach(I in 1..N) Tmp[I] #=< Xs[I] end.


%
% A related problem:
%
% Is there a set of coin denominations which make it possible to change 
% into 1..99 with less than 8 coins?
% 
% Answer: Yes, there is. For example the following configuration:
%
% num_coins:7
% variables:[1,2,3,6,12,25,50]
% x:[1,1,1,1,1,1,1]
% 
% Though, it come with a cost of using 7 different coin denominations.
%
% Also, we can see that there is a set with just 5 different 
% denominations for the 8 coin change. However, it requires that 
% more than one coin of some of the denominations
%
% This is done by comment this constraint:
%       NumCoins #=< 8,
%
% Result: 
%   num_coins:8
%   variables:[1,2,4,11,33]
%   x:[1,1,2,2,2]
%
% This problem is faster using the SAT solver (about 13.7s) compared to the cp solver (about 51.3s)
%
go2 =>
    nolog, 
    % Number of coin denominations
    % Note: It increases with each failure to
    %       solve the instance.
    % N :: 1..10,
    % indomain(N),
    member(N, 1..10),
    write(n=N),nl,

    % we assume that there are no coin of a denomination larger than 50.
    Variables = new_list(N),
    Variables :: 1..50,

    all_different(Variables),
    increasing_strict(Variables),

    Xs = new_list(N),
    Xs :: 1..2, % use either 1 or two coins

    % total number of the coins used
    % in the exchange

    % optimize over total number of coins
    NumCoins #= sum(Xs),

    foreach(J in 1..99) do_coins(J,Xs,Variables,N) end,

    % optimize over number of denominations
    % NumCoins #= sum([1 : _ in Xs]),
    
    % can we manage with less than 8 coins?
    NumCoins #< 8,

    % search
    % Vars = Xs ++ Variables,
    Vars = Variables ++ Xs,
    println(vars=Vars),
    solve([$min(NumCoins)],Vars),

    % output
    writeln(num_coins=NumCoins), 
    writeln(variables=Variables),
    writeln(x=Xs), nl, nl.