Prolog Break Money into Smaller Amounts

Question

I have this predicate which returns true if S is equal to some equation say K + 2N + 3L = S. The money we have are 1, 5, and 10 respectively for K, N, L.

I don't want to use :- use_module(library(clpfd)), I want to solve this without it.

My intuition was to break this into subproblems like write a function breakMoney1(S,K) :- K is S. and create more helpers with one more parameter added however I am struggling with the problem of getting uninstantiated variables, when I compare.

 breakMoney(S,K,N,L) :-

Prolog doesn't have *functions*. It has *predicates*. They aren't the same thing. A *function* is imperative ("do such and such"). A *predicate* expresses a *relation* or a *rule*. It's unfortunately you're wanting to avoid CLPFD because it's a pure Prolog way of expressing *relationships* between numeric expressions. To your problem, you are saying your code has such-and-such a problem, but you haven't shown your code. Perhaps you can show what you've tried. — lurker, Mar 30 '15 at 10:35

score 5 · Accepted Answer · 2015-04-01T06:23:51.773

This is easier than you think, probably. A very naive solution following @Will Ness' suggestion would be:

break(Sum, K, N, L) :- integer(Sum), Sum >= 0,

    % upper bounds for K, N, and L
    K_Max is Sum div 1,
    N_Max is Sum div 5,
    L_Max is Sum div 10,

    % enumerate possible values for K, N, and L
    between(0, L_Max, L),
    between(0, N_Max, N),
    between(0, K_Max, K),

    Sum =:= K + 5*N + 10*L.

This will "magically" turn into a clp(fd) solution with very little effort: for example, replace between with X in 0..Max, and the =:= with #=. Although, it should be enough to simply say that X #>= 0 for each of the denominations. It is a good exercise to see how much of the constraints you can remove and still get an answer:

break(Sum, K, N, L) :-
    K #>= 0, N #>= 0, L #>= 0,
    Sum #= K + 5*N + 10*L.

Depending on how you instantiate the arguments, you might immediately get a unique answer, or you might need to use label/1:

?- break(100, P, 8, 5).
P = 10.

?- break(10, K, N, L).
K in 0..10,
-1*K+ -5*N+ -10*L#= -10,
N in 0..2,
L in 0..1.

?- break(10, K, N, L), label([K, N, L]).
K = N, N = 0,
L = 1 ;
K = L, L = 0,
N = 2 ;
K = 5,
N = 1,
L = 0 ;
K = 10,
N = L, L = 0.

But as @lurker has pointed out, there is very little reason not to use constraint programming for this problem. Unless, of course, you have a very clever algorithm for solving this particular problem and you know for a fact that it will outsmart the generic clp(fd) solution. Even then, it might be possible to achieve the same effect by using the options to labelling/2.

a less naive enumeration could be `between(0,L_Max,L), S1 is Sum - L*10, Nmax is S1 div 5, between(0,Nmax,N), S2 is S1 - N*5, 0 is S2 rem 1, K is S2 div 1, ...`. another approach entirely is to allow for the Sum to be unknown too, and generate all the possibilities in order of their sum total somehow, possibly in the manner similar to how the Hamming ("ugly") numbers are generated. might have to simulate streams for that, like e.g. [here](http://stackoverflow.com/a/8882745) or [here](http://stackoverflow.com/a/14514298/849891) and [here](https://gist.github.com/mndrix/4644762). — Will Ness, Apr 01 '15 at 22:35

Prolog Break Money into Smaller Amounts

1 Answers1

Linked