Q4.

The celebrity problem is the problem of finding the celebrity among n people. A celebrity is someone who does not know anyone (including themselves) but is known by everyone. Write a Python program to solve the celebrity problem.

-----------------------------------------------------------------------------------------------------------------------------

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.

-----------------------------------------------------------------------------------------------------------------------------

Celebrity Identification Steps

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.

-----------------------------------------------------------------------------------------------------------------------------

In [1]:
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.

-----------------------------------------------------------------------------------------------------------------------------

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() function returns True on the possible_celebrity, then that person is the celebrity, otherwise there is no celebrity.