X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=08-word-chains%2Fword-chain-solution.ipynb;h=ba6e8bfce76bc7ea936f531b9b25c594989e2998;hb=0d5419df577af1f1f0bdfdaae5974a62c3c453b0;hp=038b3c49f56741ae3cac412f6a44779f7d32d07c;hpb=2f750972c876ebbb88e1af96be1ce74b4d3558f8;p=ou-summer-of-code-2017.git

diff --git a/08-word-chains/word-chain-solution.ipynb b/08-word-chains/word-chain-solution.ipynb
index 038b3c4..ba6e8bf 100644
--- a/08-word-chains/word-chain-solution.ipynb
+++ b/08-word-chains/word-chain-solution.ipynb
@@ -27,7 +27,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 1,
+   "execution_count": 2,
    "metadata": {
     "collapsed": true
    },
@@ -39,10 +39,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 2,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 3,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -50,19 +48,19 @@
        "2336"
       ]
      },
-     "execution_count": 2,
+     "execution_count": 3,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
-    "words = [w.strip() for w in open('08-words.txt').readlines()]\n",
+    "words = [w.strip() for w in open('08-rooms.txt').readlines()]\n",
     "len(words)"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 3,
+   "execution_count": 4,
    "metadata": {
     "collapsed": true
    },
@@ -77,7 +75,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 4,
+   "execution_count": 5,
    "metadata": {
     "collapsed": true
    },
@@ -89,7 +87,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 5,
+   "execution_count": 6,
    "metadata": {
     "collapsed": true
    },
@@ -102,7 +100,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 6,
+   "execution_count": 7,
    "metadata": {
     "collapsed": true
    },
@@ -115,7 +113,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 7,
+   "execution_count": 8,
    "metadata": {
     "collapsed": true
    },
@@ -132,7 +130,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 8,
+   "execution_count": 9,
    "metadata": {
     "collapsed": true
    },
@@ -146,7 +144,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 9,
+   "execution_count": 10,
    "metadata": {
     "collapsed": true
    },
@@ -164,7 +162,7 @@
     "        else:\n",
     "            successors = extend(current)\n",
     "            agenda = agenda[1:] + successors\n",
-    "    if agenda:\n",
+    "    if finished:\n",
     "        return current\n",
     "    else:\n",
     "        return None        "
@@ -172,7 +170,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 10,
+   "execution_count": 11,
    "metadata": {
     "collapsed": true
    },
@@ -192,7 +190,7 @@
     "            closed.add(current[-1])\n",
     "            successors = extend(current, closed)\n",
     "            agenda = agenda[1:] + successors\n",
-    "    if agenda:\n",
+    "    if finished:\n",
     "        return current\n",
     "    else:\n",
     "        return None   "
@@ -200,7 +198,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 11,
+   "execution_count": 12,
    "metadata": {
     "collapsed": true
    },
@@ -218,7 +216,7 @@
     "        else:\n",
     "            successors = extend(current)\n",
     "            agenda = successors + agenda[1:]\n",
-    "    if agenda:\n",
+    "    if finished:\n",
     "        return current\n",
     "    else:\n",
     "        return None        "
@@ -226,7 +224,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 12,
+   "execution_count": 13,
    "metadata": {
     "collapsed": true
    },
@@ -246,7 +244,7 @@
     "            successors = extend(current)\n",
     "            for s in successors:\n",
     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
-    "    if agenda:\n",
+    "    if finished:\n",
     "        return current\n",
     "    else:\n",
     "        return None        "
@@ -254,7 +252,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 13,
+   "execution_count": 14,
    "metadata": {
     "collapsed": true
    },
@@ -275,7 +273,7 @@
     "            successors = extend_raw(current) # Difference here\n",
     "            for s in successors:\n",
     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
-    "    if agenda:\n",
+    "    if finished:\n",
     "        return current\n",
     "    else:\n",
     "        return None        "
@@ -283,7 +281,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 14,
+   "execution_count": 15,
    "metadata": {
     "collapsed": true
    },
@@ -305,7 +303,7 @@
     "            successors = extend(current, closed)\n",
     "            for s in successors:\n",
     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
-    "    if agenda:\n",
+    "    if finished:\n",
     "        return current\n",
     "    else:\n",
     "        return None   "
