{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a016336c",
   "metadata": {},
   "source": [
    "NAME:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db477b79",
   "metadata": {},
   "source": [
    "<center>\n",
    "    <h3>ASSIGNMENT#1 (Algorithms) - Nov. 27, 2023</h3>\n",
    "</center>\n",
    "\n",
    "Due date: **December 8th, 2023, 5pm** (no extension will be allowed).\n",
    "\n",
    "Submit your solution by email: romain.vuillemot@ec-lyon.fr\n",
    "\n",
    "You may work as a group (max 2) but all members are required to submit their solution and indicate their collaborator (if any).\n",
    "\n",
    "## Goal of this assignment\n",
    "\n",
    "In this assignment we provide you with a dataset of characters from a movie. Your role will be to answer the questions below programmatically, using Pyhon. **Please note you need to answer with fully working python code embedded in this notebook as solution (no external modules or files can be included).** You may then replace the code below with your answer for each question:\n",
    "\n",
    "```python\n",
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()\n",
    "```\n",
    "\n",
    "## Grading\n",
    "\n",
    "- 20% for the results to the questions\n",
    "- 60% for the code quality\n",
    "- 20% for the notebook presentation\n",
    "-  +10% bonus question\n",
    "\n",
    "## Getting started\n",
    "\n",
    "We provide you with a dataset containing movie characters. Each character is represented as a row, along with connections to other characters, based on the movie script. You will use those connections to create a graph-based data structure and answer the questions. \n",
    "\n",
    "To get you started with the dataset, we provide you with the code that loads it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cf409997-537f-4f89-a039-c2b3494972f2",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "data_file = 'users.csv'\n",
    "\n",
    "with open(data_file, 'r') as file:\n",
    "    lines = file.readlines()\n",
    "    data = [tuple(line.strip().split(',')) for line in lines[1:]]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c48b6391-d858-4a35-b428-b99434ee2d57",
   "metadata": {
    "tags": []
   },
   "source": [
    "The `data` variable contains the list of characters. You may look at the `users.csv` file to grasp the values of this variable. Here is a sample:\n",
    "\n",
    "```\n",
    "[('Tony_Stark',\n",
    "  '40',\n",
    "  'Male',\n",
    "  '1.85',\n",
    "  'Steve_Rogers Natasha_Romanoff Bruce_Banner Thor_Odinson'),\n",
    " ('Steve_Rogers',\n",
    "  '98',\n",
    "  'Male',\n",
    "  '1.88',\n",
    "  'Tony_Stark Natasha_Romanoff Sam_Wilson Bucky_Barnes'),\n",
    "...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70e93e78-f4dd-435f-b0f7-d56d928d7051",
   "metadata": {},
   "source": [
    "**Question 1 -** How many characters are there in the dataset?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9022b450-6fa6-41d0-999e-e019917cda79",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "6474e3afbe1bbdb5b06ce64fc0534c4f",
     "grade": false,
     "grade_id": "cell-f45150625899eb53",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a1a4c6c-f95c-4dc3-8bb3-863d1048ae79",
   "metadata": {},
   "source": [
    "**Question 2 -** Write a function that turns the `data` variable into a dictionnary data structure like the one below. You may then be able to plot it with the `plot_character_connections` function provided in the next cell:\n",
    "\n",
    "```\n",
    "{'Tony_Stark': ['Steve_Rogers', 'Natasha_Romanoff', 'Bruce_Banner', 'Thor_Odinson'], 'Steve_Rogers': ['Tony_Stark', 'Natasha_Romanoff', 'Sam_Wilson', 'Bucky_Barnes'],\n",
    "..\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7139b3cf-1c00-43bb-bc1b-67b4a8e2a92d",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "65a8683bbae1730e7882a91135df6dfa",
     "grade": false,
     "grade_id": "cell-2b24cbad2d825c82",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "adjacency_list = {}\n",
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fbbdd57e-6895-4d3c-b561-406d5e6668a9",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# please run the cells below the \"Utils\" section first\n",
    "plot_character_connections(adjacency_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a62b350-2bc8-476d-b9c6-13a08d649bdc",
   "metadata": {},
   "source": [
    "**Question 3 -**  Is there a character self-connected to her/himself?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "232f3d2a-8300-40c1-a908-ebfa5e380ae1",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "12487a86c6f58024a3ebbe0d242b5d48",
     "grade": false,
     "grade_id": "cell-641c5f735f36d3f6",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b79c97bc-e7d5-4ff4-bb1c-5bdf1e3abae2",
   "metadata": {},
   "source": [
    "**Question 4 -** How many communities can you identify? We define a community as a sub-graph of connected people by a path (i.e. a connected component)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "98186a3a-bd4c-4bf8-9ebd-2f350a83c856",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "dcfadd1483b4e91449dcd93f77e36868",
     "grade": false,
     "grade_id": "cell-7b6675c6e2784006",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "840a8875-2f71-4da9-bbe7-0f1aab5f612b",
   "metadata": {},
   "source": [
    "**Question 5 -** Are connections mutual in the graph?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "12d15b4d-cf98-45aa-994c-e41070b9ea3a",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "90802fd6bde9d5da3b4577c3d86f9774",
     "grade": false,
     "grade_id": "cell-8875e1c325dd6853",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e1b0409-1dff-4d8b-a5d8-a1efa1c10125",
   "metadata": {},
   "source": [
    "**Question 6 (BONUS) -**  Among the community of characters, is there a fully connected one? (i.e. where all characters are directly connected to the others)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d8a1900d-c15f-4ef4-83d8-1ecfbc8bfcf8",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8a0cd9235224e442fb7dfe36544029cf",
     "grade": false,
     "grade_id": "cell-777cc851157e530d",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00c753ed-0905-4132-b276-4b415ba31408",
   "metadata": {},
   "source": [
    "## Utils"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d9f71538-98b6-4730-adc1-7ca84aa3748e",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def plot_character_connections(adjacency_list):\n",
    "    G = nx.DiGraph()\n",
    "    for character, connections in adjacency_list.items():\n",
    "        G.add_node(character)\n",
    "        for connection in connections:\n",
    "            G.add_edge(character, connection)\n",
    "\n",
    "    plt.figure(figsize=(12, 8))\n",
    "    pos = nx.spring_layout(G, seed=42)\n",
    "\n",
    "    nx.draw(\n",
    "        G,\n",
    "        pos,\n",
    "        with_labels=True,\n",
    "        node_size=500,\n",
    "        node_color='skyblue',\n",
    "        font_weight='bold',\n",
    "        font_size=10\n",
    "    )\n",
    "    plt.title('Movie characters')\n",
    "    plt.show()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}