Solve the celebrity problem using Python

In this tutorial, we will learn to solve the celebrity problem using a Python program. Here, we need to find the celebrity among a group of people on the basis of his/her popularity. A celebrity is a person who is well known to everyone among the group. So, in this tutorial, we will get to know about the celebrity problem, a method to find a celebrity among a group of people, and a Python program to solve the celebrity problem.

The celebrity problem in Python

So, while solving the celebrity problem, we need to find whether there is a celebrity among a group of people. There are some conditions/rules by which we can find the celebrity. The conditions/rules are-

  • Every person of the group must know the celebrity.
  • Celebrity does not know anyone among the group.
  • The celebrity does not know himself/herself.
  • The maximum number of celebrities among the group is one.

An example of solving a celebrity problem

Problem statement-

  • Suppose there is a group of 4 people.
  • To find the celebrity among this group, we need the information of people known to each person in the group.
  • Let the name of 4 people be-
    1. Afiya
    2. Tanushri
    3. Amira
    4. Swara.
  • Let us consider the following information of people known to Afiya, Tanushri, Amira, and Swara-
    1. Afiya knows Tanushri and Swara.
    2. Tanushri knows no one.
    3. Amira knows Afiya, Tanushri, and Swara.
    4. Swara knows Tanushri and Amira.

Solution-

  • In the above example, to find the celebrity we will check the conditions/rules stated above-
  • Everyone in the group knows Tanushri.
  • Tanushri does not know anyone.
  • Moreover, she does not know herself.
  • There is only one person who fulfills every condition i.e. Tanushri.

Conclusion-

  • So, the person Tanushri is the celebrity among this group.

Implementation method to find celebrity among a group in Python

Firstly, we will take the number of people in the group from the user. Using a Python list, we will store the people known to each person of that group. Then, we will find the people who can be the celebrity. To find such people, we will search the people who know no one i.e. people having an empty Python list. After this, we will search the Python list of every person in that group and check whether they know these people. So, in the end, we will get the person whom everybody in the group knows. But this person will know no one including himself/herself. Finally, we will get a celebrity in the group. If no such person exists, there will be no celebrity in that group.

Let us understand the above implementation method with the help of an example-

Example 1: Person-1 is the celebrity in the group.

Number of people in group = 4
Name of people-
        Person-0
        Person-1
        Person-2
        Person-3
People known to Person-0 are --> Person-0, Person-1, and Person-3
People known to Person-1 are --> No one
People known to Person-2 are --> Person-1 and Person-2
People known to Person-3 are --> Person-0, Person-1, and Person-3

At first, we find the person having an empty list.
Here, Person-1 is having an empty list.
Because Person-1 does not know anyone.

Now, check whether everyone knows Person-1 or not.
So, Person-0, Person-2, and Person-3 know Person-1.
Finally, we conclude that Person-1 is the celebrity in this group.

Example 2: There is no celebrity in the group.

Number of people in group = 4
Name of people-
        Person-0
        Person-1
        Person-2
        Person-3

People known to Person-0 are --> Person-0 and Person-1.
People known to Person-1 are --> No one.
People known to Person-2 are --> Person-1, Person-2, and Person-3.
People known to Person-3 are --> No one.

At first, we find the people having an empty list.
Here, Person-1 and Person-3 are having an empty list.
Because Person-1 and Person-3 do not know anyone.

Now, check whether everyone knows Person-1 or not.
So, only Person-0 and Person-2 know Person-1.
Person-3 does not know Person-1.
Therefore, we conclude that Person-1 is not a celebrity in this group.

Now, check whether everyone knows Person-3 or not.
So, only Person-2 knows Person-3.
Person-0 and Person-1 do not know Person-3.
Therefore, we conclude that Person-3 is also not a celebrity in this group.

So, there is no celebrity in this group.

Python program to solve the celebrity problem

Now, we will see a Python program that solves the celebrity problem. Firstly, we will take the number of people in the group and the people known to each person of the group from the user as input. The Python program is given below-

def possible_celeb(people):
  possible = []	
  for i in range(0,len(people)):
    if len(people[i])==0:
      possible.append(i)
  return possible
def find_celeb(people,possible):
  result = []
  for position in possible:
    celeb = False
    for person in range(0,len(people)):
      if person != position:
        for known in people[person]:
          if (ord(known) - 48) == position:
            celeb = True
            result.append(position)
  if len(result) == len(people) - 1:
    return result[0]
  else:
    return -1
num = int(input("ENTER NUMBER OF PEOPLE : "))
print("THERE ARE %d PEOPLE -"%num)
for person in range(0,num):
  print("PERSON-%d"%person,end = ' ')
print('\n')
people = []
for i in range(num):
  people.append(input("ENTER PEOPLE KNOWN TO PERSON-{} : ".format(i)).split())
possible = possible_celeb(people)
celeb = find_celeb(people,possible)
if celeb == -1:
  print("THERE IS NO CELEBRITY AMONG THESE PEOPLE")
else:
  print("THE PERSON-%d IS THE CELEBRITY AMONG THESE PEOPLE"%celeb)

The function ‘possible_celeb’ finds out people who know no one in the group. And the function ‘find_celeb’ finds which person of the list ‘possible’ is known to everyone in the group. If a person is found, that person is called a celebrity. Otherwise, there will be no celebrity in the group.

Python program output

Finally, the output after sample execution of the above Python program which displays the celebrity person name if found in the group is-

siddharth@siddharth-Lenovo-Y520-15IKBN:~/python$ python3 celeb.py
ENTER NUMBER OF PEOPLE : 4
THERE ARE 4 PEOPLE -
PERSON-0 PERSON-1 PERSON-2 PERSON-3 

ENTER PEOPLE KNOWN TO PERSON-0 : 0 3
ENTER PEOPLE KNOWN TO PERSON-1 : 3
ENTER PEOPLE KNOWN TO PERSON-2 : 3 4
ENTER PEOPLE KNOWN TO PERSON-3 : 
THE PERSON-3 IS THE CELEBRITY AMONG THESE PEOPLE
siddharth@siddharth-Lenovo-Y520-15IKBN:~/python$

So, the person ‘PERSON-3’ is the celebrity among this group.

Thanks for reading this tutorial. I hope it helps you.

Also read: How to solve triangular matchstick number in Python

Leave a Reply