class_04_content_based_recommenders.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "exciting-specific",
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "from IPython.display import Markdown, display, HTML\n",
    "from collections import defaultdict\n",
    "from sklearn.model_selection import KFold\n",
    "from sklearn.feature_extraction.text import TfidfVectorizer\n",
    "import time\n",
    "\n",
    "pd.set_option('display.max_columns', 50)\n",
    "\n",
    "from evaluation_and_testing.testing import evaluate_train_test_split_explicit\n",
    "from evaluation_and_testing.testing import evaluate_leave_one_out_explicit\n",
    "from evaluation_and_testing.testing import evaluate_train_test_split_implicit\n",
    "from evaluation_and_testing.testing import evaluate_leave_one_out_implicit\n",
    "\n",
    "from recommenders.recommender import Recommender\n",
    "\n",
    "# Fix the dying kernel problem (only a problem in some installations - you can remove it, if it works without it)\n",
    "import os\n",
    "os.environ['KMP_DUPLICATE_LIB_OK'] = 'True'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "administrative-charleston",
   "metadata": {},
   "source": [
    "# Load the data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "architectural-andrews",
   "metadata": {},
   "outputs": [],
   "source": [
    "ml_ratings_df = pd.read_csv(os.path.join(\"data\", \"movielens_small\", \"ratings.csv\")).rename(columns={'userId': 'user_id', 'movieId': 'item_id'})\n",
    "ml_movies_df = pd.read_csv(os.path.join(\"data\", \"movielens_small\", \"movies.csv\")).rename(columns={'movieId': 'item_id'})\n",
    "ml_df = pd.merge(ml_ratings_df, ml_movies_df, on='item_id')\n",
    "\n",
    "display(ml_movies_df.head(10))\n",
    "\n",
    "# Filter the data to reduce the number of movies\n",
    "seed = 6789\n",
    "rng = np.random.RandomState(seed=seed)\n",
    "left_ids = rng.choice(ml_movies_df['item_id'], size=1000, replace=False)\n",
    "\n",
    "ml_ratings_df = ml_ratings_df.loc[ml_ratings_df['item_id'].isin(left_ids)]\n",
    "ml_movies_df = ml_movies_df.loc[ml_movies_df['item_id'].isin(left_ids)]\n",
    "ml_df = ml_df.loc[ml_df['item_id'].isin(left_ids)]\n",
    "\n",
    "print(\"Number of chosen interactions: {}\".format(len(ml_ratings_df)))\n",
    "\n",
    "display(ml_df.head(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bottom-grill",
   "metadata": {},
   "source": [
    "# Baseline recommenders"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "controlled-phoenix",
   "metadata": {},
   "source": [
    "**Task 1.** Implement the MostPopularRecommender (check the slides for class 1), evaluate it with leave-one-out procedure for implicit feedback, print HR@1, HR@3, HR@5, HR@10, NDCG@1, NDCG@3, NDCG@5, NDCG@10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "sixth-basketball",
   "metadata": {},
   "outputs": [],
   "source": [
    "class MostPopularRecommender(Recommender):\n",
    "    \"\"\"\n",
    "    Base recommender class.\n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize base recommender params and variables.\n",
    "        \"\"\"\n",
    "        # Write your code here\n",
    "    \n",
    "    def fit(self, interactions_df, users_df, items_df):\n",
    "        \"\"\"\n",
    "        Training of the recommender.\n",
    "        \n",
    "        :param pd.DataFrame interactions_df: DataFrame with recorded interactions between users and items \n",
    "            defined by user_id, item_id and features of the interaction.\n",
    "        :param pd.DataFrame users_df: DataFrame with users and their features defined by user_id and the user feature columns.\n",
    "        :param pd.DataFrame items_df: DataFrame with items and their features defined by item_id and the item feature columns.\n",
    "        \"\"\"\n",
    "        # Write your code here\n",
    "    \n",
    "    def recommend(self, users_df, items_df, n_recommendations=1):\n",
    "        \"\"\"\n",
    "        Serving of recommendations. Scores items in items_df for each user in users_df and returns \n",
    "        top n_recommendations for each user.\n",
    "        \n",
    "        :param pd.DataFrame users_df: DataFrame with users and their features for which recommendations should be generated.\n",
    "        :param pd.DataFrame items_df: DataFrame with items and their features which should be scored.\n",
    "        :param int n_recommendations: Number of recommendations to be returned for each user.\n",
    "        :return: DataFrame with user_id, item_id and score as columns returning n_recommendations top recommendations \n",
    "            for each user.\n",
    "        :rtype: pd.DataFrame\n",
    "        \"\"\"\n",
    "        \n",
    "        # Write your code here\n",
    "        \n",
    "    \n",
    "# Quick test of the recommender\n",
    "\n",
    "most_popular_recommender = MostPopularRecommender()\n",
    "most_popular_recommender.fit(ml_ratings_df, None, ml_movies_df)\n",
    "recommendations = most_popular_recommender.recommend(pd.DataFrame([[1], [2], [6]], columns=['user_id']), ml_movies_df, 10)\n",
    "\n",
    "recommendations = pd.merge(recommendations, ml_movies_df, on='item_id', how='left')\n",
    "print(\"Recommendations\")\n",
    "display(HTML(recommendations.to_html()))\n",
    "\n",
    "most_popular_recommender = MostPopularRecommender()\n",
    "\n",
    "most_popular_results = [['MostPopularRecommender'] + list(evaluate_leave_one_out_implicit(\n",
    "    most_popular_recommender, ml_ratings_df.loc[:, ['user_id', 'item_id']], ml_movies_df, max_evals=300, seed=6789))]\n",
    "\n",
    "most_popular_results = pd.DataFrame(\n",
    "    most_popular_results, \n",
    "    columns=['Recommender', 'HR@1', 'HR@3', 'HR@5', 'HR@10', 'NDCG@1', 'NDCG@3', 'NDCG@5', 'NDCG@10'])\n",
    "\n",
    "display(HTML(most_popular_results.to_html()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "endangered-designer",
   "metadata": {},
   "source": [
    "**Task 2.** Implement the HighestRatedRecommender (check the slides for class 1), but recommend only those movies which got at least 50 ratings. Evaluate it with leave-one-out procedure for implicit feedback, print HR@1, HR@3, HR@5, HR@10, NDCG@1, NDCG@3, NDCG@5, NDCG@10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "robust-agenda",
   "metadata": {},
   "outputs": [],
   "source": [
    "class HighestRatedRecommender(Recommender):\n",
    "    \"\"\"\n",
    "    Base recommender class.\n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize base recommender params and variables.\n",
    "        \"\"\"\n",
    "        # Write your code here\n",
    "    \n",
    "    def fit(self, interactions_df, users_df, items_df):\n",
    "        \"\"\"\n",
    "        Training of the recommender.\n",
    "        \n",
    "        :param pd.DataFrame interactions_df: DataFrame with recorded interactions between users and items \n",
    "            defined by user_id, item_id and features of the interaction.\n",
    "        :param pd.DataFrame users_df: DataFrame with users and their features defined by user_id and the user feature columns.\n",
    "        :param pd.DataFrame items_df: DataFrame with items and their features defined by item_id and the item feature columns.\n",
    "        \"\"\"\n",
    "        # Write your code here\n",
    "    \n",
    "    def recommend(self, users_df, items_df, n_recommendations=1):\n",
    "        \"\"\"\n",
    "        Serving of recommendations. Scores items in items_df for each user in users_df and returns \n",
    "        top n_recommendations for each user.\n",
    "        \n",
    "        :param pd.DataFrame users_df: DataFrame with users and their features for which recommendations should be generated.\n",
    "        :param pd.DataFrame items_df: DataFrame with items and their features which should be scored.\n",
    "        :param int n_recommendations: Number of recommendations to be returned for each user.\n",
    "        :return: DataFrame with user_id, item_id and score as columns returning n_recommendations top recommendations \n",
    "            for each user.\n",
    "        :rtype: pd.DataFrame\n",
    "        \"\"\"\n",
    "        \n",
    "        # Write your code here\n",
    "    \n",
    "# Quick test of the recommender\n",
    "\n",
    "highest_rated_recommender = HighestRatedRecommender()\n",
    "highest_rated_recommender.fit(ml_ratings_df, None, ml_movies_df)\n",
    "recommendations = highest_rated_recommender.recommend(pd.DataFrame([[1], [2], [6]], columns=['user_id']), ml_movies_df, 10)\n",
    "\n",
    "recommendations = pd.merge(recommendations, ml_movies_df, on='item_id', how='left')\n",
    "print(\"Recommendations\")\n",
    "display(HTML(recommendations.to_html()))\n",
    "\n",
    "highest_rated_recommender = HighestRatedRecommender()\n",
    "\n",
    "highest_rated_results = [['HighestRatedRecommender'] + list(evaluate_leave_one_out_implicit(\n",
    "    highest_rated_recommender, ml_ratings_df.loc[:, ['user_id', 'item_id', 'rating']], ml_movies_df, max_evals=300, seed=6789))]\n",
    "\n",
    "highest_rated_results = pd.DataFrame(\n",
    "    highest_rated_results, \n",
    "    columns=['Recommender', 'HR@1', 'HR@3', 'HR@5', 'HR@10', 'NDCG@1', 'NDCG@3', 'NDCG@5', 'NDCG@10'])\n",
    "\n",
    "display(HTML(highest_rated_results.to_html()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "valid-malaysia",
   "metadata": {},
   "source": [
    "**Task 3.** Implement the RandomRecommender (check the slides for class 1), evaluate it with leave-one-out procedure for implicit feedback, print HR@1, HR@3, HR@5, HR@10, NDCG@1, NDCG@3, NDCG@5, NDCG@10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "french-multiple",
   "metadata": {},
   "outputs": [],
   "source": [
    "class RandomRecommender(Recommender):\n",
    "    \"\"\"\n",
    "    Base recommender class.\n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self, seed=0):\n",
    "        \"\"\"\n",
    "        Initialize base recommender params and variables.\n",
    "        \n",
    "        :param int seed: Seed for the random number generator.\n",
    "        \"\"\"\n",
    "        self.seed = seed\n",
    "        self.rng = np.random.RandomState(seed=seed)\n",
    "        # Write your code here\n",
    "    \n",
    "    def fit(self, interactions_df, users_df, items_df):\n",
    "        \"\"\"\n",
    "        Training of the recommender.\n",
    "        \n",
    "        :param pd.DataFrame interactions_df: DataFrame with recorded interactions between users and items \n",
    "            defined by user_id, item_id and features of the interaction.\n",
    "        :param pd.DataFrame users_df: DataFrame with users and their features defined by user_id and the user feature columns.\n",
    "        :param pd.DataFrame items_df: DataFrame with items and their features defined by item_id and the item feature columns.\n",
    "        \"\"\"\n",
    "        # Write your code here\n",
    "    \n",
    "    def recommend(self, users_df, items_df, n_recommendations=1):\n",
    "        \"\"\"\n",
    "        Serving of recommendations. Scores items in items_df for each user in users_df and returns \n",
    "        top n_recommendations for each user.\n",
    "        \n",
    "        :param pd.DataFrame users_df: DataFrame with users and their features for which recommendations should be generated.\n",
    "        :param pd.DataFrame items_df: DataFrame with items and their features which should be scored.\n",
    "        :param int n_recommendations: Number of recommendations to be returned for each user.\n",
    "        :return: DataFrame with user_id, item_id and score as columns returning n_recommendations top recommendations \n",
    "            for each user.\n",
    "        :rtype: pd.DataFrame\n",
    "        \"\"\"\n",
    "        \n",
    "        # Write your code here\n",
    "    \n",
    "# Quick test of the recommender\n",
    "\n",
    "random_recommender = RandomRecommender(seed=6789)\n",
    "random_recommender.fit(ml_ratings_df, None, ml_movies_df)\n",
    "recommendations = random_recommender.recommend(pd.DataFrame([[1], [2], [6]], columns=['user_id']), ml_movies_df, 10)\n",
    "\n",
    "recommendations = recommendations.merge(ml_movies_df, on='item_id', how='left')\n",
    "print(\"Recommendations\")\n",
    "display(HTML(recommendations.to_html()))\n",
    "\n",
    "random_recommender = RandomRecommender(seed=seed)\n",
    "\n",
    "random_results = [['RandomRecommender'] + list(evaluate_leave_one_out_implicit(\n",
    "    random_recommender, ml_ratings_df.loc[:, ['user_id', 'item_id', 'rating']], ml_movies_df, max_evals=300, seed=seed))]\n",
    "\n",
    "random_results = pd.DataFrame(\n",
    "    random_results, \n",
    "    columns=['Recommender', 'HR@1', 'HR@3', 'HR@5', 'HR@10', 'NDCG@1', 'NDCG@3', 'NDCG@5', 'NDCG@10'])\n",
    "\n",
    "display(HTML(random_results.to_html()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "optional-chain",
   "metadata": {},
   "source": [
    "# Linear Regression Recommender\n",
    "\n",
    "For every movie we transform its genres into one-hot encoded features and we normalize them, for every user we count percentages for all genres how often do they appear among films watched by the user, we multiply both vectors (for the item and the user) to obtain explanatory variables, and then we fit a linear regression model to those features and actual ratings."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "spanish-employee",
   "metadata": {},
   "source": [
    "**Task 4.** Implement the calculate_user_genres method for calculating a DataFrame with one row per user and columns corresponding to genres (e.g. 'user_action', 'user_drama') with values calculated as follows:\n",
    "\n",
    "- count the number of times a given user watched a given genre,\n",
    "- apply a natural logarithm to this value plus one,\n",
    "- normalize those values so that the sum of them over all columns within a row is equal to 1.\n",
    "\n",
    "Implement the calculate_item_genres method for replacing the 'genres' column with one column per genre (e.g. 'action', 'drama') with values calculated as follows:\n",
    "\n",
    "- place 1 in every column for which the genre appears in genres,\n",
    "- normalize those values so that the sum of them over all genre columns within a row is equal to 1.\n",
    "\n",
    "If item_features is None, then first find all genres and prepare a list of them. If item_features is not None, then create columns based on this list. Return both the transformed DataFrame and the list of genres.  Do not use MultiLabelBinarizer.\n",
    "\n",
    "Note that in this second method you have to preserve the remaining structure of the DataFrame.\n",
    "\n",
    "Evaluate the LinearRegressionRecommender with it using leave-one-out procedure for implicit feedback, print HR@1, HR@3, HR@5, HR@10, NDCG@1, NDCG@3, NDCG@5, NDCG@10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fifth-battery",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Prepare data for tests\n",
    "interactions_df = pd.merge(ml_ratings_df, ml_movies_df, on='item_id')\n",
    "interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.replace(\"-\", \"_\", regex=False)\n",
    "interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.replace(\" \", \"_\", regex=False)\n",
    "interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.replace(\"(\", \"\", regex=False)\n",
    "interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.replace(\")\", \"\", regex=False)\n",
    "interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.lower()\n",
    "interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.split(\"|\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "pressing-domain",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_user_genres(interactions_df):\n",
    "    # Write your code here\n",
    "    \n",
    "    return users_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "appropriate-administration",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test the calculate_user_genres method\n",
    "display(calculate_user_genres(interactions_df))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "excited-scott",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.preprocessing import MultiLabelBinarizer\n",
    "\n",
    "def calculate_item_genres(item_genres, item_features=None):\n",
    "    # Write your code here\n",
    "    \n",
    "    return item_genres, item_features"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "academic-daughter",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "# Test the method\n",
    "\n",
    "item_genres, item_features = calculate_item_genres(interactions_df)\n",
    "display(item_genres)\n",
    "print(item_features)\n",
    "\n",
    "item_genres, item_features = calculate_item_genres(interactions_df, ['comedy', 'crime', 'drama', 'horror', 'test_category'])\n",
    "display(item_genres)\n",
    "print(item_features)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "sonic-horror",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.linear_model import LinearRegression\n",
    "from sklearn.preprocessing import MultiLabelBinarizer\n",
    "\n",
    "from recommenders.recommender import Recommender\n",
    "\n",
    "class LinearRegressionRecommender(Recommender):\n",
    "    \"\"\"\n",
    "    Linear regression recommender class.\n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize recommender params and variables.\n",
    "        \"\"\"\n",
    "        self.model = None\n",
    "        self.mlb = None\n",
    "        self.users_dict = None\n",
    "        self.user_features = None\n",
    "        \n",
    "        self.uses_dot_product = True\n",
    "    \n",
    "    def fit(self, interactions_df, users_df, items_df):\n",
    "        \"\"\"\n",
    "        Training of the recommender.\n",
    "        \n",
    "        :param pd.DataFrame interactions_df: DataFrame with recorded interactions between users and items \n",
    "            defined by user_id, item_id and features of the interaction.\n",
    "        :param pd.DataFrame users_df: DataFrame with users and their features defined by user_id and the user feature columns.\n",
    "        :param pd.DataFrame items_df: DataFrame with items and their features defined by item_id and the item feature columns.\n",
    "        \"\"\"\n",
    "        \n",
    "        # Transform genres to a more code-friendly form\n",
    "        \n",
    "        interactions_df = pd.merge(interactions_df, items_df, on='item_id')\n",
    "        interactions_df = self._transform_genres(interactions_df)\n",
    "        \n",
    "        # Prepare user features\n",
    "        \n",
    "        users_df = interactions_df[['user_id', 'genres']].copy()\n",
    "        users_df = users_df.explode('genres')\n",
    "        users_df['val'] = 1\n",
    "        users_df = users_df.pivot_table(index='user_id', columns='genres', values='val', aggfunc='count')\n",
    "        users_df = users_df / users_df.sum(axis=1).values.reshape(-1, 1)\n",
    "        users_df = users_df.rename_axis(None, axis=1).fillna(0)\n",
    "        users_df = users_df.add_prefix('user_')\n",
    "#         display(users_df.head(10))\n",
    "        \n",
    "        self.users_dict = users_df.to_dict('index')\n",
    "        \n",
    "        self.user_features = users_df.columns.tolist()\n",
    "        \n",
    "        interactions_df = interactions_df.merge(users_df, on='user_id')\n",
    "#         display(interactions_df.head(10))\n",
    "                \n",
    "        # Prepare item features\n",
    "        \n",
    "        # Transform genres into binary values\n",
    "        \n",
    "        self.mlb = MultiLabelBinarizer()\n",
    "        interactions_df = interactions_df.join(\n",
    "            pd.DataFrame(self.mlb.fit_transform(interactions_df.pop('genres')),\n",
    "                         columns=self.mlb.classes_,\n",
    "                         index=interactions_df.index))\n",
    "        \n",
    "        # Normalize the values so that each movie's genres sum up to 1\n",
    "        \n",
    "        interactions_df[self.mlb.classes_] = interactions_df[self.mlb.classes_] \\\n",
    "            / interactions_df[self.mlb.classes_].sum(axis=1).values.reshape(-1, 1)\n",
    "        \n",
    "#         display(interactions_df.loc[:, self.mlb.classes_].head(10))\n",
    "\n",
    "        # Prepare input data and fit the model\n",
    "    \n",
    "        # Dot product for personalization\n",
    "        if self.uses_dot_product:\n",
    "            interactions_df[self.mlb.classes_] = interactions_df[self.mlb.classes_] \\\n",
    "                * interactions_df[self.user_features].values\n",
    "    \n",
    "#         display(interactions_df.head(10))\n",
    "        \n",
    "        if self.uses_dot_product:  # Personalized\n",
    "            x = interactions_df.loc[:, self.mlb.classes_].values\n",
    "        else:  # Non-personalized\n",
    "            x = interactions_df.loc[:, list(self.mlb.classes_) + self.user_features].values\n",
    "        \n",
    "        y = interactions_df['rating'].values\n",
    "    \n",
    "        self.model = LinearRegression().fit(x, y)\n",
    "    \n",
    "    def recommend(self, users_df, items_df, n_recommendations=1):\n",
    "        \"\"\"\n",
    "        Serving of recommendations. Scores items in items_df for each user in users_df and returns \n",
    "        top n_recommendations for each user.\n",
    "        \n",
    "        :param pd.DataFrame users_df: DataFrame with users and their features for which recommendations should be generated.\n",
    "        :param pd.DataFrame items_df: DataFrame with items and their features which should be scored.\n",
    "        :param int n_recommendations: Number of recommendations to be returned for each user.\n",
    "        :return: DataFrame with user_id, item_id and score as columns returning n_recommendations top recommendations \n",
    "            for each user.\n",
    "        :rtype: pd.DataFrame\n",
    "        \"\"\"\n",
    "        \n",
    "        # Transform the item to be scored into proper features\n",
    "        \n",
    "        items_df = items_df.copy()\n",
    "        items_df = self._transform_genres(items_df)\n",
    "        \n",
    "        items_df = items_df.join(\n",
    "            pd.DataFrame(self.mlb.transform(items_df.pop('genres')),\n",
    "                         columns=self.mlb.classes_,\n",
    "                         index=items_df.index))\n",
    "        \n",
    "        items_df[self.mlb.classes_] = items_df[self.mlb.classes_] \\\n",
    "            / items_df[self.mlb.classes_].sum(axis=1).values.reshape(-1, 1)\n",
    "\n",
    "        # Score the item\n",
    "    \n",
    "        recommendations = pd.DataFrame(columns=['user_id', 'item_id', 'score'])\n",
    "        \n",
    "        for ix, user in users_df.iterrows():\n",
    "            if user['user_id'] in self.users_dict:\n",
    "                user_df = pd.DataFrame.from_dict({user['user_id']: self.users_dict[user['user_id']]}, orient='index')\n",
    "            else:\n",
    "                user_df = pd.DataFrame.from_dict(\n",
    "                    {user['user_id']: [1 / len(self.user_features)]*len(self.user_features)}, orient='index')\n",
    "                user_df.columns = self.user_features\n",
    "#             display(user_df)\n",
    "#             display(items_df)\n",
    "            input_df = items_df.copy()\n",
    "            \n",
    "            if self.uses_dot_product:\n",
    "                input_df[self.mlb.classes_] = items_df[self.mlb.classes_] * user_df.values\n",
    "#                 display(input_df)\n",
    "                scores = self.model.predict(input_df.loc[:, self.mlb.classes_].values)\n",
    "            else:\n",
    "                input_df = input_df.merge(user_df, how='cross')\n",
    "#                 display(input_df)\n",
    "                scores = self.model.predict(input_df.loc[:, list(self.mlb.classes_) + self.user_features].values)\n",
    "    \n",
    "            chosen_pos = np.argsort(-scores)[:n_recommendations]\n",
    "        \n",
    "            user_recommendations = []\n",
    "            for item_pos in chosen_pos:\n",
    "                user_recommendations.append(\n",
    "                    {\n",
    "                        'user_id': user['user_id'],\n",
    "                        'item_id': input_df.iloc[item_pos]['item_id'],\n",
    "                        'score': scores[item_pos]\n",
    "                    }\n",
    "                )\n",
    "                \n",
    "            user_recommendations = pd.DataFrame(user_recommendations)\n",
    "\n",
    "            recommendations = pd.concat([recommendations, user_recommendations])\n",
    "\n",
    "        return recommendations\n",
    "    \n",
    "    def _transform_genres(self, df):\n",
    "        \"\"\"\n",
    "        Transforms a string with genres into a list of cleaned genre names.\n",
    "        \n",
    "        :param pd.DataFrame df: A DataFrame with 'genres' column.\n",
    "        \"\"\"\n",
    "        df.loc[:, 'genres'] = df['genres'].str.replace(\"-\", \"_\", regex=False)\n",
    "        df.loc[:, 'genres'] = df['genres'].str.replace(\" \", \"_\", regex=False)\n",
    "        df.loc[:, 'genres'] = df['genres'].str.replace(\"(\", \"\", regex=False)\n",
    "        df.loc[:, 'genres'] = df['genres'].str.replace(\")\", \"\", regex=False)\n",
    "        df.loc[:, 'genres'] = df['genres'].str.lower()\n",
    "        df.loc[:, 'genres'] = df['genres'].str.split(\"|\")\n",
    "        return df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "colored-favorite",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "# Quick test of the recommender\n",
    "\n",
    "lr_recommender = LinearRegressionRecommender()\n",
    "lr_recommender.fit(ml_ratings_df, None, ml_movies_df)\n",
    "recommendations = lr_recommender.recommend(pd.DataFrame([[3], [5], [39]], columns=['user_id']), ml_movies_df, 10)\n",
    "\n",
    "recommendations = pd.merge(recommendations, ml_movies_df, on='item_id', how='left')\n",
    "display(recommendations)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "usual-archives",
   "metadata": {},
   "source": [
    "### Train-test split test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bound-offer",
   "metadata": {},
   "outputs": [],
   "source": [
    "lr_recommender = LinearRegressionRecommender()\n",
    "\n",
    "t0 = time.time()\n",
    "\n",
    "results = [['LinearRegressionRecommender'] + list(evaluate_train_test_split_explicit(\n",
    "    lr_recommender, ml_ratings_df.loc[:, ['user_id', 'item_id', 'rating']], ml_movies_df, seed=seed))]\n",
    "\n",
    "results = pd.DataFrame(results, \n",
    "                       columns=['Recommender', 'RMSE', 'MRE', 'TRE'])\n",
    "\n",
    "display(results)\n",
    "\n",
    "print('Total evaluation time: {}'.format(time.time() - t0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "immediate-warehouse",
   "metadata": {},
   "source": [
    "### Leave-one-out test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "national-sight",
   "metadata": {},
   "outputs": [],
   "source": [
    "lr_recommender = LinearRegressionRecommender()\n",
    "\n",
    "t0 = time.time()\n",
    "\n",
    "results = [['LinearRegressionRecommender'] + list(evaluate_leave_one_out_explicit(\n",
    "    lr_recommender, ml_ratings_df.loc[:, ['user_id', 'item_id', 'rating']], ml_movies_df, seed=seed))]\n",
    "\n",
    "results = pd.DataFrame(results, \n",
    "                       columns=['Recommender', 'RMSE', 'MRE', 'TRE'])\n",
    "\n",
    "display(results)\n",
    "\n",
    "print('Total evaluation time: {}'.format(time.time() - t0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "static-mozambique",
   "metadata": {},
   "source": [
    "# TF-IDF Recommender\n",
    "TF-IDF stands for term frequency–inverse document frequency. Typically Tf-IDF method is used to assign keywords (words describing the gist of a document) to documents in a corpus of documents.\n",
    "\n",
    "In our case we will treat users as documents and genres as words.\n",
    "\n",
    "Term-frequency is given by the following formula:\n",
    "<center>\n",
    "$$\n",
    "    \\text{tf}(g, u) = f_{g, u}\n",
    "$$\n",
    "</center>\n",
    "where $f_{g, i}$ is the number of times genre $g$ appear for movies watched by user $u$.\n",
    "\n",
    "Inverse document frequency is defined as follows:\n",
    "<center>\n",
    "$$\n",
    "    \\text{idf}(g) = \\log \\frac{N}{n_g}\n",
    "$$\n",
    "</center>\n",
    "where $N$ is the number of users and $n_g$ is the number of users with $g$ in their genres list.\n",
    "\n",
    "Finally, tf-idf is defined as follows:\n",
    "<center>\n",
    "$$\n",
    "    \\text{tfidf}(g, u) = \\text{tf}(g, u) \\cdot \\text{idf}(g)\n",
    "$$\n",
    "</center>\n",
    "\n",
    "In our case we will measure how often a given genre appears for movies watched by a given user vs how often it appears for all users. To obtain a movie score we will take the average of its genres' scores for this user."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "authentic-cursor",
   "metadata": {},
   "source": [
    "**Task 5.** Implement the following method for calculating a TF-IDF scores in a form of a dict (use defaultdict):\n",
    "\n",
    "`{(1, 'action'): 0.45306430692185395, (1, 'adventure'): 0.39370003643934415, (1, 'animation'): 0.20886242957049514, ...}`\n",
    "\n",
    "without using TfidfVectorizer (you can use loops).\n",
    "\n",
    "Evaluate the TFIDFRecommender with it using leave-one-out procedure for implicit feedback, print HR@1, HR@3, HR@5, HR@10, NDCG@1, NDCG@3, NDCG@5, NDCG@10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "frank-active",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_tf_idf_scores(interactions_df):\n",
    "    # Write your code here\n",
    "    \n",
    "    return tfidf_scores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "retained-traffic",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test the method\n",
    "interactions_df = pd.merge(ml_ratings_df, ml_movies_df, on='item_id')\n",
    "interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.replace(\"-\", \"_\", regex=False)\n",
    "interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.replace(\" \", \"_\", regex=False)\n",
    "interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.replace(\"(\", \"\", regex=False)\n",
    "interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.replace(\")\", \"\", regex=False)\n",
    "interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.lower()\n",
    "        \n",
    "tfidf_scores = calculate_tf_idf_scores(interactions_df)\n",
    "print(tfidf_scores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "infrared-southwest",
   "metadata": {},
   "outputs": [],
   "source": [
    "class TFIDFRecommender(Recommender):\n",
    "    \"\"\"\n",
    "    Recommender based on the TF-IDF method.\n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize base recommender params and variables.\n",
    "        \"\"\"\n",
    "        self.tfidf_scores = None\n",
    "    \n",
    "    def fit(self, interactions_df, users_df, items_df):\n",
    "        \"\"\"\n",
    "        Training of the recommender.\n",
    "        \n",
    "        :param pd.DataFrame interactions_df: DataFrame with recorded interactions between users and items \n",
    "            defined by user_id, item_id and features of the interaction.\n",
    "        :param pd.DataFrame users_df: DataFrame with users and their features defined by user_id and the user feature columns.\n",
    "        :param pd.DataFrame items_df: DataFrame with items and their features defined by item_id and the item feature columns.\n",
    "        \"\"\"\n",
    "        \n",
    "        self.tfidf_scores = defaultdict(lambda: 0.0)\n",
    "\n",
    "        # Prepare the corpus for tfidf calculation\n",
    "        \n",
    "        interactions_df = pd.merge(interactions_df, items_df, on='item_id')\n",
    "        interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.replace(\"-\", \"_\", regex=False)\n",
    "        interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.replace(\" \", \"_\", regex=False)\n",
    "        interactions_df.loc[:, 'genres'] = interactions_df['genres'].str.lower()\n",
    "                \n",
    "        self.tfidf_scores = calculate_tf_idf_scores(interactions_df)\n",
    "    \n",
    "    def recommend(self, users_df, items_df, n_recommendations=1):\n",
    "        \"\"\"\n",
    "        Serving of recommendations. Scores items in items_df for each user in users_df and returns \n",
    "        top n_recommendations for each user.\n",
    "        \n",
    "        :param pd.DataFrame users_df: DataFrame with users and their features for which recommendations should be generated.\n",
    "        :param pd.DataFrame items_df: DataFrame with items and their features which should be scored.\n",
    "        :param int n_recommendations: Number of recommendations to be returned for each user.\n",
    "        :return: DataFrame with user_id, item_id and score as columns returning n_recommendations top recommendations \n",
    "            for each user.\n",
    "        :rtype: pd.DataFrame\n",
    "        \"\"\"\n",
    "        \n",
    "        recommendations = pd.DataFrame(columns=['user_id', 'item_id', 'score'])\n",
    "        \n",
    "        # Transform genres to a unified form used by the vectorizer\n",
    "        \n",
    "        items_df = items_df.copy()\n",
    "        items_df.loc[:, 'genres'] = items_df['genres'].str.replace(\"-\", \"_\", regex=False)\n",
    "        items_df.loc[:, 'genres'] = items_df['genres'].str.replace(\" \", \"_\", regex=False)\n",
    "        items_df.loc[:, 'genres'] = items_df['genres'].str.lower()\n",
    "        items_df.loc[:, 'genres'] = items_df['genres'].str.split(\"|\")\n",
    "                \n",
    "        # Score items    \n",
    "        \n",
    "        for uix, user in users_df.iterrows():\n",
    "            items = []\n",
    "            for iix, item in items_df.iterrows():\n",
    "                score = 0.0\n",
    "                for genre in item['genres']:\n",
    "                    score += self.tfidf_scores[(user['user_id'], genre)]\n",
    "                score /= len(item['genres'])\n",
    "                items.append((item['item_id'], score))\n",
    "                \n",
    "            items = sorted(items, key=lambda x: x[1], reverse=True)\n",
    "            user_recommendations = pd.DataFrame({'user_id': user['user_id'],\n",
    "                                                 'item_id': [item[0] for item in items][:n_recommendations],\n",
    "                                                 'score': [item[1] for item in items][:n_recommendations]})\n",
    "\n",
    "            recommendations = pd.concat([recommendations, user_recommendations])\n",
    "\n",
    "        return recommendations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "sorted-alcohol",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Print movies watched by user 3, 5, 39\n",
    "\n",
    "active_user_movies = ml_df.loc[(ml_df['user_id'] == 3) | (ml_df['user_id'] == 5) | (ml_df['user_id'] == 39)]\n",
    "print(\"Active users history\")\n",
    "display(active_user_movies)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "oriented-service",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Quick test of the recommender\n",
    "\n",
    "tfidf_recommender = TFIDFRecommender()\n",
    "tfidf_recommender.fit(ml_ratings_df, None, ml_movies_df)\n",
    "recommendations = tfidf_recommender.recommend(pd.DataFrame([[3], [5], [39]], columns=['user_id']), ml_movies_df, 10)\n",
    "\n",
    "recommendations = pd.merge(recommendations, ml_movies_df, on='item_id', how='left')\n",
    "print(\"Recommendations\")\n",
    "display(recommendations)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sealed-liberty",
   "metadata": {},
   "source": [
    "### Train-test split test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "identified-destination",
   "metadata": {},
   "outputs": [],
   "source": [
    "tfidf_recommender = TFIDFRecommender()\n",
    "\n",
    "t0 = time.time()\n",
    "\n",
    "results = [['TFIDFRecommender'] + list(evaluate_train_test_split_implicit(\n",
    "    tfidf_recommender, ml_ratings_df.loc[:, ['user_id', 'item_id']], ml_movies_df))]\n",
    "\n",
    "results = pd.DataFrame(results, \n",
    "                       columns=['Recommender', 'HR@1', 'HR@3', 'HR@5', 'HR@10', 'NDCG@1', 'NDCG@3', 'NDCG@5', 'NDCG@10'])\n",
    "\n",
    "display(results)\n",
    "\n",
    "print('Total evaluation time: {}'.format(time.time() - t0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "creative-beast",
   "metadata": {},
   "source": [
    "### Leave-one-out test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "qualified-westminster",
   "metadata": {},
   "outputs": [],
   "source": [
    "tfidf_recommender = TFIDFRecommender()\n",
    "\n",
    "t0 = time.time()\n",
    "\n",
    "results = [['TFIDFRecommender'] + list(evaluate_leave_one_out_implicit(\n",
    "    tfidf_recommender, ml_ratings_df.loc[:, ['user_id', 'item_id']], ml_movies_df, max_evals=300, seed=6789))]\n",
    "\n",
    "results = pd.DataFrame(results, \n",
    "                       columns=['Recommender', 'HR@1', 'HR@3', 'HR@5', 'HR@10', 'NDCG@1', 'NDCG@3', 'NDCG@5', 'NDCG@10'])\n",
    "\n",
    "display(results)\n",
    "\n",
    "print('Total evaluation time: {}'.format(time.time() - t0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "visible-burlington",
   "metadata": {},
   "source": [
    "**Task 6\\*.** Implement an SVRRecommender by replacing the LinearRegression model with the SVR model (`from sklearn.svm import SVR`). Use separate features for users and items, not the dot product.\n",
    "\n",
    "Tune params of the SVR model to obtain as good results as you can. \n",
    "\n",
    "To do tuning properly:\n",
    "\n",
    "- divide the set into training, validation and test sets (randomly divide the dataset in proportions 60%-20%-20%),\n",
    "- train the model with different sets of tunable parameters on the training set, \n",
    "- choose the best tunable params based on results on the validation set, \n",
    "- provide the final evaluation metrics on the test set for the best model obtained during tuning.\n",
    "\n",
    "Recommended method of tuning: use hyperopt. Install the package using the following command: `pip install hyperopt`\n",
    "    \n",
    "Print the RMSE, MAPE and TRE on the test set. Use seed 6789."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "promotional-gregory",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "from sklearn.svm import SVR\n",
    "from sklearn.preprocessing import MultiLabelBinarizer\n",
    "\n",
    "    \n",
    "class SVRRecommender(Recommender):\n",
    "    \"\"\"\n",
    "    SVR recommender class.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, kernel='rbf', c=1.0, epsilon=0.1):\n",
    "        \"\"\"\n",
    "        Initialize base recommender params and variables.\n",
    "        \"\"\"\n",
    "        super().__init__()\n",
    "        self.model = None\n",
    "        self.mlb = None\n",
    "        self.kernel = kernel\n",
    "        self.c = c\n",
    "        self.epsilon = epsilon\n",
    "        self.mlb = None\n",
    "        self.users_dict = None\n",
    "        self.user_features = None\n",
    "        self.uses_dot_product = False\n",
    "\n",
    "    def fit(self, interactions_df, users_df, items_df):\n",
    "        \"\"\"\n",
    "        Training of the recommender.\n",
    "\n",
    "        :param pd.DataFrame interactions_df: DataFrame with recorded interactions between users and items\n",
    "            defined by user_id, item_id and features of the interaction.\n",
    "        :param pd.DataFrame users_df: DataFrame with users and their features defined by user_id\n",
    "            and the user feature columns.\n",
    "        :param pd.DataFrame items_df: DataFrame with items and their features defined by item_id\n",
    "            and the item feature columns.\n",
    "        \"\"\"\n",
    "\n",
    "        # Write your code here\n",
    "\n",
    "    def recommend(self, users_df, items_df, n_recommendations=1):\n",
    "        \"\"\"\n",
    "        Serving of recommendations. Scores items in items_df for each user in users_df and returns\n",
    "        top n_recommendations for each user.\n",
    "\n",
    "        :param pd.DataFrame users_df: DataFrame with users and their features for which recommendations\n",
    "            should be generated.\n",
    "        :param pd.DataFrame items_df: DataFrame with items and their features which should be scored.\n",
    "        :param int n_recommendations: Number of recommendations to be returned for each user.\n",
    "        :return: DataFrame with user_id, item_id and score as columns returning n_recommendations top recommendations\n",
    "            for each user.\n",
    "        :rtype: pd.DataFrame\n",
    "        \"\"\"\n",
    "\n",
    "        # Write your code here\n",
    "\n",
    "    @staticmethod\n",
    "    def _transform_genres(df):\n",
    "        \"\"\"\n",
    "        Transforms a string with genres into a list of cleaned genre names.\n",
    "\n",
    "        :param pd.DataFrame df: A DataFrame with 'genres' column.\n",
    "        \"\"\"\n",
    "        df.loc[:, 'genres'] = df['genres'].str.replace(\"-\", \"_\", regex=False)\n",
    "        df.loc[:, 'genres'] = df['genres'].str.replace(\" \", \"_\", regex=False)\n",
    "        df.loc[:, 'genres'] = df['genres'].str.replace(\"(\", \"\", regex=False)\n",
    "        df.loc[:, 'genres'] = df['genres'].str.replace(\")\", \"\", regex=False)\n",
    "        df.loc[:, 'genres'] = df['genres'].str.lower()\n",
    "        df.loc[:, 'genres'] = df['genres'].str.split(\"|\")\n",
    "        return df\n",
    "    \n",
    "    \n",
    "# Quick test of the recommender\n",
    "\n",
    "svr_recommender = SVRRecommender()\n",
    "svr_recommender.fit(ml_ratings_df, None, ml_movies_df)\n",
    "recommendations = svr_recommender.recommend(pd.DataFrame([[1], [2], [6]], columns=['user_id']), ml_movies_df, 10)\n",
    "\n",
    "recommendations = pd.merge(recommendations, ml_movies_df, on='item_id', how='left')\n",
    "print(\"Recommendations\")\n",
    "display(HTML(recommendations.to_html()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "second-teach",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "svr_recommender = SVRRecommender(kernel='rbf', c=5.9672721141155, epsilon=0.8583733904374324)\n",
    "\n",
    "results = [['SVRRecommender'] + list(evaluate_train_test_split_explicit(\n",
    "    svr_recommender, ml_ratings_df.loc[:, ['user_id', 'item_id', 'rating']], ml_movies_df, seed=seed))]\n",
    "\n",
    "results = pd.DataFrame(results, \n",
    "                       columns=['Recommender', 'RMSE', 'MRE', 'TRE'])\n",
    "\n",
    "display(results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ambient-brother",
   "metadata": {},
   "outputs": [],
   "source": [
    "from hyperopt import hp, fmin, tpe, Trials\n",
    "import traceback\n",
    "\n",
    "# Split into train_validation and test sets\n",
    "\n",
    "shuffle = np.arange(len(ml_ratings_df))\n",
    "rng.shuffle(shuffle)\n",
    "shuffle = list(shuffle)\n",
    "\n",
    "train_test_split = 0.8\n",
    "split_index = int(len(ml_ratings_df) * train_test_split)\n",
    "\n",
    "train_validation = ml_ratings_df.iloc[shuffle[:split_index]].loc[:, ['user_id', 'item_id', 'rating']]\n",
    "test = ml_ratings_df.iloc[shuffle[split_index:]].loc[:, ['user_id', 'item_id', 'rating']]\n",
    "\n",
    "# Tune\n",
    "\n",
    "def loss(tuned_params):\n",
    "    svr_recommender = SVRRecommender(kernel='rbf', c=tuned_params['C'], epsilon=tuned_params['epsilon'])\n",
    "    rmse, mre, tre = evaluate_train_test_split_explicit(\n",
    "        svr_recommender, train_validation, ml_movies_df, seed=seed)\n",
    "    return rmse\n",
    "\n",
    "# Define the search space for hyperopt\n",
    "# Write your code here\n",
    "\n",
    "\n",
    "succeded = False\n",
    "n_tries = 3\n",
    "t = 0\n",
    "while not succeded and t < n_tries:\n",
    "    try:\n",
    "        trials = Trials()\n",
    "        best_param_set = fmin(loss, space=space, algo=tpe.suggest, max_evals=100, show_progressbar=True, trials=trials)\n",
    "        succeded = True\n",
    "    except:\n",
    "        t += 1\n",
    "        traceback.print_exc()\n",
    "\n",
    "# Best params\n",
    "\n",
    "print(\"C = {}\".format(best_param_set['C']))\n",
    "print(\"epsilon = {}\".format(best_param_set['epsilon']))\n",
    "    \n",
    "# Test\n",
    "\n",
    "C = 0.8078294657404328\n",
    "epsilon = 0.3898720771476633\n",
    "\n",
    "svr_recommender = SVRRecommender(C=best_param_set['C'], epsilon=best_param_set['epsilon'])\n",
    "\n",
    "results = [['SVRRecommender'] + list(evaluate_train_test_split_explicit(\n",
    "    svr_recommender, {'train': train_validation, 'test': test}, ml_movies_df, seed=seed))]\n",
    "\n",
    "results = pd.DataFrame(results, \n",
    "                       columns=['Recommender', 'RMSE', 'MRE', 'TRE'])\n",
    "\n",
    "display(HTML(results.to_html()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "commercial-gathering",
   "metadata": {},
   "source": [
    "**Task 7.** Gather the results for LinearRegressionRecommender, SVRRecommender, TFIDFRecommender, MostPopularRecommender, HighestRatedRecommender, RandomRecommender from the evaluate_train_test_split_implicit method and print them as a single DataFrame."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "intermediate-captain",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write your code here"
   ]
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}