The celebrity problem is the problem of finding the celebrity among n
people.
Consider the below mentioned scenario:
Ruby, a columnist for the Times of India, is covering a party. Ruby's job is to identify a celebrity, if one exists. A celebrity is someone who does not know anyone (including themselves) but is known by everyone. Now, the problem is to find who the celebrity is in the party by asking questions to all the guests in the party of the following form, "Excuse me. Do you know the person over there?" Assume that all of the guests at the party are polite (even the celebrity).
Below are the steps in identifying the Celebrity.
Step 1.
The program uses a matrix such that matrix[i][j]
is True
if and only if i
knows j.
Step 2.
Create two functions eliminate_non_celebrities()
and check_if_celebrity().
Step 3.
The function eliminate_non_celebrities()
returns a candidate who maybe a celebrity. It takes the matrix and n as argument.
Step 4.
The function check_if_celebrity()
determines whether a person is a celebrity. It takes the matrix, possible_celebrity and n as argument.
Step 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
does not know j
, then j
cannot be the celebrity.
Step 6.
The function check_if_celebrity()
whether possible_celebrity
is known by everyone else and whether possible_celebrity
does not know anyone. If so, it returns True.
def eliminate_non_celebrities(matrix, n):
"""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_celebrity = 0
n = len(matrix)
for p in range(1, n):
if (matrix[possible_celebrity][p]
or not matrix[p][possible_celebrity]):
possible_celebrity = p
return possible_celebrity
def check_if_celebrity(possible_celebrity, matrix, n):
"""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_celebrity][i] is True:
return False
for i in range(n):
if matrix[i][possible_celebrity] is False:
if i != possible_celebrity:
return False
return True
def user_input():
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 = []
for i in range(n):
m.append([False]*n)
for i in range(n):
people = input(f'Enter list of people known to {i}: ').split()
for p in people:
p = int(p)
m[i][p] = True
possible_celebrity = eliminate_non_celebrities(m, n)
if check_if_celebrity(possible_celebrity, m, n):
print(f'{possible_celebrity} is the celebrity.')
else:
print('There is no celebrity.')
if __name__ == "__main__":
user_input()
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.
The user is asked to enter the number of people n.
The user is asked to specify the people known to each person and the matrix is updated.
A possible celebrity is returned by the function eliminate_non_celebrities().
If check_if_celebrity()
function returns True
on the possible_celebrity,
then that person is the celebrity, otherwise there is no celebrity.