Search code examples
prologeclipse-clp

For this currency code in Prolog, how can I make sure that the total number of coins are between 1 and 99 cents?

So here is a currency problem which calculates the fewest amount of coins to carry. There are 4 different kinds of coins (1 cent, 5 cent, 10 cent, and 25 cent). So when I ran the program the result gave me this:

?- questionFour(Coins, X).
Coins = [4, 1, 2, 3]
X = 10
Yes (0.03s cpu)

Found a solution with cost 10
Found no solution with cost 4.0 .. 9.0

The instructions state: "We want to carry as few coins as possible in the pockets but we also want to make sure that those coins can meet the request of any amount from 1 to 99 cents." So, when I calculated the total, it resulted in 104 cents. How can I make the total amount of cents in between 1 to 99 cents? I'm not sure if what I did was right or I need to add more code to this...

questionFour(Coins, Min) :-
    initiatingcoinsquestionFour(Values, Coins),
    coin_cons(Values, Coins, Pockets),
    Min #= sum(Coins),
    minimize((labeling(Coins), check(Pockets)), Min).

initiatingcoinsquestionFour(Values, Coins) :-
    Values = [1, 5, 10, 25],
    length(Coins, 4),
    Coins :: 0..99.

coin_cons(Values, Coins, Pockets) :-
    ( for(Price, 1, 99),
    foreach(CoinsforPrice, Pockets),
    param(Coins, Values)
    do
        price_cons(Price, Coins, Values, CoinsforPrice)
    ).

price_cons(Price, Coins, Values, CoinsforPrice) :-
    ( foreach(V, Values), foreach(C, CoinsforPrice), foreach(Coin, Coins),
    foreach(Prod, ProdList)
    do
        Prod = V*C,
        0 #=< C,
        C #=< Coin
    ),
    Price #= sum(ProdList).

check(Pockets) :-
    ( foreach(CoinsforPrice, Pockets)
    do
        once(labeling(CoinsforPrice))
).

I'm not sure if what I did was right, but I would like your opinion about this... Thank you!

Solution

  • I think your answer is correct. It's totally reasonable that sum of values of all chosen coins is 104 if you want to be able to get any value 1..99 from that coins.

    Here is a program (very different from your program) I've written to verify your result. I've got the same answer - so I think your program is OK.

    :- lib(ic).
:- lib(branch_and_bound).

questionFour(Coins, Sum) :-
    Values = [](1, 5, 10, 25),
    dim(Coins, [4]),
    Coins :: 0..99,
    ( for(Amount, 1, 99), param(Values, Coins) do
        [Ai, Bi, Ci, Di] :: 0..99,
        Ai #=< Coins[1], Bi #=< Coins[2], Ci #=< Coins[3], Di #=< Coins[4], 
        Ai * Values[1] + Bi * Values[2] + Ci * Values[3] + Di * Values[4] #= Amount ),
    array_list(Coins, CoinsList),
    Sum #= sum(CoinsList),
    minimize(labeling(Coins), Sum).