Portuguese Logic Programming Contest CeNPL'2003

University of Évora

9-11 May 2003
CELEBRITY

Introduction

At a party, a person $c$ is a celibrity if $c$ is a person whom everyone knows and who knows no one. For instance, in the figure below, it is represented a party with celebrity Ivo (an arrow from $A$ to $B$ represents that A knows B).

Given that parties without celebrities are not interesting, they are not even considered as such.

Task

 
The task is to write an efficient program for finding the celibrity of a party. By efficient we mean that the search must be linear in the number of persons in the party.

Data

 
The program receives the party through the file "party.pl". Therein, the party is represented through facts built over predicates
people/1 (its parameter is a list with the people in the party), and knows/2.

Example:

people([ana,ze,to,rui,ivo]).
knows(ana,to).
knows(ana,ivo).
knows(ze,ivo).
...

The invocation of the program should be done through the predicate celebrity/1, which parameter should become unified with the  celebrity of the party.
 

Results

During the search of the celebrity, the program should print the tests it performs, for instance, by printing sentences like "Does ana know ze?".