Knight's_Dialer_Performance_Profiling.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Knight's Dialer Performance Profiling",
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/SandersAaronD/Knights_Dialer_Profiler/blob/main/Knight's_Dialer_Performance_Profiling.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RfAoboQ3iG6B"
      },
      "source": [
        "## The Knight's Dialer\n",
        "\n",
        "The Knight's Dialer is an old Google interview question. Details can be found [here.](https://alexgolec.dev/google-interview-questions-deconstructed-the-knights-dialer/)\n",
        "\n",
        "If you want to understand it read the article, this notebook is entirely for determining empirically what the runtimes of the various solutions are. I'll also profile the python @cache decorator and numpy for this problem.\n",
        "\n",
        "All of this was originally run on Colaboratory, your mileage may vary depending on how your hardware differs from theirs. You will want to set different upper bounds probably, and your cache might behave differently, and so on, and so on, and so on."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0b3SukjjizPK"
      },
      "source": [
        "%matplotlib inline\n",
        "import matplotlib.pyplot as plt\n",
        "import time\n",
        "import numpy as np\n",
        "\n",
        "plt.style.use('seaborn-whitegrid')"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "So_XbGnHiaDK"
      },
      "source": [
        "def profile(fn, args_lists):\n",
        "  \"\"\"Profiles input function fn for performance against several sets of arguments and returns a list of runtimes.\n",
        "  \"\"\"\n",
        "  times = []\n",
        "  for args_list in args_lists:\n",
        "    tik = time.time()\n",
        "    y = fn(*args_list)\n",
        "    tok = time.time()\n",
        "    times.append(tok-tik)\n",
        "  \n",
        "  return times"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "InoeG-kvPiok"
      },
      "source": [
        "def make_dialer_profile_graph(fn, upper_bound):\r\n",
        "  '''Specific to the knight's dialer, runs the function for all values up to the upper_bound and graphs it.\r\n",
        "  '''\r\n",
        "  num_hops = list(range(1, upper_bound))\r\n",
        "  starting_positions = [1 for _ in range(1, upper_bound)]\r\n",
        "  args_lists = zip(starting_positions, num_hops)\r\n",
        "  times = profile(fn, args_lists)\r\n",
        "  plt.plot(num_hops, times, 'o', color='black')"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HADEafWMk9-4"
      },
      "source": [
        "# Necessary for other knight's dialer functions to run.\n",
        "NEIGHBORS_MAP = {\n",
        "    1: (6, 8),\n",
        "    2: (7, 9),\n",
        "    3: (4, 8),\n",
        "    4: (3, 9, 0),\n",
        "    5: tuple(),  # 5 has no neighbors\n",
        "    6: (1, 7, 0),\n",
        "    7: (2, 6),\n",
        "    8: (1, 3),\n",
        "    9: (2, 4),\n",
        "    0: (4, 6),\n",
        "}\n",
        "def neighbors(position):\n",
        "    return NEIGHBORS_MAP[position]"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qrsGNuRtlFFZ"
      },
      "source": [
        "# Naive solution, brute force, basically.\n",
        "def yield_sequences(starting_position, num_hops, sequence=None):\n",
        "    if sequence is None:\n",
        "        sequence = [starting_position]\n",
        "    \n",
        "    if num_hops == 0:\n",
        "        yield sequence\n",
        "        return\n",
        "\n",
        "    for neighbor in neighbors(starting_position):\n",
        "        yield from yield_sequences(\n",
        "            neighbor, num_hops - 1, sequence + [neighbor])\n",
        "\n",
        "def count_sequences(starting_position, num_hops):\n",
        "    num_sequences = 0\n",
        "    for sequence in yield_sequences(starting_position, num_hops):\n",
        "        num_sequences += 1\n",
        "    return num_sequences"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "unC4mF6tn4OQ",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 262
        },
        "outputId": "79f86f48-0187-4e8e-95fe-7bca8c67d2da"
      },
      "source": [
        "# Choosing an upper bound higher than 16 for this function took an annoyingly long time to run.\n",
        "make_dialer_profile_graph(count_sequences, 16)"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD1CAYAAABA+A6aAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAS0klEQVR4nO3dcYykd13H8fceFeqCNQWFo01vN4XOl+1hjHcQORFKbQVUSBM8wh+DpJFmta2ExBBTWBGLbhBPcgr4B/sHoNwW24qtRSkcIBTIlVAmoUE6fi0E9qR3yAmxLaxLoTf+sbPt3PR2dnZvZmeeX9+v5NKZ3/P8nvl0kv3cc7955tmJVquFJKn6dow6gCRpMCx0SSqEhS5JhbDQJakQFrokFcJCl6RCnDWqF240Gl4vKUlbsHfv3onTjY+s0AH27t07ypd/jGazyczMzKhj9K1KeauUFaqVt0pZoVp5xzFro9FYd5tLLpJUCAtdkgphoUtSISx0SSqEhS5JhbDQJWmbLC4uMj09zY4dO5ienmZxcXGgxx/pZYuS9HixuLjI7Owsy8vLACwtLTE7OwtAvV4fyGt4hi5J22Bubu6RMl+zvLzM3NzcwF7DQpekbXD06NFNjW+FhS5J22DXrl2bGt8KC12StsH8/DyTk5OnjE1OTjI/Pz+w17DQJWkb1Ot1FhYWmJqaYmJigqmpKRYWFgb2gSh4lYskbZt6vT7QAu/mGbokFcJCl6RCWOiSVAgLXZIKYaFLUiEsdEkqhIUuSYWw0CWpEBa6JBXCQpekQljoklQIC12SCmGhS1Ih+rrbYkQcBF4AtIA3ZuZdHdsuBd4BPAwkcBXwYuBm4Gvt3b6amW8YYG5JUpcNCz0iLgEuysx9ETEDvB/Y17HLAnBpZn47Im4GXg4sA3dk5v5hhJYkPVY/Sy6XAbcCZGYTODcizunYvjczv91+fAJ42mAjSpL60c+Sy06g0fH8RHvsAYDMfAAgIp4JvBR4K/ALwMURcRvwVOD6zPxk94GbzeYZhR+0lZWVscvUS5XyVikrVCtvlbJCtfJWKSts7TcWTXQPRMTTgY8C12Tm9yLiXuB64CbgQuAzEfHszHyoc97MzMwWXn54ms3m2GXqpUp5q5QVqpW3SlmhWnnHMWuj0Vh3Wz+FfozVM/I15wHH1560l19uB+Yy8zBAZt4H3Nje5RsR8R3gfOCbm0ouSepbP2voh4H9ABGxBziWmQ92bH8XcDAzP742EBH1iHhT+/FO4BnAfQNLLUl6jA3P0DPzSEQ0IuIIcBK4NiKuBO4HPgG8DrgoIq5qT7kB+DBwQ0RcATwRuLp7uUWSNFh9raFn5nVdQ3d3PH7SOtNeuaVEkqQt8ZuiklQIC12SCmGhS1IhLHRJKoSFLkmFsNAlqRAWuiQVwkKXpEJY6JJUCAtdkgphoUtSISx0SSqEhS5JhbDQJakQFrokFcJCl6RCWOiSVAgLXZIKYaFLUiEsdEkqhIUuSYWw0CWpEBa6JBXCQpekQljoklQIC12SCnFWPztFxEHgBUALeGNm3tWx7VLgHcDDQAJXZebJXnMkSYO34Rl6RFwCXJSZ+4DXA+/u2mUB2J+ZLwR+Bnh5H3MkSQPWz5LLZcCtAJnZBM6NiHM6tu/NzG+3H58AntbHHEnSgPVT6DtZLeo1J9pjAGTmAwAR8UzgpcDHNpojSRq8vtbQu0x0D0TE04GPAtdk5vciYsM5AM1mcwsvPzwrKytjl6mXKuWtUlaoVt4qZYVq5a1SVuiv0I9x6tn1ecDxtSftpZTbgbnMPNzPnDUzMzObzTtUzWZz7DL1UqW8VcoK1cpbpaxQrbzjmLXRaKy7rZ8ll8PAfoCI2AMcy8wHO7a/CziYmR/fxBxJ0oBteIaemUciohERR4CTwLURcSVwP/AJ4HXARRFxVXvKDZm50D1nOPElSWv6WkPPzOu6hu7uePykPudIkobIb4pKUiEsdEkqhIUuSYWw0CWpEBa6JBXCQpekQljoklQIC12SCmGhS1IhLHRJKoSFLkmFsNAlqRAWuiQVwkKXpEJY6JJUCAtdkgphoUtSISx0SSqEhS5JhbDQJakQFrokFcJCl6RCWOiSVAgLXZIKYaFLUiEsdEkqxFn97BQRB4EXAC3gjZl5V8e2s4H3Absz83ntsZcANwNfa+/21cx8wwBzS5K6bFjoEXEJcFFm7ouIGeD9wL6OXQ4AXwF2d029IzP3DyypJKmnfpZcLgNuBcjMJnBuRJzTsf0twC1DyCZJ2oR+Cn0ncKLj+Yn2GACZ+eA68y6OiNsi4gsR8etnkFGS1Ie+1tC7TPSxz73A9cBNwIXAZyLi2Zn5UOdOzWZzCy8/PCsrK2OXqZcq5a1SVqhW3iplhWrlrVJW6K/Qj9FxRg6cBxzvNSEz7wNubD/9RkR8Bzgf+GbnfjMzM/0n3QbNZnPsMvVSpbxVygrVylulrFCtvOOYtdForLutnyWXw8B+gIjYAxzrscxCe796RLyp/Xgn8Azgvn4DS5I2b8Mz9Mw8EhGNiDgCnASujYgrgfsz85aIuBm4AIiI+CywANwG3BARVwBPBK7uXm6RJA1WX2vomXld19DdHdtevc60V241lCRp8/ymqCQVwkKXpEJY6JJUCAtdkgphoUtSISx0SSqEhS5JhbDQJakQFrokdVlcXGR6eprdu3czPT3N4uLiqCP1ZSt3W5SkYi0uLjI7O8vy8jIAS0tLzM7OAlCv10cZbUOeoUtSh7m5uUfKfM3y8jJzc3MjStQ/C12SOhw9enRT4+PEQpekDrt27drU+Dix0CWpw/z8PJOTk6eMTU5OMj8/P6JE/bPQJalDvV5nYWGBqakpJiYmmJqaYmFhYew/EAWvcpGkx6jX69Tr9bH8FXS9eIYuSYWw0CWpEBa6JBXCQpekQljoklQIC12SCmGhS1IhLHRJKoSFLkmFsNAlqRB9ffU/Ig4CLwBawBsz866ObWcD7wN2Z+bz+pkjSRq8Dc/QI+IS4KLM3Ae8Hnh31y4HgK9sco4kacD6WXK5DLgVIDObwLkRcU7H9rcAt2xyjiRpwPop9J3AiY7nJ9pjAGTmg5udI0kavK3cPndiUHOazeYWDjU8KysrY5eplyrlrVJWqFbeKmWFauWtUlbor9CPcerZ9XnA8UHMGbf7DFft3sdVylulrFCtvFXKCtXKO45ZG43Gutv6WXI5DOwHiIg9wLF1llnOdI4k6QxseIaemUciohERR4CTwLURcSVwf2beEhE3AxcAERGfBRYy84buOcP7X5AkQZ9r6Jl5XdfQ3R3bXt3nHEnSEPlNUUkqhIUuSYWw0CWpEBa6JBXCQpekQljoklQIC12SCmGhS1IhLHRJKoSFLkmFsNAlqRAWuiQVwkKXpEJY6JJUCAtdkgphoUtSISx0SSqEhS5JhbDQJakQFrokFcJCl6RCWOiSVAgLXZIKYaFLUiEsdEkqhIUuSYWw0CWpEH0VekQcjIg7I+JIRDy/a9vlEfGl9va3tsdeEhEnIuKz7T/vGUZ4SY9vi4uLTE9Ps2PHDqanp1lcXBx1pJE6a6MdIuIS4KLM3BcRM8D7gX0du7wbeBlwH3BHRHykPX5HZu4fdGBJgtUyn52dZXl5GYClpSVmZ2cBqNfro4w2Mv2coV8G3AqQmU3g3Ig4ByAiLgS+n5n/lZkngY+195ekoZqbm3ukzNcsLy8zNzc3okSjt+EZOrATaHQ8P9Eee6D93xMd274LPAv4KnBxRNwGPBW4PjM/2X3gZrO5xdjDsbKyMnaZeqlS3iplhWrlrVJWGFzeo0ePrjs+qPejau9tP4XebaKPbfcC1wM3ARcCn4mIZ2fmQ507z8zMbOHlh6fZbI5dpl6qlLdKWaFaeauUFQaXd9euXSwtLZ12fFDvxzi+t41GY91t/Sy5HGP1THzNecDxdbadDxzLzPsy88bMbGXmN4DvtLdJ0kDMz88zOTl5ytjk5CTz8/MjSjR6/RT6YWA/QETsYbWwHwTIzG8B50TEdEScBbwCOBwR9Yh4U3vOTuAZrH5oKkkDUa/XWVhYYGpqiomJCaamplhYWHjcfiAKfSy5ZOaRiGhExBHgJHBtRFwJ3J+ZtwBXAx9u735jZv5nRBwHboiIK4AnAld3L7dI0pmq1+uP6wLv1tcaemZe1zV0d8e2z3HqZYy0z+BfecbpJEl985uiklQIC12SCmGhS1IhLHRJKoSFLkmFsNAlqRAWuiQVwkKXtC3W7l2+e/du710+JFu5OZckbYr3Lt8enqFLGjrvXb49LHRJQ9fr3uUaHAtd0tDt2rVrU+PaGgtd0tB57/LtYaFLGjrvXb49vMpF0rZYu3f5OP5at1J4hi5JhbDQJakQFrokFcJCl6RCWOiSTrF2z5UdO3Z4z5WK8SoXSY/wnivV5hm6pEd4z5Vqs9ClihrG7Wi950q1WehSBa0tjSwtLdFqtR5ZGjnTUveeK9VmoUsVNKylEe+5Um0WujRkw7hqZFhLI95zpeJardaGf2q12sFarXZnrVY7UqvVnt+17fJarfal9va39jOn1Wrx5S9/ubUVhw4dak1NTbUmJiZaU1NTrUOHDm3pOMM+pscd3jGrdNxDhw61JicnW8AjfyYnJ8/4uFNTU6ccc+3P1NTUGR13O9xzzz2jjtC3ccza7s7TdnU/ZX5JrVb7l/bjmVqtdmfX9ntqtdoFtVptR61W+3ytVrt4ozmtLRb6MH44hvUD53GrlXVYxx1W8Q7rPdgO41iS6xnHrGda6G+v1WpXdTz/j1qtdk778YW1Wu0LHdveXKvV3tBrTusMCn0YPxzD+oHzuNXKOqzjTkxMnPaYExMTZ5S11Rrev1KGbRxLcj3jmLVXoffzxaKdQKPj+Yn22APt/57o2PZd4FnAz/WY84hms9nHyz+q17rhZo81zGN63OEds2rH3blzJ8ePHz/t+JlkBdizZw+33347KysrnH322cDmf6ZGYWVlpRI5oVpZYWvfFJ3YwrbTjm/2nsi7du1iaWnptONbvb/yMI7pcYd3zKod98CBA6d88xJWrxo5cODAwO4JXrX7i1cp7zhmbTQa627r5yqXY6yeXa85Dzi+zrbz22O95mzZMC6pGtZlWh63WlmHdVyvGtG2Wm8tpvXo+vev1Gq1T7Yf7+lcM2+Pfa1Wq03XarWzarXaXbVVPee0vMrlcXPcKmUd5nGHaRzXeXupUt5xzNprDX2i1WptWPoR8RfAi4GTwLXALwH3Z+YtEfFi4J3tXT+SmX91ujmZeXfnMRuNRmvv3r0D+4tpEMbxn1e9VClvlbJCtfJWKStUK+84Zm00Guzdu/e0y9h9raFn5nVdQ3d3bPscsK+POZKkIfKbopJUCAtdkgphoUtSISx0SSpEX1e5DEOj0RjNC0tSxa13lcvICl2SNFguuUhSISx0SSrEVm7OVaSI+EvgRay+J+/IzH8acaSeIuKngX8H/iwzPzjiOD1FRB34I+AnwJ9k5r+OONJpRcRTgL8HzgWeBFyfmZ8YbarHiojnAv8MHMzM90bEBcCHgCewes+k38nMH40yY6d18n4A+Cngx8BrM/M7o8y4pjtrx/jLgI9nZq+bE46cZ+hARFwKPDcz9wEvB/56xJH68cfA90cdYiMR8TTgbcCvAq8Arhhtop6uBDIzLwX2A38z2jiPFRFPBt4DfLpj+O3A32bmi4CvA787imyns07ePwcWMvMS4BbgD0eRrds6WYmIs4E3M4AbDA6bhb7qc8Cr24//F3hyRDxhhHl6iojnABcDY3mm2+Vy4FOZ+WBmHs/M2VEH6uF/gKe1H5/bfj5ufgT8Jqt3NF3zEuC29uOPsvqej4vT5b0G+Ej78Qkefc9H7XRZAd4C/C3w0LYn2iQLHcjMhzPzh+2nrwc+lpkPjzLTBt7FmJzV9GEamIyI2yLi8xFx2agDrScz/wHYFRFfZ/Uv+TeNONJjZOZPMvP/uoaf3LHE8l3gmdsca12ny5uZP8zMh9snTdcCN4wm3alOlzUiasAvZubNI4q1KRZ6h4i4gtVC/4NRZ1lPRLwOuDMzvznqLH2aYPUM7FWsLml8ICLGch0yIl4LHM3MZwO/Brx3gynjaCzf227tMv8Q8G+Z+emN9h+hg1Tn5MlCX9P+0GMO+I3MvH/UeXr4LeCKiPgicBXw1ogYp39id/tv4Ej77OcbwIPAz48403peCHwCoH275/PGeemtww/aH5LDo79kZtx9ALg3M68fdZD1RMT5wHOAxfbP2zMj4o4Rx+rJq1yAiPhZ4ABweWaO9QeNmfmatccR8afAtzLzU6NLtKHDwAcj4p2srks/hfFcm4bVDxR/GfhIREwBPxjzpbc1nwJ+GzjU/u/HRxunt/ZVTw9l5ttGnaWXzLyP1d+RDEBEfKv9Qe7YstBXvYbVX2x9U0Ssjb0uM0//W4PVt8y8LyL+Efhie+gNmXlylJl6eB/w/vZZ2FnA7484z2NExF5WP0OZBn4cEfuBOqt/af4esAT83egSnmqdvE8HViLis+3d7snMa0aT8FHrZH3VuJ/kdfKr/5JUCNfQJakQFrokFcJCl6RCWOiSVAgLXZIKYaFLUiEsdEkqhIUuSYX4f4GgrFX300oXAAAAAElFTkSuQmCC\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ue0JqtQHzB5c"
      },
      "source": [
        "Does anyone dispute that this is exponential? No? Okay, good."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3VnS-cBZtUqK"
      },
      "source": [
        "# Basically the same thing, but with recursion, and we don't store the sequences, only count them.\n",
        "def count_sequences_naive_recursion(start_position, num_hops):                  \n",
        "    if num_hops == 0:                                           \n",
        "        return 1                                                \n",
        "                                                                \n",
        "    num_sequences = 0                                           \n",
        "    for position in neighbors(start_position):                  \n",
        "        num_sequences += count_sequences(position, num_hops - 1)\n",
        "    return num_sequences   "
      ],
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 262
        },
        "id": "CwoeTRPUtjBJ",
        "outputId": "31e61331-d27d-48da-bd9f-19b1b58bbee8"
      },
      "source": [
        "make_dialer_profile_graph(count_sequences_naive_recursion, 16)"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD1CAYAAABA+A6aAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAATRElEQVR4nO3df4zkd13H8eeWCueCNbUK12u43VQ6b7ZnYrzT2PMHpRYVtaQJHvGPQdJIswpn02CIKaxgi66IJzlF/YP9A1Bui1Bra6ktnCAUyWEsk9ggHd8i4fakd5UTYimsS6E3/rGz17nt7uzs3szOfD99PpLLzXy+P+bVbe51n/vMfOc71mq1kCRV3wXDDiBJ6g8LXZIKYaFLUiEsdEkqhIUuSYWw0CWpEBcO64UbjYafl5SkLdi3b9/YWuNDK3SAffv2DfPln6bZbDI1NTXsGD2rUt4qZYVq5a1SVqhW3lHM2mg01t3mkoskFcJCl6RCWOiSVAgLXZIKYaFLUiEsdEnaJvPz80xOTnLBBRcwOTnJ/Px8X88/1I8tStIzxfz8PNPT0ywuLgKwsLDA9PQ0APV6vS+v4QxdkrbBzMzM2TJfsbi4yMzMTN9ew0KXpG1w4sSJTY1vhYUuSdtg9+7dmxrfCgtdkrbB7Ows4+Pj54yNj48zOzvbt9ew0CVpG9Trdebm5piYmGBsbIyJiQnm5ub69oYo+CkXSdo29Xq9rwW+Wk+FHhGHgauAFnBzZj7Yse0a4O3Ak0ACNwIvAe4APt/e7XOZeVMfc0uSVtmw0CPiauCKzNwfEVPAe4D9HbvMAddk5pcj4g7g5cAi8EBmHhhEaEnS0/Wyhn4tcDdAZjaBiyPioo7t+zLzy+3Hp4FL+htRktSLXgp9J8tFveJ0ewyAzPw6QERcCvwccF9705URcU9EfDoifrZPeSVJ69jKm6JPu/VRRDwf+DDw+sz8akR8AbgN+BBwOfCJiHhRZj7ReVyz2dzCyw/O0tLSyGXqpkp5q5QVqpW3SlmhWnmrlBV6K/STdMzIgV3AqZUn7eWX+4GZzDwKkJmPAB9s7/LFiHgUuAz4UueJR+3WTqN4u6luqpS3SlmhWnmrlBWqlXcUs57vLeiOAgcAImIvcDIzH+/Y/k7gcGZ+ZGUgIuoR8cb2453AC4BHNh9dktSrDWfomXksIhoRcQw4AxyMiBuAx4CPAq8BroiIG9uH3A58ALg9Iq4Hng28bvVyiySpv3paQ8/MW1YNPdTx+DnrHPaKLSWSJG2Jl/5LUiEsdEkqhIUuSYWw0CWpEBa6JBXCQpekQljoklQIC12SCmGhS1IhLHRJKoSFLkmFsNAlqRAWuiQVwkKXpEJY6JJUCAtdkgphoUtSISx0SSqEhS5JhbDQJakQFrokFcJCl6RCWOiSVAgLXZIKYaFLUiEsdEkqhIUuSYWw0CWpEBa6JBXiwl52iojDwFVAC7g5Mx/s2HYN8HbgSSCBGzPzTLdjJEn9t+EMPSKuBq7IzP3Aa4F3rdplDjiQmT8JfA/w8h6OkST1WS9LLtcCdwNkZhO4OCIu6ti+LzO/3H58Grikh2MkSX3WS6HvZLmoV5xujwGQmV8HiIhLgZ8D7tvoGElS//W0hr7K2OqBiHg+8GHg9Zn51YjY8BiAZrO5hZcfnKWlpZHL1E2V8lYpK1Qrb5WyQrXyVikr9FboJzl3dr0LOLXypL2Ucj8wk5lHezlmxdTU1GbzDlSz2Ry5TN1UKW+VskK18lYpK1Qr7yhmbTQa627rZcnlKHAAICL2Aicz8/GO7e8EDmfmRzZxjCSpzzacoWfmsYhoRMQx4AxwMCJuAB4DPgq8BrgiIm5sH3J7Zs6tPmYw8SVJK3paQ8/MW1YNPdTx+Dk9HiNJGiCvFJWkQljoklQIC12SCmGhS1IhLHRJKoSFLkmFsNAlqRAWuiQVwkKXpEJY6JJUCAtdkgphoUtSISx0SSqEhS5JhbDQJakQFrokFcJCl6RCWOiSVAgLXZIKYaFLUiEsdEkqhIUuSYWw0CWpEBa6JBXCQpekQljoklQIC12SCmGhS1IhLHRJKsSFvewUEYeBq4AWcHNmPtixbQfwbmBPZv5oe+ylwB3A59u7fS4zb+pjbknSKhsWekRcDVyRmfsjYgp4D7C/Y5dDwL8Ce1Yd+kBmHuhbUklSV70suVwL3A2QmU3g4oi4qGP7m4G7BpBNkrQJvSy57AQaHc9Pt8e+DpCZj0fEJWscd2VE3AN8H3BbZv7D6h2azebmEw/Q0tLSyGXqpkp5q5QVqpW3SlmhWnmrlBV6XENfZayHfb4A3AZ8CLgc+EREvCgzn+jcaWpqagsvPzjNZnPkMnVTpbxVygrVylulrFCtvKOYtdForLutl0I/yfKMfMUu4FS3AzLzEeCD7adfjIhHgcuAL/XwepKkLehlDf0ocAAgIvYCJzPz8W4HREQ9It7YfrwTeAHwyHlmlSR1seEMPTOPRUQjIo4BZ4CDEXED8Fhm3hURdwAvBCIiPgnMAfcAt0fE9cCzgdetXm6RJPVXT2vomXnLqqGHOra9ap3DXrHVUJKkzfNKUUkqhIUuSYWw0CWpEBa6JBXCQpekQljoklQIC12SCmGhS1IhLHRJKoSFLkmFsNAlqRAWuiQVwkKXpEJY6JJUCAtdkgphoUtSISx0SVplfn6eyclJ9uzZw+TkJPPz88OO1JOe7lgkSc8U8/PzTE9Ps7i4CMDCwgLT09MA1Ov1YUbbkDN0SeowMzNztsxXLC4uMjMzM6REvbPQJanDiRMnNjU+Six0Seqwe/fuTY2PEgtdkjrMzs4yPj5+ztj4+Dizs7NDStQ7C12SOtTrdebm5piYmGBsbIyJiQnm5uZG/g1R8FMukvQ09Xqder1Os9lkampq2HF65gxdkgphoUtSISx0SSqEhS5JhejpTdGIOAxcBbSAmzPzwY5tO4B3A3sy80d7OUaS1H8bztAj4mrgiszcD7wWeNeqXQ4B/7rJYyRJfdbLksu1wN0AmdkELo6Iizq2vxm4a5PHSJL6rJdC3wmc7nh+uj0GQGY+vtljJEn9t5ULi8b6dUyz2dzCqQZnaWlp5DJ1U6W8VcoK1cpbpaxQrbxVygq9FfpJzp1d7wJO9eOYUbsCq2pXhVUpb5WyQrXyVikrVCvvKGZtNBrrbutlyeUocAAgIvYCJ9dZZjnfYyRJ52HDGXpmHouIRkQcA84AByPiBuCxzLwrIu4AXghERHwSmMvM21cfM7j/BEkS9LiGnpm3rBp6qGPbq3o8RpI0QF4pKkmFsNAlqRAWuiQVwkKXpEJY6JJUCAtdkgphoUtSISx0SSqEhS5JhbDQJakQFrokFcJCl6RCWOiSVAgLXZIKYaFLUiEsdEkqhIUuSYWw0CWpEBa6JBXCQpekQljoklQIC12SCmGhS1IhLHRJKoSFLkmFsNAlqRAWuiQVwkKXpEJY6JJUiAt72SkiDgNXAS3g5sx8sGPby4A/AJ4E7svM34uIlwJ3AJ9v7/a5zLypn8ElSefasNAj4mrgiszcHxFTwHuA/R27vAv4eeAR4IGIuLM9/kBmHuh3YEnS2npZcrkWuBsgM5vAxRFxEUBEXA58LTP/KzPPAPe195ckbbNeCn0ncLrj+en22FrbvgJc2n58ZUTcExGfjoifPe+kkqSuelpDX2Wsh21fAG4DPgRcDnwiIl6UmU907txsNrfw8oOztLQ0cpm6qVLeKmWFauWtUlbob957772Xw4cP8+ijj7Jz507e8IY3cN111/Xl3FC9n20vhX6Sp2bkALuAU+tsuww4mZmPAB9sj30xIh5tb/tS54mnpqa2knlgms3myGXqpkp5q5QVqpW3Slmhf3nn5+e59dZbWVxcBODUqVPceuut7Nq1i3q9ft7nh9H82TYajXW39bLkchQ4ABARe1ku7McBMvM4cFFETEbEhcB1wNGIqEfEG9vH7ARewPKbppLUFzMzM2fLfMXi4iIzMzNDSjR8G87QM/NYRDQi4hhwBjgYETcAj2XmXcDrgA+0d/9gZv5HRJwCbo+I64FnA69bvdwiSefjxIkTmxp/JuhpDT0zb1k19FDHtk9x7scYac/gX3He6SRpHbt372ZhYWHN8WcqrxSVVEmzs7OMj4+fMzY+Ps7s7OyQEg2fhS6pkur1OnNzc0xMTDA2NsbExARzc3N9e0O0irbysUVJGgn1ev0ZXeCrOUOXpEJY6JJUCAtdkgphoUtSISx0SSqEhS5JhbDQJakQFrokFcJCl6RCWOiSVAgLXZIKYaFL2hbz8/NMTk6yZ88eJicnmZ+fH3ak4vjlXJIGbn5+nunp6bN3GFpYWGB6ehrAL9fqI2fokgbO28VtDwtd0sB5u7jtYaFLGrj1bgv3TL5d3CBY6JIGztvFbQ8LXdLAebu47eGnXCRti5XbxTWbTaampoYdp0jO0CWpEBa6pHOsXAB0wQUXeAFQxbjkIuksLwCqNmfoUkUN4lJ6LwCqNmfoUgUNaibtBUDV5gxdGrBBrEkPaibtBUDVZqFLHfq9jLEyk15YWKDVap2dSZ/veQc1k/YCoIprtVob/qrVaodrtdpnarXasVqt9mOrtr2sVqv9S3v7W3o5ptVq8dnPfra1FUeOHGlNTEy0xsbGWhMTE60jR45s6TyDPqfnHdw5B3XeI0eOtMbHx1vA2V/j4+Pnde6JiYlzzrfya2Ji4ryyDuq8rdbg/p+tePjhh/t6vkEaxazt7lyzq3sp86trtdq97cdTtVrtM6u2P1yr1V5Yq9UuqNVq/1Sr1a7c6JjWFgt9EH/gBnFOz1u9rK3WYEpybGxszXOOjY2dV9ZB/Qy2wyiW5HpGMev5FvrbarXajR3P/71Wq13Ufnx5rVb7dMe2N9VqtZu6HdM6j0IfxB+4qs2gqnTeKmVttQZTvlWeSQ/KKJbkekYxa7dC7+VTLjuBRsfz0+2xr7d/P92x7SvADwLf3+WYs5rNZg8v/5Ru64abPdcgz+l5B3fOQZ53586dnDp1as3xrZ734MGDvPWtb2Vpaens2I4dOzh48OB5ZQXYu3cv999/P0tLS+zYsQPY/J+pYVhaWqpETqhWVtjaxxbHtrBtzfHNfp/D7t27WVhYWHN8q98NMYhzet7BnXOQ5z106NA5HwWE5TcEDx06tOXzTk1NsWvXLmZmZjhx4gS7d+9mdna2rxfpVO27UaqUdxSzNhqNdbf18imXkyzPrlfsAk6ts+2y9li3Y7ZsEO/AD+pdfc9brawwuG8ErNfrHD9+nDNnznD8+HGvuNTgrLcW03pq/fsnarXaP7Qf7+1cM2+Pfb5Wq03WarULa7Xag7VlXY9p+SmXZ8x5q5S10yiuna6nSllbrWrlHcWs3dbQx1qt1oalHxF/CLwEOAMcBH4EeCwz74qIlwDvaO96Z2b+8VrHZOZDnedsNBqtffv29e0vpn4YxX9edVOlvFXKCtXKW6WsUK28o5i10Wiwb9++NZexe1pDz8xbVg091LHtU8D+Ho6RJA2QV4pKUiEsdEkqhIUuSYWw0CWpED19ymUQGo3GcF5YkipuvU+5DK3QJUn95ZKLJBXCQpekQnhP0baI+CPgp1n+mbw9M/92yJG6iojvBv4N+L3MfN+Q43QVEXXgt4HvAG/NzL8fcqQ1RcTzgL8CLgaeA9yWmR8dbqqni4gfAv4OOJyZfx4RLwTeDzyL5e9M+tXM/NYwM3ZaJ+97ge8Cvg28OjMfHWbGFauzdoz/PPCRzOz25YRD5wwdiIhrgB/KzP3Ay4E/GXKkXvwO8LVhh9hIRFwC/C7wU8B1wPXDTdTVDUBm5jXAAeBPhxvn6SLiucCfAR/vGH4b8BeZ+dPAfwK/Noxsa1kn7+8Dc5l5NXAX8FvDyLbaOlmJiB3Am+jDFwwOmoW+7FPAq9qP/xd4bkQ8a4h5uoqIFwNXAiM5013lZcDHMvPxzDyVmdPDDtTF/wCXtB9f3H4+ar4F/CLL32i64qXAPe3HH2b5Zz4q1sr7euDO9uPTPPUzH7a1sgK8GfgL4IltT7RJFjqQmU9m5jfbT18L3JeZTw4z0wbeyYjManowCYxHxD0R8U8Rce2wA60nM/8a2B0R/8nyX/JvHHKkp8nM72Tm/60afm7HEstXgEu3Oda61sqbmd/MzCfbk6aDwO3DSXeutbJGRA344cy8Y0ixNsVC7xAR17Nc6L857CzriYjXAJ/JzC8NO0uPxliegb2S5SWN90bESK5DRsSrgROZ+SLgZ4A/3+CQUTSSP9vV2mX+fuAfM/PjG+0/RIepzuTJQl/RftNjBviFzHxs2Hm6+CXg+oj4Z+BG4C0RMUr/xF7tv4Fj7dnPF4HHgR8Ycqb1/CTwUYD21z3vGuWltw7faL9JDk/dZGbUvRf4QmbeNuwg64mIy4AXA/PtP2+XRsQDQ47VlZ9yASLie4FDwMsyc6TfaMzMX1l5HBG3Ascz82PDS7Sho8D7IuIdLK9LP4/RXJuG5TcUfxy4MyImgG+M+NLbio8Bvwwcaf/+keHG6a79qacnMvN3h52lm8x8hOV7JAMQEcfbb+SOLAt92a+wfGPrD0XEythrMnPtuxGrZ5n5SET8DfDP7aGbMvPMMDN18W7gPe1Z2IXAbww5z9NExD6W30OZBL4dEQeAOst/af46sAD85fASnmudvM8HliLik+3dHs7M1w8n4VPWyfrKUZ/kdfLSf0kqhGvoklQIC12SCmGhS1IhLHRJKoSFLkmFsNAlqRAWuiQVwkKXpEL8Pw72sHtQHta2AAAAAElFTkSuQmCC\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "um0jtMJwzJKp"
      },
      "source": [
        "Still exponential."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mgBCVHbwocUf"
      },
      "source": [
        "def count_sequences_with_memo(start_position, num_hops):\n",
        "    cache = {}\n",
        "\n",
        "    def helper(position, num_hops):\n",
        "        if (position, num_hops) in cache:\n",
        "            return cache[ (position, num_hops) ]\n",
        "\n",
        "        if num_hops == 0:\n",
        "            return 1\n",
        "\n",
        "        else:\n",
        "            num_sequences = 0\n",
        "            for neighbor in neighbors(position):\n",
        "                num_sequences += helper(neighbor, num_hops - 1)\n",
        "            cache[ (position, num_hops) ] = num_sequences\n",
        "            return num_sequences\n",
        "\n",
        "    res = helper(start_position, num_hops)\n",
        "    return res"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 262
        },
        "id": "bBr63KJqpmrb",
        "outputId": "4fa4c5b3-73f7-4511-ed70-144b85abc289"
      },
      "source": [
        "# 1024 throws recursion depth error so we're doing 512.\n",
        "make_dialer_profile_graph(count_sequences_with_memo, 512)"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXkAAAD1CAYAAAC1BoUqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3df3Ac53kf8O/iCBg8nFWaixkDco3DOON9Q01m4iHHE9OeRMpQsWOWrZ2xI3vmANKWVFhH2mHZRrLSaxhaHrgealIWSk2ymFgyhbt4rExGTorSrit6bCem2kpo7Wkl9FXbFIAdUiMRnMoEQYgUsP3jbo97i9293b39cdj9fmZ2RNzt3u0DnJ5979n3h6LrOoiIKJ16kj4BIiKKDpM8EVGKMckTEaUYkzwRUYoxyRMRpRiTPBFRim1L+gSs5ubm2KeTiCiAPXv2KNbHui7JA8CePXsCHTc/P49du3aFfDbdKUuxAow3zbIUKxBdvHNzc7aPs1xDRJRiTPJERCnGJE9ElGJM8kREKcYkT0SUYkzyRJQ6tVoNo6Oj6OnpwejoKGq1WtKnlJiu7EJJRBRUrVbDxMQEVldXAQCLi4uYmJgAAJRKpSRPLRFsyRNRqlQqlWaCN6yurqJSqSR0RslikieiVFlaWvL1eNoxyRNRqoyMjPh6PO2Y5IkoVSYnJ5HP51sey+fzmJycTOiMksUkT0SpUiqVMD09jWKxCEVRUCwWMT09ncmbrgB71xBRCpVKpcwmdSu25ImIUsxTS14IcQrABwDoAI5KKV8wPXcvgK8AWAdwXkr5ZQ/HfATAd6WUm+Y+JiKi8LRtyQsh7gbwXinlXgAPAHjCsssTAD4B4EMAPiyEuMvtGCFEP4A/AHA5nBCIiMiJl3LNPgDfBgAp5TyAdwgh7gAAIcR7AFyVUv5MSrkB4Hxjf8djAPxzAF8DcDPMQIiIaDMvSX4IwOumn19vPGb33GsAhp2OEUJoAH5VSvnngc+YiIg8C9K7xq2O7vSc8fgpAL/X7g3m5+f9nhMAYG1tLfCxW02WYgUYb5plKVYg/ni9JPlLuN1yB4A7cbuebn3uXY3Hbtoc8yaAXwZQE0IAwLAQ4odSyrutbxh0/cMsrRWZpVgBxptmWYoViH+NVy9J/nsAvgTg3wohdgO4JKW8BgBSygUhxB1CiFEAPwdwAEAJwKDNMYsAfsl4USHEgl2CJyKi8LRN8lLKi0KIOSHERQAbAI4IIT4D4A0p5bMAygC+2dj9W1LKVwC8Yj0mmtMnIiI3nmryUspHLQ/91PTcjwDs9XCM9flRL+9NRETBccQrEVGKMckTEaUYkzwRUYoxyRMRpRiTPBFRijHJExGlGJM8EVGKMckTEaUYkzwRUYoxyRMRpRiTPBFRijHJExGlGJM8EVGKMckTEaUYkzwRUYoxyRMRpRiTPBFRijHJExGlGJM8EVGKMckTEaUYkzwRUYoxyRMRpRiTPBFRijHJExGlGJM8EVGKMckTZUStVsPo6Ch6enowOjqKWq2W9ClRDLYlfQJEFL1arYaJiQmsrq4CABYXFzExMQEAKJVKSZ4aRYwteaIMqFQqzQRvWF1dRaVSSeiMKC5M8kQZsLS05OvxtMlyqYpJnigDRkZGfD2eJkapanFxEbquN0tVWUn0TPJEGTA5OYl8Pt/yWD6fx+TkZEJnFJ+sl6qY5IkyoFQqYXp6GsViEYqioFgsYnp6OhM3XbNeqmLvGqKMKJVKmUjqViMjI1hcXLR9PAvYkieiVMtyqQpgkieilMtyqQpguYaIMiCrpSqALXki2kKy3N89KLbkiWhL4NQMwXhK8kKIUwA+AEAHcFRK+YLpuXsBfAXAOoDzUsovOx0jhNgL4HEAtwC8CWBcSvl6iPEQUUq59XdnknfWtlwjhLgbwHullHsBPADgCcsuTwD4BIAPAfiwEOIul2P+KYCDUsrfBPA8gH8cThhElHZZ7+8elJea/D4A3wYAKeU8gHcIIe4AACHEewBclVL+TEq5AeB8Y3/bY6SUvyul/FshhALgXQB+HnpERJRKWZ6aoRNekvwQAHNJ5fXGY3bPvQZg2O0YIcRvA5AA3gmgGuisiShzst7fPaggN16VAM81H5dSflcIIQB8FcCjqNfzW8zPzwc4LWBtbS3wsVtNlmIFGG+aeY119+7dOHHiBE6dOoVXX30VQ0NDOHbsGHbv3u16/Ozs7KZjDhw4EGYIvsT9t/WS5C/hdssdAO4EcNnhuXc1Hrtpd4wQ4neklM9KKXUhxF8AOGH3hrt27fJ29hbz8/OBj91qshQrwHjTzE+su3btwsMPP+z5tWu1Gk6cONG8YXv58mWcOHECd955Z6w3a2u1GiqVCpaWljA0NITHH3889Pefm5uzfdxLueZ7AD4JAEKI3QAuSSmvAYCUcgHAHUKIUSHENgAHGvs7HXNCCPG+xuv+GuplGyKiSHTDDJTWqY4vX74c61THbVvyUsqLQog5IcRFABsAjgghPgPgDSnlswDKAL7Z2P1bUspXALxiPabx/AMATgsh3gJwA8B4uOEQEd3WDT1yku766akmL6V81PLQT03P/QjAXg/HQEr5IoAP+jxHIqJA4pqB0lyOGRkZweTkZDOBJ32h4bQGRJRacfTIabfyVNJdP5nkiSi14piBsl3d3+lCs3///ljm4eHcNUSUalHPQNmuHGO8t7l3zcc//nGcO3culnl42JInIuqAl3JMqVTCwsICNjY2cOHCBZw/fz62Xj9M8kREHQhS94/zZiyTPBGlUlxzzwep+8d5M5ZJnohSp12Pl7CZyzELCwvNBO90oYlzHh4meSJKnW4c6WpcaGZnZ2Ndd5ZJnohSJ66at1tJyOlCc+rUKQDOrf+wMckTUerEUfNuVxJyuqC8+uqroZ2DF0zyRJQ67WreYdyUbVcScrqgDA0N2T4eFSZ5Ikodt5q315uy5gvB4OAgBgcHWy4K7UpCTheaY8eORRO0AyZ5IrIVVxfEqDjVvL3clLVeCJaXl7G8vNxyUdi5c6ft++q6jtHRUQCwvdAAiPX3yiRPRJvE3QUxTl5uytpdCMyM56wtdYN5mgLzhQYAjh8/3vJ7HR8fh6IokSV8Jnki2qQbuiBGxctNWS+9cK5evdpsqdtZXV3FoUOHNvW4WVtba9lP13UAiOxCyiRPlAF+Sy9Jz4EeJS8Dkbz0whkZGWmWhBTFfnnr9fV1Tz1uDFFcSJnkiVIuSOkl6TnQo+RlIJLdhcDMz0XB3KL38vsL/UKq63pXbS+++KIe1Msvvxz42K0mS7HqOuPtRLFY1AFs2orFouMx1WpVz+fzLfvn83m9Wq2Gdl6Gbv3bVqtVvVgs6oqi6Kqq6qqq6oqi6MVicdPvwe73Zd36+vr0crms9/b2uu6Xy+UC/Z4buXNTTmVLnijl7Ja/A9xbjHEOu+9W5t45U1NTKBQKrvtOT08jl8s57nPz5k08/fTTzRq8E2uJp1NM8kQpVqvVHOvF7UoHcQ2770Qc3Tztyl12PWJKpRLOnTvnWua5fv063nrrrbbvGWZtnkmeKMUqlYpjy3F5eXlLd4mMq5unXU8j43dqfU+jRR+GsGrzTPJEKeaWKFZWVmLt+x52q9vroCYv72nspygKenp6oCgKFEXB4OCgY7nL6T1LpRJUVbXdt6fHe8oN7Sa3XaE+yY03Xr3JUqy6zniDcrrpCo83YMPidiM3aKyKorjevASwaZ/e3t7mDVTjZqrdfn43RVE2xWu9wdrb26uXy2W9v7+/7esFucnNG69EGTQ5OelYkzfE0fc9isFVbi3d9fV1ALfLKoZbt241pycwpiqw28+q3e/Qei6lUglPPfVUy43rp556CqdPn8Zjjz3mOIAKAHK5XKg3uZnkiVKsVCrhoYceck1ScfR9j2JwVbu+7GFyuwg4rehk3LiemZkBAIyPjzfntHEbQLWxsRHqTW4meaKUO336NGZmZmzrxFEtOQe01sOdatGdXGDM3Tzj1NvbC1VVPXUttbs5/Mgjj0BRFMcLR+gXXbsaTpIba/LeZClWXWe8YTEP8LEb1BPm+7QbHOS1Ju/lnL3cewhz83ofw+95dTLgjDV5Ioqt77vTLI65XM7X4Cq7lvDY2BgGBwdbesq4lW6Msoiqqujr6+sgqtvalZmMbzHteuZYbd++vZPTssUkT0Shc0qCGxsbni4wRpIcGxuzvVgsLy/b9k83SjfGyNNisYiZmRnouo6pqSm8/e1vb76GU028WCw2W8FOpSBzScXaTfPw4cPNC5Nf1rhCYde8T3JjucabLMWq64x3q/EzX87LL7+8aZ6Yvr6+UMsmXspHxmbuDml3XG9vrz4wMNAV5SAzlmuIMi7IYKSgA5i8TOdrmJ2d3bQK082bNz29j9feOe0WATGz3vg0l1AGBgawsbGB69eve3qtoELt1mqX+ZPc2JL3Jkux6jrj7VSQWSU7nYnS603e4eHhSFq85vf3+nrm+Ozi73TQVBhxOXFqySee1K0bk7w3WYpV1xlvp4JMNxzkmCCCJk63C47X8ox51Kv5MeMCEUdC9xOXG5ZriDIsyGCkIMf4Ke8Y++q67riPIZ/Po1wut4wgPXToECqViu17eSnP5PN53HffffjFL37R8vjy8jLGxsYC3TjtlKqq4U/pbJf5k9zYkvcmS7HqOuPtVBwteT/lHb83Qsvl8qbj7eaGMd6r3bcDo7VubcXHvRnnGcaYBZZrUiZLseo647XyO6gprJq8eYIv6/v6uSj4LYVYX8MtOReLxbbJO5/P6+VyOfakrqqqvmPHjkgGozHJp0yWYtV1xmsW9IZokNGu7bo2mpO+W2vVym8d3voa7fZvt8Re3Jv57xPVZ5k1eaIQxbEikZOgMzoGGe1qPqZQKGzq2mie1dGJ3VwsTvOzOC2f53c+l1u3bvnaP0qR1Nl98JTkhRCnhBDPCyEuCiHeb3nuXiHEf2k8/4duxwgh3i2EeE4I8cPGf4fCDYcoenGtSOQkihkd7VgvZEFuRPb29mJlZWXTxdCpH/3ExISn/vVOi3LYvb+fhTrCYtwcrlaruHLlSrJLJ9o1782bpml3a5o22/j3Lk3Tnrc8/7Kmae/WNK1H07S/1jTtLqdjNE07p2nafY1/H9E07aT1/Viu8SZLsep6d8UbR9dCt3jDfH9rCadcLjdf31pS8VNicSrvWPuh25WPvJSVqtWq51GxAwMDnm/yhrG1+zvEXa7xkuQf0zTtQdPP/1PTtDsa/36Ppml/Y3ruDzRN+4LTMZqmDWialms8dp+maV+3vh+TvDdZilXXuytep2RnV3sOKoqavJfX8ZK8vSY5rxejoH9bP71j9u3bF8tAJi9/h26syQ8BeN308+uNx+yeew3AsNMxUsrrUsp1IUQOwBEAf+bh/Ym6ilN9OI7FN4DWybjMMzoC8HWfwM9Qf4Ou6833tZvV0VxaiaqsVKvVUCgUMDY21lzZqZ0f/OAHrvcN/DDPpGntu59k7d3JtgDHuK2D5fRc8/FGgp8B8H0p5QW7nefn5wOcFrC2thb42K0mS7EC3RXvkSNHcPz4caytrTUf6+/vx5EjR0I7x3bx7t69G9/5zneaP8/Ozrac0+LiIh588EFcunQJBw4csH2NIMl2eHh40/ueOnUKr776KoaGhnDs2DHs3r0b8/PzGBoawuXLlze9xtDQUEtsfv62s7Oz+OIXv+g7YRvLAfqVy+Vaju3v78djjz3W8jv9whe+0HJMu1hi/yzbNe/11nLNCU3TPmf6+W81TXt749+j5hq9pml/pGna59sc87SmaV9yej+Wa7zJUqy63n3xRr34ht94wxzs5Lb5idOtrGT+/Q0PD3t+3aBTDRgLezttfX19zfsR5r9pFH/nbqzJf1DTtP/Y+Pducw2+8dhLjWS/TdO0F7Q622M0TStpmvanbu/HJO9NlmLVdcbbTpD7BEFq8n7ZJcl29xSstXZjdKpbnO22crnsGKv59ePQdUleryfnr2qadlHTtL/RNO1XNU37jKZpv9N47jc0TXu+sf2+0zGNxy5qmvZfNU37QWM7bX0vJnlvshSrrjPedpxauKqqurZErUm4UCgETvJeW71ON0vtJgvz87zbcX7OL2pdmeTj3JjkvclSrLqe3Xi9JianKQjcujDacWspG8nS6f3d5pIx7xekJR5062TN1KgwyTPJe5KlWHU9m/H67SppvSA4tXqD1umd+qu7HWO9MAStqVu3djV2I85uS/C6ziTPJO9RlmLV9ezEa07UTonM66CnsOr0drNAOu1rt5mF2Uovl8uhjRmIUzf2kyeiGFinS3Dq9ue162OQ/vx2ffBnZmZw+vTpTfv67Wdfq9UcF88O4uzZswBgO2ag2/qqJ8ou8ye5sSXvTZZi1fVsxOu1lOG1JR91K9fLuZrLNWGVaoL8LroJW/JEGeWlhe60GLYdp5GxYbRyvbTK+/r6cN9992FwcBCKokSy0lISqzdtNUzyRF3CbfrdoEk6yPTCVsZslIqioKenB4qiYGxsrH5Tz0Eul8PNmzdx5swZz1MPBKEoSqzTPG9FTPJECbFO5bt//37baXbPnTvXUZJu977t1mE17hMAcE3s5nMOOo2AX7qut51HP/PsajhJbqzJe5OlWHU9ffE61cvthtZH/b5u64xGUUf3ug0MDOgDAwNt9wtz9s84xF2TDzJBGRF1yGl1p/Pnz2NhYQHz8/PYtWtXx+9Tq9VQqVSwtLSEkZERrKysbHpfvdE6NxY/AdD8xhD2QiR+DA4OYmFhofmz08Ilcc3+uVWxXEMUMbvySByrO9mtYNWuPm5dRjDJBGr9XTitJuX1RnRWMclT6iW5HqvTUoE7d+603T/MpBpkvnigNblOTk6G2rfdqlAoYMeOHbbPWX8XUfYWSjW7Gk6SG2vy3mQpVl3vbPWgJEdEuk0c5nZeYfx9g87YaO17HuQ1/LzXyZMnt9yo1U6wnzxRiJxq31H0yPBTlrl69WrkrVKnbwWqqqJYLNo+Z/RnN3/j8bpodhBLS0s4cOAAW+hRssv8SW5syXuTpVh1PXi8cazHquvO3xi8TBJmN9NkGH9ft28x5XK5bUvf2DfI9L7mraenx3EK42KxyM9ySNiSp0xyqn07PR6U0zcGAK43C51q9rOzs4HOw/xt4ujRoy31dFVVm2vBnjlzpm2fd+Mbz9WrV32dg6IoKJfLzSSzvr6Os2fP8qZpUuwyf5IbW/LeZClWXQ8er1MrtKenJ9Sar9s3Brc54Z1q9sPDw77Pod2skEbL3Evfc/Pm1lfemCnT+G+7Oe/tfg/8LIeDUw2nTJZi1fXwyzXmpBeGIGusup2fXTnJmiStA6e8lFWClF727dsX6e+Rn+VwsFxDmeTWJdF8A7bTbpZB+3A7nd/Q0FDLz4cPH8b4+HhLWefMmTO++sADCDSPzPe//33X0k5UN7IpHEzylGp2yddsaWnJsS7uJ9Fb+3Crqort27djfHzc9aLhdHE4duxY8+darYazZ8+2raFHxcv7Jjkyltqwa94nubFc402WYtX1zuKtVquuqyy5lVqCLP7c6bJ95XJZHx4ebpZt7M4t6NbT0xPq65l/V0HxsxwO1uRTJkux6nrn8bol3nb1Zq/J2uCnPm+X4L0sqdfJ5uf1vVxkWJP3h0meSd6TLMWq6+HE69Qqd0rKQddY9Xoz1W1GyKg2p28n5gW5zT1l7C46vb29uqqqoc2Uyc9yOJjkUyZLsep6tPE6tfLdWrdu3C4aXrpPRrkFSchBSlZ+8LMcDvauIXLgNPGV09D/dpOIOd3sXV9fx/j4OBRFweDgYOxL16mqGmiqgDBWl6LkcD55ItQTmV3ympiYaBnJ6qVbpPE6hw4d2rRCkq7rAIJ1ZexEPp/H1NRUrO9J3YEteSIHnUxtWyqVsLGxEcl5DQwM+D6GE35lF5M8pUYU88YHKVUY52G02sPW39+Pvr4+z/sXi0Um+AxjuYZSwRjQZJRW7Jayi/K9K5UKFhcXoShKZMnd4KfUw0nAiC152hJmZ2ddW+lxzhtvZp5uAEDkCd4rzstOBiZ5CiyuZfVqtRqOHz/uOu1A0DVTO4nh8OHDnqbsjVuxWGRPGLrNrl9lkhv7yXuTdKxxLqvnZQSp2zJ7Tn287RbO8BpDu5GySW1bcdm8pD/LceNgKCZ5T5KONejUulZeBtp4GUFqd9Hp7e3V+/r6bJOgW5K2xmB3jkkMZLK7gAHe5nLvZkl/luPGJM8k70nSsYaxrJ7XbwNeLyjWZOy29J5bkjbH4NTaTzK5K4qil8vljv5+3STpz3LcmOSZ5D1JOtYwWvJ+knd/f3/bi4GV24WoXanFmLcljpJMoVBw/XbgVnJKg6Q/y3FjkmeS9yTpWMOoyfv5NnDy5Enfic7tIuKl3BJGgldV1XERa+sShHHe5+gmSX+W48YkzyTvSTfE2unEVX6+DQSJ16lOb5Rxkr5x6mWJv7QneF3vjs9ynDhBGW0ZnU5cFXTJPDfmLpGVSgWHDh1qmWjs1q1bzcFEuq4Hfp8w2E10ZvxOX3rpJXaBpFAwyVNigswN49av3W4ZvzNnzuDy5ctxhOMLR6JSXDxNayCEOAXgA6h/zTwqpXzB9Ny9AL4CYB3AeSnll92OEUL8HoA/BvAOKeVKiLHQFuQ0+6OddlMX2I16BYCbN2+Gd8IBqaqKQqGApaUljIyMYHJykq10ikXblrwQ4m4A75VS7gXwAIAnLLs8AeATAD4E4MNCiLucjhFCHATwTgCXwguBssJp6oKjR48C6N7FpPv6+jA1NcU52SkRXso1+wB8GwCklPMA3iGEuAMAhBDvAXBVSvkzKeUGgPON/Z2OeVZKWUG9dU/ki1MSX15exuDgYOI1doOqqi3/fvLJJ5nUKTFekvwQgNdNP7/eeMzuudcADDsdI6W8FvxUyU1c88gkyW1FprgX4XBSLBZx5cqVZs+GK1euMMFTooJMNawEeM7tmE3m5+f97N60trYW+Nitxhzr7Owsjh8/jrW1NQD1WvWDDz6IS5cu4cCBA0meZmjW1tZw5MgRPPLII0mfiqPe3l4cOXIklM9gVj/LWRB3vF6S/CXcbrkDwJ0ALjs8967GYzddjmlr165dXndtMT8/H/jYrcYc60c/+tFmgjesra3ha1/7Gh5++OEkTs8Xp/nYVVXF1NQUSqUS5ufnceeddyZyftY54vP5PA4dOoRnnnmm+Q3CfK5hyOpnOQuiindubs72cS/lmu8B+CQACCF2A7hklF2klAsA7hBCjAohtgE40Njf8RgKX9BpdqPgt2xk7vYItPZdX15extjYGBRFwd69e3Hw4MFIz91OsVjEzMzMpm6ep0+fZlmGtoS2LXkp5UUhxJwQ4iKADQBHhBCfAfCGlPJZAGUA32zs/i0p5SsAXrEeAwBCiAqA30K9lf8dIcTzUsru/f69RYyMjDSTpPXxOAVZncmp26PVG2+8Ed6JetTX19fs6sgETluW3TDYJDdOa+CNOdak5zxpN/WuqqqOxyY9tYD5HM2zVqqqmuiUAln9LGcBpzUg34KMHPXD6yhTJ8vLy1AUpbkVCgUUCoVY1kP1QlEUTE1NsfxCqcSFvFMiqpJC0FGmbq5fvx76eXqhqipu3LjRcr6KouChhx5iQqfUYkueXDmNMjVuiLq14LuJ0Vq3fuOZmZnB6dOnkz49osiwJU+u4u6ho6oq3ve+9+HChQuhvq65tc5WO2UJW/K0iVGDT6Jmvry8HDjBK8rmMXeFQgHVapWtdcosJnlq4eVGqptcLgfAPuFGyaitm0sx1WoV165dY8udMo1JPqC0zBVjbrVv27YNY2Njvm+kAvUySz6fx/r6OoDoFuQYGBhAX19fy2NGgj99+jRneiSyYJIPwG5xiomJia5M9E4Xo1qthsHBQYyNjTVb7UaC9iufz+PNN98MdHHwo1qtYmVlBU8++SRvnhJ5Zdd5PsltKwyG8rM2aVS8xGo3SMoYfBR0EFIul2v5b7FY1MvlcuSDlT796U/H8FvtHlkaIJSlWHWdg6G2hG6ZK8atlT46OmpbetEbZRTjv37t2LED1WoVExMTyOVyzSX2olQul3H8+PFI34MordiFMoBumCtmdnYWJ06c2DRI6cc//jHOnTsXWunE2sPGmDQsTPv27cNPfvKTTXPCW2ehJCL/2JIPYHJyEvl8vuWxOBZmNrfcH330UdtBStPT06Ek+Hw+j3K5jJ6eaD8i5XIZzz33XMuUAsbGqQWIOsckH0DUc8UYzEl9cHAQ999/f/Nm78bGhu0xQW+eAmgm9Fwuh9XVVZw9e7aj13OjKArK5TJvmBJFjOWagKKYK8ZYPGNpaQk7d+7EtWvXcPPmTQDel7fL5XKOidlaejF+LhaLzW8h999/f/M9g9bt2wl7gQ0icsaWfILcWurLy8vNZOtVPp/HxMSEbSmpWq1uWvxiZmYGuq5jYWEBADA+Pu77Pb0wviEYA5RYhiGKkV2XmyS3rdCFMgx23RuDbLlcTlcURS8Wi835z4353a2PG8+Z502PYiuXy6H/vrbS3zYMWYo3S7HqOrtQdpUwR7VaX+vo0aMd3yDN5/M4d+7cphGepVJp08jPWq2GQqGAsbExz6Ufv1RV5TwxRN3GLvMnuXVLSz7oakt2reiwWu29vb26qqq6oij68PBwS8vduqpRuVyOvMXu9XcSBrb20itLsep6/C35xJO6dYsqybuVMOwEGdXqdGEImmzNSd16zkas1WpV7+3tjTyZG1tPT4/jOUWJiSC9shSrrjPJR5Lkg7TKnYb9K4rieIzbOqd+N7tauvkidfLkSb1arTanF4g6sdudU5yYCNIrS7HqOpN8JEk+SKs8yDFhLUptvZCEVe7xs/X39ye6kLUVE0F6ZSlWXeeN10gEmWum3ahWu5uyTtMa2M2tns/noaqq7f4jIyMtr3/w4MHIZ3g05HI5lMtl3Lhxg90ciVIgE0neKfkaj9slbOuoVlVVsX379ubapsYUvbp+e6rh/fv3b7owAPVvS2aqqmJ6ehpTU1O2+1+5csXT6NZOGb1hzFf9t956i71jiFIkE0nerVXuNje80RVxZmYGN27ccO16uLq6imeeeablwmCskmRVKBQAwLEb5fXr18qIaosAAAdESURBVCMZlATUByaVy2XoOueGIcqCTCR5t7lmKpWK7URflUoFQL2Vf+jQIU/lEuMiYPRRd2qBLy4uRtpf3crcYl9fX2dLnShDMjN3jdNcM051+cXFRSiK4nsx60ql0nwfpymJ45DL5TAxMcGETpRxmWjJu2k3B7yfBA+gJanv378/0DkFZdw0ZW2diAyZack7mZycxMTERKi9V+x600SFMzoSkZvMJ3kjOR49ejS2GnknjKS+e/du7Nq1K+nTIaIul/lyTa1W6/oEb75xyh4xRORHplvyhw8fxtmzZ33X3aPE8gsRhSmzSf7w4cM4c+ZM4OP7+vrQ19eHlZWVjs+Fy+ARUVQyU64xj2p929ve1lGCV1UVTz75JK5fv+772HK53NJfn/OvE1GUMtGSN0a1Gj1ogowmzefzmxbrrlQqvvrBs8VORHHLREu+01WYjLlmrHXyycnJ5vql7Y5ni52IkpD6lvy9994buOdMu5ugxuOf+9znWko3hUIBZ8+e5c1TIkpc6lrytVoNg4ODzSkJLly44Ps1jJa3l+6KpVIJKysrLTM5Xrt2jQmeiLpCqpL87OwsPvvZzwZuuXN2RiJKG0/lGiHEKQAfQH3VoKNSyhdMz90L4CsA1gGcl1J+2ekYIcS7AcwAyAG4DGBcSvlmp0HUarVNJRM/FEXBzMwMEzsRpU7blrwQ4m4A75VS7gXwAIAnLLs8AeATAD4E4MNCiLtcjnkMwNeklL8O4H8DuL/TAGq1Gg4ePBg4wW/bto0JnohSy0u5Zh+AbwOAlHIewDuEEHcAgBDiPQCuSil/JqXcAHC+sb/TMfcA+KvG6/47APd2GkClUgm8clKhUMA3vvENJngiSi0v5ZohAHOmn19vPPaLxn9fNz33GoBfAjDocMyAqTzzGoDhYKd9m9s6rXbuuusuvPTSS52+LRHRlhCkC6XbPLpOz9k97vg68/Pznk9maGgIly9fbrufoij41Kc+hePHj/t6/W61traWiji8YrzplaVYgfjj9ZLkL6HeCjfcifpNU7vn3tV47KbDMStCiO1SyhumfTfxM4Xu448/joMHD7qWbNI40nR+fj5TUw0z3vTKUqxAdPHOzc3ZPu6lJv89AJ8EACHEbgCXpJTXAEBKuQDgDiHEqBBiG4ADjf2djnkO9Zu0aPz3uwHjaSqVSnj66acxMDCw6TmONCWirGvbkpdSXhRCzAkhLgLYAHBECPEZAG9IKZ8FUAbwzcbu35JSvgLgFesxjef/CMDTQojPAVgEcC6MIIz1W7PWIiAiasdTTV5K+ajloZ+anvsRgL0ejoGU8jKA3/J5jkREFFCqRrwSEVErJnkiohRjkiciSjEmeSKiFFO6aRFrAJibm+uuEyIi2iL27NmzaZBp1yV5IiIKD8s1REQpxiRPRJRiqVjj1W1Rk61OCPErAP4SwCkp5b9xWnhFCFEC8E9QH2E8LaX8emInHZAQ4iSAX0f9c/kvAbyA9MaaB/ANAO8E0A/gy6gPMkxlvAAghNgO4H+gHusFpDRWIcQ9AP4cgDHd7X8HcBIJxbvlW/IeFjXZsoQQAwD+BPX/IQybFl5p7Hcc9fn57wFwTAixM+bT7YgQ4jcB/Erj7/jbAP41Uhprwz8E8KKU8m4A9wH4V0h3vADwLwBcbfw77bH+UEp5T2P7AhKMd8snebgsapICbwLYj9bZOu/B5oVXfg3AC1LKNxozfP4Y9ZW6tpIfAfjdxr//H4ABpDdWSCm/JaU82fjx3QB+jhTHK4T4ZQB3Afj3jYfuQUpjdXAPEoo3DeUat0VNtjQp5VsA3hJCmB+2W3jFbvGWjhdkiZOUch2AsYbjA6ivMvaRNMZq1pjE7++jPoPrcymO948BfB7AocbPqfwcm9wlhPgrADsBfAkJxpuGlryV26ImaeNnkZYtQQjxMdST/OctT6UuVgCQUn4QwD8CUEVrLKmJVwhxEMDzUsr/67BLamJt+F+oJ/aPoX5R+zpaG9SxxpuGJO+2qEkarTRuYAG3F15xWrxlSxFCfARABcBHpZRvIN2x7mncRIeU8ieoJ4FrKY33HwD4mBDiPwF4EMAfIsV/Wynl3zXKcbqU8v8AeBX1MnIi8aYhyTsuapJSdguv/GcA7xdC7BBCFFCv6/11QucXiBDi7wF4HMABKaVxcy6VsTb8BoB/BgBCiHcCKCCl8UopPyWlfL+U8gMA/hT13jWpjBUAhBAlIcTvN/49hHoPqqeQULypGPEqhPgq6v/TbAA4IqX8aZtDtgQhxB7Ua5mjAG4B+DsAJdS73vWjvvDKZ6WUt4QQnwTwMOrdSP9ESllL4pyDEkJMADgB4BXTw4dQTwqpihVodif8Ouo3Xbej/vX+RQBPI4XxGoQQJwAsAPgPSGmsQoi3A/gzADsA9KH+t/1vSCjeVCR5IiKyl4ZyDREROWCSJyJKMSZ5IqIUY5InIkoxJnkiohRjkiciSjEmeSKiFGOSJyJKsf8PLuihmQm13RoAAAAASUVORK5CYII=\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5Sl1kC5hzOrU"
      },
      "source": [
        "Nice and flat, O(n) for sure. Now that we're running a lot of values we start to see how 'messy' execution really is; it's flat in aggregate, in general, but individual runtimes for individual function calls are 'noisy'. Still, obviously O(n)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LWH7sfZdp1Ec"
      },
      "source": [
        "def count_sequences_dynamic_programming(start_position, num_hops):                \n",
        "    prior_case = [1] * 10                                     \n",
        "    current_case = [0] * 10                                   \n",
        "    current_num_hops = 1                                      \n",
        "                                                              \n",
        "    while current_num_hops <= num_hops:                       \n",
        "        current_case = [0] * 10                               \n",
        "        current_num_hops += 1                                 \n",
        "                                                              \n",
        "        for position in range(0, 10):                         \n",
        "            for neighbor in neighbors(position):              \n",
        "                current_case[position] += prior_case[neighbor]\n",
        "        prior_case = current_case                             \n",
        "                                                              \n",
        "    return current_case[start_position]   "
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 262
        },
        "id": "Z3D0-7t0p3w5",
        "outputId": "9eb62b85-c978-4981-e7ae-1c52c56c47d0"
      },
      "source": [
        "make_dialer_profile_graph(count_sequences_dynamic_programming, 512)"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX8AAAD1CAYAAAC4GPVtAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3df2zc933f8edXlFTlxGm2ySGSvegEG8Z7NFpgkBHErtdZBdW087QVQdxt2J0s/1hsk+rKuotXo1wdOzazQkKj2V1lh0isuOLZcBbDXuopjWEVqQOriy1iCbbo8Fa7jbRbSbBEY7Z+MZLJ2x93xxxPd8fvHb+8H997PYADze/3+/ne9yPS7/vw8+P9CXK5HCIi0l1WtfoBRESk+RT8RUS6kIK/iEgXUvAXEelCCv4iIl1IwV9EpAutbvUDhDU5Oak5qSIidbr55puDSsc7JvgD3HzzzXWXyWazDAwMrMDTtCfVN766qa6g+kZhcnKy6jl1+4iIdCEFfxGRLqTgLyLShRT8RUS6kIK/iEgXUvAXka6QyWTYsmULq1atYsuWLWQymVY/Ukt11FRPEZFGZDIZ7r//fi5cuADA9PQ0999/PwCpVKqVj9YyavmLSOyNjo4uBP6iCxcuMDo62qInaj0FfxGJvXfffbeu491AwV9EYm/z5s11He8GCv4iEntjY2MkEolFxxKJBGNjYy16oqWt9AC1gr+IxF4qlWJ8fJxkMkkQBCSTScbHx9t2sLc4QD09PU0ul1sYoI7yA0DBX0S6QiqVYmpqivn5eaampto28ENzBqgV/EVE2kwzBqgV/EVE2kwzBqgV/EVE2kwzBqgV/EVE2kwzBqiV3kFEpA2lUqkVHZRWy19EpAsp+IuIdCEFfxGRLqTgLyKxp1z+V9KAr4jEmnL5VxYq+JvZPuAWIAeMuPs7Jee2A18B5oBD7v5EtTJmdiuwF7gM/BTY6e6nzSwF/DYwD4y7+zeiqqCIdLdaqRK6Ofgv2e1jZrcDN7r7rcB9wNNllzwNfB64Dfismd1Uo8zvAHe5+y8Dfwl8wczWA48C24FtwENmds2yayYignL5VxOmz38QeBXA3bPA1Wa2AcDMrgc+cPf33H0eOFS4vmIZd/8Nd/8/ZhYA1wF/A3wGeMfdP3T3i8Bb5D9IRESWTbn8KwvT7bMRmCz5/nTh2EeFr6dLzr0P3AD0VytjZr9G/i+BLDAB/KsK99hU6UGy2WyIx11sdna2oXKdSvWNr26qK0RX3927d/Poo48yOzu7cGzdunXs3r27rf49m/3zbWTAN2jg3MJxd/8zMzPgD4BHgKmw9x8YGAj5iD+TzWYbKtepVN/46qa6QnT1HRgY4Nprr2V0dJR3332XzZs3MzY21nb9/Svx852cnKx6Lky3zwnyrfaia4GTVc5dVzhWsYyZfQ7A3XPAy8A/qnEPEZFIdFIu/2YJE/xfB+4EMLOtwAl3Pwvg7lPABjPbYmargR2F66uVeczM/mHhvp8BHPgh8Gkzu8rMesn39/8govqJiEgFS3b7uPsRM5s0syPkp2LuNrO7gQ/d/RVgCHixcPlL7n4cOF5epnD+PmC/mX0MXCQ/1fOimT0CfI/8tNDH3f3DCOsoIiJlQvX5u/sjZYd+XHLuTeDWEGVw96PAL1Y4/m3g22GeRURElk/pHUREupCCv4hIF1LwFxHpQgr+IiJdSMFfRGJN6ZwrU0pnEYktpXOuTi1/EYmtWumcu52Cv4jEVqPpnLuhq0jBX0Riq5F0zsWuounpaXK53EJXUdw+ABT8RSS2xsbGSCQSi44lEgnGxsaqlumWriIFfxGJrVQqxfj4OMlkkiAISCaT7Nq1i9HR0apdOt2y85eCv4jEWmk657GxMZ5//vmaXTrdsvOXgr+IdI0wXTqNdBV1IgV/EekaYbp0KnUVjY+Px25dgBZ5iUjX2Lx5M9PT0xWPl0qlUrEL9uXU8heRrtEtXTphKPiLSNfoli6dMNTtIyJdpRu6dMJQy19EpAsp+IuIdCEFfxGRLhSqz9/M9gG3ADlgxN3fKTm3HfgKMAcccvcnqpUxs08BB4A1wGUg7e6nzOwy8FbJWw66+9yyayciIhUtGfzN7HbgRne/1cwGgOeAW0sueRr4VeBvgb8ws5eBv1elzJPAuLt/y8x2A78D/HvgQ3ffFmG9RESkhjDdPoPAqwDungWuNrMNAGZ2PfCBu7/n7vPAocL11coMAy8X7nsa6IuwLiIiElKYbp+NwGTJ96cLxz4qfD1dcu594Aagv1IZdz8OYGY9wG7gy4Xz68zsBSAJvOzuX630INlsNsTjLjY7O9tQuU6l+sZXN9UVVN+V1sg8/6CBcwvHC4H/IPDn7n64cPiLwAT58YE3zexNdz9afpOBgYG6HzabzTZUrlOpvvHVTXUF1TcKk5OTVc+FCf4nyLfwi64FTlY5d13h2KUaZQ4Af+XujxdPuvuzxf82s8PALwBXBH8REYlGmD7/14E7AcxsK3DC3c8CuPsUsMHMtpjZamBH4fqKZcwsBVxy9y8Vb255L5hZULjHbcBPIquhiHS1btiPtxFLtvzd/YiZTZrZEWAe2G1md5OfofMKMAS8WLj8pUK//vHyMoXzu8n373+/8P0xdx82s/eAtwvXfsfd346ofiLSxYr78RZz+Bc3bwG6PsVDqD5/d3+k7NCPS869yeKpn9XK4O6/WOX+vxvmOURE6lFr85ZuD/5a4SsisdUt+/E2QsFfRGKrW/bjbYSCv4jEVqXNW4Ig4I477mjRE7UPBX8Ria1UKsWuXbsIgp8tQcrlcjz//PNdP+tHwV9EYu3QoUPkcrlFx4qDvt1MwV9EYq0TB32bsTZBwV9EYq3eQd9WLworrk2Ynp4ml8strE2I+jkU/EUk1ioN+iYSCcbGxq64tlmBt5ZaaxOipOAvIrGWSqUYHx8nmUwSBAHJZJLx8fGKi7yaFXhraVY3VSNZPUVEOkoqlQq1orcdxgc2b97M9PR0xeNRUstfRKSgHRaF1dNNtRwK/iIiBc0KvLXU0021HOr2EREpKAbY0dFR3n33XTZv3szY2FjTk8CF7aZaDrX8RaRrhJnGmUqlmJqaYn5+nqmpKYBY7geglr+IdIWwuf0zmcxCy/+aa67h7NmzXLp0qWaZTqSWv4h0hTDTOMvn+c/MzCwE/mplOpWCv4h0hTDTOCt9QNRzr06i4C8iXSHMNM6wQb0ZUz9XOs2Egr+IdIUw0zjDBvWV3g+gGWkmFPxFpCuEmT8/NjbGmjVrlrzXt771rZV81KakmVDwF5GuUT6Ns9KMnbm5uSXvMzMzE3k3zGuvvbbQzVMpvQNEO9YQaqqnme0DbgFywIi7v1NybjvwFWAOOOTuT1QrY2afAg4Aa4DLQNrdT5lZCvhtYB4Yd/dvRFVBEZEwil0t8/Pzoa4fHR2NbLpnJpPh0UcfZXZ2tuZ1UY41LNnyN7PbgRvd/VbgPuDpskueBj4P3AZ81sxuqlHmSfLB/XbgFeB3zGw98CiwHdgGPGRm1yy7ZiIidQg706coylb46OjokoE/6jQTYbp9BoFXAdw9C1xtZhsAzOx64AN3f8/d54FDheurlRkGXi7c9zTQB3wGeMfdP3T3i8Bb5D9IRESapt5gHmUrfKn3Xon8PmG6fTYCkyXfny4c+6jw9XTJufeBG4D+SmXc/TiAmfUAu4EvV7nHpkoPks1mQzzuYrOzsw2V61Sqb3x1U12hvvq+9tpr7Nu3j1OnTrFx40YeeughduzYUdf7bdy4kZMnT4a6dt26dezevTvU84V5tlrvHQQB3/3ud4HGYmA1jaR3CBo4t3C8EPgPAn/u7ofN7F+Hvf/AwEDohyzKZrMNletUqm98dVNdIXx9M5kMjz322EKXzcmTJ3nssce49tpr62op7927d1H6h2p6enr4+te/HureYZ9t7969pNPpivfYvHlzwz/3ycnJqufCdPucIN86L7oWOFnl3HWFY7XKHAD+yt0fX+IeIiJLqmdaZK2FU+VTQauZn58P/aFSz7N94hOfuOLY2rVrVyyddJjg/zpwJ4CZbQVOuPtZAHefAjaY2RYzWw3sKFxfsUxhVs8ld/9Syf1/CHzazK4ys17y/f0/iKR2IjHT6s3F21HY3bfCLJwqnQqaTCYr3reevv5az1b8WQZBQDqd5uLFi1dcd+nSJQ4cOBD6/eqxZPB39yPApJkdIT9rZ7eZ3W1mnytcMgS8SD5gv+TuxyuVKVy7G9hqZt8vvPYXBnkfAb4HvAE87u4fRllJkTh47bXXWr65eDsKu/tWrVZ4JpOhv7+fIAgIgoD+/n7uuOOOZW/sUuuDIp1OV53PX+rw4cMMDw+Hfs/QcrlcR7yOHj2aa8SxY8caKtepVN/42rRpU478uplFr2Qy2epHWxFhf7YTExO5RCKx6N8kkUjkJiYmFl0XBEHFf79qr7Vr1+aGhoZyyWQyFwRBLplMXnHPRp6tkVdPT09d71tUiJsVY6ry+Yt0iFOnTlU8HocMk8sRdvetahujV3Pp0iUOHTq0sKHLcp5tZGSEmZmZhu8TZtVxvZTeQaRDbNy4seLxZm4u3q7CpG2olNhtKaUfrPWOt2QyGXp7e0mn08sK/JCfYRQ1BX+RDvHQQw+1fHPxTlY6myes4gdrpcHidDpNf3//wodA+bhBOp3m/PnzkTx7cfewKCn4i3SIHTt2LJmVspuF3Z+3nnTMxWurpX6YmZnhnnvuiayFX66np4ehoSH2798f6X1Be/iKdJRUKqVgX0E9+/M+++yzoe976NAhoPa4yuXLl7l8+XIjj32FIAh48MEHVyTYl1PLX0Q6XtjFVKOjo+RyudD3LQb9lR5X6e3tZc+ePczPzzcl8IOCv4jEQNiFXo0mb1upcZVEIsHExARnz56tOxfRcin4i0jHC7vQq54W/EoNpq9alQ+7rR6zUfAXkY4XZn/eatdV0tfXtygwL3f7xLVr1y4srpqbmyOXy1WdktosCv4i0vHC7M9b7bqhoaFF309MTHDmzJlFZZezkG7NmjU899xzDZdfKZrtIyKxEHYmVCMzpupdHVyUTCYrrjZuB2r5i0hHamaG03pWBxf/emiHrp1aFPxFpOOESc9cvC6KD4jy1cHFdAulgb74aueAX0rdPiLSUTKZDLt27boi2dmFCxfYuXPnwo5Y69ev5/Lly1y6dAmovvArrLgtsFPLX0Q6RrHFXy3LZekCrvPnzy8E/qJqu2h1IwV/EekY1XLs1KPbU2AXKfiLSMOava1kFIFbKbDzFPxFpCFhB13D3ivMh0gUgVspsPMU/EWkIWGTqS2l2ofIa6+9dsW1Y2NjC+kRGhWnQdvlUPAXkYaETaa2lGofIvv27Vv4fnh4mNWrV5NOp5mfn6//YQtWYkesTqWpniLSkGqrXuvtmqn2YXHy5En6+/sj3SBlJXbE6lShgr+Z7QNuIb+T/Ii7v1NybjvwFWAOOOTuT9QqY2a/BfwhcLW7nyscuwy8VfKWg+4e/Y7FIhKZsbGxRRuoQLhMmJlMZtFm6+vXr+fcuXMVr40q8Ddzk5ROsWS3j5ndDtzo7rcC9wFPl13yNPB54Dbgs2Z2U7UyZnYX8EngRNk9PnT3bSUvBX6RKpo9w6aasMnUSlXq368W+JerdPVtMzdJ6RRh+vwHgVcB3D0LXG1mGwDM7HrgA3d/z93ngUOF66uVecXdR8n/NSAidYpyhk0UUqkUU1NTzM/Ph0prEMU8/aX09PQwMTHRMWkWWiVMt89GYLLk+9OFYx8Vvp4uOfc+cAPQX6mMux+v8h7rzOwFIAm87O5frXRRNpsN8biLzc7ONlSuU6m+8TU7O8vDDz9ccXD04YcfZuvWrS16svBWeoHVVVddxe/93u+xdevWjvu9aPbvciMDvkED52qVAfgiMEH+L4I3zexNdz9aftHAwEC4JyyRzWYbKteo8v7MZqdzbXZ9W62b6pvNZjl16lTFc6dOnWqLf4dqv/+ZTIaRkZG69s8NY3BwkDfeeCPSe7bKSvwuT05OVj0XptvnBPkWftG1wMkq564rHKtV5gru/qy7n3P388Bh4BdCPFfbabc/ySV+wm5X2MxxgeJ7BUHAzp07F/3+p9NpgiAgnU5HOmunp6eHoaGh2AT+VggT/F8H7gQws63ACXc/C+DuU8AGM9tiZquBHYXrq5YpZ3kvmFlQuMdtwE+WV63WiGrRi0g1YbYrXG4jpJ4PjtL3AiJv2Zfq7e1dGMD9+OOPNYC7TEsGf3c/Akya2RHys3Z2m9ndZva5wiVDwIvAD4CX3P14pTIAZjZqZt8n/1fBd81sj7s78B7wNvnpnofc/e1Ia9kkUS16EakmzAyb5TRC6v3gaMYAbjHonz17VgO4USrdhKCdX0ePHs014tixYw2Va0QymcyRH7dY9Eomk017hmbWtx10U32PHTuWm5iYyCWTyVwQBLlkMpmbmJi44rogCCr+Hub/d1+s/H59fX1L/g4Xy1R7j6hemzZtqli/uFqJ3+VC3KwYU1se1MO+OiH4T0xM5BKJxKJf4EQi0dRf4G4Khrlcd9V3z549oX6/qgXmIAgWXVvp97XaKwiCuss0+hoaGsrlct31s83lFPw7Ovjncle2pJrdctH/MPG1adOmUH9ZTkxMVG39l15bT+u9WG4lW/xBECwE/lyuu362uVzzg78Su0Ws3kUvImFVm+ZZPqaUSqXyLbslrq1nLGpmZoYgCCrm8mnU4ODgorGLgwcPahC3iZTYTaRDbNy4kZMnr5wxXWn6ZzKZXDLpWrXEbOvXr+fChQuLPkCiTMHQ19fHU089pYZRi6nlL9IhHnrooSWneRaFmRJa6ZogCJibm6v6l0OjSvPsnDlzRoG/DSj4i3SIHTt2hE6kFjbpWhAsXnyfy+WYnZ2N5Hn7+voWAr66QNuPgr+0neLGHUEQsHr1aoaHh1v9SG0j7JhSaZqFa665hnPnzrFz586FRVvDw8Ok02nOnz8f2bOtX79+0YCiWvjtTX3+0laGh4d55plnFr6fm5vjmWee4fjx41rKH1JxoVZx8VVpWoViyoWorV27lq997WuR31dWjlr+0lbGx8crHj98+LByJIXUjFW3pZLJJM8995xa+R1GwV/aytxc9X18lCMpnJVOJ7Ju3bqFvnz153cuBX9pK6tWVf+VVI6k2ooJ2aKeqVO0atUqhoaGuHjxooJ9DCj4S9tYqlvnmmuuadKTtL/yzJvbt29fSKccldWrVy9q4c/NzWkRVoxowFfaxsjICPPz861+jLZXPqA7PT0dadBftWoVDzzwgAJ9zKnlLy2XyWTo7+9fcrOPDz74oElP1FrFf48gCAiCgP7+/kV/Fa3EgO7atWsXWvlq4XcHtfylpcpbsbVU28UqTjKZDPfccw+XL19eODYzM7Mi0zOLlG6hOyn4S0uFbcVWS2MQN6Ojo4sCf9R6e3t59tlnFehF3T7SWmFm8NRKYxA3KzWjaWhoiFwup92wZIGCv7TUUl05fX19sZ9HXroBetTTNIMgYGhoSH34cgUFf2mppbpynnrqqSY9SWsMDw9HPkUTfhb05+fnFfilIgV/aalUKsX69esrnlu/fn2sWvzls3iCIOCZZ56JrLVfzNCpjVEkDAV/abmvfe1rrFmzZtGxNWvWxCpRWHEWz1LTWetVmid/fn5e6RYktFDB38z2mdlfmtkRM/t02bntZvZ24fzvL1XGzH7LzC6bWW/JsZSZvWNmPzSz+6KomHSOVCrFgQMHFuWeP3DgQMcEsFrz8ovn0ul0ZLN4ent7lSdflm3J4G9mtwM3uvutwH3A02WXPA18HrgN+KyZ3VStjJndBXwSOFFy//XAo8B2YBvwkJlpHX+XKA527ty5E4CDBw92VECr1KKfmZlh165d/NzP/RzpdDqS1n4ikWDPnj2asSORCdPyHwReBXD3LHC1mW0AMLPrgQ/c/T13nwcOFa6vVuYVdx8FSjs5PwO84+4fuvtF4C3yHyQSc8UFXtPT0+RyOaanp7n//vs7KnVztXn5c3NzXLp0KZL3KE513bFjRyT3E4Fwi7w2ApMl358uHPuo8PV0ybn3gRuA/kpl3P14lfuX32NTpQfJZrMhHnex2dnZhsp1qk6q78MPP3zFAq8LFy7w8MMPs3Xr1lD3aHV9V2pefiKR4LHHHlsU8Ftd12ZTfVdWIyt8gwbO1SoT+tqBgYE6bpOXzWYbKtepOqm+p06dqno8bB1aVd9MJsPIyEjk8/JrpVropJ9tFFTf5ZucnKx6Lky3zwnyrfOia4GTVc5dVzhWq8xS9y/eQ2Ku2gKvdsnhU20gt7j/bVQzd4p58rXvrTRTmOD/OnAngJltBU64+1kAd58CNpjZFjNbDewoXF+1TAU/BD5tZlcVZgDdBvyg8SpJpxgbGyORSCw61i45fKoN5KbT6UV7DDdqcHBQefKlpZYM/u5+BJg0syPkZ+3sNrO7zexzhUuGgBfJB+yX3P14pTIAZjZqZt8n39L/rpntKQzyPgJ8D3gDeNzdP4y0ltKWUqkU4+Pji6Z4rmQOn/INUGoNLK9UgrW+vj4mJia0Gb20XrH10e6vo0eP5hpx7Nixhsp1KtW3somJiVwikciRn2mWA3JBEOSAXDKZzA0ODuZ6enpywMLXqF9DQ0NNqWtcqL7LV4ibFWOqUjpLV6iUOjpXGKwt3wmr1ibyjVC+fGlHCv7SFZqx+XsQBDz44IPqv5eOoOAvsZfJZFYkXXIppU2WTqPEbhJrxVk7K7UxfHEAV4FfOo2Cv8RG6aYoxVeUCdWKShOraV6+dCoFf2lb9UzN3L59O+l0OvJNUUoVW/lKrCZxoD5/aUvFpG/FGTrFpG/AFYF3+/btHD58eEWeQ4O4ElcK/tKWKk3NvHDhAul0mnQ6vWLvq2mZ0i0U/KUtNWNqZlEikVjRlcUi7Uh9/tKWVjK5WxAE9PX1NSWlhEi7UvCXtrRSyd1Wr17NwYMHOXPmDPPz8x21a5hIlBT8pS1FHZB7enoYGhri8uXLCvYiKPhLSPVMu2wXyWRyYT7+xx9/rBk7IiUU/GVJUe61W75BSumruFlKUV9fX0PPm0gkmJiYUJeOSA0K/rKkatMuR0dHQ9+jGPRr7YA1MzPDvffeu/AB8NRTT4W+fxDkd//UAK5IOAr+sqRq0y7LV9NW6xoqrr4Ns+3hpUuXFj5UUqkUQ0NDC4G9kquuuoqJiQnm5+fJ5XJq7YuEpOAvS6o17bK3t3ehG2fnzp2LuobS6TRBENS9+rb0w2b//v0cPHiQZDIJ5Adu4Wf9+UeOHFGwF2mAgr8saWxsrGrr+/z58wst+qhSJpd/2KRSKaamphYGbtXCF1k+BX9ZUiqVWtFc+OXaYQN3kbhT8JcFtaZzNjrzpl5DQ0Nq0Ys0gYJ/hNp5LvxSz1ZrOmcmk+Gjjz5a0efTpigizRUqsZuZ7QNuAXLAiLu/U3JuO/AVYA445O5PVCtjZp8CDgI9wElgp7v/1MwuA2+VvOWgu0e7i/YKqycFcbOFebZa0znPnTsX+YYoRcqiKdIaS7b8zex24EZ3vxW4D3i67JKngc8DtwGfNbObapT5MvDH7v5LwF8D9xaOf+ju20peHRX4IZq58CslzLNV2wRleno61BTNsIaGhsjlcgsv7YQl0hphun0GgVcB3D0LXG1mGwDM7HrgA3d/z93ngUOF66uV2QZ8p3DfPwW2R1eV1qo2F76ZqYmrqRXYt2zZwvDw8Io/g7p1RNpLmG6fjcBkyfenC8c+Knw9XXLufeAGoL9KmfXu/tOSazcV/nudmb0AJIGX3f2rlR4km82GeNzFZmdnGypXr40bN3Ly5MmKx5vx/kWV6rtq1aqqG5hPT0/zzDPPRP4ca9eu5cknn2THjh2Ljkf9b9Gsn2876Ka6guq70hrZzKX6csvq5yodLz32RWCC/PjAm2b2prsfLS8wMDAQ+iGLstlsQ+XqtXfv3kX96pDPMbN3796F989kMoyOjvLuu++yefNmxsbGIu/yqFTfaoF/pQwNDTWthd+sn2876Ka6guobhcnJyarnwnT7nCDfai+6lvxgbaVz1xWOVStzzsw+UXYt7v6su59z9/PAYeAXQjxXW0mlUoyPj5NMJq/YJKQ0r00UydHqVVwdu9LUtSPSOcIE/9eBOwHMbCtwwt3PArj7FLDBzLaY2WpgR+H6amXeID84TOHrn1neC2YWFO5xG/CTqCrYTMWVqKWbhBRn2lQaNF3JAeHSqZ1nzpxZkfcoTZmswVuRzrJkt4+7HzGzSTM7AswDu83sbvIzdF4BhoAXC5e/5O7HgePlZQrnvwT8iZk9AEwDz7v7ZTN7D3i7cO133P3tCOvYUiMjI1fMtClVbTB2Ocqndp4/fz6ye/f29vLss88qyIt0uFB9/u7+SNmhH5ecexO4NUQZ3P0k8CsVjv9umOfoFMW+/TCBvZioLKr3/cIXvsDFixcju2eR5uOLxEsjA75SQ3mreylzc8tf0jA8PBzpjB0FepH4U3qHiFVaUFVLEAShBn2LffhBELB69epFO2BFFfjXrl3LxMSE+u5FuoCC/zKVBuUgCOruw8/lcjUHfYeHh1m1atXCTCGI5q+Fcn19fTz33HMK+iJdQt0+y5DJZLjnnnuWnfemdBVwPeMFy5FMJldknYGIdAYF/2UYGRmJJOFZLpejv7+f2dnZSGfmlAuCgAcffFDz8EVE3T6NKHb1RJnwbGZmZkUCfxAEC8nU5ufnFfhFBFDwr1tp3vt69fX1MTg4WHND8qgo4ItILQr+dchkMtx11111zebp6elZWAV75swZfvSjH63Yloi9vb3s2bOHXC6ngC8iNSn411A+kyedTteVJC2RSPD8888vDKpmMplIu4ogn7Gz2Mo/e/bsFVk0RUQq0YBvFfUu1irX09OzkNitKMo8PlqIJSLLoeBfQSaTYdeuXQ3Pp08kElcEfljexi6rVq3igQceUHeOiERC3T4szoDZ39/Pvffe23DgL03lXG7z5s1136+YJnlubk6BX0Qi0/XBv3T2Ti6XY2ZmhkuXLtV9n2K/ezGVcyVjY2MkEokl79Xb27tokFhdOyISta4P/vXm4qmkr68vVKu8dMOXcqUB/31ce0YAAAXHSURBVOzZswr4IrKiurrPP5PJLDuNQiKR4Kmnngp9fSqVUmAXkZbr2pZ/JpPh3nvvXdY9+vr6qvbvi4i0s65t+Y+MjDTUtw+aZikina/rWv6ZTIbe3t6GFlsVB3U1CCsina6rgv/w8DDpdLruBGrF5GiaaikicdEV3T7F/v1GunkGBwd54403VuCpRERaJ9bBf7l72yrwi0hchQr+ZrYPuAXIASPu/k7Jue3AV4A54JC7P1GtjJl9CjgI9AAngZ3u/lMzSwG/DcwD4+7+jeVWbDmBX7tciUjcLdnnb2a3Aze6+63AfcDTZZc8DXweuA34rJndVKPMl4E/dvdfAv4auNfM1gOPAtuBbcBDZnbNcis2Pj5e1/WrV69eWGRVa5WuiEgchBnwHQReBXD3LHC1mW0AMLPrgQ/c/T13nwcOFa6vVmYb8J3Cff+UfMD/DPCOu3/o7heBt8h/kCxLPbl51q1bxze/+U0FfBHpGmG6fTYCkyXfny4c+6jw9XTJufeBG4D+KmXWu/tPS67dVOUemyo9SDabDfG4eatWrVoy9/7atWt58sknF3Lg13P/djU7OxuLeoTVTfXtprqC6rvSGhnwrbUHYbVzlY7Xcy0AAwMDNd56sQceeKBmn39cB3Oz2Wxd/06drpvq2011BdU3CpOTk1XPhen2OUG+dV50LfnB2krnriscq1bmnJl9Yolri8eXZf/+/QwNDV1xvJgiOY6BX0QkrDDB/3XgTgAz2wqccPezAO4+BWwwsy1mthrYUbi+Wpk3yA8OU/j6Z8APgU+b2VVm1ku+v/8HUVRu//79HDt2jFwut/DS6lwRkRDdPu5+xMwmzewI+amYu83sbuBDd38FGAJeLFz+krsfB46Xlymc/xLwJ2b2ADANPO/ul83sEeB75KeFPu7uH0ZYRxERKROqz9/dHyk79OOSc28Ct4Yog7ufBH6lwvFvA98O8ywiIrJ8XZXbR0RE8hT8RUS6kIK/iEgXCnK5XKufIZTJycnOeFARkTZy8803V1w71THBX0REoqNuHxGRLqTgLyLShWK9mUutfQg6mZn9PPBfgX3u/p+buU9CK5jZHuCXyP++/kfgHWJYXzNLAN8EPgmsA54gv6YmdnUtVUj58r/I1/cwMa2vmW0D/gvwk8Kh/wnsoUX1jW3LP8Q+BB2psP/BH5H/n6SoafskNJuZ/TLw84Wf468B/4n41vefAUfd/XbgXwBfJb51LfUfgA8K/x33+v6Fu28rvP4tLaxvbIM/NfYh6HA/Be5gcfK7bTRpn4QWeBP4jcJ//z9gPTGtr7u/5O57Ct9+CvgbYlrXIjP7B8BNwH8rHNpGjOtbwTZaVN84d/vU2oegY7n7x8DHZlZ6eFn7JLQzd58Dzhe+vY/8hkG/Gtf6AhRyYv198okS34hzXYE/BH4T2FX4Pra/ywU3mdl3gGuAx2lhfePc8i9Xax+COKl7n4ROYGa/Tj74/2bZqdjV191/EfjnwASL6xGruprZXcBfuvv/rXJJrOoL/BX5gP/r5D/svsHiBnhT6xvn4F9rH4K4ado+Ca1gZr8KjAL/pJDxNZb1NbObC4P3uPuPyAeGs3Gsa8E/BX7dzP478G+A3yemP1sAd//bQtdezt3/N3CKfHd0S+ob5+BfdR+CGGrqPgnNZGZ/F9gL7HD34qBgXOv7j4F/B2BmnwR6iW9dcfd/6e6fdvdbgK+Tn+0T2/qaWcrMvlj4743kZ3UdoEX1jfUKXzP7A/L/Q80Du939x0sUaXtmdjP5ftItwGXgb4EU+SmC68jvk3BPYZ+EO4GHyU91/SN3z7TimZfDzO4HHgOOlxzeRT5YxKq+hRbgN8gP9n6CfBfBUeBPiFldy5nZY8AU+X09YllfM/s7wAvAVcBa8j/f/0GL6hvr4C8iIpXFudtHRESqUPAXEelCCv4iIl1IwV9EpAsp+IuIdCEFfxGRLqTgLyLShRT8RUS60P8HChZPUNJqrssAAAAASUVORK5CYII=\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BjzPK5sK5gHT"
      },
      "source": [
        "Still flat. Not obviously much faster than recursion with memoization, but \r\n",
        "asymptotically the memory use would matter a lot. Also much 'tighter', make me think the cache resize is where we got the 'noise' in the memoization runtime graph. Allocating more memory is inherently less predictable in runtime than doing a calculation. This is O(1) space complexity, and has no such memory issues."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yzPgxteqqLfo"
      },
      "source": [
        "# In the original post this is called 'neighbors_map' even though it is referred to in the later code as 'neighbors_matrix'.\n",
        "# This causes an unassigned value error. This is why we can't have nice things.\n",
        "NEIGHBORS_MATRIX = {\n",
        "  0: (0, 0, 0, 0, 1, 0, 1, 0, 0, 0),\n",
        "  1: (0, 0, 0, 0, 0, 0, 1, 0, 1, 0),\n",
        "  2: (0, 0, 0, 0, 0, 0, 0, 1, 0, 1),\n",
        "  3: (0, 0, 0, 1, 0, 0, 0, 0, 1, 0),\n",
        "  4: (1, 0, 0, 1, 0, 0, 0, 0, 0, 1),\n",
        "  5: (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),\n",
        "  6: (1, 1, 0, 0, 0, 0, 0, 1, 0, 0),\n",
        "  7: (0, 0, 1, 0, 0, 0, 1, 0, 0, 0),\n",
        "  8: (0, 1, 0, 1, 0, 0, 0, 0, 0 ,0),\n",
        "  9: (0, 0, 1, 0, 1, 0, 0, 0, 0, 0),\n",
        "}"
      ],
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9KbIceaSqXEH"
      },
      "source": [
        "def matrix_multiply(A, B):\n",
        "    A_rows, A_cols = len(A), len(A[0])\n",
        "    B_rows, B_cols = len(B), len(B[0])\n",
        "    result = list(map(lambda i: [0] * B_cols, range(A_rows)))\n",
        "\n",
        "    for row in range(A_rows):\n",
        "        for col in range(B_cols):\n",
        "            for i in range(B_rows):\n",
        "                result[row][col] += A[row][i] * B[i][col]\n",
        "\n",
        "    return result\n",
        "\n",
        "def count_sequences_with_matrices(start_position, num_hops):\n",
        "    # Start off with a 10x10 identity matrix\n",
        "    accum = [[1 if i == j else 0 for i in range(10)] for j in range(10)]\n",
        "\n",
        "    # bin(num_hops) starts with \"0b\", slice it off with [2:]\n",
        "    for bit_num, bit in enumerate(reversed(bin(num_hops)[2:])):\n",
        "        if bit_num == 0:\n",
        "            import copy\n",
        "            power_of_2 = copy.deepcopy(NEIGHBORS_MATRIX)\n",
        "        else:\n",
        "            power_of_2 = matrix_multiply(power_of_2, power_of_2)\n",
        "\n",
        "        if bit == '1':\n",
        "            accum = matrix_multiply(accum, power_of_2)\n",
        "\n",
        "    return matrix_multiply(accum, [[1]]*10)[start_position][0]"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 262
        },
        "id": "wGSA-hIfqavL",
        "outputId": "575289d4-690e-4d0e-dd26-d58aa3d7245c"
      },
      "source": [
        "make_dialer_profile_graph(count_sequences_with_matrices, 512)"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXkAAAD1CAYAAAC1BoUqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO2df3Ac53nfPweQGOpA0bFOqUG5IWDZft+Qzkw6YB2L9jhUAtmOXaaejBQ3M2eZdsUwhiSHZRp27CBRZHngptSkLJXYVjiVGkl3saVMxqrL0D9qNZHkUm1kTONpLORV3ZSga4gVBdmSKAqmQl7/wB28WOze7e7t3e3tfT8zOzjs7rv7Pvvju88+7/O+W6jVagghhMgnQ72ugBBCiM4hkRdCiBwjkRdCiBwjkRdCiBwjkRdCiBwjkRdCiByzodcV8DM3N6ecTiGESMDOnTsL/nmZE3mAnTt3Jio3Pz/P9u3bU65NNhkkW0H25plBshU6Z+/c3FzgfIVrhBAix0jkhRAix0jkhRAix0jkhRAix0jkhRAix0jkhRCiDarVKhMTEwwNDTExMUG1Wu11ldaQyRRKIYToB6rVKvv37+f8+fMALCwssH//fgDK5XIvq7aKPHkhhEjIzMzMqsA3OH/+PDMzMz2q0Xok8kIIkZDTp0/Hmt8LJPJCCJGQbdu2xZrfCyTyQgiRkNnZWYrF4pp5xWKR2dnZHtVoPRJ5IYRISLlc5tixY4yPj1MoFBgfH+fYsWOZaXQFZdcIIURblMvlTIm6H3nyQgiRYyTyQgiRYyTyQgiRYyTyQgiRYyI1vFprjwDXADXggHPuSc+y64BPAxeBE865T4WVsdZuBO4D3gS8BNzgnPt+ivYIIYTw0NKTt9buBt7snNsF3ATc5VvlLuB64B3Au621O5qU+VXgrHPuZ4AHgXemY4YQQoggooRrpoCHAZxz88BrrbVbAKy1VwPPO+e+65y7BJyorx9W5heBan3+Mefcl1K2RwghhIcoIj8GnPX8f7Y+L2jZs8DWJmUmgPdaa//SWvsFa+0VCesthBAiAkk6QxUSLCt4/jrn3Cettb8NfAI45F95fn4+QbVgeXk5cdl+Y5BsBdmbZwbJVui+vVFEfpEfee4AVwHPhCx7fX3ehZAy/w94tD7vq8Ang3a4ffv2CNVaz/z8fOKy/cYg2QqyN88Mkq3QOXvn5uYC50cJ13wNuAHAWjsJLDrnXgJwzp0CtlhrJ6y1G4A99fXDynwZ+IX6dncCLqE9QgghItDSk3fOnbTWzllrTwKXgFustR8GXnDOfRGYBj5fX/1B59zTwNP+MvXldwH3WWtvAs4Be9M1RwghhJdIMXnn3Md9s77lWfYYsCtCGZxz54FfjllHIYQQCVGPVyGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDESeSGEyDEboqxkrT0CXAPUgAPOuSc9y64DPg1cBE445z4VVsZa+8fATmCpXvxO59yfp2SLEEIIHy1F3lq7G3izc26XtXY7cC+wy7PKXcB7gO8Bj1pr/wz48SZlPuGcO56mEUIIIYKJEq6ZAh4GcM7NA6+11m4BsNZeDTzvnPuuc+4ScKK+fmgZIYQQ3SNKuGYMmPP8f7Y+78X637OeZc8CbwSuDCkDcKu19jfq697qnHvOv8P5+fmo9V/D8vJy4rL9xiDZCrI3zwySrdB9eyPF5H0UEixrzH8AWHLO/bW19uPA7cCt/pW3b9+eoForD4ekZfuNQbIVZG+eGSRboXP2zs3NBc6PIvKL/MgLB7gKeCZk2evr8y4ElXHOPe2Z9yXgcxH2L4QQIiFRYvJfA24AsNZOAovOuZcAnHOngC3W2glr7QZgT339wDLW2j+rx/EBrgX+JkVbhBBC+GjpyTvnTlpr56y1J4FLwC3W2g8DLzjnvghMA5+vr/5g3Vt/2l+mvvwPgQetteeBc8BH0jVHCCGEl0gxeefcx32zvuVZ9hhrUyrDyuCc+wvgrTHrKIQQIiHq8SqEEDlGIi+EEDlGIi+EEDlGIi+EEDlGIi+EEDlGIi+EEDlGIi+EEDlGIi+EEDlGIi+EEDlGIi+EEDlGIi+EEDlGIi+EEDlGIi+EEDlGIi+EEDlGIi+EEDlGIi8Gmmq1ysTEBENDQ0xMTFCtVntdJSFSRSIvBpZqtcr+/ftZWFigVquxsLDA/v37JfQiFll3FCTyYmCZmZnh/Pnza+adP3+eAwcO9KhGot/oB0dBIi8GltOnTwfOX1paytRNKrJLmKMwMzPToxqtRyIvBpZt27aFLsvSTSqyS5ijEDa/F0jkxcAyOzsbuixLN6nILmGOQjMHottI5MXAUi6XKZVKgcuydJOK7DI7O0uxWFwzr1gsNnUguo1EXgw0R48ezfxNKrJLuVzm2LFjjI+PUygUGB8f59ixY5TL5V5XbZUNva6AEL2kcTPOzMxw+vRptm3bxuzsbKZuUpFtyuVypq8XibwYeLJ+kwrRDpFE3lp7BLgGqAEHnHNPepZdB3wauAiccM59KkKZ9wBfcc4V0jJECCHEelrG5K21u4E3O+d2ATcBd/lWuQu4HngH8G5r7Y5mZay1m4BPAM+kY4IQQogwojS8TgEPAzjn5oHXWmu3AFhrrwaed8591zl3CThRXz+0DPBbwGeAC2kaIoQQYj1RRH4MOOv5/2x9XtCyZ4GtYWWstQb4aefcnyauscgkWR+/Q4hBJUnDa7M4etiyxvwjwK+32sH8/HzcOgGwvLycuGy/kSVbjx8/zm233cby8jIACwsL7Nu3j8XFRfbs2ZPKPrJkbzcYJHsHyVbovr1RRH6RH3nuAFfxo3i6f9nr6/MuBJT5IfCTQNVaC7DVWvuoc263f4fbt2+PWv81zM/PJy7bb2TJ1ve+972rAt9geXmZz3zmMxw6dCiVfXTb3mq12tO0yiyd304zSLZC5+ydm5sLnB8lXPM14AYAa+0ksOicewnAOXcK2GKtnbDWbgD21NcPKrPgnHujc+4a59w1wDNBAi/6j7AhABYWFrpck3Toh5EFRf/RCGm+5S1v6WpIs6XIO+dOAnPW2pOsZMncYq39sLX2l+qrTAOfBx4HHnTOPR1UpjPVF1kgbAiAQqHQl8LYDyMLiv6ip45DrVbL1PTNb36zlpSnnnoqcdl+I0u2ViqVWqFQqLHSJ2LNND4+nso+umlvmC2FQqFrdcjS+e00g2Dr+Ph4R++PWq1Wq2vnOk3V2DWibcrlMrVaLXBZP47meMUVVwTO16BlIim9HJJYIi9SIS+jOVarVV588cV180dGRjRomUhML4cklsiLtsmTMM7MzPDqq6+um3/55ZdrfBuRmF4OSSyRF22TJ2EMe31+/vnnu1wTkSd6OSSxRF60TZ6EsR++9CP6k3K5zKlTp/j2t7/NqVOnuuYASeRF2+RJGPvhSz8if3RyWBCJvGibMGF83/ve13fj2fTDl35Evuh0Dr1EXqTCZZddtvq7VCqxd+9e7rvvvr7sNdp4rb506VJXX6vFYNLpzncSedEWDS9kaWlpdd4rr7zCQw89pF6joudkeXTURt3Chv9IK4den/8TbRHmhfjnNejHzlGiP2k4II1rsfE2CfT87cxftyDSatOSJy/aIq5o92NjrIhHVrznLI9BFFQ3L2k29kvkRVvEEW1lqeSfLI3g2cuhBFrRrA6bN29OtbFfIi/aIiizJghlqQwGWfKes5DaG/RWc/z4cYaGwqX35ZdfTrcSQaOW9XLSKJTRyJKtlUoldJQ9Uhq9sdv2em0aHh5eHTGwUql0Zf9ZOr9xSDKCZ6dsrVQqtWKxuKYexWIxlXPYuD4KhULodRG0/40bN9Y2btwYeq/QxuiUYaNQ9lzU/ZNEPhpZtLWTw6l2096gmzNtkWhFFs9vFJJcA520tVKp1Eql0mo9hoaG2n5gT09Pr3uYBV0XzRyfVlMSx0hDDYuOk4feotVqlb1794Y2imWl4S6rZPEaeOWVV1Z/X7p0CSBxW0G1WuXuu+9eN7R20HXRTuw/1ZBSkPL3cpInH42s2hrlNTYJ3bC3mQfvnzpNVs9vFOJeA520tZU3HfctM8r2GnZ73yDiTEnfFuXJC9GCVmltXrLUqSZrZKnHcCtvOq633Wp9b1bR97///VjbBhgaGko9QUEiL1IjS+lzSYhzwycN2WQlh3xQaBX2CFre7BzFCaM0QkNxSFKmJUHufS8nhWuikUVb+73hNU5DWZKGsTjZHlk8v37SCs11uuE1LAQ3MjKyrs6tzlGz7xmnNSW9X5RdkzOyaGsnP4CdtZh8khsxzkPQb2+n2jqSEnSsCoVCbWpqKnY90zi3zY7P9PR04HEfHh6OnBFTKpVapgmnJfJJ7xeJfM7Ioq397snXamvFolQqrebIt/IAoxDnIei1t5P53kmJ+tZTKBRq09PTTbfV7NwmzUcvFou16enp2A2vScS6VCrVpqenIzsI8uQl8pHIoq2dFKNe2OvPsW7c0EntSerJt/Iue+HdxxHDQqHQtG5h5zbq9RSWxRKljv4HbJLc9sb5a9UpMMrUzv0ikc8ZWbW131MovV78yMhIqg+spDH5qILaTv2inrekQpakM1Sz/TTqWKlUUvWa44Ts0nxQNB7a7VxfEvmckSVbuxEv7rS9UW/udkNPUY9VFE8+rfpF7cGZRADDhDDMVi+tHm7FYjFxLnpjaoR0vOfDf45a7aNUKq0en6jnamRkJPV7RiKfQdoRxyzYGhTOCBOIdum0vXFizN2gVUw+rfo1yxbxPzDaCUWk7cmnNbXKpInyEBkZGalNTU0liuen6RS1JfLGmCPGmCeMMSeNMW/1LbvOGPNX9eW/06yMMWaXMeYbxpi/MMZ8xRjz4/59DYrItxu/7rWtrYQnjcZWL522Nw2xSpNW2TVh4hO3fq0yRrwkzSBpdV3HicmnOQU1qnuFN8pAYmk9aDrpybfsDGWt3Q282Tm3C7gJuMu3yl3A9cA7gHdba3c0KfMbwIeccz8HPAH8aqv955UsDcmahFa9Q3s9ZnecTkfVapVCodBym70cg8Xfi/To0aOpjBHT7Dz5O/7E6QjUOJ7jbQ4x7f12cJoUi0UuXrwYuGxhYYEPfvCDvPrqqx3Zt5+O3/dByl9b66nfYYzZ5/n/b40xW+q/rzbGfMOz7BPGmI81K1P/v2CMOWaM+ZB/f4PiybebU95rW1t5dUk83mbhqzj2xn1LihoW6Gb2SpS0Qmh/GOQw2/0ZMVFDF95pamoqsa2d9OIb+fHdCAdFndIIA4Z58lG+8ToGzHn+P1uf92L971nPsmeBNwJXhpWx1v4CK579PFAJ2uH8/HyEaq1neXk5cdluMzY2xjPPPBM4P4oNvbY1rP4AGzZs4IUXXmBoaIixsTEOHjzInj17mm7v+PHj3HbbbSwvLwMr3tS+fftYXFxkz549sew9dOhQ4FvSoUOHmJycXLffsA8pe9m6dSuTk5NdO+Zh9vqPU8Mb3bVrV+T6HT9+nCNHjnDmzBk2bdoUuM7b3vY2FhcXueqqq0LPcyseeeQR7rzzztBz763H2NgYu3fv5tFHH+XMmTPAigOaNps2beKOO+5gcXGRH/zgB6lvPylR7/tEBCl/ba0nf8wY837P/98wxpj677cbY77oWbbPGPPpZmVqP/Lk/40x5rf8+8uSJ9/JrJG8xuRHR0djpx5WKpWm8dFaLZ69Ud+SonqLveh4lKQxMqyjkPcajtppp1QqpeJJh73RdTreHjQ1PPg09x21I9To6Gjouet0TD6KyN9ujPk1z/9/Z4y5vP57whjzhGfZ7xpjbg0rY4z5Jc+8nzHGnPDvLysi341ehv2cXeN/fW/k+IZdyElv9oYwx7E3ah2yGKZpkCStsJHK1yBs6IFuCmtQGKLZQ73TU62WTtZO436dnp5uacvGjRtrpVJp9T7/lV/5lY44j+2I/NuNMf+5/nvSG4Ovz/t2Xew3GGOeNCsEljHGfMsY84/qvz9mjDni319WRD6uWHWbXop8swdg3LaGVjdcEk8+6gM66s3cbSqVSm3r1q2BItAqLu4lCzFn//HrhQfvvQbTGGCs4dCEjYnjnzZs2LDm/02bNnXEcWg3hfL36qmQ3zDG/LQx5sMNr9wY87P1VMknjDG/GVamPu8f1+c9Zoz5qjHmH/j3lRWR7+RgW2nQS5Fv9gAMW+b3Mhs0u+G8whzX3lZvSVFu9qRj1CStU2OdsAdUlLQ+L+2IWbudjPznr0GvHzzNrtG4tjU+JZi0HmmjzlAxkScfTrMHYJgQhQlm2HH2jxCYtr1RejH2og0myQPUW+co22ol/o04c7tiGnT8uh0uinONdrseaSORj0kWR/7z0unhWZvR6gEYp6NO1OOc9rltdgOmtQ/vsY1yTJrVq1AoNBXIDRs2RBqGwD86Y9BwBu2OqJgkXbVQKKxrsPdPabxdtLpGuzXJk09IP2XXtEu7trbzEAtr0GsMKRs31BXWiJumvV6aecRp3HxJhiFo5V02e1A0jllYXRrXcKlUqo2Ojq6W8YcbhoeHa1NTU6k0igbF4tsNk4yOjrb1JuC9vtN4o2j1UIKVRlf/epmMyXdzypLIZ5l2bW03HNVsUKs0Mmz8D5y4Da/NHs7NbvA0br44YtYQ51ZlvOIcNHkfFmFeejcn7wO9l42t3mvPe27bfeAEiTdQ27Fjx7prz389Hj58uO1rLAiJfM5o19Z2G5abCXlaPU69D4WGva0EPMqIis084jREPo64Nt5a0hKxXotp0LnrZWNr2AdLohyrxnkcr/cviBt+C6NTOiWR72OChK3Xnnyrh0SU7JZWN7/3gfPUU0+1fHg0ayxs9fm2uPb78dobN9zRrjC3eoPq9uR/qPayLs3OV5S4fNwG5ChOkkReIr+GMGFr95Wv3YblOA+JpL0u/Z582D5LpVJqDWlpfaA76tRu/NubhdSr8EyzsdHTyEtPOoU9sKempmJtJ24WVCsk8hL5NYRdTFu3bk20PX9DnLcnXpxQRdSHRFIBDIrJd0MsknjyST3oNEIr3phvL4QUmj8Ye5XFEuawJE0NDWpITuokSeQzJvK9zrBJs1NW2mmhUY5NUvEJyq7ptJAlPRZJHj5pjYSY5gekG9dV3GXNGtQ7eb6Cjmmr+zTpm1PY8AxJtEEinyGRz0KufJqefLtx+CQk/VqOn7CYfFpTJz7QHfSdWP81VKlU2uo5mdYYMKOjo5G2FeUzga2OSyemqPdlq+uuG/eIRD5DIt8LUfSTZky+2Y3bKZK8rgdlRBw+fHj1fHjHUN+8eXPbApFk+AJ/2Msv5mEpdrDScWl6errnHXKaiXcrMYzivaYRXmvWdyCK5+6n2QO1EfrqtGMnke+ByIe9dmVl/Jo0smuaNYCl/dBqNwzhF91KpVLbtGlTR0UuzjHIUqpit0dzjHOc2vXkGyGtqB8aj3LewkTe+4GTTodoJfJdFvk0O/V0k7i2Nrvh2vFig7Ip0hqHvJsNinEe3L1s5PRfp2nH5FvtL27jfBrfhY3SI7qd8zY6Ohp7W+0gke+iyLfybrMQkw8jrq3Nbqgge4KEPCy32HtM0hTAbnrLcR7cvR5ky3t91mrJM0aS7i8qlUqlZU/doMkr4mneg1l5M5fId1HkmwlS1E497dDOtsO+ixlVmJsJXNCN1SzG7N1GWgLY7TBEnGPfa0/ef76S1Mc/xnmxWKxNTU2tOX+bN29OfL0HvSG3moI89DTfprPyZi6R76LIN7sIO33i2/VQ/LaGhUn8N3PQ5PdkkohGYxtpCGCUgZ/SnKJ+cLpBEgGLOg0PDzd9KAc1EifZT6MHcLMOakk95qRhmqD9ZTmFOCkS+Qx48v4v1XeCdr0Kv63tiKt/n+2kPbYbk9+8eXOkT6qFTUNDQ6sdvFqFCoaGhkLHNgmj042uDW/28OHD68Q+yNNNGqqJ+mBP02NOci2m7X33ut9LrSaR73pMvtmQuZ2kXQ/Fb2saDVwN4t6kQdkwjW20qlcj28EbXgoT0Vb55P5Ybqs3giReXJK0R+9Y71GO7caNG9elDob1Jk563qM+2JN4zO285fj3lxXvO00k8l3OrunVkz0Lnnwj5uo/BnEzNoaGhloet6BGOO8of2k13DaEPqoYx/EIk3rN3rHe2xHANGLxYSKZVU++VsuG950mEvkMdYbqJHE8lKCLvNE5yCvMcQUkLAUvSQ/MZt5VpdL6c2utPgQety5R143qqbZTN+8+2hFAf12j1scffw+7xtKMyacxXlFekcjnROSjeB9B+b/+cav9GQ8Q/DqfdEozi8X/XdYGUYVtvEm38k5NUT3VtLzTNEMsUeoURzjT9JjD3qaajdE+CAJfq0nkcyHyUb2iLPWcTGuKkyERJABpefNJ6xpGO/uJ21gaJyYf1O6wefPmngunt13GOwxFUH2yct92C4l8DkQ+anyz215r0NSJfPSkdjbKpdG5p1QqNX3bidtrMulx8n97NaxR2t8A7Q/Hhb0J+m3cuHFjzz3iuKGfrNy33UIinwORj5qp0Ouek0EdYNKY/HZGEe04n+iLsi3/AGB+EY1L0nq0GvIhTPyiXMtpNpamSdx6ZeW+7RYS+QyJfNIYZT948o189E6Ei+La6T22UcarGR4eXhXt4eHh2tTUVMvsoHbHzW/1IGw8WJpdL3HEL8q1nJVu+u3WSyKfDhL5mLSTbRB11LxexOS9/QDafciMjo6uiwm302sxShZO0PAK/n2m7eHGDTeFEUf85Mnnl0yKvDHmiDHmCWPMSWPMW33LrjPG/FV9+e80K2OM+QljzNeNMY/W/47595UVkU96A4WlMoZ1na9UKl0dp8UriO2GaaJ4r3GOZTshGu+20vZw4zQcNyNtTz6rHYUUk29O5kTeGLPbGHO8/nu7MeYJ3/Kn6uI9ZIx53BizI6yMMeY+Y8wH6r9vMcYc9u8vKyIfRyiihBi8QyUEdT7qptA3RCWNcFEUrzHqTd9OPaLkovfak087Jt/YZhbTEOPUSyKfDu2I/B3GmH2e///WGLOl/vtqY8w3PMs+YYz5WFgZY8yoMWa4Pu8Dxph7/PvLisg3EwrvBRz2ibegqfHhbP/8dj7/1o4gppHFEqczUaubPq2HTdoebpSwWtTtRxW/QRK+QbK1Vuu+yA/RmjHgrOf/s/V5QcueBbaGlXHOveycu2itHQZuAf4kwv57wuzsLMVicc28YrHIm970Jm688UYWFhao1WosLS1x4cKFSNtcWlpiaWlp3fxLly6lUueobNu2jWq1yn333ZfKtqJQLpc5deoUly5d4tSpU5TL5XXrlEqlltvZuHEjIyMja+YVi0VmZ2fX7OvYsWOMj49TKBQYHx/n2LFjgfuMymWXXbamntPT04m2H+U4CJEmGxKUKSRYtjq/LvAPAP/FOfdI0Mrz8/MJqgXLy8uJy/qZnJzk9ttv58iRI5w5c4axsTF2797NF77whVS23ys2bdrELbfcwqFDhzh//nwq20rrmL/rXe8KPL6FQoFarcbWrVs5ePAgwJrzcvDgQSYnJ9fUY3Jyki9/+ctrtpOknsePH+e2225jeXl5dd7LL7/MG97whlS2H0aa13LWGSRboQf2Brn3tbXhmtuNMb/m+f/vjDGX139PeGP0xpjfNcbc2qLM/caYT4btLyvhmiB6mfIYZxoeHg4MIXk7ALXb6Jp2/LfViKC9eqXvVQbLIIUwBsnWWi2b4ZqvATcAWGsngUXn3EsAzrlTwBZr7YS1dgOwp75+YBlrbRm44Jz73Qj7zRynT59OVK5UKrF58+aUaxPM0NAQFy9e5PLLL6dUKq2GEyqVCs8999xqeGB0dLTpdgqF4JeyUqlErVZLPdQwMzOz7s2iVqtx4sSJ1PaRhLBznvRaEKLbtBR559xJYM5aexK4C7jFWvtha+0v1VeZBj4PPA486Jx7OqhMfd1bgElr7V/Wp8+mbVAY1WqVK6+8kkKhQKFQ4Morr6RarUYuf/PNN6+0VCdgeXmZc+fOJSoLK8Lqj0OH0YjvLy0t8corr/DAAw+sE+Sbb765ZX1qtdo6oS8Wixw9ejRm7aORVTENa3OI2hYhRM8Jcu97OXUiXBPWySbsYxf+zIdufCg5bPJ/axbijTcTFFaIk83TrfS8VmGRXr3S9yoXfZBCGINka62WwRTKbk+dEPlmsfSGiDS7mbv9UWnvFDZ8b9IOOpVKpa0HRKdoJaa9FIJe5KIPkvANkq21mkS+IyIfRQTDeltmobE1yHPcunVrIqGOak8vek42E1MJQX4ZJFtrtWw2vPY9w8PDocsaOeNB+euwEhNuVj5NSqVS4L7Onz/PgQMHmJiYYGhoiImJCXbv3r0uj9+PP38cmse4N2/enFpeeRKUQy5E+gyEyF+8eDF02blz5/jgBz8Yunzbtm3s378/8b6npqZCM1WCCKvr0tLSageshYUFHn74Yfbu3bumQ06UDjphDYajo6O89NJLElghckaSzlB9x/j4OAsLC4HLwjz4BrOzs6uC97nPfW51fqFQ4Od//ud57LHHePXVV9eVayz/zne+EzkrZ2lpabXjTyuWl5c5ceIEp06dirTtBrOzs+zfv39NumKxWOSP/uiPYm1HCNEfDIQnHzREQVRmZma4+eabeeihh9bMr9VqPPLII4ECD7BhwwYef/zx0IdLGLXa+tTFMJKkF3aiy78QIrsMhCffELCZmRlOnz7NFVdc0dKDb7CwsLDGg49KmPhHoVarMT4+zunTp9m2bRvnzp0LrG/SXO1yuSxRF2JAGAhPHtY26nWr92lSxsfH1zRAHj16dN2byKZNm9Y1qgohhJ+BEXlY6fU6MTERO4TSKYJ6sgZlxASFWO644w5540KIlgyMyFerVfbv358ZgR8fH+e5557j3nvvjRQf96cX7tmzpwe1FkL0GwMRk4fgAbA6RalUahrzHxkZWfXWFR8XQnSSgfHkuzHQlXe0x/Hx8cB1hi/Noe8AAAfuSURBVIaGuPfeeyXsQoiuMDAi3+lRAwuFwppORGFflrr//vsl8EKIrjEwIj87O8vGjRs7tn3/Q0T56EKILDAwIl8ul9myZUsq2woaZz0onVFjsQghes3AiDzA888/33R5lA9JF4tFPvrRj8pDF0L0BQOTXQMrIZWwFMpSqcTRo0fXjesStI4EXQjRLwyUJx8Wlx8ZGVkV7717964b7jfoG6lCCNEP5Frk/d91PXDgAPv27VsTlhkaGuLChQurA5Hdd999a4b7bcTbJe5CiH4ktyJfrVb5yEc+sqZT0tLSEvfccw8f+MAHVoW+8eHrhYUF7r777nWhmvPnzzMzM9O9igshRIrkNiY/MzMTOBLkhQsXuPvuuwPHbA8bx70bHamEEKIT5NaTbybMUT/i0aDTHamEEKJT5E7kGyNNxhXyBlFz4IUQoh/IlcgfP368rZEmlQMvhMgbuYrJHzlyJPFIk8qBF0LkkVx58mfOnIm87vDw8Kq3rhx4IUReieTJW2uPANcANeCAc+5Jz7LrgE8DF4ETzrlPNStjrf114PeB1zrnzqVoC2NjYzzzzDMt1xsZGdFwv0KIgaClJ2+t3Q282Tm3C7gJuMu3yl3A9cA7gHdba3eElbHWfgh4HbCYngk/4uDBg+saToO4/PLLJfBCiIEgSrhmCngYwDk3D7zWWrsFwFp7NfC8c+67zrlLwIn6+mFlvuicm2HFu0+dPXv2RMqqaTVQmRBC5IUo4ZoxYM7z/9n6vBfrf896lj0LvBG4MqiMc+7pKJWan5+Psto6lpeX2bp1a8uQzdjYWOJ9ZIXl5eW+tyEOsje/DJKt0H17k2TXNIuHhC1rHUPxsH379jirrzI/P8+dd97JjTfeGOrRFwoF7rzzzsT7yArz8/N9b0McZG9+GSRboXP2zs3NBc6PEq5ZZMVjb3AV8EzIstfX5zUr03H8n93z8tGPflTxeCHEwBBF5L8G3ABgrZ0EFp1zLwE4504BW6y1E9baDcCe+vqhZTpBo5frjh07uPHGG3n55ZfXrVMqlahUKnz2s5/tVDWEECJztAzXOOdOWmvnrLUngUvALdbaDwMvOOe+CEwDn6+v/mA97v60vwyAtXYGeBcrXv6XrbVPOOf+VTsGVKvVNR/6CArTFAoFdXQSQgwkkWLyzrmP+2Z9y7PsMWBXhDI452aBVAeCmZmZadnLtVarMTMzI5EXQgwcfd/jNeowwBouWAgxiPS9yEcdBljDBQshBpG+F/nZ2dmm2TSg4YKFEINL34t84+PbYWi4YCHEINP3Ig/w0EMPhS7TR7iFEINMLkTe+7FuP/oItxBikMmFyDdDWTVCiEEmFyJfKpVClymrRggxyORC5I8ePcrQ0HpTRkZGlFUjhBhociHy5XKZ+++/n9e85jWr80qlkr7+JIQYeHLzIe9yuczk5ORADVkqhBCtyIUnL4QQIhiJvBBC5BiJvBBC5BiJvBBC5BiJvBBC5JhC2Aeve8Xc3Fy2KiSEEH3Czp07C/55mRN5IYQQ6aFwjRBC5BiJvBBC5Jhc9Hi11h4BrgFqwAHn3JM9rlJqWGt/CviPwBHn3B9aa38CeAAYBp4BbnTO/dBaWwb+BXAJOOacu6dnlU6ItfYw8E5Wrst/DTxJfm0tAn8MvA7YBHwK+BY5tRfAWnsZ8Des2PoIObXVWnst8KfAt+uz/idwmB7Z2/eevLV2N/Bm59wu4Cbgrh5XKTWstaPAH7ByQzS4A/iMc+6dwHeAf15f7zbgOuBa4KC19oouV7ctrLU/B/xU/Tz+AvDvyKmtdX4R+KZzbjfwAeDfkm97AX4beL7+O++2Puqcu7Y+fYwe2tv3Ig9MAQ8DOOfmgddaa7f0tkqp8UPgfcCiZ961wJfqv/8TKxfI24AnnXMvOOdeAf4r8I4u1jMNHgN+uf77B8Ao+bUV59yDzrnD9X9/Avi/5Nhea+1PAjuAP6/Pupac2hrCtfTI3jyEa8aAOc//Z+vzXuxNddLDOff3wN9ba72zR51zP6z/fhbYyoq9Zz3rNOb3Dc65i8DL9X9vAk4A78mjrV6stSeBfwjsAb6eY3t/H7gVaHyQOZfXsYcd1tovAVcAn6SH9ubBk/ezLk80x4TZ2rfHwFr7flZE/lbfotzZCuCcezvwT4EKa23Jjb3W2g8BTzjn/k/IKrmxtc7/YkXY38/KQ+0e1jrUXbU3DyK/yMoTscFVrDRs5JVz9QYsgNezYr//GDTm9xXW2vcAM8B7nXMvkG9bd9Yb0XHO/TUrIvBSTu39J8D7rbX/DdgH/A45PrfOue/Vw3E159z/Bs6wEkbuib15EPmvATcAWGsngUXn3Eu9rVJH+Tpwff339cBXgP8OvNVa+2PW2s2sxPUe71H9EmGtfQ1wJ7DHOddonMulrXV+FviXANba1wGbyam9zrl/5px7q3PuGuDfs5Jdk0tbAay1ZWvtb9Z/j7GSQfUf6JG9uejxaq39PVZumkvALc65b/W4Sqlgrd3JSixzAngV+B5QZiX1bhOwAHzEOfeqtfYG4BAraaR/4Jyr9qLOSbHW7gduB572zN7LiijkylZYTSe8h5VG18tYeb3/JnA/ObS3gbX2duAU8FVyaqu19nLgT4AfA0ZYObf/gx7ZmwuRF0IIEUwewjVCCCFCkMgLIUSOkcgLIUSOkcgLIUSOkcgLIUSOkcgLIUSOkcgLIUSOkcgLIUSO+f/I4qEr8gxpGAAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fo7brOfC6Udo"
      },
      "source": [
        "This is an interesting graph.\n",
        "\n",
        "Our first real surprise: For the values tested, this is actually slower than either the memoized or dynamic programming solution.\n",
        "\n",
        "The argument for this algorithm being O(log n) seems pretty sound, but big-O is asymptotic performance. For these (relatively low) values, the overhead on handling matrices (in pure python, no less) is higher than the difference between O(log n) and O(n).\n",
        "\n",
        "To eyeball the graph, there are a few interesting things. First, the spread is a lot more dramatic than the previous one: this, again, appears noisy. But it doesn't actually appear to be all random noise: it has a period. What kind of period? If I had to hazard a guess, that big drop in the middle is where we hit 256 ... ie, a power of two, requiring fewer intermediate matrix multiplications.\n",
        "\n",
        "Within the periods there appear to be periods, so probably there is a period for each power of two. This again makes sense: if we are below 3^32 but approaching 2^16, the runtime will drop when we hit 2^16. At 2^16 - 1, we are performing a matrix multiplication for each power of two up to 15, and at 2^16 we are only performing one for that range.\n",
        "\n",
        "And so on for each power of two. The 'worst' runtime relative to input in a range will always be the one with the most one bits in its binary representation, and a power of two minus one is mostly ones bits."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "w7nvgtuiIR3W"
      },
      "source": [
        "# Verifying Asymptotic Performance Without Making a Graph\r\n",
        "\r\n",
        "To verify that this is in fact asymptotically faster, rather than running all values up to a specified one (which is what the make_knight_dialer_graph function does) we can simply run the function for a large value several times. We can assume that noise will cancel out over multiple runs, and believing the analysis sound we will expect the O(log n) solution to outperform the O(n) one."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lSJ78hexIQBQ",
        "outputId": "8bfdf7d4-8b32-44c5-81d3-cc9621bc70ef"
      },
      "source": [
        "num_hops = [65535 for _ in range(1, 32)]\r\n",
        "starting_positions = [1 for _ in range(1, 32)]\r\n",
        "args_lists = list(zip(starting_positions, num_hops)) # A fun exercise: Why does this have to be a list instead of a zip?\r\n",
        "\r\n",
        "times_for_matrices = profile(count_sequences_with_matrices, args_lists)\r\n",
        "\r\n",
        "print(\"Runtime for the matrix solution:\")\r\n",
        "print(sum(times_for_matrices))\r\n",
        "\r\n",
        "times_for_dp = profile(count_sequences_dynamic_programming, args_lists)\r\n",
        "\r\n",
        "print(\"Runtime for the dp solution:\")\r\n",
        "print(sum(times_for_dp))"
      ],
      "execution_count": 16,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Runtime for the matrix solution:\n",
            "25.546484231948853\n",
            "Runtime for the dp solution:\n",
            "61.77008271217346\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AT1MAfUeRPYy"
      },
      "source": [
        "Since those are full seconds, the O(n) solution chugged along for something of an eon of extra time in computer time and we can declare the O(log n) solution the winner.\r\n",
        "\r\n",
        "While writing and debugging this I noticed something else. See if you can spot it:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "K1OF960sR9Yk",
        "outputId": "8e8be5a9-1f90-44a8-972c-628a43303b27"
      },
      "source": [
        "print(count_sequences(1, 8))\r\n",
        "print(count_sequences_naive_recursion(1, 8))\r\n",
        "print(count_sequences_with_memo(1, 8))\r\n",
        "print(count_sequences_dynamic_programming(1, 8))\r\n",
        "print(count_sequences_with_matrices(1, 8))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "712\n",
            "712\n",
            "712\n",
            "712\n",
            "613\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "X787UsSGTkZg"
      },
      "source": [
        "One of these things just isn't the same. Could the problem be our matrix multiply?"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hWvfbtPpViSV",
        "outputId": "a7b1c6f0-74e9-4f2c-e08b-1f897dade91d"
      },
      "source": [
        "import numpy as np\r\n",
        "\r\n",
        "A = [[8, 6, 7],\r\n",
        "    [5, 3, 0],\r\n",
        "    [9, 9, 9]]\r\n",
        "\r\n",
        "B = [[3, 1, 4],\r\n",
        "    [1, 5, 9],\r\n",
        "    [2, 6, 5]]\r\n",
        "\r\n",
        "print(np.matrix(A) @ np.matrix(B))\r\n",
        "\r\n",
        "print(matrix_multiply(A, B))"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[ 44  80 121]\n",
            " [ 18  20  47]\n",
            " [ 54 108 162]]\n",
            "[[44, 80, 121], [18, 20, 47], [54, 108, 162]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dOlCMe2cXDg5"
      },
      "source": [
        "Either Numpy is wrong or this matrix multiply is good, at least outside of weird edge cases. (Numpy is a surprise tool that will help us later.)\r\n",
        "\r\n",
        "Is the NEIGHBORS_MATRIX correct? I confess that I cannot easily read off its correctness or incorrectness, and it will be easier to write a script that outputs which keys allow you to reach which other keys and then compare that against my phone keypad."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "AjR2X-F9Y3wC",
        "outputId": "e2f3f0e4-b253-41e7-a9c0-d1f0b32af6b4"
      },
      "source": [
        "for origin in NEIGHBORS_MATRIX.keys():\r\n",
        "  for destination, reachable in enumerate(NEIGHBORS_MATRIX[origin]):\r\n",
        "    if reachable:\r\n",
        "      print((origin, destination))"
      ],
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "(0, 4)\n",
            "(0, 6)\n",
            "(1, 6)\n",
            "(1, 8)\n",
            "(2, 7)\n",
            "(2, 9)\n",
            "(3, 3)\n",
            "(3, 8)\n",
            "(4, 0)\n",
            "(4, 3)\n",
            "(4, 9)\n",
            "(6, 0)\n",
            "(6, 1)\n",
            "(6, 7)\n",
            "(7, 2)\n",
            "(7, 6)\n",
            "(8, 1)\n",
            "(8, 3)\n",
            "(9, 2)\n",
            "(9, 4)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BscDeBeRZvaq"
      },
      "source": [
        "(3, 3) is our mistake. It should be (3, 4)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fRENREFLZtOp",
        "outputId": "34e87c75-a4e8-4563-afbb-a67b15e528c8"
      },
      "source": [
        "NEIGHBORS_MATRIX = {\r\n",
        "  0: (0, 0, 0, 0, 1, 0, 1, 0, 0, 0),\r\n",
        "  1: (0, 0, 0, 0, 0, 0, 1, 0, 1, 0),\r\n",
        "  2: (0, 0, 0, 0, 0, 0, 0, 1, 0, 1),\r\n",
        "  3: (0, 0, 0, 0, 1, 0, 0, 0, 1, 0),\r\n",
        "  4: (1, 0, 0, 1, 0, 0, 0, 0, 0, 1),\r\n",
        "  5: (0, 0, 0, 0, 0, 0, 0, 0, 0, 0),\r\n",
        "  6: (1, 1, 0, 0, 0, 0, 0, 1, 0, 0),\r\n",
        "  7: (0, 0, 1, 0, 0, 0, 1, 0, 0, 0),\r\n",
        "  8: (0, 1, 0, 1, 0, 0, 0, 0, 0 ,0),\r\n",
        "  9: (0, 0, 1, 0, 1, 0, 0, 0, 0, 0),\r\n",
        "}\r\n",
        "\r\n",
        "print(count_sequences_with_matrices(1, 8))"
      ],
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "712\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ha4Y6pj_vE-0"
      },
      "source": [
        "Much better. It's possible that this glitch was causing more zero values and therefore a faster runtime, and gave this implementation an advantage, so we'll need to run our race again."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5sNng9SmaOY_",
        "outputId": "655999ef-05b3-4dcd-821e-c4fcf834221a"
      },
      "source": [
        "num_hops = [65535 for _ in range(1, 32)]\r\n",
        "starting_positions = [1 for _ in range(1, 32)]\r\n",
        "args_lists = list(zip(starting_positions, num_hops))\r\n",
        "\r\n",
        "times_for_matrices = profile(count_sequences_with_matrices, args_lists)\r\n",
        "\r\n",
        "print(\"Runtime for the matrix solution:\")\r\n",
        "print(sum(times_for_matrices))\r\n",
        "\r\n",
        "times_for_dp = profile(count_sequences_dynamic_programming, args_lists)\r\n",
        "\r\n",
        "print(\"Runtime for the dp solution:\")\r\n",
        "print(sum(times_for_dp))"
      ],
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Runtime for the matrix solution:\n",
            "5.677034616470337\n",
            "Runtime for the dp solution:\n",
            "61.94935727119446\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5NMrS3fW0L-4"
      },
      "source": [
        "Not at all! It turns out it's much faster with the error gone. Why? I would assume the (3, 3) value was causing the value in (3, 3) to grow significantly faster than it would otherwise, which in turn caused the arithmetic to need larger numbers, consuming more resources.\r\n",
        "\r\n",
        "Now let's try to compare the python @cache decorator with hand-implemented caching, and numpy with our handrolled matrix multiply."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4xVfFUHhz7Uj"
      },
      "source": [
        "import functools\r\n",
        "\r\n",
        "@functools.lru_cache()\r\n",
        "def count_sequences_with_imported_cache(position, num_hops):\r\n",
        "    if num_hops == 0:\r\n",
        "        return 1\r\n",
        "    else:\r\n",
        "        num_sequences = 0\r\n",
        "        for neighbor in neighbors(position):\r\n",
        "            num_sequences += count_sequences_with_imported_cache(neighbor, num_hops - 1)\r\n",
        "        return num_sequences\r\n",
        "    return res"
      ],
      "execution_count": 22,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 273
        },
        "id": "QyHztQ-u4S-p",
        "outputId": "d869fbd0-e207-4443-e211-0faedefd5086"
      },
      "source": [
        "make_dialer_profile_graph(count_sequences_with_imported_cache, 512)"
      ],
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAEACAYAAACTXJylAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3df4wkaX3f8Xfv7C7L7IYlHts3k4Pt1UmpL3s6y2hWTu4OGQ4N4sd5CcJnDKIJdoI10QQie8Er5Iwha05D0CIYHxwOmhjxIz1G5yB+OMvyIywmd8ARbicGATN6IMgze3A7ukOruwBzc8Bt5Y/pXnp6q7qrqquqq6o/L6k009Vd3c9TP7711PM89VTN931ERKQ89gw7ASIiEo8Ct4hIyShwi4iUjAK3iEjJKHCLiJSMAreISMnszeuHzOwm4FPAonPu7pjLHgW+Bay0Zj3inHtFuikUESmHXAK3mR0E3gucH+BrnHPutnRSJCJSXnmVuJ8Abgfe3J5hZjcCdwM+8GPgD51zj+aUHhGR0sqljts59wvn3ONds98L/Dvn3AzweeD1fb5m0sw+ZmZfNbNGJgkVESmB3Oq4A/wL4L+aGcBTgAfMbBr4q67PfYqdkvlbgCZwGPi6mX3ROXcpx/SKiBTCMAP3FvB851z3YCk3h3z+g62/PzKzC8CzAAVuERk5w+wO+E3gxQBm9iozmwn7oJk938ze3fr/IPBs4Lu5pFJEpGBqeYwOaGbHgXcBR4GfAz8E5oF3AFeAx4FXO+cuhyy/F/hrwIAx4L845z4Y9FkRkarLJXCLiEh6dOekiEjJKHCLiJRMLr1KVlZWVB8jIpLA8ePHa93zcusOePz48djLrK2tcezYsQxSU0zKb3WNUl5B+U3LyspK4HxVlYiIlIwCt4hIyShwi4iUjAK3iEjJKHCLiJSMAreIjJzl5WWOHj3Knj17OHr0KMvLy8NOUizDHB1QRCR3y8vLzM7OsrW1BcDGxgazs7MANBrlGOpfJW4RGSnz8/NXg3bb1tYW8/PzQ0pRfArcIjJSLl68GGt+ESlwi8hIOXLkSKz5RaTALSIjZWFhgfHx8V3zxsfHWVhYGFKK4lPgFpGR0mg0WFpaol6vU6vVqNfrLC0tlaZhEtSrRERGUKPRKFWg7qYSt4hIyShwi4iUTKSqEjN7KvBt4E7n3Ic65r8AeDvwJHDOOXdnFokUEZFfilri/nMg6Ans7wHuAJ4DvNDMbkwrYSIiEqxv4DazZwE3Ap/umn8DcNk596Bz7gpwDpjJJJUiInJVlBL3u4A3BsyfBB7peP0wMJVGokREJFzPOm4zey1wv3PuH82s33dd80DLTmtrazGTBtvb24mWKyvlt7pGKa+g/GatX+Pk7wA3mNkJ4BnAE2b2A+fcF4CH2Cl1t13fmhcoyYM09cDRahul/I5SXkH5TUvYw4J7Bm7n3Cvb/5vZaWC9FbRxzq2b2dPM7CjwA+AEUN4e7SIiJRH7zkkz+0PgMefcJ4A54KOtt+5xzn03xbSJiEiAyIHbOXc6YN69wC1pJkhERHrTnZMiCZX98VdSXhpkSiSBKjz+SspLJW6RBKrw+CspLwVukQSq8PgrKS8FbpEEqvD4KykvBW6RBKrw+CspLwVukQSq8PgrKS/1KhFJqOyPv5LyUolbRKRkFLhFREpGgVtEpGQUuEVESkaBW0SkZBS4RURSlvUAZOoOKCKSojwGIFOJW0QkRXkMQKbALSKSojwGIFPgFhFJUR4DkClwi4ikKI8ByBS4RURSlMcAZH17lZjZOPAh4DrgAHCnc+5sx/vrwIPAk+10O+d+mFoKRURKJusByKJ0B3wpcME5d8bM6sD/BM52feYlzrmfpJ46ERG5Rt/A7Zy7p+PlM4EfZJccERHpJ/INOGb2VeAZwImAt99vZkeBLwN/5pzz00meiIh0q/l+9BhrZs8GPgL8Zjs4m9lrgc8Cl4FPAh9yzn2sc7mVlRW/u5U1iu3tbQ4cOBB7ubJSfqtrlPIKym9atra2OH78eK17fpTGyePAw865B51z3zCzvcCvAQ8DOOc+0vHZc8BvAB/r/p5jx47FTvTa2lqi5cpK+a2uUcorKL9pWVlZCZwfpTvgc4E3AZjZdcAh4Eet14fN7HNmtr/12ecB3x44tSIiEipK4H4/8Otmdh/waeD1wGvN7OXOuceAc8DXzOwrwCMElLZFRCQ9UXqVPA68usf7dwF3pZkoEREJpzsnRURKRoFbRKRkFLhFREpGgVtEpGQUuEVESkaBW0SkZBS4RURKRoFbRKRkFLhFREpGgVtEpGQUuEVESkaBW0SkZBS4RURKRoFbRKRkFLhFREpGgVtEpGQUuEVESkaBW0SkZBS4RSQzy8vLHD16lD179nD06FGWl5eHnaRK6PvMSRGRJJaXl5mdnWVrawuAjY0NZmdnAWg0GsNMWun1DdxmNg58CLgOOADc6Zw72/H+C4C3A08C55xzd2aTVBEpk/n5+atBu21ra4v5+XkF7gFFqSp5KXDBOfc84PeBd3e9/x7gDuA5wAvN7MZ0kygiZXTx4sVY8yW6viVu59w9HS+fCfyg/cLMbgAuO+cebL0+B8wAqymnU0RK5siRI2xsbATOl8FEbpw0s68CfwP8ScfsSeCRjtcPA1PpJE1EymxhYYHx8fFd88bHx1lYWBhSiqojcuOkc+5WM3s20DSz33TO+QEfq4Utv7a2Fjtx29vbiZYrK+W3ukYpr7CT3+npaU6fPs3i4iKbm5tMTk5y8uRJpqenK7cu8t6+URonjwMPO+cedM59w8z2Ar/GTun6IXZK3W3Xt+Zd49ixY7ETt7a2lmi5slJ+q2uU8gq/zO+xY8c4derUsJOTuay278rKSuD8KFUlzwXeBGBm1wGHgB8BOOfWgaeZ2dFWQD8BfD6F9IqISIgogfv9wK+b2X3Ap4HXA681s5e33p8DPgrcB9zjnPtuJikVEREgWq+Sx4FX93j/XuCWNBMlIiLhdMu7iEjJKHCLiJSMAreISMkocMtQLC8vMzMzo1HjRBJQ4C6RqgyR2R417tKlS/i+f3XUuLLmRyRvCtwl0Q52GxsbpQ92vUaNE5H+FLhLokrBLstR46pyVSLSiwJ3SVRpiMyw0eEGHTWuSlclIr0ocJdEVsFuGLIaNa5KVyUivShwl0SVhshsNBosLS0xNTVFrVajXq+ztLQ08FNRqnRVItJL5QN3Veo828GuXq+nGuyGpdFocP78ea5cucL6+noq+ajSVUmZqatnDnzfz3y6cOGCn8Tq6mqi5dqazaY/Pj7uA1en8fFxv9lsDvS9WRk0v2WTdn6LvL2LuG2bzaZfr9f9Wq3m1+v1VNZTkbdBlrLavq3YeU1MrXTgrtfru3ag9lSv1wf63qwU8eDOUhb5zSIYpaFo2zarAFu2Yy4teQfuSleVqM5z9DQaDdbX11OtgqmirBpydczlo9KBW3WeIsGyCrA65vJR6cBdpZ4YIlFEbYzPKsBmecxVpaNBKoLqT9KehlXH7fvFrfMMUrR60KyNUn7zyGuceussGxGbzaY/NTU1Uo2eapzsMEoHtu8rv1WWR17jNgxmWahJO79Fb/TMO3D3fXSZiJRD3HrrRqNRmsZbNXruVuk6bpFRUuWGwSrnLYlIgdvMzpjZ/Wb2gJn9btd762Z2n5l9qTVdn01SRaSXKjfGVzlvSfStKjGz5wM3OeduMbMJ4B+Aj3d97CXOuZ9kkUARiaZd7TE/P8/Fixc5cuQICwsLpakO6aXKeUsiSh33vcDXW/8/Chw0szHn3JPZJUtEkihTvXVcVc5bXH0DdytA/7T18nXAuYCg/X4zOwp8Gfgz55yfaipFROSqyL1KzOxl7ATuF3a99Vbgs8Bl4JPAHcDHupdfW1uLnbjt7e1Ey5WV8ltdo5RXUH6zFilwm9mLgHngxc65xzrfc859pONz54DfICBwHzt2LHbi1tbWEi1XVspvdY1SXkH5TcvKykrg/L69SszsMPBO4IRz7nL3e2b2OTPb35r1PODbA6ZVRER6iFLifiXwq8Dfmll73heBbznnPtEqZX/NzB5np8fJNaVtERFJT5TGySVgqcf7dwF3pZkoEREJpzsnRURKRoFbRKRkFLhFREpGgVsEDdIv5aJhXWXkLS8vMzs7e/UZjBsbG8zOzgLoFmspJJW4ZeRl9eBckawocMvI0yD9UjYK3DLyNEi/RFGkdhAFbhl5GqRf+mm3g2xsbOD7/tV2kGEFbwVuGXmNRoOlpSXq9Tq1Wo16vc7S0pIaJuWqorWDqFeJCBqkX3orWjuIStwiIn0UrR1EgVtEpI+itYMocA+gSK3MIpKdorWDqI47Id1tJzJaitQOohJ3QkVrZR4WXXWI5E8l7oSK1so8DLrqEBkOlbgTGrSVuQolVV11iAyHAndCg7Qyh92Fdfbs2aySmwlddUhSVSi4DJMCd0KDtDKHlVQXFxezSm4mita3VcqhaLePl1GkwG1mZ8zsfjN7wMx+t+u9F5jZ11vvvyWbZBZTo9FgfX2dK1eusL6+HrleN6xEurm5mWbyMle0vq1SDqpiG1zfwG1mzwducs7dArwY+Muuj7wHuAN4DvBCM7sx9VRWTFiJdHJyMueUDKZofVtlcHlUYaiKbXBRStz3Aq9o/f8ocNDMxgDM7AbgsnPuQefcFeAcMJNJSiskrKR68uTJIaUouaRXHVI8eVVhqIptcH0Dt3PuSefcT1svXwecc8492Xo9CTzS8fGHgal0k1g9YSXVEydODDtpMsLyqsJQFdvgIvfjNrOXsRO4X9jjY7WwN9bW1mIka8f29nai5cpgenqaz3zmM7vmVTm/QUYpv2XIa68qjLhp75Xf6elpTp8+zeLiIpubm0xOTnLy5Emmp6cLv47C5L19IwVuM3sRMA+82Dn3WMdbD7FT6m67vjXvGseOHYuduLW1tUTLlZXyW11lyOuRI0fY2NgInB837f3ye+zYMU6dOhU7jUWV1fZdWVkJnB+lcfIw8E7ghHPucud7zrl14GlmdtTM9gIngM8PnFoRyZ2qMMojSon7lcCvAn9rZu15XwS+5Zz7BDAHfLQ1/x7n3HdTT6WIZK7dsDw/P8/Fixc5cuQICwsLanAuoL6B2zm3BCz1eP9e4JY0EyUiw1GkEfAknO6cFBEpGQVuEZGSUeAWESkZBW4RkZJR4JZS0DCgIr+kJ+BI4elJOyK7qcQthadhQEV2U+CWwtMwoCK7KXBL4WkYUJHdFLil8DSGhshuCtxSeHrSjshu6lUipaAxNER+SSVuEZGSUeAWEYmhCDeDKXCLVFwRAk1VhD1Q+ezZs7mmY+QDt3ZqqbKkT27XcREs7GawxcXFXNMx0oE76U4tUhZJ7jrVcREu7Kavzc3NXNMx0oFbt1JL1SW561THRbiwm74mJycD52dlpAO3bqWWvOVdBZHkrlMdF+HCbgY7efJkrukY6cCtW6klT8Oogkhy16mOi3BhN4OdOHEi34T4vt938jzvJs/zvu953hsC3lv3PO8+z/O+1Jqu7/7MhQsX/CRWV1cTLRdVs9n0x8fHfeDqND4+7jebzUx/N0zW+S2aUcrv6uqqX6/Xd+1r7aler2f6281m06/X636tVvPr9frV/bvX/EGPiyTbNiw9ZZDVvtyKndfE5ChB+6DneX/ved5Sj8B9qNd3FDVw+36xdpZRCmS+P1r5XV1d9Wu1WmDgrtVquaShc1+fmJjw9+/fHxqc4wb7oPzGTVvehag0j/0iBu69nuc91fO801UM3EWi/FbXsErc7eDUPkEE/X7UtMQJrnG3bd7rJu0TRd6Bu28dt3PuF865x/t87P1m9mUze4eZ1fp9p8goynuUw846ddgppPUzrN4meTeIlr3nTBqDTL0V+CxwGfgkcAfwse4Pra2txf7i7e3tRMuVlfKbzNmzZ1lcXGRzc5PJyUlOnjyZf2NRH9vb20xPT3P69Olr0jo9PZ3Jdj916tQ1wamfycnJ0LT0Cq7dy8TdtpOTk1y6dClWegYRJy9R5H7sBhXDg6awqpKuz/x7z/P+onu+qkqiySK/RarD75ZGfge55M1z3QxjX45SNRJnvcWpzih6HXevvCTZLwpXx+33CNye5x32PO9znuftb72+x/O8V3Qvm3XgLnJwiiPtjT/owZD1ek0jv0nrRvMOFIPmNcm2CFs37Wnfvn3+xMRE5O8MW2dzc3P+xMTE1XkTExP+mTNncsljUr3y0mu/CEtj4QK353nHW9381j3P+17r/zd6nvfy1vt/7Hne//E87yue593teV6t+zuyDNxF69I3iLQ3/iANPnms1zTym7SnRt6NYYPkNem2CFquvb6SBsbuwDU3N+fv27cv8KRQ9GMwKAj3K4mHbYfCBe40pjQDd/fK7jzT53EAZintjT9I97M8AtswS9x5d80bJK+DnoCzKsU2m01/z549oSX6Mh6DcauX2lcYCtwduldG0BkvbMq6b2wWB0SRStx5BLZh1nEPemKKu/0Hyeuw+38HmZubi3QcFl3UgmC/KUnVUBSVCNz96uzyOttnVY1QpDruspS4fT/ZSXTQRs24yw6rxJ2FZrMZqWQ6NjY2lPRFFbQd9+3bl6jUPTU1lUkaKxG4o67QrOu4szqQitSrpCx13INIum6SbP9BbgFvl67z2sfn5uZ2/d6hQ4d2/VacAlSRxclHvymrq59KBO6wFT0xMZFba7TvZ3fpOuxA1q0MvUqyFrQOkmz/1dXVWOszi4bFKMKqQNq3yccpjdZqtUI1UM7NzfljY2NXrwbSCtqAv2fPnkzyWonAPayduVsZStxl6CIZtH2LlOawq44kDeJnzpyJdQUzrOqRtANaURooo9bJDzLt378/9X22EoHb94d3+didhiLXcZeli2RnfouY5l5XeHHTOjU1FSuwDatBMu1gNswG1E5pn5DCpomJiVTTXdrAHVYKG3Y3wEHqjsOW6xe4o/5mr7q7JCXZrErCnfktWgOc7/cOnnHXSdxAPMj66Je2oL7Y7ddpB7I0t19YvjoLc+0A3Z3vPIJ2dwBP4zgpZeAOurzct2+ff/DgwcKf4YP0K1X2CtxxSqRRDsCoO1aSknDUoNaZ3yJ2eUvzZBK3xJ3mTTfdd/5F7VI76NT+3TRO/HHudOyMFXHr5dOcxsbGBg7epQzcYTt7r6kodWpB+gWCXoE7ThCJ2hc1i/7OcQJO0UvcaVbfvOpVrwrM39zcXM/fjxvw+q3HXldjaUztIDk1NXU1aKexDsPSnVcVSNJp0KqTUgbuJGfKotXjdupXquwVuOOUSOPcRNAvMGZ5iZ9lHXfUoBe3WiFpeuKWuIPS0BmowtLSb3tlWfqcmJi45mo47M7KOCfkZrM59AA8yDRITCpl4I5b4k67YSBtvUoNtVrtaiklzrLdB0CSnTxIZ7CIc+DFCfRZ9SqJchJoNps9T3BhVUlxu/RFqTvuVW3Vr2ojah/rrEvctVotcMySqPtdr04Hvaail7hhsN4mpQzcZ86cibwzDLMHQlAQ2LNnzzWXwVHrF4Mun6MGoyT1l0GlzH7f0x0w2pKWuJMKKo2GHcztNERdT/v379/VcDcxMeHv3bu350HZffNK0oO734kzbHv0209mZmYyCU6HDh2KvUx73WaRnqJNSQuVpQzcq6urkS7702rBTaLZbPY8uQQF73Yg6DVAT5LSXtKDoHunivo9QSWJpHXcScQ9UbVL/XHWU9SGXt8fvK9w3BNL2Pbo1fsii6qSmZmZRN87rEbDpFPnPSPdQ9lGmZLEqNIG7kEuM/tJ49I8ShDoPniiXD5D74arIIMcCIMeRJ3bIUmvkriazWbsy+R2YMwiYPh+On2FfX/w6oz2Ou/eDkkHUIoylaHKotf66rVP9NqP4+yHcer120obuKPubIcOHcpskKHOA2BiYuJqF6O4B8JTnvKUa56sHXWKcoIqwmXnwYMHIw/OnzRwJ73cb58Is1hPaTSg1Wq1XO7wi5umvLoPDmNqH/Nxqvi6NZtN/8CBA5HWZVylDNxx6rg7pyhP9girkwtq7EsabNOeejVy9GtsG9bUa0D9M2fO7DohdvZICDtRDVJHO2hVRB5T0aoP5ubmYtW3Fy39vabO8UUG7dV05syZviXvkSlxJ+nHHTR1b4BepZrus2LRgmHQxi9yIILghpkopZSgBrtB0tG5bZP2Yhil6eDBg7H3s/Y6vvnmm4ee/jj7Q+c+kaTqtF+1btLOE6UM3GkeUO0Ghahnxbit+nlOaTVK5p3mQepbs6xDbZfuk9Sbl32KU4iJcly0j5+g4SqSNOhlOSUpAYdZXV0NXS+D3EFZysD99Kc/PfeNGdalqohTu1RQhhJjGdLY3dUv66kIVXBJ63f7VS0E9dHv1Ysq7yntIWfbJ6q0B0orXeBuNpu5H0hJuosNe+o1zKim4k5zc3OZ9amOM0V5snmvYzSsaqE7cBdpH203Aqepnd+0biJrGyhwe553k+d53/c87w0B773A87yve553v+d5bwlaPkng7hU8x8fHE3X4j3Iw+X62twWHTRMTE6HjWQw6dV6qJSmhx22g0hQ+dd64VJRqmXaASTPgdAfuYeexPWV1z0fhHhbsed5Bz/P+3vO8pZDAvep53jM9z9vjed59nufd2P2ZJIE77+A5MzPj+36y/sFpHDS+H6/7Y5ypu5Ev7o7erfMgL0rwyXN7Jd1G3VUPw85Le8piBMZBA/fY2FisgkLU/TCrO6zzDtx76O8J4Hbgoe43zOwG4LJz7kHn3BXgHDAT4Tv7OnLkSBpfE9n58+ep1Wq85jWv4cknn8zlN8fGxlhfX6fRaFydd9dddzE+Pp7q7/zsZz9jfn5+1+9GsX//fu66665r5jcaDdbX17ly5Qqzs7OppbPo6vU66+vribfR7bfffvX/5eXlNJM2kDyOtYmJiVifn52dZWFh4Zr1vG/fPvbv379r3vj4OB/+8IdpNpt9t8vW1tauY6G0gqJ50OR53unuErfnebd6nveJjtev8zzv7d3LJq3jjtKpvexTp+56sjR/p7NUFeXzUS4py9KIm9YUdSyRQ4cOBd4G3jk+dZ7rrX3TWHs/CEpT2oIaJ3ulsd1wOTY2tqv+OagKp1e1TpQ7k/O4wkhLWIm75vs+UZjZaeBHzrm7O+bdCpxyzr289fqPgBucc/+xc9mVlRU/SQnl4x//OO973/u4dOlS7GXLYGpqivPnz199vb29zYEDB3Z95uzZs7z5zW8m6naK8lszMzOB67Q7Pf2EfU+epqam2NzcpFarceXKlVjLHj58mFqtxmOPPcbk5GTPvBw+fJj7778/8nf3WsdAovW2Z88erly5sivd/faL7m169uxZFhcX2dzcZHJykpMnT3LixInYaeknaF++9dZbefTRR6/5bNx1G1Va+3kUQflNw9bWFsePH69d80ZQNA+aQkrcRz3Pu7/j9X8Kqgcf9JmT/fqNFuE24bh1ckHdkcLO2oOW0KKMIpik5DXsLn6ddcZJ11FnvsO2X5KuY72Gt02y3sJ6QcTZ7nkKe15sns8VzfP3Ctc46fcI3K3532kF8L2e5z3geZ7X/ZlBA3fYCHztRrci9HZo97wIetRad3/dsO5I/R5dFvfE0A5uSUYajGKY6z0omCZtNO11K3zSrmO9+kbHXW/ddzBG+Z00Hps1iF6FkDR7r/ST1+8VLnB7nnfc87wveZ637nne91r/v9HzvJe33n9uqyvg/Z7n/WnQd6TxlPfusTg662DzKPmNjY1dHf/k4MGDV+vkarXargGuOsdvjlInF5bfXqIEojwO2rASzdzcXKY3W0QJpnFujw+6FT7LhzmEneCDTjb9BuHPuxQbVVaBrKgKF7jTmNII3L0kLfnFqWYJK7WmedBEyW+vfthp3w0WRVigazabPR/qPMgJNGoeo3bbS/PW57B10/10o7BGt7DCSdTfyeuk3Y8CdzoqHbiT1G/2G84xyoHd63I4q/z2S29WQSiJOCfUdpDqtR3jnhSj7Bd5lU4VyKpNgbtDnJXRXVqJEiR8v381S68DO+6DdNPIb7/0ZtHVKak4VVjtG306S4+dY58nLUkGDXQ0jNKpAlm1KXC3NJtNf2pqKvYB1h3A+w3s36/HSq/fVYm7t7iNqVWmQFZtCtx+vg0ug/zWsOq4wy7/i9Ao1SlOFVaRTjhZUCCrNgVuP7yklvRJyf0M0riTZsNQnDr99jpq90QoSqNUt860hlWdFO2EkwUFsmpT4PZ7141W+QAflZ29iL0gsjYq27ZN+U3HIINM5a7XoDeVGCBmxLUHqfrOd75zzSBbItJfIQP3wsJC6HsXL17MMSUiIsVTyMDdaDRCh4HMe7hXEZGiKWTghp1xqbtH2xofH+9ZGhcRGQWFDdyNRoO3ve1t1Ot1arUa9XqdpaUl1YeKyMjbO+wE9HLixAlOnTo17GSIiBRKYUvcIiISTIFbRKRkFLhFREpGgVtEpGQUuEVESibyU94HsbKykv2PiIhUUNBT3nMJ3CIikh5VlYiIlIwCt4hIyRT2zkkzWwRuZmcc7j92zj0w5CSlwsxuAj4FLDrn7jazZwL/DRgDLgH/2jn3hJk1gD8BrgBLzrkPDC3RAzCzM8Bvs7Ov/WfgASqYXzMbBz4EXAccAO4EvkkF89rJzJ4KfJud/J6novk1s9uA/w58pzXrW8AZhpTfQpa4zex5wD93zt0CvA54z5CTlAozOwi8l50dvO1twPucc78N/F/g37Y+91bgBcBtwEkz+5WckzswM3s+cFNrO74Y+Euqm9+XAhecc88Dfh94N9XNa6c/By63/q96fv+Xc+621vQfGGJ+Cxm4gRngkwDOuTXgn5rZ04abpFQ8AdwOPNQx7zbg71r//w92Nvi/BB5wzj3mnHsc+ArwnBzTmZZ7gVe0/n8UOEhF8+ucu8c5d6b18pnAD6hoXtvM7FnAjcCnW7Nuo8L5DXAbQ8pvUatKJoGVjtePtOb9v+EkJx3OuV8AvzCzztkHnXNPtP5/GJhiJ6+PdHymPb9UnHNPAj9tvXwdcA54UVXzC2BmXwWeAZwAvlDlvALvAt4A/EHrdWX35ZYbzezvgF8B/oIh5reoJe5u1/RjrKiwfJY6/2b2MivggPcAAAGySURBVHYC9xu63qpcfp1ztwL/CmiyOx+VyquZvRa43zn3jyEfqVR+ge+xE6xfxs6J6gPsLvjmmt+iBu6H2Dlztf0zdir/q+gnrQYegOvZyXt3/tvzS8fMXgTMAy9xzj1GRfNrZsdbDc04577BzkH94yrmteV3gJeZ2deAPwLeQkW3LYBz7oet6jDfOfd9YJOdKtyh5LeogfvzwO8BmNk08JBz7sfDTVJmvgDc0fr/DuCzwP8GfsvMnm5mh9ipI7tvSOlLzMwOA+8ETjjn2g1YVc3vc4E3AZjZdcAhqptXnHOvdM79lnPuZuCv2elVUtn8mlnDzP609f8kO72HPsiQ8lvYOyfN7B3sHAxXgNc757455CQNzMyOs1MveBT4OfBDoMFON7IDwAbwb5xzPzez3wNOsdMd8r3OueVhpHkQZjYLnAa+2zH7D9g50CuV31bJ6wPsNEw+lZ3L6gvAR6hYXruZ2WlgHfgcFc2vmf0T4G+ApwP72dm+/8CQ8lvYwC0iIsGKWlUiIiIhFLhFREpGgVtEpGQUuEVESkaBW0SkZBS4RURKRoFbRKRkFLhFRErm/wOu8qNDeh7d3gAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SStDN87X_JBi"
      },
      "source": [
        "The imported cache is at least three orders of magnitude faster than using a python dictionary was. Why? Because some of the underlying implementation is in C.\r\n",
        "\r\n",
        "I don't think I will be implementing caching by hand very much any more."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2FMRtq-h0uft"
      },
      "source": [
        "NEIGHBORS_MATRIX_NP = np.matrix([x for x in NEIGHBORS_MATRIX.values()])\r\n",
        "\r\n",
        "def count_sequences_with_np_matrices(start_position, num_hops):\r\n",
        "    # Apologies for the code golf.\r\n",
        "    return np.sum(np.linalg.matrix_power(NEIGHBORS_MATRIX_NP, num_hops)[start_position])"
      ],
      "execution_count": 24,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 262
        },
        "id": "2MRoYC5HBF2I",
        "outputId": "d9c2376c-4034-40eb-eb90-6af7ee831800"
      },
      "source": [
        "make_dialer_profile_graph(count_sequences_with_np_matrices, 512)"
      ],
      "execution_count": 25,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAD1CAYAAAC/duk9AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3df4wc533f8fdyeQx1R1EWl0ZIObpjbOi+JWOhAImgVh1FSkg7Fcs0COw0iY8u9Qu0jkyhCvElBq6hEgmnJBQaxkpFsgf/iMw7G0JS2LVpRrWlJLYsWYV8/oG2OT+qnd7RCUmYOsIW6fORDLn9Y2emc3Mzs7O/f31ewIDH2ZnZ55ndfb4zz/PM8+SKxSIiIiIAq1qdABERaR8KCiIiElBQEBGRgIKCiIgEFBRERCSgoCAiIoHVrU5ALWZmZtSfVkSkCjt27MjFre/ooACwY8eOqvabnZ1l69atdU5N++ql/PZSXkH57WaNyuvMzEzia6o+EhGRgIKCiIgEFBRERCSgoCAiIgEFBRERCSgoNNj09DRbtmxh1apVbNmyhenp6VYnSUQkUcd3SW1n09PT7N+/n8XFRQDm5+fZv38/ACMjI61MmohILN0pNND4+HgQEHyLi4uMj4+3KEUiIukUFBro9OnTFa0XEWk1BYUGGhwcrGi9iEirKSg00MTEBP39/cvW9ff3MzEx0aIUpVOjuIgoKFQpSwE6MjLC5OQkQ0ND5HI5hoaGmJycbMtGZr9RfH5+nmKxGDSKKzCI9BYFhSpUUoCOjIwwNzfH9evXmZuba8uAAGoUF5ESBYUqdGMBqkZxEQEFhap0YwGqRnERAQWFqnRjAdppjeIi0hgKClXoxgK0kxrFRaRxFBSq0KkFaLkeU53SKC4ijaOgUKVmFaD1enbg5MmT6nIqImUpKLSxej47cOTIka7rMSUi9aeg0MbKdX09cOAAq1evJpfLsXr1ag4cOJB4rHPnzsWu7+QeUyJSfwoKbSyt6+uBAwc4duwY165dA+DatWscO3aMAwcOxFY5bdq0KfZYndxjSkTqT0GhjaV1fZ2cnIx97fjx47FVTnfddVfX9ZgSkfpTUGhjaV1f/TuEqGKxGFvl9KUvfakje0yJSHMpKLSxtK6v+Xy+omOdO3dOXU5FpCwFhTaXVJD703pGrVu3LnZ9UpuCiEiYgkKHOnr0KKOjo8EdQz6fZ3R0lOPHj8dWOT3yyCOtSKaIdJjVrU6AVO/o0aMcPXo09rXx8XFOnz7N4OAgExMTbN++vcmpE5FOpKDQhUZGRla0F8zOzrYoNSLSSVR9JCIiAQUFEREJKCiIiEhAQUFERAIKCiIiElBQaLF6zZfQKO2ePhGpL3VJbSF/vgR/rCJ/8DqgLYagaPf0iUj9ZQoKZnYEeAdQBB52zr0aem0X8ARwDTjlnHs8aR8zuxU4AeSBs8D7nXOXzezXgd8GrgMvOOfGzexe4HHgu95bfdE511VDeqbNl9AOhW67p09E6q9sUDCzu4DbnHN3mNlW4GPAHaFNngJ+CfhH4Etm9l+BNyfs8xjwtHPuL8zsCeB+M3sG+GPgduAS8IqZ+XUUzzrnPliXnLahtPkS2kG7p09E6i9Lm8JO4DMAzrlZ4GYzWw9gZm8FLjjnvuecuw6c8rZP2udu4LPecT8H7HLOLQK3O+cuOueKwAJQqFP+2lrafAntoN3TJyL1l6X6aBMwE/r/eW/dG96/50OvfR94G7AxYZ8B59zl0LabAZxzFwHM7HZgC/CKd5y7zOw5oA/4oHPuG9HEVTt8w9LSUsuHfjh48CCHDh1iaWkpWLd27VoOHjxY97RVk99mpq+e2uGzbSblt3u1Iq/VNDTnqngtbv2ydWZ2G/BJ4H3Ouatm9gpw3jn3eTO7A/gEpSqmZbZu3Zot1RGzs7NV71svW7du5ZZbblkxeF0j6uuryW8z01dP7fDZNpPy270aldeZmZnE17IEhTOUrvJ9t1BqJI577S3euisJ+1wysxuccz8ObYuZ/RSl6qb3O+e+CeCc+zbwbe/vr5rZm80s75yLn3KsQ8UNXtdO2j19IlJfWdoUvgC8F8DMtgNn/Ooe59wcsN7MtpjZamCPt33SPs8D7/GO+x7gOe/vjwKjzrmv+29qZr9jZr/p/f12SncNXRUQRETaTdk7Befcy2Y2Y2YvU+oyetDrLvpD59yngVHgU97mzzrnXgNei+7jvf4o8Akz+wAwDzxjZsPAncBjZua/7Z9Qqko6YWYPeel8oPbsiohImkxtCs65D0VWfSv02pdZ3kU1aR+cc2eBd0VWvwb0R7f1/EKW9ImISH1omAsREQkoKIiISEBBQUREAgoKIiISUFAQEZGAgoKIiAQUFCI0qYyI9DJNshOiSWVEpNfpTiEkbVIZEZFeoKAQokllRKTXKSiEaFIZEel1CgohExMT9PcvH4apv7+fiYmumhpaRCSRgkLIyMgIk5OTDA0NkcvlGBoaYnJyUo3MItIz1PsoQpPKiEgv052CiIgEFBRERCSgoCAiIgEFBRERCSgoiIhIQEFBREQCCgoiIhJQUBARkYCCgoiIBBQUREQkoKAgIiIBBQUREQkoKIiISEBBQUREAgoKIiISUFAQEZGAgoKIiAQUFEREJKCgICIigUxzNJvZEeAdQBF42Dn3aui1XcATwDXglHPu8aR9zOxW4ASQB84C73fOXTazXwd+G7gOvOCcGzezPuDPgSHv2Pc55/6+DnkWEZEEZe8UzOwu4Dbn3B3AA8BTkU2eAt4DvBN4t5ltS9nnMeBp59ydwHeA+82sH/hjYCdwB7DLzLYB7wN+4Jz7OWAC+MPasioiIuVkqT7aCXwGwDk3C9xsZusBzOytwAXn3Pecc9eBU972SfvcDXzWO+7ngF3OuUXgdufcRedcEVgACt4xPu1t+zyloCMiIg2UpfpoEzAT+v95b90b3r/nQ699H3gbsDFhnwHn3OXQtpsBnHMXAczsdmAL8Arwe/6xnXPXzaxoZmucc1fCiZudnc2QhZWWlpaq3rcT9VJ+eymvoPx2s1bkNVObQkSuitfi1i9bZ2a3AZ8E3uecu2pmmY69devWlOQkm52drXrfTtRL+e2lvILy280aldeZmZnE17JUH52hdJXvu4VSI3Hca2/x1iXtc8nMbohsi5n9FKXqpn3OuW9Gj+01OueidwkiIlJfWYLCF4D3ApjZduCMX93jnJsD1pvZFjNbDezxtk/a53lKjdJ4/z7n/f1RYNQ59/XI+/6a9/cvA39TTQZFRCS7stVHzrmXzWzGzF6m1GX0oJndC/zQOfdpYBT4lLf5s86514DXovt4rz8KfMLMPgDMA8+Y2TBwJ/BYqMroT4BngXeZ2VeAy8C9NedWRERSZWpTcM59KLLqW6HXvkypK2m5fXDOnQXeFVn9GtCf8Nb3ZUmfiIjUh55oFhGRgIKCiIgEFBRERCSgoCAiIgEFBRERCSgoiIhIQEFBREQCCgoiIhJQUBARkYCCgoiIBBQUREQkoKAgIiIBBQUREQkoKIiISEBBQUREAgoKIiISUFAQEZGAgoKIiAQUFEREJKCgICIiAQUFEREJKCiIiEhAQUFERAIKCiIiElBQEBGRgIKCiIgEFBR60PT0NFu2bGHVqlVs2bKF6enpVidJRNrE6lYnQJprenqa/fv3s7i4CMD8/Dz79+8HYGRkpJVJE5E2oDuFHjM+Ph4EBN/i4iLj4+MtSpGItBMFhR5z+vTpitaLSG9RUOgxGzZsiF0/ODjY5JSISDtSUOgh09PTvPHGGyvWr1mzhomJiRakSETajRqae8D09DRjY2OcPXs29vUbb7xRjcwiAmQMCmZ2BHgHUAQeds69GnptF/AEcA045Zx7PGkfM7sVOAHkgbPA+51zl83sZuBTwCXn3Hu9/e8FHge+673VF51zupytULS3UZwLFy40MUUi0s7KVh+Z2V3Abc65O4AHgKcimzwFvAd4J/BuM9uWss9jwNPOuTuB7wD3e+uPA1+JeftnnXN3e0tdAoLfR/9nfuZneqKPflxvo6jBwcEVzy4cOHCgp59l0LMc0quytCnsBD4D4JybBW42s/UAZvZW4IJz7nvOuevAKW/7pH3uBj7rHfdzwC7v7weJDwp15V81z8/PUywWgz76nfyDL1d4letV1N/fz+7du1ecl2PHjnXVeapEN35PRLLKUn20CZgJ/f+8t+4N79/zode+D7wN2Jiwz4Bz7nJo280AzrmLZhb33neZ2XNAH/BB59w3ohvMzs5myELJ2NhYbB/9sbExtm/fnvk47eLkyZMcOnSIpaUloPQg2oMPPsiZM2fYs2cPAJs2bUpsS9i8eTOPPPIIR44cKXs30UnnaWlpqaLvRVSnfU9qzW+n6aX8tiKv1TQ056p4LW592nEAXgHOO+c+b2Z3AJ8Abo9utHXr1jKH+f/OnTuXuL6S47SLe+65JwgIvqWlJZ5++mnGxsYAePLJJ1e0KfT39zM5ORk0Lv/u7/5upvfrlPM0OztbUzo77XtSa347TS/lt1F5nZmZSXwtS/XRGUpX+b5bKDUSx732Fm9d0j6XzOyGyLaxnHPfds593vv7q8CbzSyfIb2Jkvrid2of/SwPoo2MjDA5OcnmzZvJ5XIMDQ0tCwiQPf+dep4q1W3fE5FKZAkKXwD8HkHbgTPOuYsAzrk5YL2ZbTGz1cAeb/ukfZ6n1CiN9+9zSW9qZr9jZr/p/f12SncN1yrOYcjExAT9/f3L1vX393dsH/2shdfIyAgvvPAC169fZ25ubkX307jzEtXJ56lS3fY9EalE2aDgnHsZmDGzlyn1IjpoZvea2a96m4xS6k76IqXeQq/F7eNt+yiwz8xeBDYAz5hZ3sz+FvhTSm0If2tmvwh8EthvZl8C/gulXkw18a+ah4aGEq+aO0m9Cq/weQHI5ZbX7OVyOfbt29ex56lS3fY9EalIsVjs2OVrX/tasVp/93d/V/W+7WRqaqo4NDRUzOVyxaGhoeLU1FTsdlnzOzQ0VKT0bMmyZWhoqI6pbqxu+WyzUn67V6Py6pWdseWqnmjucCMjI3W9gtWAeSK9TWMfyTJqZBXpbQoKTVbNk7KVPG1c65O4ce0UuVyO+fl5Pdkr0guS6pU6Yem0NoWpqalif3//srr6/v7+xHaApH2ii3+MtONXkt/R0dFiLpdLfa921kt1zsWi8tvNWtGmoDuFJqpm1rMsYxctLi6yd+9e9u3bV/OsatPT03zkIx+hWCwmvpdmaRPpXgoKTZSlETda/TM/P5/5+NeuxT/GUUkj8fj4OFevXk3dRo3OIt1LQaGJkhpri8Vi0FYQHYgt+sxAPd8XqgtCanQW6V4KCk2U9uTw/Pw8x48fX1H9UywWawoMfX19XLp0KXao8LjRQMu9l57sFeluCgpNFH1yOCqpHj8uMKQV3vl8nlwuR6FQIJfLsbCwEDsEdFx7RVIafL30ZLNIL1JQaLKRkRHm5uYquvrP5/MrCutisUihUIgd5mL//v0MDg6ysLDAlStXlr0ebihOaxtYtSr+q3Hq1KnM6RaRzqOg0CJJ9fLRYNHf35/YgHzhwoUVY/Ts27ePZ555JrVtwA8GSWkYGhpKvGNQI7NId1NQaJGkweweeuihFQOxJVU3bdiwIbjz8EdAPXXqVKbpN5PS4LdBJAUFNTKLdDcFhYhmzc0bbV/I5/MsLi5y6tQpJiYmlg1zPTExQV9f34pjXLx4serpNzdu3MjevXtZXFwMqooGBga4evUqCwsLifuqkVmkyyU91dYJS72faK7mieNaZX3PQqGQafTSpFFO/W137twZ+1o+n099atp/PW0k1nbRS0+8FovKbzfTE80tVs0Tx816zwsXLsTuH70zSKqWOnz4MBMTE/z1X/917HGS2i2ir2sSe5HupqAQ0shho5OqpbK+ZyWzrE1OTlIoFIJ1i4uLPPHEEzz88MNlu5xmoaEuRLqXgkJIo4aNjntIzL/a3rBhQ6b3TJtlLRpwXnrpJd54441l2/7gBz9IbCuohnohiXQnBYWQRs3Nm1RFtHfv3sSCevfu3cv+H3cHcMMNN/DSSy+tCDjHjh0rO35RVNxzE7lcjnXr1sVur15IIt1JQSGk1rl5K60iSnPq1Kllx9u4cSMf+MAHlgWRhYWF2KExKvUTP/ETK3o35XI5HnroIY4fP65J7EV6SVILdCcs7TCfgj9HMhA7B0GhUEjsOVRuKTePQq1LPp9flv7o4vdsyjoPdLvopd4pxaLy2800R3OH8dsK/Cv1Ykwj7sLCAn19feTz+bI9fML85xYa6dq1a4yPjyc+/ezf4dR7HmgRaV+qPqpBlglwAK5evVpRQFizZk1F21fLn2YzidoNRHqPgkINGtEDp1Ao8LGPfSxxaIuopKG4faOjo7FPQ0P6iKhqNxDpTT0bFE6ePFnzcBb1uJIeGhpiamoqqM97/fXXg6EtyhX4hUIhdWykQqHA0aNH+fjHP85NN920bH2afD5fUQN7WLOGCRGRBklqbOiEpdqG5qmpqeLatWtrHs4iboiKSpboEBVxx49rxC4UCsvSmpSOdevWBY3Dhw8fXnbstOEwcrlcRechLR2NHiYkTi81RBaLym83a0VDc8sL9lqWaoNCud42lQj3zCk3flBaYRnt4TM6OprYq8n/f7gn0OjoaGzvp/ASDiZTU1Op27X6vNailwqNYlH57WYKCk0KCkmFZ7VXyOWOm1Y4F4u13XH4wSXtyj/u/UdHR4urVq2KfX3NmjVVXd036rxWqpcKjWJR+e1Gje4GrqAQ0agr2koK5vAHXcl+ScfKGpCidxtpx2yX81qpXig0wpTf7tKMaliNkhoxMTHB2rVrl62rR2+bLI3Dvvn5efbu3cvGjRtTu4Vmcfr06YobvYvFYtljVqpRw4SI9JJWjNYc1pNBYWRkhMceeyzzcBZZe9REJ87JYmFhoaL5muOsWrWK3bt3Zw5IWVTTs6rWYUJEpLGjNWeSdAvRCUszhrlIqu+PtgtEVdLoTIbqHP/1pO36+/uDxulcLlcsFArFgYGBqt6zFT2G6qnbqxeilN/u0oxqWFUf1SDpqeWFhYXUyWYqfSK5WCwue35gYGCAQqEQXHGfOHGCYrHIiRMnyOfzK/b3p/L052t+/fXXuXTpElNTU7HPJYTngwaCY+rqXqS1Wl4NmxQtOmFpxp1CpQ2ylfYE8pdCoZC5camaXj6HDx/uqEHtatHtV5JRym/3aWXvo0wD4pnZEeAdXuHzsHPu1dBru4AngGvAKefc40n7mNmtwAkgD5wF3u+cu2xmNwOfAi45597r7d8H/Dkw5B37Pufc32eMdXUzODiY2hDs1/MdOHCA48ePl23AjZPL5bh8+XLinAt79+6lUCjw4Q9/mJGRETZs2BA7D0NaO8CePXsYGxurOG0i0nz+IJSzs7Ns3bq1qe9dtvrIzO4CbnPO3QE8ADwV2eQp4D3AO4F3m9m2lH0eA552zt0JfAe431t/HPhK5LjvA37gnPs5YAL4w0ozVw/lehQNDg6ya9cujh07VlVAgNLd2qVLl1K3WVhY4P777+fAgQMrZlWD0iB66uWznIbcEKlcljaFncBnAJxzs8DNZrYewMzeClxwzn3POXcdOOVtn7TP3cBnveN+Dtjl/f0gK4PCTuDT3t/PUwo6TRc341nY66+/zgsvvJB6jFwuV3MPI4ArV64wOTkZO6vajTfeqHaAkLQpUJudDgUm6SRZqo82ATOh/5/31r3h/Xs+9Nr3gbcBGxP2GXDOXQ5tuxnAOXfRzOLe97z3+nUzK5rZGufclfBGs7OzGbKw0tLSUuZ9t2/fzosvvsjJkyd59NFH+fGPfxy89qMf/ajs/ps2bQLg7NmzVaU1LKkB+8KFC6n5qSS/nW5paYmxsbHY6rixsTG2b9/elHScPHmSQ4cOsbS0BJSeTXnwwQc5c+YMe/bsqdv79NJnC72V31bktZpJdtIueZNei1tf6aVz7PbV1rdVU1f39a9/fVlAyKK/v58nn3wSYNmEPNVKmqxncHAwNT+tqJtsldnZWc6dOxf72rlz55p2Hu65554gIPiWlpZ4+umn69q+00ufLfRWfhuV15mZmcTXslQfnaF01e67hVIjcdxrb/HWJe1zycxuiGxb9n29Rudc9C6hUeJu+aenp9m3b19Fx1m3bl3QvbOaB9ui1qxZw/79+/XUcAZJje7NnDio5Q8hSddoZjVklqDwBcDvEbQdOOOcuwjgnJsD1pvZFjNbDezxtk/a53lKjdJ4/z5X5n1/zfv7l4G/yZ6t6sXVRd93333cf//9FT17sHr1ai5duhQMZTE9Pc3IyAhzc3NMTU2tmPgmaSIcnz/5ztGjR/XUcAYt7+tNewQm6RxJBX/T28eS+qqGl+Hh4T8aHh5+eXh4+CvDw8P/fHh4+N7h4eFf9V77+eHh4a96yweT9vHWbR4eHv7i8PDwi8PDw1PDw8N9w8PD+eHh4b8dHh7+5vDw8Hnv71/01n/c2/+F4eHhW6PpasRzCrUOTpe0REcejeuH3MgnGXuhb7fPz2uj+3qX06z5JXrpsy0Wm5ffZn5/kr4r/vNF9S4XNEpqjKQvVqWjjVayZJlUp1GFSC8VHO2U12YULO2U32ZoRn6bPWFUUsG/efPmhgxJr2EuKtDIW/tydckaUK77+FWG169fZ25uTp9lm/OrcPbu3dvUkUqTyoZz5841vRqyJ4PC9PQ0O3fujG20qWT460pl+RA7sRBRX3zpBuG6+ySN6iSQVDasX78+9sHWhraPJd1CdMJSTfVRltvCtKkqgWI+ny+uW7eupjaFZmvULXe7zMscpuqUzlFN9Vqj8pulPbHWKXuT8hj3O+rr6yv29fWtSMPAwECxUCjUVCWpNoWQrI025Sa2T5tCs6+vb9mw1eWG2W6GZv+Qmj3bWlg7F5KNaGNo5/ymqfaCIim/tZ7bcu2J1VzsxOUxl8sVR0dHV6S5UCgsK+wLhUJi+VNruhQUQrI22kxNTSVu6xd44R5D/vwJ7ToCaaMKjkY0gmW9skrapl0LyUbdVWXJb6t7YvlpCBd0SXOEl7ugiMtv1nObdB6mpqZS50Cp9pwlXTT5gSEtYFTS6aXSizAFhZBKrmxHR0frEpXbQafcKWSt3kvbphVBIUuh24hzFX3PpHX1CEa1BJapqanYqpBqLijiPt8s5zbpPMQVztWep+g5SstnUhDyayKyVGdVexGmoBCS9gOJu5ULf3jR27tOCg6d0qaQ5cddbptmB4Ws56Ced1VJddBr1qxZkY6kaohKglGtn3MlBVw1dwpZzm1SGpLuWPL5fMUBIe7KP2u+o+dgamqquHbt2rqcsygFhYipqamg/2/a1VS5pZPuGhpZUNazaiLLj7vcNs1+eK3Wdqpq7hQqKWSTlkqCUa1pz1o4VtumkCV91RTQ5b434e9YpVPwpm3v3y3cdNNNwbpowPeX1atXq03BX+r58Fq1P7Jqb/2brV3r2aPqdafQzF5RlbRT1StN9XjIMvrdTatvrzWwpP2+8vl8zb2Pspzban/jcdWX/rGyfg5x1dA7d+5M3T4pCFT7GYQpKMSIfrGq/ZHV0qDaTLUGhXpfdacVQPVoU6jHVXnWPFfyXpWcx7RtKyngwj3hwovfoJl2TtPq2/0CPfzZhdM7Ojq6rDq23JV01l561fY+KtfVvFzaks5TNcvAwEBitVU1S6UUFGLoTiG7el91lztePXof1Vp/X0meG3FXEtcw29fXlxo845asbQpJ3/8sVSJZgoef/qQA5S9ZnudJulPIEmyTzkWhUChbBlTa+NusJZ/PV/z9UlCIEf1iqU0hWT3rwhtxvKisdwrVXIknVbmEC9B6dE9OKrxWrVq1InhCfDXGwMBAaiFcTS+XtIIp63ZJeYue56SLhMOHD6/4DOoVwNPOhZ+GVgeB6BK+48tKQSFGXGNkuMdRJV/aTlBLUKj3swiNeLYhLEubQtJFgF+Fkfbj9z/7uC7L0SXLhUNctUslx3zTm95UVWFSKBTKXghV2nhazyXtDmR0dLRsQPOrfNLOd6FQyFx3D8k9lVq1DAwMVPUbUVCIkVRwZPlCdFpAKBYbc6fg33JX2s5Q7Z1C1iqCLL2P0gqTtCoXf8na575cvqqto/aPWW09uV8glttm586ddalDr3apNSiNjo4m5rOSYNCOi3+nVw0FhRhpVQxJH0D4/51UdVQs1r9NIalPfFwvjSyNyeEnObOmIekzyJLXclf49awmiLsDqrXaxj9mrccot41/td6Odem9vlRTbeRTUIiR1hiZdemURuZisf69j8o1XqY9yDM0NFTcuXNnbKAN91gJB5JK7i6y5LWZhdzAwMCK6qF6XH1nrepMOm9Zz4F/jltR8LWy+qqdl6SqsawUFGJUeqcQt3RKd9Risf7PKZRrF6j23CYFirR9oldMaXlthx4krW6s9B92ytIm0uql06t4GrHUo5ZCk+wk2L17N7lcrux2Sdv08ly75Sb+qHbc+WKxuOz/i4uLHDt2LHWfY8eOceDAgbLHzjJefjNE89hsN910EwDPPPNMy9MSFf2tXblypUUpaR+5XI5CodC8ibeSokUnLLXcKfzGb/xGpqicdLvfS20KcWrp2teIxe+rHTeEia/VdwjtsmQZrK0VS5YG/lacq1anodaqojiqPorI0mMj/KCQv081PW3aRSOGuYjrox/urtnsH09Sdci6detakp52XdoxIPjfm3YohNttaUQ1tYJCRKUNbN2gXkEhrk99lp5JzfjhqEDJdp62bdvW8nSEl/DvrJ3uFMo9fd2K81MvCgoRlQxi1S3qERTSehS1eql0etReXdIGYWvFEn2gsF0eDuvv7296WuIuptauXduQWgkFhQjdKVSnHasd/KUdglMlT8S3amn0Z+jPH5y2TdxDoO0UEPx0pW0THdIkuvgPB5b7XkarpMsN6VEvCgoRU1NTxdWrV6d+WLU8LdiOan14TQEhffG1Q1qSlmYErHJdkuMaTaem0qfCbMXnmBYUwgPQ1TK5T5aLzkYNea+gEOPw4cOpE2PX8rRgO6r2y1WvoYK7eQkXdO0aPPv6+upW8KZd0ac9vJjUY69d7q7ChXTa5xguGxn1zikAAAgVSURBVLIU+LWMoqug0MSgED7Znd6zKItqv1ztWsi10xLtpVbJuEiNXMI9wupV8KZVkUXvrrP+ruqRrkrymGWIlrQ7vrCsBX61ZYyCgoJCw1T75Wrn6pB6F57VLlHN6v6a1oUz2kmiHkO6+L+LrAVmVrWkK5zPpLtav50jre4++puvpMqnkeWHgkILgkIjJkhpR912p1CPq3H/B56lEE8qCOMKiWacM7/KKmvhVe4qeihlLKTosWqpI4+qdpTXpPesVwHdLuWCgkILgkI9v+DtrNPaFLZt27aiIA4PqFdrdUh4hq9yhXihUKjoqfasV+Xbtm1b1otl586dywq0tH3DvXbWrl1bNl1p58s/F5VUhdSrwMwaQLNU+dRbO9QgKCi0ICg0esKXdlFr76NmP8jjv2/Sj7KWY4dnLysW0wvxaurIsxR0WYYuyNqD5/Dhw2XTVe881qvALDeZUSVVPt1IQUF3Cg1Tjy9XvUbV9K+I0wqDNJUMh5BlHox6fwfKpS/rFW7WK/Jahgpv9fe8mnQ1qqBsRwoKLQgK7VJ32Gj1+nLVWl++bt261CEyspz7rGlIm58hrBHfgaQA6k/3mVWWq+Msn227fs+rSZeCQu0UFGKo91F1Kr1T8Ht9xM2Fm7XQriQN1U6Z2ojvQLO+V1k/23b9nleaLgWF2qUFhVyxWKQcMzsCvMP74T3snHs19Nou4AngGnDKOfd40j5mditwAsgDZ4H3O+cum9kI8B+A68Ckc+6jZnYv8DjwXe+tvuicmwina2Zmprhjx46y6Y8zOzvL1q1bq9q3E9Urv1u2bKloPgL/+5W039DQEHNzc3VJg38sfbbdrZfy26i8zszMsGPHjtiJYspOsmNmdwG3OefuAB4Anops8hTwHuCdwLvNbFvKPo8BTzvn7gS+A9xvZgPAIWAXcDfwiJlt8LZ/1jl3t7csCwjSGhMTE/T392fadmhoKPg7adKdaibjiUtDf38/ExP6iojUKsvMazuBzwA452aBm81sPYCZvRW44Jz7nnPuOnDK2z5pn7uBz3rH/RylQPAvgFedcz90zv0YeIlSgJE2NDIywuTkJENDQ8FMUKOjo2UL6XIztdWahobPRiXSI1Zn2GYTMBP6/3lv3Rvev+dDr30feBuwMWGfAefc5dC2mxOOsRm4AtxlZs8BfcAHnXPfiCZudnY2QxZWWlpaqnrfTlTP/G7fvp2/+qu/Wrbup3/6pzly5Ajnzp1j06ZNPPLII2zfvj14z4MHD3Lo0CGWlpaCfdauXcvBgwerSldcGvzj6LPtbr2U31bkNUtQiEqb1Djptbj15bZ9BTjvnPu8md0BfAK4PbpxtfVtvVQvCY3P79atWxkbG0t9/ZZbbmF8fJzTp08zODjIxMREQ67u9dl2t17KbyPbFJJkqT46Q+lq3ncLpUbiuNfe4q1L2ueSmd1QZtu3AGecc992zn0ewDn3VeDNZpbPkF5pUyMjI8zNzXH9+nXm5uZU3SPShrIEhS8A7wUws+2UCuyLAM65OWC9mW0xs9XAHm/7pH2ep9Qojffvc8D/AH7WzN5kZusotSe8aGa/Y2a/6R3j7ZTuGq7VIc8iIpKgbPWRc+5lM5sxs5cpdRk96HUX/aFz7tPAKPApb/NnnXOvAa9F9/FefxT4hJl9AJgHnnHOXTWzDwH/nVL31T9wzv3QzD4JnDCzh7x0PlCvTIuISLxMbQrOuQ9FVn0r9NqXgTsy7INz7izwrpj1fwn8ZWTdPwC/kCV9IiJSH1mqj0REpEcoKIiISCDTMBftamZmpnMTLyLSQknDXHR0UBARkfpS9ZGIiAQUFEREJFDNMBcdLW0Y8E7nPeT334Ajzrn/XMlQ5S1LdJXM7DBwJ6Xv8B8Cr9K9ee0H/hz4SWAtpSHlv0WX5hfAG/ngf1HK6wt0aV7N7G7gL4D/7a36n8BhWpjfnrpTyDAMeMfyhiD/M0o/IF+lQ5V3BDP7BeDt3uf4r4A/pUvz6vll4GvOubuAfwv8Cd2dX4D/CFzw/u72vH4pNEXAv6fF+e2poEDKMOBd4DKwm9JYUr676c6hyr8M/Jr39w+AAbo3rzjnnnXOHfb+eyvwD3Rxfs3snwHbgM97q+6mS/Oa4G5amN9eqz5KGwa8oznn/gn4JzMLr65kqPKO4Y2B9SPvvw9Qmsfjl7oxr2HesDE/RWmMsee7OL//CfgtYJ/3/678HodsM7PPAhuAP6DF+e21O4WotGHAu00lw5p3BDP7FUpB4bciL3VdXgGcc/8S+DfAFMvz0jX5NbN/B3zVOfd/Ezbpmrx6/g+lQPArlILgR1l+sd70/PZaUEgbBrwbZR6qvNkJq5WZ/RIwDtzjnPsh3Z3XHV6nAZxz36RUaFzs0vz+a+BXzOwV4EHg9+jiz9Y5949e9WDROfdd4Bylau2W5bfXgkLiMOBdKvNQ5S1KX1XM7CbgSWCPc85vjOzKvHp+HvhtADP7SWAdXZpf59yvO+d+1jn3DuAjlHofdWVeAcxsxMw+6P29iVIPs4/Twvz23BPNZvZHlH5k14GDzrlvldmlI5jZDkp1sVuAq8A/AiOUujKupTRU+X3eUOXvBcYodcv9M+fcdCvSXC0z2w/8PvBaaPU+SoVIV+UVgu6ZH6XUyHwDpeqGr1GajbDr8uszs98H5igNq9+VeTWzG4FPAm8C1lD6bL9BC/Pbc0FBRESS9Vr1kYiIpFBQEBGRgIKCiIgEFBRERCSgoCAiIgEFBRERCSgoiIhIQEFBREQC/w9E6oGA5t3N1QAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jnSBSAqrBQvf"
      },
      "source": [
        "Same story: Much faster, and it's because the underlying implementation is at least partially in C. It was also a lot easier to write, I imagine."
      ]
    }
  ]
}