# Celebrity Problem in Python

This is a Python program to solve the celebrity problem.

Problem Description

The celebrity problem is the problem of finding the celebrity among n people. A celebrity is someone who doesn’t know anyone (including themselves) but is known by everyone. The problem is to find who the celebrity is by asking people questions of the form, “Do you know x?”

Problem Solution

1. The program uses a matrix such that matrix[i][j] is True iff i knows j.
2. Create two functions eliminate_non_celebrities and check_if_celebrity.
3. The function eliminate_non_celebrities returns a candidate who is maybe a celebrity. It takes the matrix as argument.
4. The function check_if_celebrity determines whether a person is a celebrity. It takes the matrix and the possible celebrity as argument.
5. The function eliminate_non_celebrities works on the principle that if matrix[i][j] = True, that is i knows j, then i cannot be the celebrity and if matrix[i][j] = False, that is i doesn’t know j, then j cannot be the celebrity.
6. The function check_if_celebrity checks whether possible_celeb is known by everyone else and whether possible_celeb doesn’t know anyone. If so, it returns True.

Program/Source Code

Here is the source code of a Python program to solve the celebrity problem. The program output is shown below.

def eliminate_non_celebrities(matrix):
"""Take an n x n matrix that has m[i][j] = True iff i knows j and return
person who is maybe a celebrity."""
possible_celeb = 0
n = len(matrix)
for p in range(1, n):
if (matrix[possible_celeb][p]
or not matrix[p][possible_celeb]):
possible_celeb = p
return possible_celeb

def check_if_celebrity(possible_celeb, matrix):
"""Take an n x n matrix that has m[i][j] = True iff i knows j and return
True if possible_celeb is a celebrity."""
for i in range(n):
if matrix[possible_celeb][i] is True:
return False

for i in range(n):
if matrix[i][possible_celeb] is False:
if i != possible_celeb:
return False

return True

n = int(input('Number of people: '))

# create n x n matrix initialized to False that has m[i][j] = True iff i knows j
m = [[False]*n for _ in range(n)]

for i in range(n):
people = input('Enter list of people known to {}: '.format(i)).split()
for p in people:
p = int(p)
m[i][p] = True

possible_celeb = eliminate_non_celebrities(m)

if check_if_celebrity(possible_celeb, m):
print('{} is the celebrity.'.format(possible_celeb))
else:
print('There is no celebrity.')
Program Explanation

1. The user is asked to enter the number of people n.
2. The user is asked to specify the people known to each person and the matrix is updated.
3. A possible celebrity is returned by the function eliminate_non_celebrities.
4. If check_if_celebrity returns True on the possible celebrity, then that person is the celebrity, otherwise there is no celebrity.

Runtime Test Cases
Case 1:
Number of people: 6
Enter list of people known to 0: 3 2 0
Enter list of people known to 1: 1 0 2 3
Enter list of people known to 2: 4 1 3
Enter list of people known to 3:
Enter list of people known to 4: 0 1 2 3 4 5
Enter list of people known to 5: 3
3 is the celebrity.

Case 2:
Number of people: 2
Enter list of people known to 0: 1
Enter list of people known to 1: 0
There is no celebrity.

Case 3:
Number of people: 1
Enter list of people known to 0:
0 is the celebrity.

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]