Subject: Re: interesting problem

From: "Pascal J. Bourguignon" <[email-masked]>
Date: Tue, 16 May 2000 02:19:18 +0200

> Date: Mon, 15 May 2000 15:46:21 +0200 (GMT+0200)
> From: Paul Sephton <[email-masked]>
> 
> I _love_ these problems, and couldn't resist.  If this is a homework 
> assignment, then so be it...

Well, my own solution is somewhat different (it still gives equivalent
results,  of course).   I would  like to  have the  opinion  of prolog
experts  about  style, advantages,  inconvenients  and performance  of
these solutions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/*
Joe is hosting a party of an international organization. Not everybody 
speaks the same language and some of them speak more than 1 language. He 
invited 10 guests and including himself he plans to have a ROUND TABLE 
CHATTING SESSION. To make everybody comfortable, he sets the following 
rules.

Everybody can have conversation with both people who sit next to him/her in 
some language.

No two females sit next to each other.

Information about the invitee and the host is as following:

     Joe,Chris,Emily,Heidi, and Isacc speaks in English.
     Beth,Gong, and Isacc can speak in French.
     Chris,Dongjoon,Fred, and Jane can speak in Korean
     Gong,Heidi,Jane and Kenny can speak in Chinese
     Beth,Emily,Heidi,Chris, and Jane are females.

Find all possible seat arrangments starting with Joe. There are less
than 5 unique solutions.  HINT: Try on much simpler set of databases
and debug your program using trace.  Since there are 10!  possible
arrangements w/o any constraints, it may take time. For any case, you
may assume that there are at least 3 people in the party.
*/

language(joe,english).
language(chris,english).
language(emily,english).
language(heidi,english).
language(isaac,english).

language(beth,french).
language(gong,french).
language(isaac,french).

language(chris,korean).
language(dongjoon,korean).
language(fred,korean).
language(jane,korean).

language(gong,chinese).
language(heidi,chinese).
language(jane,chinese).
language(kenny,chinese).

sex(beth,female).
sex(emily,female).
sex(heidi,female).
sex(chris,female).
sex(jane,female).

male(X):- \+ sex(X,female).
female(X):- sex(X,female).
people(X):-language(X,_).

all_people(P):-
    findall(X,call(people,X),List),
    list_to_set(List,P).

not_two_female(X,Y):-
    \+ (female(X),female(Y)).

common_language(First,Second):-
    language(First,Language),language(Second,Language).

extract(Elem,[Elem|OldList],OldList).
extract(Elem,[Head|OldList],[Head|NewList]):-
    extract(Elem,OldList,NewList).

resolve_seats(First,Seated,[]):-
    Seated=[Last|_],
    not_two_female(First,Last),
    common_language(First,Last),
    write(Seated),write('\n').

resolve_seats(First,Seated,Unseated):-
    Seated=[Last|_],
    extract(New,Unseated,NUnseated),
    not_two_female(New,Last),
    common_language(New,Last),
    resolve_seats(First,[New|Seated],NUnseated).

internationnal_chat:-
    all_people(People),
    extract(joe,People,Unseated),!,
    resolve_seats(joe,[joe],Unseated),fail.

% ?- internationnal_chat.
% [emily, isaac, beth, gong, heidi, kenny, jane, fred, dongjoon, chris, joe]
% [emily, isaac, beth, gong, heidi, kenny, jane, dongjoon, fred, chris, joe]
% [chris, fred, dongjoon, jane, kenny, heidi, gong, beth, isaac, emily, joe]
% [chris, dongjoon, fred, jane, kenny, heidi, gong, beth, isaac, emily, joe]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

For example, I feel that using a list such as:

> language([english,joe,chris,emily,heidi,isacc]).

may be less performant than using a set of facts such as:

language(joe,english).
language(chris,english).
language(emily,english).
language(heidi,english).
language(isaac,english).

While  I'm new  to  prolog, up  to  now, I  find  that usually  prolog
programs can be just litteral transcriptions of the problem statements
(with some syntax).

For example, instead of writting :

> seatable(Left, Person) :-
>   sex(Person, female), speaks(Lang, Person),  speaks(Lang, Left),  
>   Left \= Person, not(seated(Left, _)), sex(Left, male).
> seatable(Left, Person) :-
>   sex(Person, male), speaks(Lang, Person), speaks(Lang, Left), 
>   Left \= Person, not(seated(Left, _)).

I write quite directly the rules edicted in the problem statement:

resolve_seats(First,Seated,Unseated):-
    Seated=[Last|_],
    extract(New,Unseated,NUnseated),
    not_two_female(New,Last),
    common_language(New,Last),
    resolve_seats(First,[New|Seated],NUnseated).

(With the special case when all are seated, because we have a round table:
resolve_seats(First,Seated,[]):-
    Seated=[Last|_],
    not_two_female(First,Last),
    common_language(First,Last),
    write(Seated),write('\n').
)

Also, using  assert to store  intermediate (non constant)  values does
not feel  prolog-like to me.  If I were  to use assert in  my program,
that would be only to cache the result of the rules not_two_female and
common_language.

-- 
__Pascal Bourguignon__    PGP Key ID:      0xEF5E9966
mailto:[email-masked]    PGP fingerprint: 00 F5 7B DB CA 51 8A AD 04 5B 
http://www.imaginet.fr/~pjb/               6C DE 32 60 16 8E EF 5E 99 66