CODEWITHSUNDEEP
prolog
Ohad
Ohad

Reputation: 1647

Prolog - a program that finds a group of values that sum to a particular value

I want to make a program that receives 3 arguments:

  1. list1 of coins for example: [5,2,1]
  2. value - sum we want to get
  3. list of coins that sum to that particular value - this list is a sub-list of list1 (it's allowed to repeat the same element , for ex: to reach 4, we can have the list [2,2])

so the program should do 2 things:

  1. change([5,2,1],4,[2,2]) will return Yes (cause 2+2 =4)

  2. change([5,2],6,Coins) will return Coins = [2,2,2]

this is my attempt:

change(_,0,Res).
change([X|Xs],Sum,Cs):- Sum <X, change(Xs,Sum,Cs).
change([X|Y],Sum,[X|Res]):- Sum>=X, Sum2 is Sum - X, change([X|Y],Sum2,Res).

Upvotes: 0

Views: 130

Answers (2)

CapelliC
CapelliC

Reputation: 60034

'guessing' an element from a list can be done with member/2.

Just pay care to termination

change(_,0,[]).
change(Coins,Sum,[C|Cs]) :-
   Sum > 0, member(C, Coins), Rest is Sum-C, change(Coins,Rest,Cs).

Upvotes: 1

Tudor Berariu
Tudor Berariu

Reputation: 4910

You need to change Res to [] for the last argument of the first rule. In addition, you should add a cut operator in the same rule to avoid getting the same result multiple times.

change(_, 0, []):-!.
change([X|Y], Sum, [X|Res]):-
    Sum >= X, !, % remove the cut operator to get all solutions
    Sum2 is Sum - X,
    change([X|Y], Sum2, Res).
change([_|Xs],Sum,Cs):-
    change(Xs, Sum, Cs).

Upvotes: 1

Related Questions