@@ -313,10 +311,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 15,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 16,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -324,7 +320,7 @@
        "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
       ]
      },
-     "execution_count": 15,
+     "execution_count": 16,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -335,10 +331,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 16,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 17,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -346,7 +340,7 @@
        "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
       ]
      },
-     "execution_count": 16,
+     "execution_count": 17,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -357,56 +351,59 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 17,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 18,
+   "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "6"
+       "['boon', 'boot', 'bolt', 'belt', 'bell', 'sell']"
       ]
      },
-     "execution_count": 17,
+     "execution_count": 18,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
-    "len(astar_search('vice', 'wars'))"
+    "astar_search_raw('boon', 'sell')"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 18,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 19,
+   "metadata": {},
    "outputs": [
     {
-     "ename": "KeyboardInterrupt",
-     "evalue": "",
-     "output_type": "error",
-     "traceback": [
-      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
-      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
-      "\u001b[0;32m<ipython-input-18-77e0f8036978>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbfs_search\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'vice'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'wars'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
-      "\u001b[0;32m<ipython-input-9-0c5cf399e032>\u001b[0m in \u001b[0;36mbfs_search\u001b[0;34m(start, goal, debug)\u001b[0m\n\u001b[1;32m     10\u001b[0m         \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m             \u001b[0msuccessors\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mextend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcurrent\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m             \u001b[0magenda\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0magenda\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0msuccessors\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0magenda\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mcurrent\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
-      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
-     ]
+     "data": {
+      "text/plain": [
+       "6"
+      ]
+     },
+     "execution_count": 19,
+     "metadata": {},
+     "output_type": "execute_result"
     }
    ],
    "source": [
-    "len(bfs_search('vice', 'wars'))"
+    "len(astar_search('vice', 'wars'))"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 19,
+   "execution_count": 20,
    "metadata": {
-    "collapsed": false
+    "collapsed": true
    },
+   "outputs": [],
+   "source": [
+    "# len(bfs_search('vice', 'wars'))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 21,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -414,7 +411,7 @@
        "6"
       ]
      },
-     "execution_count": 19,
+     "execution_count": 21,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -425,10 +422,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 20,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 22,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -436,7 +431,7 @@
        "793"
       ]
      },
-     "execution_count": 20,
+     "execution_count": 22,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -447,16 +442,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 21,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 23,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "1000 loops, best of 3: 225 µs per loop\n"
+      "10000 loops, best of 3: 157 µs per loop\n"
      ]
     }
    ],
@@ -467,16 +460,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 22,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 24,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "10 loops, best of 3: 22.1 ms per loop\n"
+      "100 loops, best of 3: 15.5 ms per loop\n"
      ]
     }
    ],
@@ -487,16 +478,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 23,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 25,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "1000 loops, best of 3: 280 µs per loop\n"
+      "10000 loops, best of 3: 166 µs per loop\n"
      ]
     }
    ],
@@ -507,47 +496,26 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 24,
+   "execution_count": 26,
    "metadata": {
-    "collapsed": false
+    "collapsed": true
    },
