CODEWITHSUNDEEP
prolog
Sam Daly
Sam Daly

Reputation: 51

List processing calculation in Prolog to find a destination friends will visit

I'm trying to write a predicate that calculates which destination a group of friends will visit. The friends list their countries of preferences like this 

choice(marie, [peru,greece,vietnam]). 
choice(jean, [greece,peru,vietnam]). 
choice(sasha, [vietnam,peru,greece]). 
choice(helena,[peru,vietnam,greece]). 
choice(emma, [greece,peru,vietnam]).

I want to write a predicate called where that takes 2 arguments to perform the calculation. The formula I have in mind is that the first country is worth 3 points, the second one is worth 2 points, and the last one is worth 1 point.

Here's an example of what I'm trying to achieve.

?- where([marie,jean,sasha,helena,emma],Country). 
peru .

So far I have this

where([], X).
where([H|T], N) :- choice(H, [A|B]), where(T,N).

It lets me iterate through all the different friends and shows their choices but I can't iterate through the list of choices and assign points to the destinations.

How should I go about iterating through the list of choices for each friend and assigning points to calculate the best destination?

Upvotes: 0

Views: 228

Answers (2)

Guy Coder
Guy Coder

Reputation: 24996

While this will solve your problem, I know it uses many predicates that you have not seen. So think of this an opportunity to excel and learn a lot.

Even if you don't understand it all, there is enough detail and intermediate results in the test that you should be able to navigate your way to a proper solution you create.

Also this is by no means efficient, it was just a quick proof of concept I did to see how this could be done.

choice(marie, [peru,greece,vietnam]).
choice(jean, [greece,peru,vietnam]).
choice(sasha, [vietnam,peru,greece]).
choice(helena,[peru,vietnam,greece]).
choice(emma, [greece,peru,vietnam]).

destinations(Destinations) :-
    findall(D1,choice(_,D1),D2),
    flatten(D2,D3),
    list_to_set(D3,Destinations).

init_weights(Destinations,Weights) :-
    empty_assoc(Assoc),
    init_weights(Destinations,Assoc,Weights).

init_weights([],Weights,Weights).
init_weights([H|T],Assoc0,Weights) :-
    put_assoc(H,Assoc0,0,Assoc1),
    init_weights(T,Assoc1,Weights).

update_weights([C1,C2,C3],Weights0,Weights) :-
    del_assoc(C1,Weights0,Value0,Weights1),
    Value1 is Value0 + 3,
    put_assoc(C1,Weights1,Value1,Weights2),
    del_assoc(C2,Weights2,Value2,Weights3),
    Value3 is Value2 + 2,
    put_assoc(C2,Weights3,Value3,Weights4),
    del_assoc(C3,Weights4,Value4,Weights5),
    Value5 is Value4 + 1,
    put_assoc(C3,Weights5,Value5,Weights).

person_weight(Person,Weights0,Weights) :-
    choice(Person,[C1,C2,C3]),
    update_weights([C1,C2,C3],Weights0,Weights).

people(People) :-
    findall(Person,choice(Person,_),People).

choice(Destination) :-
    destinations(Destinations),
    init_weights(Destinations,Weights0),
    people(People),
    update_choices(People,Weights0,Weights1),
    cross_ref_assoc(Weights1,Weights),
    max_assoc(Weights, _, Destination),
    true.

cross_ref_assoc(Assoc0,Assoc) :-
    assoc_to_list(Assoc0,List0),
    maplist(key_reverse,List0,List),
    list_to_assoc(List,Assoc).

key_reverse(Key-Value,Value-Key).

update_choices([],Weights,Weights).
update_choices([Person|People],Weights0,Weights) :-
    person_weight(Person,Weights0,Weights1),
    update_choices(People,Weights1,Weights).

Tests

:- begin_tests(destination).

test(destinations) :-
    destinations([peru, greece, vietnam]).

test(init_weights) :-
    destinations(Destinations),
    init_weights(Destinations,Weights),
    assoc_to_list(Weights,[greece-0, peru-0, vietnam-0]).

test(update_weights) :-
    destinations(Destinations),
    init_weights(Destinations,Weights0),
    update_weights([peru,greece,vietnam],Weights0,Weights),
    assoc_to_list(Weights,[greece-2,peru-3,vietnam-1]).

test(person_weight) :-
    destinations(Destinations),
    init_weights(Destinations,Weights0),
    person_weight(jean,Weights0,Weights),
    assoc_to_list(Weights,[greece-3,peru-2,vietnam-1]).

test(people) :-
    people([marie,jean,sasha,helena,emma]).

test(update_choices) :-
    destinations(Destinations),
    init_weights(Destinations,Weights0),
    people(People),
    update_choices(People,Weights0,Weights),
    assoc_to_list(Weights,[greece-10,peru-12,vietnam-8]).

test(cross_ref_assoc) :-
    List0 = [1-a,2-b,3-c],
    list_to_assoc(List0,Assoc0),
    cross_ref_assoc(Assoc0,Assoc),
    assoc_to_list(Assoc,[a-1,b-2,c-3]).

test(choice) :-
    choice(peru).

:- end_tests(destination).

Upvotes: 2

CapelliC
CapelliC

Reputation: 60034

As suggested by GuyCoder, you need an accumulator to sum each person preferences, and foldl/N allows to does exactly this.

choice(marie, [peru,greece,vietnam]).
choice(jean,  [greece,peru,vietnam]).
choice(sasha, [vietnam,peru,greece]).
choice(helena,[peru,vietnam,greece]).
choice(emma,  [greece,peru,vietnam]).

where(People,Where) :-
    foldl([Person,State,Updated]>>(choice(Person,C),update(State,C,Updated)),
          People,
          [0=greece,0=peru,0=vietnam],
          Pref),
    aggregate(max(S,S=W),member(S=W,Pref),max(_,_=Where)).
%    sort(Pref,Sorted),
%    last(Sorted,_=Where).

update(S0,[A,B,C],S3) :-
    update(S0,3,A,S1),
    update(S1,2,B,S2),
    update(S2,1,C,S3).

update(L,V,C,U) :-
    append(X,[Y=C|Z],L),
    P is Y+V,
    append(X,[P=C|Z],U).

I have left commented the last two goals replaced by the single goal aggregate/3, so you can try to understand the syntax...

Upvotes: 1

Related Questions