/* 

  Banknote change in Picat.

  http://www.nosco.ch/ai/en/exercise_02.php#2.1
  """
  What are the possibilities to change the 100 Swiss Franc bank note into smaller notes 
  10 Fr., 20 Fr. and 50 Fr.

  Hint: Conceive the predicate

  change( N10, N20, N50)

  that finds all solutions by backtracking, such that 10*N10 + 20*N20 + 50*N50 = 100. 
  Save the possible values for N10, N20, N50 as facts, e.g. N10 can be one of 0, 1, 2, .., 10.
  """

  Code from
  http://www.nosco.ch/ai/en/solution_02.php#2.1


  This program contain 5 different approaches:
  - indexed facts
  - between/3
  - betwen/3 and findall/2.
  - list comprehension
  - CP


  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.

% Using indexed facts
go ?=>
  change(N10,N20,N50),
  println([N10,N20,N50]),
  fail,
  
  nl.

go =>
  true.


% Using between/3
go2 =>
  N100 = 100,
  between(0,N100 div 10,N10),
  between(0,N100 div 20,N20),
  between(0,N100 div 50,N50),
  100 == N10 * 10 + N20 * 20 + N50 * 50,
  println([N10,N20,N50]),
  fail,  
  nl.


% Between and findall.
go3 =>
  N100 = 100,
  All=findall([N10,N20,N50], (
                              between(0,N100 div 10,N10),
                              between(0,N100 div 20,N20),
                              between(0,N100 div 50,N50),
                              100 == N10 * 10 + N20 * 20 + N50 * 50)
                              ),
  println(All),
  
  nl.


% List comprehension
go4 => 
  N = 100,
  All = [ [N10,N20,N50] :
           N10 in 0..N div 10,
           N20 in 0..N div 20,
           N50 in 0..N div 50,
           N == N10 * 10 + N20 * 20 + N50 * 50        
         ],
  println(All),
  nl.


% CP
go5 => 
  L = new_list(3),
  L :: 0..100,
  L[1]*10 + L[2]*20 + L[3]*50 #= 100,
  All = solve_all(L),
  println(All),
  nl.



change( N10, N20, N50) =>
  c1( N10), c2( N20), c5( N50),
  100 is N10 * 10 + N20 * 20 + N50 * 50.

index(-)
c5( 0).
c5( 1).
c5( 2).

% c2( N) ?=> c5( N).
index(-)
c2( 0).
c2( 1).
c2( 2).
c2( 3).
c2( 4).
c2( 5).

% c1( N) ?=> c2( N).
index(-)
c1( 0).
c1( 1).
c1( 2).
c1( 3).
c1( 4).
c1( 5).
c1( 6).
c1( 7).
c1( 8).
c1( 9).
c1( 10).