{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "f78b2856-ed6f-630c-134a-3ca04fa8e4d6"
      },
      "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",
        "\n",
        "# Input data files are available in the \"../input/\" directory.\n",
        "# For example, running this (by clicking run or pressing Shift+Enter) will list the files in the input directory\n",
        "\n",
        "from subprocess import check_output\n",
        "print(check_output([\"ls\", \"../input\"]).decode(\"utf8\"))\n",
        "\n",
        "def distance(a, b):\n",
        "    \"Calculates the Levenshtein distance between a and b.\"\n",
        "    n, m = len(a), len(b)\n",
        "    if n > m:\n",
        "        # Make sure n <= m, to use O(min(n,m)) space\n",
        "        a, b = b, a\n",
        "        n, m = m, n\n",
        "\n",
        "    current_row = range(n+1) # Keep current and previous row, not entire matrix\n",
        "    for i in range(1, m+1):\n",
        "        previous_row, current_row = current_row, [i]+[0]*n\n",
        "        for j in range(1,n+1):\n",
        "            add, delete, change = previous_row[j]+1, current_row[j-1]+1, previous_row[j-1]\n",
        "            if a[j-1] != b[i-1]:\n",
        "                change += 1\n",
        "            current_row[j] = min(add, delete, change)\n",
        "\n",
        "    return current_row[n]\n",
        "\n",
        "df = pd.read_csv('../input/train.csv')\n",
        "for row in df.itertuples():\n",
        "    if row[6] != 0:\n",
        "        d = distance(row[4], row[5])\n",
        "        ml = max(len(row[4]), len(row[5]))\n",
        "     \n",
        "        print(row[0], row[4], '|', row[5], row[6], 1-d/ml)\n",
        "# Any results you write to the current directory are saved as output."
      ]
    }
  ],
  "metadata": {
    "_change_revision": 0,
    "_is_fork": false,
    "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.6.0"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}