Celebrity Problem in Python

This is a Python program to solve the celebrity problem.

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?”

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.

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.')

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.

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.