recursive_solution.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from tqdm import tqdm\n",
    "from pprint import pprint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Id</th>\n",
       "      <th>Email</th>\n",
       "      <th>Phone</th>\n",
       "      <th>Contacts</th>\n",
       "      <th>OrderId</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>gkzAbIy@qq.com</td>\n",
       "      <td></td>\n",
       "      <td>1</td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td></td>\n",
       "      <td>329442681752</td>\n",
       "      <td>4</td>\n",
       "      <td>vDDJJcxfLtSfkooPhbYnJdxov</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td></td>\n",
       "      <td>9125983679</td>\n",
       "      <td>0</td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>mdllpYmE@gmail.com</td>\n",
       "      <td></td>\n",
       "      <td>0</td>\n",
       "      <td>bHquEnCbbsGLqllwryxPsNOxa</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td></td>\n",
       "      <td>300364407</td>\n",
       "      <td>2</td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   Id               Email         Phone  Contacts                    OrderId\n",
       "0   0      gkzAbIy@qq.com                       1                           \n",
       "1   1                      329442681752         4  vDDJJcxfLtSfkooPhbYnJdxov\n",
       "2   2                        9125983679         0                           \n",
       "3   3  mdllpYmE@gmail.com                       0  bHquEnCbbsGLqllwryxPsNOxa\n",
       "4   4                         300364407         2                           "
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df = pd.read_json(\"contacts.json\")\n",
    "nd_array = df.values\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Id</th>\n",
       "      <th>Contacts</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>count</th>\n",
       "      <td>500000.000000</td>\n",
       "      <td>500000.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>mean</th>\n",
       "      <td>249999.500000</td>\n",
       "      <td>1.996094</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>std</th>\n",
       "      <td>144337.711635</td>\n",
       "      <td>1.412825</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>min</th>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>25%</th>\n",
       "      <td>124999.750000</td>\n",
       "      <td>1.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>50%</th>\n",
       "      <td>249999.500000</td>\n",
       "      <td>2.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>75%</th>\n",
       "      <td>374999.250000</td>\n",
       "      <td>3.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>max</th>\n",
       "      <td>499999.000000</td>\n",
       "      <td>4.000000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                  Id       Contacts\n",
       "count  500000.000000  500000.000000\n",
       "mean   249999.500000       1.996094\n",
       "std    144337.711635       1.412825\n",
       "min         0.000000       0.000000\n",
       "25%    124999.750000       1.000000\n",
       "50%    249999.500000       2.000000\n",
       "75%    374999.250000       3.000000\n",
       "max    499999.000000       4.000000"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.describe()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "500000"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ids = df[\"Id\"].values.tolist()\n",
    "len(ids)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Id                                 18\n",
       "Email         qOkuzhOuPsbltatw@qq.com\n",
       "Phone                                \n",
       "Contacts                            4\n",
       "OrderId     zSekjOkRLyiGjvOPikTKwksFK\n",
       "Name: 18, dtype: object"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.loc[18]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Id</th>\n",
       "      <th>Email</th>\n",
       "      <th>Phone</th>\n",
       "      <th>Contacts</th>\n",
       "      <th>OrderId</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>18</th>\n",
       "      <td>18</td>\n",
       "      <td>qOkuzhOuPsbltatw@qq.com</td>\n",
       "      <td></td>\n",
       "      <td>4</td>\n",
       "      <td>zSekjOkRLyiGjvOPikTKwksFK</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>274269</th>\n",
       "      <td>274269</td>\n",
       "      <td>tndZkvBDwg@gmail.com</td>\n",
       "      <td>66873440472</td>\n",
       "      <td>0</td>\n",
       "      <td>zSekjOkRLyiGjvOPikTKwksFK</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>327057</th>\n",
       "      <td>327057</td>\n",
       "      <td>sjoEThSNaVBlYk@gmail.com</td>\n",
       "      <td></td>\n",
       "      <td>1</td>\n",
       "      <td>zSekjOkRLyiGjvOPikTKwksFK</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "            Id                     Email        Phone  Contacts  \\\n",
       "18          18   qOkuzhOuPsbltatw@qq.com                      4   \n",
       "274269  274269      tndZkvBDwg@gmail.com  66873440472         0   \n",
       "327057  327057  sjoEThSNaVBlYk@gmail.com                      1   \n",
       "\n",
       "                          OrderId  \n",
       "18      zSekjOkRLyiGjvOPikTKwksFK  \n",
       "274269  zSekjOkRLyiGjvOPikTKwksFK  \n",
       "327057  zSekjOkRLyiGjvOPikTKwksFK  "
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.loc[df[\"OrderId\"] == \"zSekjOkRLyiGjvOPikTKwksFK\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Id</th>\n",
       "      <th>Email</th>\n",
       "      <th>Phone</th>\n",
       "      <th>Contacts</th>\n",
       "      <th>OrderId</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>26580</th>\n",
       "      <td>26580</td>\n",
       "      <td>pQLTiUynFTMQGlQvETVv@hotmail.com</td>\n",
       "      <td>66873440472</td>\n",
       "      <td>3</td>\n",
       "      <td>vQXjSpqgUekYYuSeVOpdaPZme</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>70474</th>\n",
       "      <td>70474</td>\n",
       "      <td>TpnGzfIuAzcV@hotmail.com</td>\n",
       "      <td>66873440472</td>\n",
       "      <td>2</td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>274269</th>\n",
       "      <td>274269</td>\n",
       "      <td>tndZkvBDwg@gmail.com</td>\n",
       "      <td>66873440472</td>\n",
       "      <td>0</td>\n",
       "      <td>zSekjOkRLyiGjvOPikTKwksFK</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "            Id                             Email        Phone  Contacts  \\\n",
       "26580    26580  pQLTiUynFTMQGlQvETVv@hotmail.com  66873440472         3   \n",
       "70474    70474          TpnGzfIuAzcV@hotmail.com  66873440472         2   \n",
       "274269  274269              tndZkvBDwg@gmail.com  66873440472         0   \n",
       "\n",
       "                          OrderId  \n",
       "26580   vQXjSpqgUekYYuSeVOpdaPZme  \n",
       "70474                              \n",
       "274269  zSekjOkRLyiGjvOPikTKwksFK  "
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.loc[df[\"Phone\"] == \"66873440472\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Get Relation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "main_memory = {}\n",
    "user_ids = set()\n",
    "output = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using numpy array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|█████████████████████████████████████████████| 500000/500000 [3:27:53<00:00, 40.08it/s]\n"
     ]
    }
   ],
   "source": [
    "def np_get_row_relation(row, user_ids, memory):\n",
    "    current_user_id = row[0]\n",
    "\n",
    "    if current_user_id in main_memory:\n",
    "        return main_memory[current_user_id]\n",
    "\n",
    "    if current_user_id not in memory:\n",
    "        memory.append(current_user_id)\n",
    "        \n",
    "        order_id = row[4]\n",
    "        email = row[1]\n",
    "        phone = row[2]\n",
    "        \n",
    "        user_ids.add(current_user_id)\n",
    "        \n",
    "        if order_id != \"\":\n",
    "            orderid_link = nd_array[(nd_array[:, 4] == order_id) & (nd_array[:, 0] == current_user_id)]\n",
    "            user_ids = user_ids.union(orderid_link[:, 0])\n",
    "            \n",
    "            for orderid_row in orderid_link:\n",
    "                user_ids = user_ids.union(np_get_row_relation(orderid_row, user_ids, memory))\n",
    "            \n",
    "        if email != \"\":\n",
    "            email_link = nd_array[(nd_array[:, 1] == email) & (nd_array[:, 0] == current_user_id)] \n",
    "            user_ids = user_ids.union(email_link[:, 0])\n",
    "            \n",
    "            for email_row in email_link:\n",
    "                user_ids = user_ids.union(np_get_row_relation(email_row, user_ids, memory))\n",
    "\n",
    "        if phone != \"\":\n",
    "            phone_link = nd_array[(nd_array[:, 2] == phone) & (nd_array[:, 0] == current_user_id)]\n",
    "            user_ids = user_ids.union(phone_link[:, 0])\n",
    "            \n",
    "            for phone_row in phone_link:\n",
    "                user_ids = user_ids.union(np_get_row_relation(phone_row, user_ids, memory))\n",
    "\n",
    "    return user_ids\n",
    "\n",
    "def numpy_solution():\n",
    "    output = []\n",
    "    for row in tqdm(nd_array):\n",
    "        current_user_id = row[0]\n",
    "        \n",
    "        if current_user_id in main_memory:\n",
    "            user_ids = main_memory[current_user_id]\n",
    "            output.append({\"ticket_id\": current_user_id, \"ticket_trace/contact\": user_ids})\n",
    "            continue\n",
    "\n",
    "        user_ids = {current_user_id}\n",
    "\n",
    "        # No relation\n",
    "        if row[4] == \"\" and row[1] == \"\" and row[2] == \"\":\n",
    "            output.append({\"ticket_id\": current_user_id, \"ticket_trace/contact\": user_ids})\n",
    "            continue\n",
    "\n",
    "        user_ids = user_ids.union(np_get_row_relation(row, user_ids, []))\n",
    "\n",
    "        for uid in user_ids:\n",
    "            main_memory[uid] = user_ids\n",
    "\n",
    "        output.append({\"ticket_id\": current_user_id, \"ticket_trace/contact\": user_ids})\n",
    "        \n",
    "numpy_solution()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sum Contacts & Submission\n",
    "```\n",
    "ticket_id,ticket_trace/contact\n",
    "0,\"0, 1\"\n",
    "1,\"1, 2\"\n",
    "2,\"2-150, 6\"\n",
    "3,\"3-100, 3\"\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "header = \"ticket_id,ticket_trace/contact\"\n",
    "with open(\"submission.csv\", \"w+\") as f:\n",
    "    f.write(header)\n",
    "    for entry in tqdm(output):\n",
    "        contacts = df.iloc[entry['trace']][\"Contacts\"].sum().tolist()\n",
    "        trace = \"-\".join([str(trace) for trace in sorted(entry['trace'])])\n",
    "        syntax = \"{},\\\"{},{}\\\"\\n\".format(entry[\"id\"], trace, contacts)\n",
    "        f.write(syntax)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pprint(output)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Submission Syntax\n",
    "```\n",
    "ticket_id,ticket_trace/contact\n",
    "0,\"0, 1\"\n",
    "1,\"1, 2\"\n",
    "2,\"2-150, 6\"\n",
    "3,\"3-100, 3\"\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}