-   "outputs": [
-    {
-     "ename": "KeyboardInterrupt",
-     "evalue": "",
-     "output_type": "error",
-     "traceback": [
-      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
-      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
-      "\u001b[0;32m<ipython-input-24-ec1214959874>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mget_ipython\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrun_cell_magic\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'timeit'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m''\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"bfs_search('vice', 'wars')\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
-      "\u001b[0;32m/usr/local/lib/python3.5/dist-packages/IPython/core/interactiveshell.py\u001b[0m in \u001b[0;36mrun_cell_magic\u001b[0;34m(self, magic_name, line, cell)\u001b[0m\n\u001b[1;32m   2113\u001b[0m             \u001b[0mmagic_arg_s\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvar_expand\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mline\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstack_depth\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   2114\u001b[0m             \u001b[0;32mwith\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbuiltin_trap\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 2115\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfn\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmagic_arg_s\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcell\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   2116\u001b[0m             \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   2117\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
-      "\u001b[0;32m<decorator-gen-58>\u001b[0m in \u001b[0;36mtimeit\u001b[0;34m(self, line, cell)\u001b[0m\n",
-      "\u001b[0;32m/usr/local/lib/python3.5/dist-packages/IPython/core/magic.py\u001b[0m in \u001b[0;36m<lambda>\u001b[0;34m(f, *a, **k)\u001b[0m\n\u001b[1;32m    186\u001b[0m     \u001b[0;31m# but it's overkill for just that one bit of state.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    187\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mmagic_deco\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0marg\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 188\u001b[0;31m         \u001b[0mcall\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mlambda\u001b[0m \u001b[0mf\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mf\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    189\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    190\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mcallable\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0marg\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
-      "\u001b[0;32m/usr/local/lib/python3.5/dist-packages/IPython/core/magics/execution.py\u001b[0m in \u001b[0;36mtimeit\u001b[0;34m(self, line, cell)\u001b[0m\n\u001b[1;32m   1042\u001b[0m             \u001b[0mnumber\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1043\u001b[0m             \u001b[0;32mfor\u001b[0m \u001b[0m_\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m10\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1044\u001b[0;31m                 \u001b[0mtime_number\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtimer\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtimeit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnumber\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1045\u001b[0m                 \u001b[0mworst_tuning\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mworst_tuning\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtime_number\u001b[0m \u001b[0;34m/\u001b[0m \u001b[0mnumber\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1046\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mtime_number\u001b[0m \u001b[0;34m>=\u001b[0m \u001b[0;36m0.2\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
-      "\u001b[0;32m/usr/local/lib/python3.5/dist-packages/IPython/core/magics/execution.py\u001b[0m in \u001b[0;36mtimeit\u001b[0;34m(self, number)\u001b[0m\n\u001b[1;32m    137\u001b[0m         \u001b[0mgc\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdisable\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    138\u001b[0m         \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 139\u001b[0;31m             \u001b[0mtiming\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minner\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mit\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtimer\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    140\u001b[0m         \u001b[0;32mfinally\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    141\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mgcold\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
-      "\u001b[0;32m<magic-timeit>\u001b[0m in \u001b[0;36minner\u001b[0;34m(_it, _timer)\u001b[0m\n",
-      "\u001b[0;32m<ipython-input-9-0c5cf399e032>\u001b[0m in \u001b[0;36mbfs_search\u001b[0;34m(start, goal, debug)\u001b[0m\n\u001b[1;32m     10\u001b[0m         \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m             \u001b[0msuccessors\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mextend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcurrent\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m             \u001b[0magenda\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0magenda\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0msuccessors\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0magenda\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mcurrent\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
-      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
-     ]
-    }
-   ],
+   "outputs": [],
    "source": [
-    "%%timeit\n",
-    "bfs_search('vice', 'wars')"
+    "# %%timeit\n",
+    "# bfs_search('vice', 'wars')"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 25,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 27,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "1 loop, best of 3: 1.12 s per loop\n"
+      "1 loop, best of 3: 554 ms per loop\n"
      ]
     }
    ],
@@ -558,16 +526,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 26,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 28,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "10 loops, best of 3: 127 ms per loop\n"
+      "10 loops, best of 3: 90.6 ms per loop\n"
      ]
     }
    ],
@@ -594,7 +560,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 27,
+   "execution_count": 29,
    "metadata": {
     "collapsed": true
    },
@@ -616,9 +582,38 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 28,
+   "execution_count": 30,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "['bash',\n",
+       " 'cash',\n",
+       " 'dash',\n",
+       " 'gash',\n",
+       " 'hash',\n",
+       " 'lash',\n",
+       " 'mash',\n",
+       " 'sash',\n",
+       " 'wash',\n",
+       " 'rush',\n",
+       " 'rasp']"
+      ]
+     },
+     "execution_count": 30,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "neighbours['rash']"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 31,
    "metadata": {
-    "collapsed": false,
     "scrolled": true
    },
    "outputs": [
@@ -629,7 +624,7 @@
        " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
       ]
      },
