Santa Klaus.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:49:44.318410Z",
     "start_time": "2020-01-10T15:49:39.552387Z"
    }
   },
   "outputs": [],
   "source": [
    "# This Python 3 environment comes with many helpful analytics libraries installed\n",
    "# It is defined by the kaggle/python docker image: https://github.com/kaggle/docker-python\n",
    "# For example, here's several helpful packages to load in \n",
    "\n",
    "import numpy as np # linear algebra\n",
    "import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n",
    "from pathlib import Path\n",
    "import tqdm\n",
    "import torch\n",
    "import torch.nn as nn\n",
    "import torch.nn.functional as F\n",
    "from torch.autograd import Variable\n",
    "\n",
    "# Input data files are available in the \"../input/\" directory.\n",
    "# For example, running this (by clicking run or pressing Shift+Enter) will list all files under the input directory\n",
    "\n",
    "#import os\n",
    "#for dirname, _, filenames in os.walk(r'C:\\Users\\Solomonzhs\\Desktop\\Kaggle\\santa-workshop-tour-2019'):\n",
    "#    for filename in filenames:\n",
    "#        print(os.path.join(dirname, filename))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:51:21.634324Z",
     "start_time": "2020-01-10T15:51:21.628321Z"
    }
   },
   "outputs": [],
   "source": [
    "# Santa Hill Climbing 2019\n",
    "\n",
    "import numba\n",
    "from numba import njit\n",
    "from numba.typed import Dict\n",
    "import numpy as np\n",
    "from time import time\n",
    "from os import path\n",
    "import csv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:49:46.612665Z",
     "start_time": "2020-01-10T15:49:45.596385Z"
    }
   },
   "outputs": [],
   "source": [
    "import scipy.special\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:50:02.785456Z",
     "start_time": "2020-01-10T15:50:02.737463Z"
    }
   },
   "outputs": [],
   "source": [
    "fpath = r'C:\\Users\\Solomonzhs\\Desktop\\Kaggle\\santa-workshop-tour-2019\\family_data.csv'\n",
    "data = pd.read_csv(fpath, index_col='family_id')\n",
    "data_choices = data.values\n",
    "\n",
    "fpath = r'C:\\Users\\Solomonzhs\\Desktop\\Kaggle\\santa-workshop-tour-2019\\sample_submission.csv'\n",
    "submission = pd.read_csv(fpath, index_col='family_id')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:54:02.530208Z",
     "start_time": "2020-01-10T15:54:02.519165Z"
    }
   },
   "outputs": [],
   "source": [
    "# const\n",
    "\n",
    "DBL_MAX = 1e+308\n",
    "\n",
    "N_FAMILES = 5000\n",
    "N_DAYS = 100\n",
    "N_CHOICES = 10\n",
    "MAX_OCCUPANCY = 300\n",
    "MIN_OCCUPANCY = 125\n",
    "\n",
    "MAX_DIFF = 300\n",
    "MAX_DIFF2 = MAX_DIFF * 2\n",
    "MAX_FAMILY_PER_DAY = 200"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:52:58.226726Z",
     "start_time": "2020-01-10T15:52:58.218726Z"
    }
   },
   "outputs": [],
   "source": [
    "DATA_DIR = \"C:/Users/Solomonzhs/Desktop/Kaggle/santa-workshop-tour-2019/\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:53:37.962632Z",
     "start_time": "2020-01-10T15:53:37.939660Z"
    }
   },
   "outputs": [],
   "source": [
    "def build_cost_lut(family_size, family_choice):\n",
    "    pref_cost = np.empty((N_FAMILES, N_DAYS), dtype=np.float64)\n",
    "    acc1_cost = np.empty((MAX_DIFF2,), dtype=np.float64)\n",
    "    acc_cost = np.empty((MAX_DIFF2, MAX_DIFF2), dtype=np.float64)\n",
    "    penalty = np.empty((MAX_DIFF2, ), dtype=np.float64)\n",
    "\n",
    "    for i in range(N_FAMILES):\n",
    "        # preference cost\n",
    "        n = family_size[i]\n",
    "        pref_cost[i][:] = 500 + 36 * n + 398 * n\n",
    "        pref_cost[i][family_choice[i][0]] = 0\n",
    "        pref_cost[i][family_choice[i][1]] = 50\n",
    "        pref_cost[i][family_choice[i][2]] = 50 + 9 * n\n",
    "        pref_cost[i][family_choice[i][3]] = 100 + 9 * n\n",
    "        pref_cost[i][family_choice[i][4]] = 200 + 9 * n\n",
    "        pref_cost[i][family_choice[i][5]] = 200 + 18 * n        \n",
    "        pref_cost[i][family_choice[i][6]] = 300 + 18 * n\n",
    "        pref_cost[i][family_choice[i][7]] = 300 + 36 * n\n",
    "        pref_cost[i][family_choice[i][8]] = 400 + 36 * n\n",
    "        pref_cost[i][family_choice[i][9]] = 500 + 36 * n + 199 * n\n",
    "        \n",
    "    for i in range(MAX_DIFF2):\n",
    "        # accounting cost\n",
    "        acc1_cost[i] = max(0, (i - 125.0) / 400.0 * i ** 0.5)\n",
    "        for j in range(MAX_DIFF2):\n",
    "            diff = abs(j - MAX_DIFF)\n",
    "            acc_cost[i][j] = max(0, (i - 125.0) / 400.0 * i ** (0.5 + diff / 50.0))\n",
    "\n",
    "        # constraint penalty\n",
    "        if i > MAX_OCCUPANCY:\n",
    "            penalty[i] = 60 * (i - MAX_OCCUPANCY + 1) ** 1.2\n",
    "        elif i < MIN_OCCUPANCY:\n",
    "            penalty[i] = 60 * (MIN_OCCUPANCY - i + 1) ** 1.2\n",
    "        else:\n",
    "            penalty[i] = 0\n",
    "\n",
    "    return pref_cost, acc1_cost, acc_cost, penalty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:54:09.887996Z",
     "start_time": "2020-01-10T15:54:09.510656Z"
    }
   },
   "outputs": [],
   "source": [
    "def build_global_data(data_dir):\n",
    "    # family data\n",
    "    family_choice = np.empty((N_FAMILES, N_CHOICES), dtype=np.int32)\n",
    "    family_size = np.empty((N_FAMILES,), dtype=np.int32)\n",
    "\n",
    "    with open(path.join(data_dir, \"family_data.csv\"), \"r\") as f:\n",
    "        reader = csv.reader(f)\n",
    "        next(reader, None)\n",
    "        for row in reader:\n",
    "            i = int(row[0])\n",
    "            choices = [int(c) - 1 for c in row[1:N_CHOICES+1]]\n",
    "            members = int(row[N_CHOICES+1])\n",
    "            family_size[i] = members\n",
    "            family_choice[i] = choices\n",
    "    # cost lut\n",
    "    pref_cost, acc1_cost, acc_cost, penalty = build_cost_lut(family_size, family_choice)\n",
    "    return pref_cost, acc1_cost, acc_cost, penalty, family_choice, family_size\n",
    "\n",
    "PREF_COST, ACC1_COST, ACC_COST, PENALTY, FAMILY_CHOICES, FAMILY_SIZE = build_global_data(DATA_DIR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:54:11.029041Z",
     "start_time": "2020-01-10T15:54:10.638625Z"
    }
   },
   "outputs": [],
   "source": [
    "PREF_COST, ACC1_COST, ACC_COST, PENALTY, FAMILY_CHOICES, FAMILY_SIZE = build_global_data(DATA_DIR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:54:58.423407Z",
     "start_time": "2020-01-10T15:54:58.410984Z"
    }
   },
   "outputs": [],
   "source": [
    "def insertion_cost(f_days, n_days, family_id, d_to, constraint_weight=1):\n",
    "    \"\"\" insertion cost for greedy method\n",
    "    \"\"\"\n",
    "    # preference cost\n",
    "    pref_cost = PREF_COST[family_id][d_to]\n",
    "\n",
    "    # accounting cost\n",
    "    n = n_days[d_to]\n",
    "    n_new = n + FAMILY_SIZE[family_id]\n",
    "    if d_to == N_DAYS - 1:\n",
    "        old_acc_cost = ACC1_COST[n]\n",
    "        new_acc_cost = ACC1_COST[n_new]\n",
    "    else:\n",
    "        old_diff = n - n_days[d_to + 1]\n",
    "        new_diff = n_new - n_days[d_to + 1]\n",
    "        old_acc_cost = ACC_COST[n][old_diff + MAX_DIFF]\n",
    "        new_acc_cost = ACC_COST[n_new][new_diff + MAX_DIFF]\n",
    "\n",
    "    # constraints penalty\n",
    "    old_penalty = PENALTY[n]\n",
    "    new_penalty = PENALTY[n_new]\n",
    "\n",
    "    return pref_cost + (new_acc_cost - old_acc_cost) + (new_penalty - old_penalty) * constraint_weight"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:54:58.769151Z",
     "start_time": "2020-01-10T15:54:58.758718Z"
    }
   },
   "outputs": [],
   "source": [
    "def total_cost(f_days, c_days, n_days, constraint_weight=1):\n",
    "    \"\"\" cost function for santa-2019\n",
    "    \"\"\"\n",
    "    \n",
    "    # preference cost\n",
    "    pref_cost = 0\n",
    "    for i in range(N_DAYS):\n",
    "        cost = 0\n",
    "        for j in range(c_days[i]):\n",
    "            cost += PREF_COST[f_days[i][j]][i]\n",
    "        pref_cost += cost\n",
    "\n",
    "    # accounting cost and constraints penalty\n",
    "    acc_cost = ACC1_COST[n_days[N_DAYS - 1]]\n",
    "    penalty = PENALTY[n_days[N_DAYS - 1]]\n",
    "    for i in range(N_DAYS - 1):\n",
    "        n = n_days[i]\n",
    "        diff = n - n_days[i + 1]\n",
    "        acc_cost += ACC_COST[n][diff + MAX_DIFF]\n",
    "        penalty += PENALTY[n]\n",
    "    return pref_cost + acc_cost + penalty * constraint_weight"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:55:00.926688Z",
     "start_time": "2020-01-10T15:55:00.921720Z"
    }
   },
   "outputs": [],
   "source": [
    "def day_insert(f_days, c_days, n_days, day, family_id):\n",
    "    \"\"\" insert family_id to day\n",
    "    \"\"\"\n",
    "    f_days[day][c_days[day]] = family_id\n",
    "    c_days[day] += 1\n",
    "    n_days[day] += FAMILY_SIZE[family_id]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T15:55:08.496215Z",
     "start_time": "2020-01-10T15:55:08.490249Z"
    }
   },
   "outputs": [],
   "source": [
    "def day_remove(f_days, c_days, n_days, day, pos):\n",
    "    \"\"\" remove family_id from day\n",
    "    \"\"\"\n",
    "    family_id = f_days[day][pos]\n",
    "    f_days[day][pos] = f_days[day][c_days[day]-1]\n",
    "    c_days[day] -= 1\n",
    "    n_days[day] -= FAMILY_SIZE[family_id]\n",
    "    return family_id"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T07:13:51.363652Z",
     "start_time": "2020-01-10T07:13:51.323228Z"
    }
   },
   "outputs": [],
   "source": [
    "family_size_dict = data[['n_people']].to_dict()['n_people']\n",
    "\n",
    "cols = [f'choice_{i}' for i in range(10)]\n",
    "choice_dict = data[cols].to_dict()\n",
    "\n",
    "N_DAYS = 100\n",
    "MAX_OCCUPANCY = 300\n",
    "MIN_OCCUPANCY = 125\n",
    "\n",
    "# from 100 to 1\n",
    "days = list(range(N_DAYS,0,-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T07:13:54.037401Z",
     "start_time": "2020-01-10T07:13:54.022810Z"
    }
   },
   "outputs": [],
   "source": [
    "def calc_family_costs(family):\n",
    "    assigned_day = family['assigned_day']\n",
    "    number_member = family['n_people']\n",
    "    if assigned_day == family['choice_0']:\n",
    "        penalty = 0\n",
    "    elif assigned_day == family['choice_1']:\n",
    "        penalty = 50\n",
    "    elif assigned_day == family['choice_2']:\n",
    "        penalty = 50 + 9 * number_member\n",
    "    elif assigned_day == family['choice_3']:\n",
    "        penalty = 100 + 9 * number_member\n",
    "    elif assigned_day == family['choice_4']:\n",
    "        penalty = 200 + 9 * number_member\n",
    "    elif assigned_day == family['choice_5']:\n",
    "        penalty = 200 + 18 * number_member\n",
    "    elif assigned_day == family['choice_6']:\n",
    "        penalty = 300 + 18 * number_member\n",
    "    elif assigned_day == family['choice_7']:\n",
    "        penalty = 300 + 36 * number_member\n",
    "    elif assigned_day == family['choice_8']:\n",
    "        penalty = 400 + 36 * number_member\n",
    "    elif assigned_day == family['choice_9']:\n",
    "        penalty = 500 + 36 * number_member + 199 * number_member\n",
    "    else:\n",
    "        penalty = 500 + 36 * number_member + 398 * number_member\n",
    "    return penalty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T07:13:55.227393Z",
     "start_time": "2020-01-10T07:13:55.203302Z"
    }
   },
   "outputs": [],
   "source": [
    "def cost_function(prediction):\n",
    "\n",
    "    penalty = 0\n",
    "\n",
    "    # We'll use this to count the number of people scheduled each day\n",
    "    daily_occupancy = {k:0 for k in days}\n",
    "    \n",
    "    # Looping over each family; d is the day for each family f\n",
    "    for f, d in enumerate(prediction):\n",
    "\n",
    "        # Using our lookup dictionaries to make simpler variable names\n",
    "        n = family_size_dict[f]\n",
    "        choice_0 = choice_dict['choice_0'][f]\n",
    "        choice_1 = choice_dict['choice_1'][f]\n",
    "        choice_2 = choice_dict['choice_2'][f]\n",
    "        choice_3 = choice_dict['choice_3'][f]\n",
    "        choice_4 = choice_dict['choice_4'][f]\n",
    "        choice_5 = choice_dict['choice_5'][f]\n",
    "        choice_6 = choice_dict['choice_6'][f]\n",
    "        choice_7 = choice_dict['choice_7'][f]\n",
    "        choice_8 = choice_dict['choice_8'][f]\n",
    "        choice_9 = choice_dict['choice_9'][f]\n",
    "\n",
    "        # add the family member count to the daily occupancy\n",
    "        daily_occupancy[d] += n\n",
    "\n",
    "        # Calculate the penalty for not getting top preference\n",
    "        if d == choice_0:\n",
    "            penalty += 0\n",
    "        elif d == choice_1:\n",
    "            penalty += 50\n",
    "        elif d == choice_2:\n",
    "            penalty += 50 + 9 * n\n",
    "        elif d == choice_3:\n",
    "            penalty += 100 + 9 * n\n",
    "        elif d == choice_4:\n",
    "            penalty += 200 + 9 * n\n",
    "        elif d == choice_5:\n",
    "            penalty += 200 + 18 * n\n",
    "        elif d == choice_6:\n",
    "            penalty += 300 + 18 * n\n",
    "        elif d == choice_7:\n",
    "            penalty += 300 + 36 * n\n",
    "        elif d == choice_8:\n",
    "            penalty += 400 + 36 * n\n",
    "        elif d == choice_9:\n",
    "            penalty += 500 + 36 * n + 199 * n\n",
    "        else:\n",
    "            penalty += 500 + 36 * n + 398 * n\n",
    "\n",
    "    # for each date, check total occupancy\n",
    "    #  (using soft constraints instead of hard constraints)\n",
    "    for _, v in daily_occupancy.items():\n",
    "        if (v > MAX_OCCUPANCY) or (v < MIN_OCCUPANCY):\n",
    "            penalty += 100000000\n",
    "\n",
    "    # Calculate the accounting cost\n",
    "    # The first day (day 100) is treated special\n",
    "    accounting_cost = (daily_occupancy[days[0]]-125.0) / 400.0 * daily_occupancy[days[0]]**(0.5)\n",
    "    # using the max function because the soft constraints might allow occupancy to dip below 125\n",
    "    accounting_cost = max(0, accounting_cost)\n",
    "    \n",
    "    # Loop over the rest of the days, keeping track of previous count\n",
    "    yesterday_count = daily_occupancy[days[0]]\n",
    "    for day in days[1:]:\n",
    "        today_count = daily_occupancy[day]\n",
    "        diff = abs(today_count - yesterday_count)\n",
    "        accounting_cost += max(0, (daily_occupancy[day]-125.0) / 400.0 * daily_occupancy[day]**(0.5 + diff / 50.0))\n",
    "        yesterday_count = today_count\n",
    "\n",
    "    penalty += accounting_cost\n",
    "    \n",
    "    return penalty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T07:28:41.479054Z",
     "start_time": "2020-01-10T07:13:56.413331Z"
    }
   },
   "outputs": [],
   "source": [
    "# Start with the sample submission values\n",
    "best = submission['assigned_day'].tolist()\n",
    "start_score = cost_function(best)\n",
    "\n",
    "new = best.copy()\n",
    "# loop over each family\n",
    "for fam_id, _ in enumerate(best):\n",
    "    # loop over each family choice\n",
    "    for pick in range(10):\n",
    "        day = choice_dict[f'choice_{pick}'][fam_id]\n",
    "        temp = new.copy()\n",
    "        temp[fam_id] = day # add in the new pick\n",
    "        if cost_function(temp) < start_score:\n",
    "            new = temp.copy()\n",
    "            start_score = cost_function(new)\n",
    "\n",
    "submission['assigned_day'] = new\n",
    "score = cost_function(new)\n",
    "submission.to_csv(f'submission_{score}.csv')\n",
    "print(f'Score: {score}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "jupyter notebook --NotebookApp.iopub_data_rate_limit=10000000000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T07:47:42.607760Z",
     "start_time": "2020-01-10T07:47:42.598841Z"
    }
   },
   "outputs": [],
   "source": [
    "def plot_results(data, name):\n",
    "    x = data.columns\n",
    "    y = data.loc[name]\n",
    "    plt.plot(x, y, 'ro')\n",
    "    plt.grid()\n",
    "    plt.title(name)\n",
    "    plt.xlabel('steps')\n",
    "    plt.ylabel('value')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T07:28:41.518017Z",
     "start_time": "2020-01-10T07:28:41.502008Z"
    }
   },
   "outputs": [],
   "source": [
    "def check_day(data, day):\n",
    "    group_data = data.groupby('assigned_day').sum()['n_people'].to_frame()\n",
    "    if (125 <= group_data.loc[day, 'n_people']) & (group_data.loc[day, 'n_people'] <= 300):\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T07:47:57.218909Z",
     "start_time": "2020-01-10T07:47:57.088197Z"
    }
   },
   "outputs": [],
   "source": [
    "for i in range(N_DAYS):\n",
    "    data.loc[i*50:(i+1)*50-1, 'assigned_day'] = i+1\n",
    "data['assigned_day'] = data['assigned_day'].astype(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-10T07:48:03.504459Z",
     "start_time": "2020-01-10T07:48:03.487189Z"
    }
   },
   "outputs": [],
   "source": [
    "family_id = 100\n",
    "cost_function(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-09T10:24:16.906984Z",
     "start_time": "2020-01-09T10:18:20.937Z"
    }
   },
   "outputs": [],
   "source": [
    "data['penalty_cost'] = data.apply(cost_function, axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-09T10:24:16.907983Z",
     "start_time": "2020-01-09T10:18:20.940Z"
    }
   },
   "outputs": [],
   "source": [
    "print('Total costs:', data['penalty_cost'].sum())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-09T10:24:16.908991Z",
     "start_time": "2020-01-09T10:18:20.942Z"
    }
   },
   "outputs": [],
   "source": [
    "def check_swap_day(data, family, choice):\n",
    "    data_copy = data.copy()\n",
    "    data_copy.loc[family, 'assigned_day'] = data_copy.loc[family, 'choice_'+str(choice)]\n",
    "    data_copy.loc[family, 'penalty_cost'] = calc_family_costs(data_copy.iloc[family])\n",
    "    \n",
    "    penalty_before = data.loc[family, 'penalty_cost']\n",
    "    \n",
    "    penalty_after = data_copy.loc[family, 'penalty_cost']\n",
    "    \n",
    "    # Check conditions\n",
    "    day_before = check_day(data_copy, data.loc[family, 'assigned_day'])\n",
    "    day_after = check_day(data_copy, data_copy.loc[family, 'assigned_day'])\n",
    "\n",
    "    if(day_before==True and day_after==True):\n",
    "        improvement = (penalty_before-penalty_after)\n",
    "    else:\n",
    "        improvement = -1\n",
    "    \n",
    "    return improvement"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-09T10:24:16.910985Z",
     "start_time": "2020-01-09T10:18:20.944Z"
    }
   },
   "outputs": [],
   "source": [
    "family_id = 386\n",
    "check_swap_day(data, family_id, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-09T10:24:16.912981Z",
     "start_time": "2020-01-09T10:18:20.946Z"
    }
   },
   "outputs": [],
   "source": [
    "def check_swap_family(data, family, choice):\n",
    "    family1 = family\n",
    "    day_family1 = data.loc[family1, 'assigned_day']\n",
    "    penalty1 = data.loc[family1, 'penalty_cost']\n",
    "    member_family1 = data.loc[family1, 'n_people']\n",
    "    \n",
    "    data = data.reset_index()\n",
    "    day_member_list = data.groupby('assigned_day')['family_id'].apply(list).to_frame()\n",
    "    \n",
    "    improvements = {}\n",
    "    for member in day_member_list.loc[data.loc[family1, 'choice_'+str(choice)], 'family_id']:\n",
    "        family2 = member\n",
    "        day_family2 = data.loc[family2, 'assigned_day']\n",
    "        member_family2 = data.loc[family2, 'n_people']\n",
    "        penalty2 = data.loc[family2, 'penalty_cost']\n",
    "        \n",
    "        # simulate the swap with another family\n",
    "        data_copy = data.copy()\n",
    "        data_copy.loc[family2, 'assigned_day'] = data_copy.loc[family1, 'assigned_day']\n",
    "        data_copy.loc[family1, 'assigned_day'] = data_copy.loc[family1, 'choice_'+str(choice)]\n",
    "        # calc the new penalty cost for both families\n",
    "        new_penalty1 = calc_family_costs(data_copy.iloc[family1])\n",
    "        new_penalty2 = calc_family_costs(data_copy.iloc[family2])\n",
    "        # check both days before and after swaping\n",
    "        day_before = check_day(data_copy, data.loc[family1, 'assigned_day'])\n",
    "        day_after = check_day(data_copy, data_copy.loc[family1, 'choice_'+str(choice)])\n",
    "        \n",
    "        # calc the accounting costs before and after swaping\n",
    "        accounting_before = calc_accounting_cost(data)\n",
    "        accounting_after = calc_accounting_cost(data_copy)\n",
    "        if(day_before==True and day_after==True):\n",
    "            improvement = (penalty1-new_penalty1) + (penalty2-new_penalty2) + (accounting_before-accounting_after)\n",
    "        else:\n",
    "            improvement = -1\n",
    "        improvements.update({member:improvement})\n",
    "   \n",
    "    maximum = max(zip(improvements.values(), improvements.keys()))\n",
    "    family_swap = maximum[1]\n",
    "    return improvement, family_swap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-09T10:24:16.913998Z",
     "start_time": "2020-01-09T10:18:20.948Z"
    }
   },
   "outputs": [],
   "source": [
    "family_id = 386\n",
    "check_swap_family(data, family_id, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# New- Solver Min Cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:06:08.615791Z",
     "start_time": "2020-01-12T16:06:08.066716Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from collections import defaultdict\n",
    "NUMBER_DAYS = 100\n",
    "NUMBER_FAMILIES = 5000\n",
    "MAX_BEST_CHOICE = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:07:27.293384Z",
     "start_time": "2020-01-12T16:07:27.250373Z"
    }
   },
   "outputs": [],
   "source": [
    "data = pd.read_csv(r'C:\\Users\\Solomonzhs\\Desktop\\Kaggle\\santa-workshop-tour-2019\\family_data.csv')\n",
    "\n",
    "submission = pd.read_csv(r'C:\\Users\\Solomonzhs\\Desktop\\Kaggle\\santa-workshop-tour-2019\\sample_submission.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:07:31.030355Z",
     "start_time": "2020-01-12T16:07:31.021062Z"
    }
   },
   "outputs": [],
   "source": [
    "assigned_days = submission['assigned_day'].values\n",
    "columns = data.columns[1:11]\n",
    "DESIRED = data[columns].values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:07:37.358950Z",
     "start_time": "2020-01-12T16:07:37.352950Z"
    }
   },
   "outputs": [],
   "source": [
    "COST_PER_FAMILY        = [0,50,50,100,200,200,300,300,400,500]\n",
    "COST_PER_FAMILY_MEMBER = [0, 0, 9,  9,  9, 18, 18, 36, 36,235]\n",
    "N_PEOPLE = data['n_people'].astype(int).values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:07:43.133525Z",
     "start_time": "2020-01-12T16:07:43.129521Z"
    }
   },
   "outputs": [],
   "source": [
    "def get_daily_occupancy(assigned_days):\n",
    "    daily_occupancy = np.zeros(100, np.int32)\n",
    "    for i, r in enumerate(assigned_days):\n",
    "        daily_occupancy[r-1] += N_PEOPLE[i]\n",
    "    return daily_occupancy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:11:00.980643Z",
     "start_time": "2020-01-12T16:11:00.955645Z"
    }
   },
   "outputs": [],
   "source": [
    "def cost_function(prediction):\n",
    "    N_DAYS = NUMBER_DAYS\n",
    "    MAX_OCCUPANCY = 300\n",
    "    MIN_OCCUPANCY = 125\n",
    "    penalty = 0\n",
    "    days = list(range(N_DAYS,0,-1))\n",
    "    tmp = pd.read_csv(r'C:\\Users\\Solomonzhs\\Desktop\\Kaggle\\santa-workshop-tour-2019\\family_data.csv', index_col='family_id')\n",
    "    family_size_dict = tmp[['n_people']].to_dict()['n_people']\n",
    "\n",
    "    cols = [f'choice_{i}' for i in range(10)]\n",
    "    choice_dict = tmp[cols].to_dict()\n",
    "\n",
    "    # We'll use this to count the number of people scheduled each day\n",
    "    daily_occupancy = {k:0 for k in days}\n",
    "    \n",
    "    # Looping over each family; d is the day for each family f\n",
    "    for f, d in enumerate(prediction):\n",
    "        # Using our lookup dictionaries to make simpler variable names\n",
    "        n = family_size_dict[f]\n",
    "\n",
    "        choice_0 = choice_dict['choice_0'][f]\n",
    "        choice_1 = choice_dict['choice_1'][f]\n",
    "        choice_2 = choice_dict['choice_2'][f]\n",
    "        choice_3 = choice_dict['choice_3'][f]\n",
    "        choice_4 = choice_dict['choice_4'][f]\n",
    "        choice_5 = choice_dict['choice_5'][f]\n",
    "        choice_6 = choice_dict['choice_6'][f]\n",
    "        choice_7 = choice_dict['choice_7'][f]\n",
    "        choice_8 = choice_dict['choice_8'][f]\n",
    "        choice_9 = choice_dict['choice_9'][f]\n",
    "\n",
    "        # add the family member count to the daily occupancy\n",
    "        daily_occupancy[d] += n\n",
    "\n",
    "        # Calculate the penalty for not getting top preference\n",
    "        if d == choice_0:\n",
    "            penalty += 0\n",
    "        elif d == choice_1:\n",
    "            penalty += 50\n",
    "        elif d == choice_2:\n",
    "            penalty += 50 + 9 * n\n",
    "        elif d == choice_3:\n",
    "            penalty += 100 + 9 * n\n",
    "        elif d == choice_4:\n",
    "            penalty += 200 + 9 * n\n",
    "        elif d == choice_5:\n",
    "            penalty += 200 + 18 * n\n",
    "        elif d == choice_6:\n",
    "            penalty += 300 + 18 * n\n",
    "        elif d == choice_7:\n",
    "            penalty += 300 + 36 * n\n",
    "        elif d == choice_8:\n",
    "            penalty += 400 + 36 * n\n",
    "        elif d == choice_9:\n",
    "            penalty += 500 + 36 * n + 199 * n\n",
    "        else:\n",
    "            penalty += 500 + 36 * n + 398 * n\n",
    "\n",
    "    # for each date, check total occupancy\n",
    "    #  (using soft constraints instead of hard constraints)\n",
    "    for _, v in daily_occupancy.items():\n",
    "        if v > MAX_OCCUPANCY or v < MIN_OCCUPANCY:\n",
    "            penalty += 100000000\n",
    "\n",
    "    # Calculate the accounting cost\n",
    "    # The first day (day 100) is treated special\n",
    "    # using the max function because the soft constraints might allow occupancy to dip below 125\n",
    "    accounting_cost = max(0, (daily_occupancy[days[0]]-125.0) / 400.0 * daily_occupancy[days[0]]**(0.5))\n",
    "    # Loop over the rest of the days, keeping track of previous count\n",
    "    yesterday_count = daily_occupancy[days[0]]\n",
    "    for day in days[1:]:\n",
    "        today_count = daily_occupancy[day]\n",
    "        diff = abs(today_count - yesterday_count)\n",
    "        accounting_cost += max(0, (today_count-125.0) / 400.0 * today_count**(0.5 + diff / 50.0))\n",
    "        yesterday_count = today_count\n",
    "\n",
    "    return penalty, accounting_cost, penalty + accounting_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:11:02.163017Z",
     "start_time": "2020-01-12T16:11:02.154016Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([4, 3, 2, 5, 7, 6, 8], dtype=int64)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data.n_people.unique()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:11:03.270350Z",
     "start_time": "2020-01-12T16:11:02.706793Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(9756955, 1941.2534888812897, 9758896.253488882)\n",
      "(8184241, 2253.902261563777, 8186494.902261564)\n",
      "(5322825, 6564.762943264543, 5329389.762943264)\n",
      "(3187985, 7082.630899220902, 3195067.6308992207)\n",
      "(1825615, 17218.631610250108, 1842833.63161025)\n",
      "(935298, 17413.745930630026, 952711.74593063)\n",
      "(422846, 16587.60956684803, 439433.609566848)\n"
     ]
    }
   ],
   "source": [
    "from ortools.graph import pywrapgraph\n",
    "\n",
    "for num_members in range(2, 9): # Families have minimum 2 and maximum 8 members\n",
    "    daily_occupancy = get_daily_occupancy(assigned_days)\n",
    "    fids = np.where(N_PEOPLE == num_members)[0]\n",
    "\n",
    "    PCOSTM = {}\n",
    "    for fid in range(NUMBER_FAMILIES):\n",
    "        if fid in fids:\n",
    "            for i in range(MAX_BEST_CHOICE):\n",
    "                PCOSTM[fid, DESIRED[fid][i]-1] = COST_PER_FAMILY[i] + N_PEOPLE[fid] * COST_PER_FAMILY_MEMBER[i]\n",
    "        else:\n",
    "            daily_occupancy[assigned_days[fid]-1] -= N_PEOPLE[fid]\n",
    "\n",
    "    offset = fids.shape[0]\n",
    "    solver = pywrapgraph.SimpleMinCostFlow()\n",
    "    for day in range(NUMBER_DAYS):\n",
    "        solver.SetNodeSupply(offset+day, int(daily_occupancy[day]//num_members))\n",
    "\n",
    "    for i in range(offset):\n",
    "        fid = fids[i]\n",
    "        solver.SetNodeSupply(i, -1)\n",
    "        for j in range(MAX_BEST_CHOICE):\n",
    "            day = DESIRED[fid][j]-1\n",
    "            solver.AddArcWithCapacityAndUnitCost(int(offset+day), i, 1, int(PCOSTM[fid, day]))\n",
    "    solver.SolveMaxFlowWithMinCost()\n",
    "\n",
    "    for i in range(solver.NumArcs()):\n",
    "        if solver.Flow(i) > 0:\n",
    "            assigned_days[fids[solver.Head(i)]] = solver.Tail(i) - offset + 1\n",
    "    print(cost_function(assigned_days))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# New 2 - PyTorch "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:15:21.220343Z",
     "start_time": "2020-01-12T16:15:21.204978Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np # linear algebra\n",
    "import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n",
    "from pathlib import Path\n",
    "import tqdm\n",
    "import torch\n",
    "import torch.nn as nn\n",
    "import torch.nn.functional as F\n",
    "from torch.autograd import Variable\n",
    "from numba import njit\n",
    "MAX_CHOICE = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:15:53.704607Z",
     "start_time": "2020-01-12T16:15:53.686325Z"
    }
   },
   "outputs": [],
   "source": [
    "data = pd.read_csv(r'C:\\Users\\Solomonzhs\\Desktop\\Kaggle\\santa-workshop-tour-2019\\family_data.csv', index_col='family_id')\n",
    "data_choices = data.values\n",
    "submission = pd.read_csv(r'C:\\Users\\Solomonzhs\\Desktop\\Kaggle\\santa-workshop-tour-2019\\sample_submission.csv', index_col='family_id')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:16:05.089588Z",
     "start_time": "2020-01-12T16:16:04.539568Z"
    }
   },
   "outputs": [],
   "source": [
    "dummies = []\n",
    "for i in range(MAX_CHOICE):\n",
    "    tmp = pd.get_dummies(data[f'choice_{i}']).values*(data['n_people'].values.reshape(-1,1))\n",
    "    dummies.append((\n",
    "        np.concatenate([tmp, tmp[:, -1].reshape(-1,1)], axis=1)\n",
    "                   ).reshape(5000, 101, 1))\n",
    "dummies = np.concatenate(dummies, axis=2)\n",
    "dummies = np.swapaxes(dummies, 1, 2)\n",
    "\n",
    "penalties = {n: [0, 50, 50 + 9 * n, 100 + 9 * n, 200 + 9 * n, 200 + 18 * n, 300 + 18 * n, 300 + 36 * n, 400 + 36 * n, 500 + 36 * n + 199 * n] for n in np.unique(data['n_people'])}\n",
    "\n",
    "mat = []\n",
    "for i in range(5000):\n",
    "    n = data.iloc[i]['n_people']\n",
    "    mat.append(penalties[n][:MAX_CHOICE])\n",
    "mat = np.array(mat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:16:38.010672Z",
     "start_time": "2020-01-12T16:16:37.974709Z"
    }
   },
   "outputs": [],
   "source": [
    "def create_init(initial_sub):\n",
    "    \n",
    "    fam_choices = data\n",
    "    a = pd.merge(initial_sub, fam_choices, on='family_id')\n",
    "\n",
    "    initial_choices = []\n",
    "    for i in range(MAX_CHOICE):\n",
    "        initial_choices.append(((a[f'choice_{i}'] == a['assigned_day'])).values.reshape(-1,1))\n",
    "    initial_choices = np.concatenate(initial_choices, axis=1)\n",
    "    initial_choices = torch.tensor(\n",
    "       initial_choices*10\n",
    "        , dtype=torch.float32)#.cuda()\n",
    "    return initial_choices\n",
    "\n",
    "initial_sub = pd.read_csv(r'C:\\Users\\Solomonzhs\\Desktop\\Kaggle\\santa-workshop-tour-2019\\sample_submission.csv')\n",
    "initial_choices = create_init(initial_sub)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:18:03.844756Z",
     "start_time": "2020-01-12T16:18:03.836519Z"
    }
   },
   "outputs": [],
   "source": [
    "family_sizes = data.n_people.values.astype(np.int8)\n",
    "cost_dict = {0:  [  0,  0],\n",
    "             1:  [ 50,  0],\n",
    "             2:  [ 50,  9],\n",
    "             3:  [100,  9],\n",
    "             4:  [200,  9],\n",
    "             5:  [200, 18],\n",
    "             6:  [300, 18],\n",
    "             7:  [300, 36],\n",
    "             8:  [400, 36],\n",
    "             9:  [500, 36 + 199],\n",
    "             10: [500, 36 + 398],\n",
    "            }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:18:16.607930Z",
     "start_time": "2020-01-12T16:18:13.423788Z"
    }
   },
   "outputs": [],
   "source": [
    "def cost(choice, members, cost_dict):\n",
    "    x = cost_dict[choice]\n",
    "    return x[0] + members * x[1]\n",
    "all_costs = {k: pd.Series([cost(k, x, cost_dict) for x in range(2,9)], index=range(2,9)) for k in cost_dict.keys()}\n",
    "df_all_costs = pd.DataFrame(all_costs)\n",
    "\n",
    "family_cost_matrix = np.zeros((100,len(family_sizes))) # Cost for each family for each day.\n",
    "\n",
    "for i, el in enumerate(family_sizes):\n",
    "    family_cost_matrix[:, i] += all_costs[10][el] # populate each day with the max cost\n",
    "    for j, choice in enumerate(data.drop(\"n_people\",axis=1).values[i,:]):\n",
    "        family_cost_matrix[choice-1, i] = all_costs[j][el]\n",
    "        \n",
    "def accounting(today, previous):\n",
    "    return ((today - 125) / 400 ) * today ** (.5 + (abs(today - previous) / 50))\n",
    "\n",
    "acc_costs = np.zeros([176,176])\n",
    "\n",
    "for i, x in enumerate(range(125,300+1)):\n",
    "    for j, y in enumerate(range(125,300+1)):\n",
    "        acc_costs[i,j] = accounting(x,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:18:24.149258Z",
     "start_time": "2020-01-12T16:18:24.139290Z"
    }
   },
   "outputs": [],
   "source": [
    "@njit(fastmath=True)\n",
    "def cost_function(prediction, family_size, family_cost_matrix, accounting_cost_matrix):\n",
    "    N_DAYS = 100\n",
    "    MAX_OCCUPANCY = 300\n",
    "    MIN_OCCUPANCY = 125\n",
    "    penalty = 0\n",
    "    accounting_cost = 0\n",
    "    max_occ = False\n",
    "    \n",
    "    daily_occupancy = np.zeros(N_DAYS + 1, dtype=np.int16)\n",
    "    for i, (pred, n) in enumerate(zip(prediction, family_size)):\n",
    "        daily_occupancy[pred - 1] += n\n",
    "        penalty += family_cost_matrix[pred - 1, i]\n",
    "        \n",
    "    daily_occupancy[-1] = daily_occupancy[-2]\n",
    "    for day in range(N_DAYS):\n",
    "        n_next = daily_occupancy[day + 1]\n",
    "        n = daily_occupancy[day]\n",
    "        max_occ += MIN_OCCUPANCY > n\n",
    "        max_occ += MAX_OCCUPANCY < n\n",
    "        accounting_cost += accounting_cost_matrix[n-MIN_OCCUPANCY, n_next-MIN_OCCUPANCY]\n",
    "    if max_occ: \n",
    "        return 1e11\n",
    "    return penalty+accounting_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:18:33.753939Z",
     "start_time": "2020-01-12T16:18:32.980209Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10641498.403135022"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cost_function(initial_sub['assigned_day'].values, family_sizes, family_cost_matrix, acc_costs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:19:00.630159Z",
     "start_time": "2020-01-12T16:19:00.611244Z"
    }
   },
   "outputs": [],
   "source": [
    "class Model(nn.Module):\n",
    "    def __init__(self, mat, dummies):\n",
    "        super().__init__()\n",
    "        self.mat = torch.from_numpy(mat).type(torch.int16)#.cuda()\n",
    "        self.dummies = torch.from_numpy(dummies).type(torch.float32)#.cuda()\n",
    "        self.weight = torch.nn.Parameter(data=torch.Tensor(5000, MAX_CHOICE).type(torch.float32)#.cuda()\n",
    "                                         , requires_grad=True)\n",
    "        self.weight.data.copy_(initial_choices)\n",
    "        \n",
    "    def forward(self):\n",
    "        prob = F.softmax(self.weight,dim=1)\n",
    "        \n",
    "        x = (prob * self.mat).sum()\n",
    "        \n",
    "        daily_occupancy = torch.zeros(101, dtype=torch.float32)#.cuda()\n",
    "        for i in range(MAX_CHOICE):\n",
    "            daily_occupancy += (prob[:, i]@self.dummies[:, i, :])\n",
    "        \n",
    "        diff = torch.abs(daily_occupancy[:-1] - daily_occupancy[1:])\n",
    "        daily_occupancy = daily_occupancy[:-1]\n",
    "        y = (\n",
    "            torch.relu(daily_occupancy-125.0) / 400.0 * daily_occupancy**(0.5 + diff / 50.0)\n",
    "        ).sum() \n",
    "        \n",
    "        v = ((torch.relu(125-daily_occupancy))**2+(torch.relu(daily_occupancy-300))**2).sum()\n",
    "        \n",
    "        entropy_loss = -1.0 * (prob * F.log_softmax(self.weight, dim=1)).sum()\n",
    "        return  x, y, v*10000, entropy_loss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:19:07.198070Z",
     "start_time": "2020-01-12T16:19:07.151798Z"
    }
   },
   "outputs": [],
   "source": [
    "model = Model(mat, dummies)\n",
    "best_score = 10e10\n",
    "best_pos = None\n",
    "optimizer = torch.optim.Adam(model.parameters(), lr = 0.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:19:38.237915Z",
     "start_time": "2020-01-12T16:19:16.299393Z"
    }
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "91802d41869f4450b597ecc73141aeb7",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "HBox(children=(IntProgress(value=0, max=1001), HTML(value='')))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\t512341.5\tinf    \t100000000000.0\n",
      "1000\tnan\tnan    \t100000000000.0\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for epoch in tqdm.tqdm_notebook(range(1_001)):\n",
    "    optimizer.zero_grad()\n",
    "    x, y, v, ent = model()\n",
    "    loss = x + y + v + 0*ent\n",
    "    loss.backward()\n",
    "    optimizer.step()\n",
    "    \n",
    "    pos = model.weight.argmax(1).cpu().numpy()\n",
    "    pred = []\n",
    "    for i in range(5000):\n",
    "        pred.append(data_choices[i, pos[i]])\n",
    "    pred = np.array(pred)\n",
    "    score = cost_function(pred, family_sizes, family_cost_matrix, acc_costs)\n",
    "    if (score < best_score):\n",
    "        best_score = score\n",
    "        best_pos = pred\n",
    "        print(best_score)\n",
    "        submission['assigned_day'] = best_pos\n",
    "        submission.to_csv(f'submission.csv')\n",
    "    if epoch % 1000 == 0:\n",
    "            x = np.round(x.item(),1)\n",
    "            y = np.round(y.item(),1)\n",
    "            print(f'{epoch}\\t{x}\\t{y}    \\t{np.round(score, 2)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# New 3 - Modeling Base Logic "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:21:23.166040Z",
     "start_time": "2020-01-12T16:21:22.893486Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import scipy.special\n",
    "import matplotlib.pyplot as plt\n",
    "import os"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:21:47.940338Z",
     "start_time": "2020-01-12T16:21:47.917302Z"
    }
   },
   "outputs": [],
   "source": [
    "data = pd.read_csv(r'C:\\Users\\Solomonzhs\\Desktop\\Kaggle\\santa-workshop-tour-2019\\family_data.csv', index_col='family_id')\n",
    "data_choices = data.values\n",
    "submission = pd.read_csv(r'C:\\Users\\Solomonzhs\\Desktop\\Kaggle\\santa-workshop-tour-2019\\sample_submission.csv', index_col='family_id')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:21:57.618644Z",
     "start_time": "2020-01-12T16:21:57.612873Z"
    }
   },
   "outputs": [],
   "source": [
    "num_days = 100\n",
    "lower = 125\n",
    "upper = 300\n",
    "days = list(range(num_days, 0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:22:04.710863Z",
     "start_time": "2020-01-12T16:22:04.699861Z"
    }
   },
   "outputs": [],
   "source": [
    "def calc_family_costs(family):\n",
    "    assigned_day = family['assigned_day']\n",
    "    number_member = family['n_people']\n",
    "    if assigned_day == family['choice_0']:\n",
    "        penalty = 0\n",
    "    elif assigned_day == family['choice_1']:\n",
    "        penalty = 50\n",
    "    elif assigned_day == family['choice_2']:\n",
    "        penalty = 50 + 9 * number_member\n",
    "    elif assigned_day == family['choice_3']:\n",
    "        penalty = 100 + 9 * number_member\n",
    "    elif assigned_day == family['choice_4']:\n",
    "        penalty = 200 + 9 * number_member\n",
    "    elif assigned_day == family['choice_5']:\n",
    "        penalty = 200 + 18 * number_member\n",
    "    elif assigned_day == family['choice_6']:\n",
    "        penalty = 300 + 18 * number_member\n",
    "    elif assigned_day == family['choice_7']:\n",
    "        penalty = 300 + 36 * number_member\n",
    "    elif assigned_day == family['choice_8']:\n",
    "        penalty = 400 + 36 * number_member\n",
    "    elif assigned_day == family['choice_9']:\n",
    "        penalty = 500 + 36 * number_member + 199 * number_member\n",
    "    else:\n",
    "        penalty = 500 + 36 * number_member + 398 * number_member\n",
    "    return penalty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:22:24.723479Z",
     "start_time": "2020-01-12T16:22:24.714518Z"
    }
   },
   "outputs": [],
   "source": [
    "def calc_accounting_cost(data):\n",
    "    accounting_cost = 0\n",
    "    daily_occupancy = {k:0 for k in days}\n",
    "    family_size_dict = data[['n_people']].to_dict()['n_people']\n",
    "    for f, d in enumerate(data['assigned_day']):\n",
    "        n = family_size_dict[f]\n",
    "        daily_occupancy[d] += n\n",
    "\n",
    "    accounting_cost = (daily_occupancy[days[0]]-125.0) / 400.0 * daily_occupancy[days[0]]**(0.5)\n",
    "    accounting_cost = max(0, accounting_cost)\n",
    "    \n",
    "    yesterday_count = daily_occupancy[days[0]]\n",
    "    for day in days[1:]:\n",
    "        today_count = daily_occupancy[day]\n",
    "        diff = abs(today_count - yesterday_count)\n",
    "        accounting_cost += max(0, (daily_occupancy[day]-125.0) / 400.0 * daily_occupancy[day]**(0.5 + diff / 50.0))\n",
    "        yesterday_count = today_count\n",
    "    return accounting_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:22:25.018478Z",
     "start_time": "2020-01-12T16:22:25.012478Z"
    }
   },
   "outputs": [],
   "source": [
    "def plot_results(data, name):\n",
    "    x = data.columns\n",
    "    y = data.loc[name]\n",
    "    plt.plot(x, y, 'ro')\n",
    "    plt.grid()\n",
    "    plt.title(name)\n",
    "    plt.xlabel('steps')\n",
    "    plt.ylabel('value')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:22:32.953425Z",
     "start_time": "2020-01-12T16:22:32.944604Z"
    }
   },
   "outputs": [],
   "source": [
    "def check_day(data, day):\n",
    "    group_data = data.groupby('assigned_day').sum()['n_people'].to_frame()\n",
    "    if (125 <= group_data.loc[day, 'n_people']) & (group_data.loc[day, 'n_people'] <= 300):\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:22:38.513786Z",
     "start_time": "2020-01-12T16:22:38.464794Z"
    }
   },
   "outputs": [],
   "source": [
    "for i in range(num_days):\n",
    "    data.loc[i*50:(i+1)*50-1, 'assigned_day'] = i+1\n",
    "data['assigned_day'] = data['assigned_day'].astype(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:24:16.252180Z",
     "start_time": "2020-01-12T16:24:16.244219Z"
    }
   },
   "outputs": [],
   "source": [
    "data['assigned_day'] = submission['assigned_day']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:24:47.494793Z",
     "start_time": "2020-01-12T16:24:47.486299Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3104"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "family_id = 100\n",
    "calc_family_costs(data.iloc[family_id])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:24:53.701258Z",
     "start_time": "2020-01-12T16:24:53.276220Z"
    }
   },
   "outputs": [],
   "source": [
    "data['penalty_cost'] = data.apply(calc_family_costs, axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:25:04.330460Z",
     "start_time": "2020-01-12T16:25:04.316490Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1907.4031350226594"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "acc_costs = calc_accounting_cost(data)\n",
    "acc_costs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:25:12.740749Z",
     "start_time": "2020-01-12T16:25:12.734057Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total costs: 10641498.403135022\n"
     ]
    }
   ],
   "source": [
    "print('Total costs:', data['penalty_cost'].sum()+ acc_costs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:25:24.846729Z",
     "start_time": "2020-01-12T16:25:24.837768Z"
    }
   },
   "outputs": [],
   "source": [
    "def check_swap_day(data, family, choice):\n",
    "    data_copy = data.copy()\n",
    "    data_copy.loc[family, 'assigned_day'] = data_copy.loc[family, 'choice_'+str(choice)]\n",
    "    data_copy.loc[family, 'penalty_cost'] = calc_family_costs(data_copy.iloc[family])\n",
    "    \n",
    "    penalty_before = data.loc[family, 'penalty_cost']\n",
    "    accounting_before = calc_accounting_cost(data)\n",
    "    \n",
    "    penalty_after = data_copy.loc[family, 'penalty_cost']\n",
    "    accounting_after = calc_accounting_cost(data_copy)\n",
    "    \n",
    "    # Check conditions\n",
    "    day_before = check_day(data_copy, data.loc[family, 'assigned_day'])\n",
    "    day_after = check_day(data_copy, data_copy.loc[family, 'assigned_day'])\n",
    "\n",
    "    if(day_before==True and day_after==True):\n",
    "        improvement = (penalty_before-penalty_after)+(accounting_before-accounting_after)\n",
    "    else:\n",
    "        improvement = -1\n",
    "    \n",
    "    return improvement"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:25:53.987293Z",
     "start_time": "2020-01-12T16:25:53.958301Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3084.460188415094"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "family_id = 100\n",
    "check_swap_day(data, family_id, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:26:16.363314Z",
     "start_time": "2020-01-12T16:26:16.347354Z"
    }
   },
   "outputs": [],
   "source": [
    "def check_swap_family(data, family, choice):\n",
    "    family1 = family\n",
    "    day_family1 = data.loc[family1, 'assigned_day']\n",
    "    penalty1 = data.loc[family1, 'penalty_cost']\n",
    "    member_family1 = data.loc[family1, 'n_people']\n",
    "    \n",
    "    day_member_list = data.groupby('assigned_day')['family_id'].apply(list).to_frame()\n",
    "    \n",
    "    improvements = {}\n",
    "    for member in day_member_list.loc[data.loc[family1, 'choice_'+str(choice)], 'family_id']:\n",
    "        family2 = member\n",
    "        day_family2 = data.loc[family2, 'assigned_day']\n",
    "        member_family2 = data.loc[family2, 'n_people']\n",
    "        penalty2 = data.loc[family2, 'penalty_cost']\n",
    "        \n",
    "        # simulate the swap with another family\n",
    "        data_copy = data.copy()\n",
    "        data_copy.loc[family2, 'assigned_day'] = data_copy.loc[family1, 'assigned_day']\n",
    "        data_copy.loc[family1, 'assigned_day'] = data_copy.loc[family1, 'choice_'+str(choice)]\n",
    "        # calc the new penalty cost for both families\n",
    "        new_penalty1 = calc_family_costs(data_copy.iloc[family1])\n",
    "        new_penalty2 = calc_family_costs(data_copy.iloc[family2])\n",
    "        # check both days before and after swaping\n",
    "        day_before = check_day(data_copy, data.loc[family1, 'assigned_day'])\n",
    "        day_after = check_day(data_copy, data_copy.loc[family1, 'choice_'+str(choice)])\n",
    "        # calc the accounting costs before and after swaping\n",
    "        accounting_before = calc_accounting_cost(data)\n",
    "        accounting_after = calc_accounting_cost(data_copy)\n",
    "        if(day_before==True and day_after==True):\n",
    "            improvement = (penalty1-new_penalty1) + (penalty2-new_penalty2) + (accounting_before-accounting_after)\n",
    "        else:\n",
    "            improvement = -1\n",
    "        improvements.update({member:improvement})\n",
    "   \n",
    "    maximum = max(zip(improvements.values(), improvements.keys()))\n",
    "    family_swap = maximum[1]\n",
    "    return improvement, family_swap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:27:32.882823Z",
     "start_time": "2020-01-12T16:27:32.249583Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3099.702689288188, 3161)"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = data.reset_index()\n",
    "family_id = 100\n",
    "check_swap_family(data, family_id, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-01-12T16:27:46.555724Z",
     "start_time": "2020-01-12T16:27:45.919489Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3950.067390674625, 3966.949943189299, 4734)"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "family_id = 386\n",
    "choice = 0\n",
    "improvement_day = check_swap_day(data, family_id, choice)\n",
    "improvement_family, family_swap = check_swap_family(data, family_id, choice)\n",
    "improvement_day, improvement_family, family_swap"
   ]
  }
 ],
 "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.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}