/* 

  Coins problem in Picat.

  COINS PROBLEM:
  http://www.comp.rgu.ac.uk/staff/ha/ZCSP/additional_problems/coins_problem/coins_problem.pdf
  
  This model is a port from the OPL version on page 4.
  The objective is to find (minumum) values of coins in order to 
  be able to handle all values from 1 to 100.

  Cf http://hakank.org/picat/coins3.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.


go ?=>
  Coin = 6, % number of coins
  Change = 100, % the change to handle: 1..Change

  Value = [1,2,5,10,20,50],
  
  %% Variant: The exact coin values are to be decided (slower)
  % Value = new_list(Coin),
  % Value :: 1..50,
  
  Num = new_list(Coin),
  Num :: 1..3,
  
  Sel = new_array(Change,Coin),
  Sel :: 0..3,

  % total number of coins (to minimize)
  SumCoins #= sum(Num),

  increasing(Value),

  % symmetry-breaking
  % foreach(I in 1..Coin-1)
  %   Value[I] * Num[I] #< Value[I+1]
  % end,

  foreach(I in 1..Coin, S in 1..Change)
     Sel[S,I] #<= Num[I]
  end,
  
  foreach(S in 1..Change)
    sum([ Value[I] * Sel[S,I] : I in 1..Coin]) #= S
  end,

  if var(Value[1]) then
    Vars = Value ++ Num ++ Sel.vars
  else 
    Vars = Num ++ Sel.vars
  end,
  println(solve),
  solve($[min(SumCoins),updown,report(printf("SumCoins: %w\n",SumCoins))],Vars),

  println(sumCoins=SumCoins),
  println(value=Value),
  println(num=Num),
  % println(sel=Sel),
  
  nl.

go => true.