-     "execution_count": 28,
+     "execution_count": 31,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -640,9 +635,31 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 29,
+   "execution_count": 32,
+   "metadata": {
+    "scrolled": true
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "(11,\n",
+       " '<code>bash</code>, <code>cash</code>, <code>dash</code>, <code>gash</code>, <code>hash</code>, <code>lash</code>, <code>mash</code>, <code>rasp</code>, <code>rush</code>, <code>sash</code>, <code>wash</code>')"
+      ]
+     },
+     "execution_count": 32,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "len(reachable_in('rash', 1)), ', '.join(sorted('<code>{}</code>'.format(r) for r in reachable_in('rash', 1)))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 33,
    "metadata": {
-    "collapsed": false,
     "scrolled": true
    },
    "outputs": [
@@ -653,7 +670,7 @@
        " '`base`, `bash`, `bask`, `bass`, `bast`, `bath`, `bosh`, `bush`, `case`, `cash`, `cask`, `cast`, `dash`, `dish`, `gash`, `gasp`, `gosh`, `gush`, `hash`, `hasp`, `hath`, `hush`, `lash`, `lass`, `last`, `lath`, `lush`, `mash`, `mask`, `mass`, `mast`, `math`, `mesh`, `mush`, `push`, `ramp`, `rasp`, `ruse`, `rush`, `rusk`, `rust`, `sash`, `sass`, `tush`, `wash`, `wasp`, `wish`')"
       ]
      },
-     "execution_count": 29,
+     "execution_count": 33,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -664,9 +681,31 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 30,
+   "execution_count": 34,
+   "metadata": {
+    "scrolled": true
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "(47,\n",
+       " '<code>base</code>, <code>bash</code>, <code>bask</code>, <code>bass</code>, <code>bast</code>, <code>bath</code>, <code>bosh</code>, <code>bush</code>, <code>case</code>, <code>cash</code>, <code>cask</code>, <code>cast</code>, <code>dash</code>, <code>dish</code>, <code>gash</code>, <code>gasp</code>, <code>gosh</code>, <code>gush</code>, <code>hash</code>, <code>hasp</code>, <code>hath</code>, <code>hush</code>, <code>lash</code>, <code>lass</code>, <code>last</code>, <code>lath</code>, <code>lush</code>, <code>mash</code>, <code>mask</code>, <code>mass</code>, <code>mast</code>, <code>math</code>, <code>mesh</code>, <code>mush</code>, <code>push</code>, <code>ramp</code>, <code>rasp</code>, <code>ruse</code>, <code>rush</code>, <code>rusk</code>, <code>rust</code>, <code>sash</code>, <code>sass</code>, <code>tush</code>, <code>wash</code>, <code>wasp</code>, <code>wish</code>')"
+      ]
+     },
+     "execution_count": 34,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "len(reachable_in('rash', 2)), ', '.join(sorted('<code>{}</code>'.format(r) for r in reachable_in('rash', 2)))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 35,
    "metadata": {
-    "collapsed": false,
     "scrolled": true
    },
    "outputs": [
@@ -676,7 +715,7 @@
        "180"
       ]
      },
-     "execution_count": 30,
+     "execution_count": 35,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -687,9 +726,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 31,
+   "execution_count": 36,
    "metadata": {
-    "collapsed": false,
     "scrolled": true
    },
    "outputs": [
@@ -699,7 +737,7 @@
        "2195"
       ]
      },
-     "execution_count": 31,
+     "execution_count": 36,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -710,9 +748,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 32,
+   "execution_count": 37,
    "metadata": {
-    "collapsed": false,
     "scrolled": true
    },
    "outputs": [
@@ -722,7 +759,7 @@
        "2192"
       ]
      },
-     "execution_count": 32,
+     "execution_count": 37,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -733,9 +770,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 33,
+   "execution_count": 38,
    "metadata": {
-    "collapsed": false,
     "scrolled": true
    },
    "outputs": [
@@ -743,7 +779,7 @@
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "100 loops, best of 3: 9.26 ms per loop\n"
+      "100 loops, best of 3: 5.81 ms per loop\n"
      ]
     }
    ],
@@ -754,9 +790,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 34,
+   "execution_count": 39,
    "metadata": {
-    "collapsed": false,
     "scrolled": true
    },
    "outputs": [
@@ -764,7 +799,7 @@
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "100 loops, best of 3: 3.64 ms per loop\n"
+      "100 loops, best of 3: 2.71 ms per loop\n"
      ]
     }
    ],
