top-10-with-first-genetic-algorithm-on-gpu.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.021841,
     "end_time": "2020-11-29T22:21:32.572218",
     "exception": false,
     "start_time": "2020-11-29T22:21:32.550377",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Top 10 Position with First Genetic Algorithm on GPU! 🔥\n",
    "\n",
    "\n",
    "## How I came up with this solution?\n",
    "\n",
    "For the Kaggle [Conway's Reverse Game of Life 2020](https://www.kaggle.com/c/conways-reverse-game-of-life-2020/overview) competition, I tried many approaches and I also wanted to try something new for me: **Genetic Algorithm**. \n",
    "\n",
    "I looked up existing Kaggle notebooks using Genetic Algorithm, but none of them were using a GPU accelerator (sorry if I am wrong and missed one). It puzzled me as the GPU is faster than the CPU. I told myself \"challenge accepted, let's make a genetic algorithm on the GPU!\".\n",
    "\n",
    "Implementing this genetic algorithm from scratch was tought but I learned a lot in the process about genetic algorithm (first purpose), but also on `pytorch` and how to optimize using `NVIDIA Nsight`.\n",
    "\n",
    "\n",
    "## Results\n",
    "\n",
    "This solution performed very well during this competition as this present notebook alone [scores in the top-10 leaderboard](https://www.kaggle.com/c/conways-reverse-game-of-life-2020/leaderboard). This new approach helped improving final solution of our team `Under a Penny`.\n",
    "\n",
    "I noticed the algorithm is running faster on RTX-2080 than Kaggle's P-100, probably thanks to the newer version of tensor-cores.\n",
    "\n",
    "\n",
    "## Requirements\n",
    "\n",
    "All we need are :\n",
    "\n",
    " - `pytorch` to implement the Genetic Algorithm on GPU\n",
    " - `pandas` to load and write .csv files\n",
    "\n",
    "## Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:32.617812Z",
     "iopub.status.busy": "2020-11-29T22:21:32.617068Z",
     "iopub.status.idle": "2020-11-29T22:21:33.906376Z",
     "shell.execute_reply": "2020-11-29T22:21:33.905215Z"
    },
    "papermill": {
     "duration": 1.314073,
     "end_time": "2020-11-29T22:21:33.906515",
     "exception": false,
     "start_time": "2020-11-29T22:21:32.592442",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "import time\n",
    "import pandas as pd\n",
    "import torch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:33.962007Z",
     "iopub.status.busy": "2020-11-29T22:21:33.961123Z",
     "iopub.status.idle": "2020-11-29T22:21:33.964027Z",
     "shell.execute_reply": "2020-11-29T22:21:33.963533Z"
    },
    "papermill": {
     "duration": 0.029858,
     "end_time": "2020-11-29T22:21:33.964129",
     "exception": false,
     "start_time": "2020-11-29T22:21:33.934271",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "torch.backends.cudnn.benchmark = True\n",
    "torch.backends.cudnn.deterministic = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.021032,
     "end_time": "2020-11-29T22:21:34.005598",
     "exception": false,
     "start_time": "2020-11-29T22:21:33.984566",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Constants"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:34.053498Z",
     "iopub.status.busy": "2020-11-29T22:21:34.052561Z",
     "iopub.status.idle": "2020-11-29T22:21:34.056259Z",
     "shell.execute_reply": "2020-11-29T22:21:34.056897Z"
    },
    "papermill": {
     "duration": 0.030442,
     "end_time": "2020-11-29T22:21:34.057067",
     "exception": false,
     "start_time": "2020-11-29T22:21:34.026625",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "N = 25  # grid dimension\n",
    "device = 'cuda'\n",
    "TEST_CSV = '../input/conways-reverse-game-of-life-2020/test.csv'\n",
    "OUTPUT_CSV = 'submission.csv'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.020918,
     "end_time": "2020-11-29T22:21:34.099370",
     "exception": false,
     "start_time": "2020-11-29T22:21:34.078452",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Apply Game Of Life steps\n",
    "\n",
    "`forward` : applies Game Of Life rules `delta` times on a board of cells (`grid`).\n",
    "\n",
    "The rules are simple and are defined in the [Kaggle competition description](https://www.kaggle.com/c/conways-reverse-game-of-life-2020/overview/description):\n",
    "\n",
    "> The Game of Life is a cellular automaton created by mathematician John Conway in 1970. The game consists of a board of cells that are either on or off. One creates an initial configuration of these on/off states and observes how it evolves. There are four simple rules to determine the next state of the game board, given the current state:\n",
    ">\n",
    ">    - *Overpopulation*: if a living cell is surrounded by more than three living cells, it dies.\n",
    ">    - *Stasis*: if a living cell is surrounded by two or three living cells, it survives.\n",
    ">    - *Underpopulation*: if a living cell is surrounded by fewer than two living cells, it dies.\n",
    ">    - *Reproduction*: if a dead cell is surrounded by exactly three cells, it becomes a live cell.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:34.151813Z",
     "iopub.status.busy": "2020-11-29T22:21:34.151151Z",
     "iopub.status.idle": "2020-11-29T22:21:39.000812Z",
     "shell.execute_reply": "2020-11-29T22:21:39.000135Z"
    },
    "papermill": {
     "duration": 4.880903,
     "end_time": "2020-11-29T22:21:39.000963",
     "exception": false,
     "start_time": "2020-11-29T22:21:34.120060",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "cv = torch.nn.Conv2d(1, 1, kernel_size=3, padding=1, padding_mode='circular', bias=False)\n",
    "cv.requires_grad=False\n",
    "cv.weight = torch.nn.Parameter(\n",
    "    torch.tensor(\n",
    "        [[[[ 1., 1., 1.],\n",
    "           [ 1., 0., 1.],\n",
    "           [ 1., 1., 1.]]]],\n",
    "        device=device,\n",
    "        dtype=torch.float16\n",
    "    ),\n",
    "    requires_grad=False,\n",
    ")\n",
    "\n",
    "\n",
    "@torch.jit.script\n",
    "def forward(grid, delta: int):\n",
    "    N=25\n",
    "    g = grid.reshape(-1, 1, N, N)\n",
    "    for _ in torch.arange(delta):\n",
    "        g = g.to(torch.float16)\n",
    "        neighbor_sum = cv(g)\n",
    "        g = ((neighbor_sum == 3) | ((g == 1) & (neighbor_sum == 2)))\n",
    "    return g.reshape(-1, N, N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.02181,
     "end_time": "2020-11-29T22:21:39.043862",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.022052",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Genetic algorithm\n",
    "\n",
    "I highly suggest to read [How the Genetic Algorithm works](https://www.mathworks.com/help/gads/how-the-genetic-algorithm-works.html) webpage as it explains many concepts mentionned in following sections of this notebook.\n",
    "\n",
    "`random_parents` : create a random initial population made of `n_parents` NxN grids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:39.096060Z",
     "iopub.status.busy": "2020-11-29T22:21:39.094445Z",
     "iopub.status.idle": "2020-11-29T22:21:39.097201Z",
     "shell.execute_reply": "2020-11-29T22:21:39.097692Z"
    },
    "papermill": {
     "duration": 0.032181,
     "end_time": "2020-11-29T22:21:39.097812",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.065631",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "@torch.jit.script\n",
    "def random_parents(n_parents: int, device: str):\n",
    "    N = 25\n",
    "    RANDOM_ALIVE = .2\n",
    "    return torch.rand((n_parents, N, N), device=device) > (1-RANDOM_ALIVE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.021408,
     "end_time": "2020-11-29T22:21:39.140927",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.119519",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "`select_best`: Scores each member of the current population `parents` by computing its fitness value. For this competition, the fitness value is the number of errors between a `target` and a population individual after applying `delta` time the Game Of Live rules. The functions returns the `n_best` best performing individuals."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:39.192019Z",
     "iopub.status.busy": "2020-11-29T22:21:39.190196Z",
     "iopub.status.idle": "2020-11-29T22:21:39.192660Z",
     "shell.execute_reply": "2020-11-29T22:21:39.193250Z"
    },
    "papermill": {
     "duration": 0.030711,
     "end_time": "2020-11-29T22:21:39.193374",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.162663",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "@torch.jit.script\n",
    "def loss(input, target):\n",
    "    return torch.sum(input ^ target, dim=(-1,-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:39.247806Z",
     "iopub.status.busy": "2020-11-29T22:21:39.246024Z",
     "iopub.status.idle": "2020-11-29T22:21:39.248521Z",
     "shell.execute_reply": "2020-11-29T22:21:39.249037Z"
    },
    "papermill": {
     "duration": 0.034283,
     "end_time": "2020-11-29T22:21:39.249242",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.214959",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "@torch.jit.script\n",
    "def select_best(parents, delta: int, target, n_best: int):\n",
    "    scores = loss(forward(parents, delta), target)\n",
    "    best_values, best_indices = torch.topk(scores, n_best, dim=0, largest=False, sorted=True)\n",
    "    new_parents = parents[best_indices, ...]\n",
    "    return new_parents, best_values[0], new_parents[0, ...]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.021318,
     "end_time": "2020-11-29T22:21:39.291988",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.270670",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "`random_combine`: combining the vector entries of a pair of parents. It is also called _crossover_."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:39.351525Z",
     "iopub.status.busy": "2020-11-29T22:21:39.349675Z",
     "iopub.status.idle": "2020-11-29T22:21:39.352181Z",
     "shell.execute_reply": "2020-11-29T22:21:39.352634Z"
    },
    "papermill": {
     "duration": 0.039219,
     "end_time": "2020-11-29T22:21:39.352754",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.313535",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "@torch.jit.script\n",
    "def random_combine(parents, n_offsprings: int, device: str, pre_masks):\n",
    "    N = 25\n",
    "    \n",
    "    dads = torch.randint(low=0, high=parents.shape[0], size=(n_offsprings,),\n",
    "                         device=device, dtype=torch.long)\n",
    "    dads = parents[dads, ...]\n",
    "    \n",
    "    moms = torch.randint(low=0, high=parents.shape[0], size=(n_offsprings,),\n",
    "                         device=device, dtype=torch.long)\n",
    "    moms = parents[moms, ...]\n",
    "    \n",
    "    masks = pre_masks[torch.randint(low=0, high=pre_masks.shape[0], size=(n_offsprings,),\n",
    "                                    device=device, dtype=torch.long)]\n",
    "\n",
    "    return torch.where(masks, dads, moms)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.021691,
     "end_time": "2020-11-29T22:21:39.396270",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.374579",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "`precomputes_masks`: pre-computes masked used for combining the vector entries of a pair of parents in `random_combine`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:39.451476Z",
     "iopub.status.busy": "2020-11-29T22:21:39.449711Z",
     "iopub.status.idle": "2020-11-29T22:21:39.452244Z",
     "shell.execute_reply": "2020-11-29T22:21:39.452724Z"
    },
    "papermill": {
     "duration": 0.034848,
     "end_time": "2020-11-29T22:21:39.452836",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.417988",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def precomputes_masks():\n",
    "    N = 25\n",
    "    BLOCK_SIZE = 17\n",
    "\n",
    "    block = torch.nn.Conv2d(1, 1, kernel_size=BLOCK_SIZE, padding=BLOCK_SIZE//2,\n",
    "                            padding_mode='circular', bias=False)\n",
    "    block.requires_grad=False\n",
    "    block.weight = torch.nn.Parameter(\n",
    "        torch.ones((1, 1, BLOCK_SIZE, BLOCK_SIZE),\n",
    "            device=device,\n",
    "            dtype=torch.float16\n",
    "        ),\n",
    "        requires_grad=False,\n",
    "    )\n",
    "\n",
    "    masks = torch.zeros((N * N, 1, N, N), device=device, dtype=torch.float16)\n",
    "    \n",
    "    for x in range(N):\n",
    "        for y in range(N):\n",
    "            masks[x * N + y, 0, x, y] = 1.\n",
    "    masks = block(masks)\n",
    "    \n",
    "    return masks[:, 0, ...] > .5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.021105,
     "end_time": "2020-11-29T22:21:39.497010",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.475905",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "`mutate`: makes random changes on parents."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:39.549262Z",
     "iopub.status.busy": "2020-11-29T22:21:39.547475Z",
     "iopub.status.idle": "2020-11-29T22:21:39.549930Z",
     "shell.execute_reply": "2020-11-29T22:21:39.550387Z"
    },
    "papermill": {
     "duration": 0.032154,
     "end_time": "2020-11-29T22:21:39.550496",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.518342",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "@torch.jit.script\n",
    "def mutate(parents, device: str):\n",
    "    MUTATION = .0016  # .005 \n",
    "    mutations = torch.rand(parents.shape, device=device) < MUTATION\n",
    "    return parents ^ mutations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.02221,
     "end_time": "2020-11-29T22:21:39.595184",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.572974",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "`optimize_one_puzzle`: runs our genetic algorithm on one puzzle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:39.653209Z",
     "iopub.status.busy": "2020-11-29T22:21:39.652267Z",
     "iopub.status.idle": "2020-11-29T22:21:39.661594Z",
     "shell.execute_reply": "2020-11-29T22:21:39.661087Z"
    },
    "papermill": {
     "duration": 0.044019,
     "end_time": "2020-11-29T22:21:39.661702",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.617683",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "@torch.jit.script\n",
    "def optimize_one_puzzle(delta: int, data, device: str, pre_masks):\n",
    "    N = 25\n",
    "    N_GENERATION = 30  # Number of generations\n",
    "    P = 4_500  # population\n",
    "    N_BEST = P // 30  # best to keep as new parents\n",
    "    N_ELITES = 8  # parents unchanged for next generation\n",
    "    \n",
    "    best_score = torch.tensor([N*N], device=device)\n",
    "    best = torch.zeros((N,N), device=device).to(torch.bool)\n",
    "    parents = random_parents(P, device)\n",
    "\n",
    "    elites = torch.empty((1, N, N), dtype=torch.bool, device=device)\n",
    "    elites[0, ...] = data  # set target as potential dad ;)\n",
    "\n",
    "    for i in range(N_GENERATION):\n",
    "        parents = random_combine(parents, P, device, pre_masks)\n",
    "        parents = mutate(parents, device)\n",
    "        parents[:N_ELITES, ...] = elites\n",
    "        parents, best_score, best = select_best(parents, delta, data, N_BEST)\n",
    "        # Some of the individuals in the current population that have lower fitness are chosen as elite.\n",
    "        # These elite individuals are passed to the next population.\n",
    "        elites = parents[:N_ELITES, ...]\n",
    "        if best_score == 0:  # early stopping\n",
    "            break\n",
    "\n",
    "    return best_score, best"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.022839,
     "end_time": "2020-11-29T22:21:39.707286",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.684447",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "`optimize_all_puzzles`: It tries to find approximate solution for all puzzles 😃"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:39.765672Z",
     "iopub.status.busy": "2020-11-29T22:21:39.764685Z",
     "iopub.status.idle": "2020-11-29T22:21:39.768350Z",
     "shell.execute_reply": "2020-11-29T22:21:39.768781Z"
    },
    "papermill": {
     "duration": 0.038366,
     "end_time": "2020-11-29T22:21:39.768931",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.730565",
     "status": "completed"
    },
    "scrolled": false,
    "tags": []
   },
   "outputs": [],
   "source": [
    "@torch.jit.script\n",
    "def optimize_all_puzzles(deltas, df, device: str, pre_masks):\n",
    "    sub = df.clone()\n",
    "    \n",
    "    for n in torch.arange(df.shape[0]):\n",
    "        delta = deltas[n]\n",
    "        data = df[n, ...]\n",
    "        _, sub[n, ...] = optimize_one_puzzle(delta, data, device, pre_masks)\n",
    "\n",
    "    return sub"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.025511,
     "end_time": "2020-11-29T22:21:39.819964",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.794453",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Load Puzzles to solve"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:39.879055Z",
     "iopub.status.busy": "2020-11-29T22:21:39.878272Z",
     "iopub.status.idle": "2020-11-29T22:21:42.593142Z",
     "shell.execute_reply": "2020-11-29T22:21:42.592215Z"
    },
    "papermill": {
     "duration": 2.747579,
     "end_time": "2020-11-29T22:21:42.593280",
     "exception": false,
     "start_time": "2020-11-29T22:21:39.845701",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "df = pd.read_csv(TEST_CSV, index_col='id')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.022908,
     "end_time": "2020-11-29T22:21:42.639727",
     "exception": false,
     "start_time": "2020-11-29T22:21:42.616819",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Use final state as our baseline for submission"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:42.691957Z",
     "iopub.status.busy": "2020-11-29T22:21:42.690592Z",
     "iopub.status.idle": "2020-11-29T22:21:42.859711Z",
     "shell.execute_reply": "2020-11-29T22:21:42.859058Z"
    },
    "papermill": {
     "duration": 0.196825,
     "end_time": "2020-11-29T22:21:42.859835",
     "exception": false,
     "start_time": "2020-11-29T22:21:42.663010",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "submission = df.copy()\n",
    "submission.drop(['delta'], inplace=True, axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.02317,
     "end_time": "2020-11-29T22:21:42.906886",
     "exception": false,
     "start_time": "2020-11-29T22:21:42.883716",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Push data to GPU"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:42.960304Z",
     "iopub.status.busy": "2020-11-29T22:21:42.959694Z",
     "iopub.status.idle": "2020-11-29T22:21:42.997797Z",
     "shell.execute_reply": "2020-11-29T22:21:42.997280Z"
    },
    "papermill": {
     "duration": 0.06747,
     "end_time": "2020-11-29T22:21:42.997926",
     "exception": false,
     "start_time": "2020-11-29T22:21:42.930456",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "indexes = df.index\n",
    "deltas = torch.from_numpy(df.delta.values).to(device)\n",
    "df = torch.BoolTensor(df.values[:, 1:].reshape((-1, N, N))).to(device)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.023889,
     "end_time": "2020-11-29T22:21:43.045952",
     "exception": false,
     "start_time": "2020-11-29T22:21:43.022063",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Let's optimize puzzles!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-29T22:21:43.100410Z",
     "iopub.status.busy": "2020-11-29T22:21:43.099783Z",
     "iopub.status.idle": "2020-11-30T00:20:30.723285Z",
     "shell.execute_reply": "2020-11-30T00:20:30.724025Z"
    },
    "papermill": {
     "duration": 7127.654651,
     "end_time": "2020-11-30T00:20:30.724251",
     "exception": false,
     "start_time": "2020-11-29T22:21:43.069600",
     "status": "completed"
    },
    "scrolled": false,
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Processed 50,000 puzzles in 7127.60 seconds 🔥🔥🔥\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "pre_masks = precomputes_masks()\n",
    "sub = optimize_all_puzzles(deltas, df, device, pre_masks)\n",
    "print(f'Processed {sub.shape[0]:,} puzzles in {time.time() - start_time:.2f} seconds 🔥🔥🔥')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.03799,
     "end_time": "2020-11-30T00:20:30.799089",
     "exception": false,
     "start_time": "2020-11-30T00:20:30.761099",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Save our submission"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-30T00:20:30.899270Z",
     "iopub.status.busy": "2020-11-30T00:20:30.897022Z",
     "iopub.status.idle": "2020-11-30T00:20:38.236466Z",
     "shell.execute_reply": "2020-11-30T00:20:38.235371Z"
    },
    "papermill": {
     "duration": 7.397382,
     "end_time": "2020-11-30T00:20:38.236635",
     "exception": false,
     "start_time": "2020-11-30T00:20:30.839253",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "submission.rename(columns={f'stop_{x}': f'start_{x}' for x in range(N*N)}, inplace=True)\n",
    "submission.iloc[:sub.shape[0], :] = sub.reshape((-1, N*N)).cpu().numpy().astype(int)\n",
    "submission.to_csv(OUTPUT_CSV)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.027658,
     "end_time": "2020-11-30T00:20:38.293283",
     "exception": false,
     "start_time": "2020-11-30T00:20:38.265625",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Compute leaderboard score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-30T00:20:38.357582Z",
     "iopub.status.busy": "2020-11-30T00:20:38.356820Z",
     "iopub.status.idle": "2020-11-30T00:20:38.361467Z",
     "shell.execute_reply": "2020-11-30T00:20:38.360968Z"
    },
    "papermill": {
     "duration": 0.041419,
     "end_time": "2020-11-30T00:20:38.361593",
     "exception": false,
     "start_time": "2020-11-30T00:20:38.320174",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def leaderboard_score(deltas, df, sub, device: str):\n",
    "    result = torch.empty(sub.shape[0], device=device, dtype=torch.long)\n",
    "    for delta in range(1, 6):\n",
    "        start = sub[deltas == delta]\n",
    "        end   = df[deltas == delta]\n",
    "        result[deltas == delta] = loss(forward(start, delta), end)\n",
    "    print('Leaderboard score:', torch.sum(result).item() / (result.shape[0]*N*N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-11-30T00:20:38.423812Z",
     "iopub.status.busy": "2020-11-30T00:20:38.422924Z",
     "iopub.status.idle": "2020-11-30T00:20:38.683368Z",
     "shell.execute_reply": "2020-11-30T00:20:38.684056Z"
    },
    "papermill": {
     "duration": 0.294809,
     "end_time": "2020-11-30T00:20:38.684217",
     "exception": false,
     "start_time": "2020-11-30T00:20:38.389408",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Leaderboard score: 0.054160928\n"
     ]
    }
   ],
   "source": [
    "leaderboard_score(deltas, df, sub, device)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "papermill": {
     "duration": 0.027573,
     "end_time": "2020-11-30T00:20:38.739531",
     "exception": false,
     "start_time": "2020-11-30T00:20:38.711958",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Conclusion\n",
    "\n",
    "I learned a lot along the way about Genetic Algorithm, pytorch and how to optimize computation on the GPU.\n",
    "\n",
    "If you like this notebook, please leave a comment 🖊, upvote 👍, and put a smile on your face 😀."
   ]
  }
 ],
 "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.6"
  },
  "papermill": {
   "duration": 7151.832825,
   "end_time": "2020-11-30T00:20:40.069450",
   "environment_variables": {},
   "exception": null,
   "input_path": "__notebook__.ipynb",
   "output_path": "__notebook__.ipynb",
   "parameters": {},
   "start_time": "2020-11-29T22:21:28.236625",
   "version": "2.1.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}