CODEWITHSUNDEEP
recursionprolog
rphello101
rphello101

Reputation: 1771

How can you find a certain condition that matches parameters in Prolog?

I'm new to Prolog and quite confused. We're just moving in to recursion and members. I have the task to find different combinations of fast food given the type, calories, and price:

burger 450 $5 
fries 250 $2 
shake 500 $3 
salad 150 $7

I created a rule:

findfood(Calories, Price, Burger, Fries, Shake, Salad) :-
    member(Burger, [0,1]),
    ...,
    C is Burger*450 + Fries*250 + ...,
    Price is Burger*5 + Fries*2 + ...,
    C =< Calories.

where '...' indicates a continuation of the previous to the end of the list of food items. Essentially, you can purchase 1 of each item and indicate such with a 0 or a 1 (this is all part of the specifications).

I need to find the most expensive food combination less than or equal to a certain caloric amount. I am allowed to create multiple rules to do this. It should be something like:

|?- most_expensive(1000, Price, Burger, Fries, Shake, Salad)

and it will return the most expensive combination of food for 1000 calories. I know I'll need to do some sort of recursive comparison, but I'm not sure how to proceed. For the record, I understand recursion pretty well, just not Prolog. Can anyone perhaps explain how I might accomplish this?

Upvotes: 0

Views: 169

Answers (1)

Daniel Lyons
Daniel Lyons

Reputation: 22803

So, you elided some of the code, but I gather this is what you have:

findfood(Calories, Price, Burger, Fries, Shake, Salad) :-
    member(Burger, [0,1]),
    member(Fries, [0,1]),
    member(Shake, [0,1]),
    member(Salad, [0,1]),
    Calories is Burger * 450 + Fries * 250 + Shake * 500 + Salad * 150,
    Price is Burger * 5 + Fries * 2 + Shake * 3 + Salad * 7.

This seems sensible, if labor-intensive. Now you can easily enumerate all of the possibilities following @mbratch's advice:

all_combos(Combinations) :-
    setof((C,P,B,F,Sh,Sa), findfood(C,P,B,F,Sh,Sa), Combinations).

You can also abuse Prolog to get the solution you want from this:

most_expensive_under(MaximumCalories, Calories, Price, Burgers, Fries, Shakes, Salads) :-
    all_combos(Combos),
    member((Calories, Price, Burgers, Fries, Shakes, Salads), Combos),
    Calories =< MaximumCalories,
    \+ (member((Calories2, Price2, _, _, _, _), Combos),
        Calories2 =< MaximumCalories,
        Price2 > Price).

This declares that the most expensive option is the one for which there is no other option satisfying the maximum calorie constraint with a greater price. Trying it seems to succeed:

?- most_expensive_under(1000, Calories, Price, Burgers, Fries, Shakes, Salads).
Calories = 850,
Price = 14,
Burgers = Fries, Fries = Salads, Salads = 1,
Shakes = 0 ;
false.

Bear in mind, this kind of solution is O(N^2). I bring it up really only to illustrate the power of unification—it's not a great idea, performance-wise. A better idea would be to use setof/3, which sorts its results, as @mbratch suggests, or library(aggregate), which I've never used but hear good things about.

Upvotes: 1

Related Questions