@@ -773,6 +808,256 @@
     "len(reachable_in('rash', 10, trim_extras=True))"
    ]
   },
+  {
+   "cell_type": "code",
+   "execution_count": 40,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "2188"
+      ]
+     },
+     "execution_count": 40,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "len(reachable_in('stay', 10))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 41,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "2193"
+      ]
+     },
+     "execution_count": 41,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "len(reachable_in('coax', 10))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 42,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "280"
+      ]
+     },
+     "execution_count": 42,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "stay5 = reachable_in('stay', 4)\n",
+    "len(stay5)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 43,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "296"
+      ]
+     },
+     "execution_count": 43,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "extras = set()\n",
+    "for w in stay5:\n",
+    "    extras.update(neighbours[w])\n",
+    "extras.difference_update(stay5)\n",
+    "len(extras)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 44,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "'know step yeps test pout book beck poor boos veep teed gent saws dyer hemp soon deem legs bets twit whim belt rock well bled whet prop spec weep peed loan week clef feed lock yens vent doer less teem toot yews blur clue pert pegs brew flea trig vets sued felt perk bobs brat tens beef leap bloc shoo moan boob jeez suet sits rood drag goat stay chip fled fist than loot pets suck peek pled heel hair sill prep char knot lens meek trap jeep beet crew draw tell nets peep meet sows glue bees bent pelt whit need foot bran chop gram chew teen veil lent gees fret soft leis pent gets weed keen reek news prim drab wets sics deed bows pier akin pock geed grey bogs goad skis peck prod loam keep pens hoot best reed yous sewn been tram pest whom bout unit deep boot dual lees omit peel sues berm dock yock shes lets mock grow jell whip lean thin sots geek stem floe tees sort fees gout mead dram said twin prom bras bier heft foul root fell melt bops coup coot atop brad chin moot shoe sacs chit hell door lead feet boon bolt leaf bell bias eery goop reel text boom herd rent leek rend club self send sick term airs frog yell next czar plus mean brow foam crow troy nest heed dell load glib peps cent chow pees bend jock held tent soil poop moor sped emit boss fest crop mews knit tout crag knob grab thaw vial sack help jets very boys flue whir newt wiry beep room pews crab baas cock coop hock blue flee moat skid quit dial brag cell aloe grad hews went leak toad wees mewl coat dent'"
+      ]
+     },
+     "execution_count": 44,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "' '.join(extras)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 45,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
+      ]
+     },
+     "execution_count": 45,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "astar_search('coax', 'stay')"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 46,
+   "metadata": {},
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "CPU times: user 620 ms, sys: 4 ms, total: 624 ms\n",
+      "Wall time: 624 ms\n"
+     ]
+    },
+    {
+     "data": {
+      "text/plain": [
+       "['coax', 'coat', 'chat', 'shat', 'spat', 'spay', 'stay']"
+      ]
+     },
+     "execution_count": 46,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "%time bfs_search_closed('coax', 'stay')"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 47,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "# %time bfs_search('coax', 'stay')"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 48,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
+      ]
+     },
+     "execution_count": 48,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "astar_search('czar', 'stay')"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 49,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "# %time bfs_search('czar', 'stay')"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 50,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "# %time bfs_search('coax', 'stay')"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 79,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "185"
+      ]
+     },
+     "execution_count": 79,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "rushn = reachable_in('rush', 3)\n",
+    "rushn.add('rush')\n",
+    "len(rushn)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 80,
+   "metadata": {
+    "scrolled": true
+   },
+   "outputs": [],
+   "source": [
+    "links = set()\n",
+    "for w in rushn:\n",
+    "    for n in neighbours[w]:\n",
+    "        if n in rushn:\n",
+    "            links.add(frozenset((n, w)))\n",
+    "\n",
+    "with open('rush3.dot', 'w') as f:\n",
+    "    f.write('graph g {\\n')\n",
+    "    for l in links:\n",
+    "        lt = tuple(l)\n",
+    "        f.write('\"{}\" -- \"{}\";\\n'.format(lt[0], lt[1]))\n",
+    "    f.write('}\\n')"
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": null,
@@ -799,7 +1084,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
-   "version": "3.5.2"
+   "version": "3.5.2+"
   }
  },
  "nbformat": 4,