{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## ```Q4.``` ##\n",
"\n",
"## ```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. ``` ##"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## -----------------------------------------------------------------------------------------------------------------------------"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The celebrity problem is the problem of finding the celebrity among ```n``` people. \n",
"\n",
"Consider the below mentioned scenario: \n",
"\n",
"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). \n",
"\n",
"Below are the steps in identifying the Celebrity."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## -----------------------------------------------------------------------------------------------------------------------------"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Celebrity Identification Steps ## \n",
"\n",
"```Step 1.``` The program uses a matrix such that ```matrix[i][j]``` is ```True``` if and only if ```i``` knows ```j.``` \n",
"\n",
"```Step 2.``` Create two functions ```eliminate_non_celebrities()``` and ```check_if_celebrity().``` \n",
"\n",
"```Step 3.``` The function ```eliminate_non_celebrities()``` returns a candidate who maybe a celebrity. It takes the _matrix_ and _n_ as argument. \n",
"\n",
"```Step 4.``` The function ```check_if_celebrity()``` determines whether a person is a celebrity. It takes the _matrix_, *possible\\_celebrity* and _n_ as argument. \n",
"\n",
"```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. \n",
"\n",
"```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.```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## -----------------------------------------------------------------------------------------------------------------------------"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Number of people: 6\n",
"Enter list of people known to 0: 3 2 0\n",
"Enter list of people known to 1: 1 0 2 3\n",
"Enter list of people known to 2: 4 1 3\n",
"Enter list of people known to 3: \n",
"Enter list of people known to 4: 0 1 2 3 4 5\n",
"Enter list of people known to 5: 3\n",
"3 is the celebrity.\n"
]
}
],
"source": [
"def eliminate_non_celebrities(matrix, n):\n",
" \"\"\"Take an n x n matrix that has m[i][j] = True iff i knows j and return\n",
" person who is maybe a celebrity.\"\"\"\n",
" possible_celebrity = 0\n",
" n = len(matrix)\n",
" for p in range(1, n):\n",
" if (matrix[possible_celebrity][p]\n",
" or not matrix[p][possible_celebrity]):\n",
" possible_celebrity = p\n",
" return possible_celebrity\n",
"\n",
"\n",
"def check_if_celebrity(possible_celebrity, matrix, n):\n",
" \"\"\"Take an n x n matrix that has m[i][j] = True iff i knows j and return\n",
" True if possible_celeb is a celebrity.\"\"\"\n",
" for i in range(n):\n",
" if matrix[possible_celebrity][i] is True:\n",
" return False\n",
"\n",
" for i in range(n):\n",
" if matrix[i][possible_celebrity] is False:\n",
" if i != possible_celebrity:\n",
" return False\n",
"\n",
" return True\n",
"\n",
"\n",
"def user_input():\n",
" n = int(input('Number of people: '))\n",
" # create n x n matrix initialized to False that has m[i][j] = True iff i knows j\n",
" m = []\n",
" for i in range(n):\n",
" m.append([False]*n)\n",
" \n",
" for i in range(n):\n",
" people = input(f'Enter list of people known to {i}: ').split()\n",
" for p in people:\n",
" p = int(p)\n",
" m[i][p] = True\n",
" possible_celebrity = eliminate_non_celebrities(m, n)\n",
" \n",
" if check_if_celebrity(possible_celebrity, m, n):\n",
" print(f'{possible_celebrity} is the celebrity.')\n",
" else:\n",
" print('There is no celebrity.')\n",
" \n",
"if __name__ == \"__main__\":\n",
" user_input()\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## -----------------------------------------------------------------------------------------------------------------------------"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Program Explanation \n",
"\n",
"1. The user is asked to enter the number of people ```n.```
\n",
"\n",
"2. The user is asked to specify the people known to each person and the matrix is updated.
\n",
"\n",
"3. A possible celebrity is returned by the function ```eliminate_non_celebrities().```
\n",
"\n",
"4. If ```check_if_celebrity()``` function returns ```True``` on the ```possible_celebrity,``` then that person is the celebrity, otherwise there is no celebrity."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
},
"pycharm": {
"stem_cell": {
"cell_type": "raw",
"metadata": {
"collapsed": false
},
"source": []
}
}
},
"nbformat": 4,
"nbformat_minor": 1
}