X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=08-word-chains%2Fexplore-word-chain-4.ipynb;h=5449951bf02476cc6fbebe11cb07a34d507e683f;hb=881b1889a51e7a0ea314b59234c477e0849c0427;hp=c2bca54e673d7b4e8236f540d5057f7dd72bd263;hpb=2f750972c876ebbb88e1af96be1ce74b4d3558f8;p=ou-summer-of-code-2017.git

diff --git a/08-word-chains/explore-word-chain-4.ipynb b/08-word-chains/explore-word-chain-4.ipynb
index c2bca54..5449951 100644
--- a/08-word-chains/explore-word-chain-4.ipynb
+++ b/08-word-chains/explore-word-chain-4.ipynb
@@ -17,9 +17,7 @@
   {
    "cell_type": "code",
    "execution_count": 2,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -33,16 +31,14 @@
     }
    ],
    "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,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -115,9 +111,7 @@
   {
    "cell_type": "code",
    "execution_count": 7,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -137,9 +131,7 @@
   {
    "cell_type": "code",
    "execution_count": 8,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -172,9 +164,7 @@
   {
    "cell_type": "code",
    "execution_count": 10,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -211,9 +201,7 @@
   {
    "cell_type": "code",
    "execution_count": 12,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -233,9 +221,7 @@
   {
    "cell_type": "code",
    "execution_count": 13,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -255,9 +241,7 @@
   {
    "cell_type": "code",
    "execution_count": 14,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -294,7 +278,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        "
@@ -322,7 +306,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        "
@@ -331,9 +315,7 @@
   {
    "cell_type": "code",
    "execution_count": 17,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
@@ -381,7 +363,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        "
@@ -390,9 +372,7 @@
   {
    "cell_type": "code",
    "execution_count": 19,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
@@ -423,9 +403,7 @@
   {
    "cell_type": "code",
    "execution_count": 20,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
@@ -942,7 +920,13 @@
       "['cart', 'mart', 'mare', 'mire']\n",
       "['cart', 'mart', 'mare', 'more']\n",
       "['cart', 'mart', 'mare', 'mace']\n",
-      "['cart', 'mart', 'mare', 'made']\n",
+      "['cart', 'mart', 'mare', 'made']\n"
+     ]
+    },
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
       "['cart', 'mart', 'mare', 'make']\n",
       "['cart', 'mart', 'mare', 'male']\n",
       "['cart', 'mart', 'mare', 'mane']\n",
@@ -1502,7 +1486,13 @@
       "['cart', 'cant', 'rant', 'raft']\n",
       "['cart', 'cant', 'rant', 'rapt']\n",
       "['cart', 'cant', 'rant', 'rang']\n",
-      "['cart', 'cant', 'rant', 'rank']\n",
+      "['cart', 'cant', 'rant', 'rank']\n"
+     ]
+    },
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
       "['cart', 'cant', 'want', 'pant']\n",
       "['cart', 'cant', 'want', 'rant']\n",
       "['cart', 'cant', 'want', 'went']\n",
@@ -1579,9 +1569,7 @@
   {
    "cell_type": "code",
    "execution_count": 21,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -1601,9 +1589,7 @@
   {
    "cell_type": "code",
    "execution_count": 22,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2219,7 +2205,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        "
@@ -2228,9 +2214,7 @@
   {
    "cell_type": "code",
    "execution_count": 24,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
@@ -2259,7 +2243,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 25,
+   "execution_count": 81,
    "metadata": {
     "collapsed": true
    },
@@ -2281,7 +2265,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        "
@@ -2290,9 +2274,7 @@
   {
    "cell_type": "code",
    "execution_count": 26,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
@@ -2330,10 +2312,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 77,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 27,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2341,7 +2321,7 @@
        "94"
       ]
      },
-     "execution_count": 77,
+     "execution_count": 27,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2367,10 +2347,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 78,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 28,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2378,7 +2356,7 @@
        "2204"
       ]
      },
-     "execution_count": 78,
+     "execution_count": 28,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2389,10 +2367,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 79,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 29,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2400,7 +2376,7 @@
        "1"
       ]
      },
-     "execution_count": 79,
+     "execution_count": 29,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2411,9 +2387,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 80,
+   "execution_count": 30,
    "metadata": {
-    "collapsed": false,
     "scrolled": true
    },
    "outputs": [
@@ -2423,7 +2398,7 @@
        "Counter({1: 75, 2: 6, 3: 7, 4: 2, 5: 2, 6: 1, 2204: 1})"
       ]
      },
-     "execution_count": 80,
+     "execution_count": 30,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2434,10 +2409,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 81,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 31,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2445,7 +2418,7 @@
        "[5]"
       ]
      },
-     "execution_count": 81,
+     "execution_count": 31,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2456,10 +2429,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 82,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 32,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2467,7 +2438,7 @@
        "[{'abbe', 'able', 'ably', 'ally', 'axle'}]"
       ]
      },
-     "execution_count": 82,
+     "execution_count": 32,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2478,10 +2449,67 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 83,
+   "execution_count": 76,
    "metadata": {
-    "collapsed": false
+    "scrolled": true
    },
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[{'demo', 'memo'},\n",
+       " {'thou', 'thru'},\n",
+       " {'crud', 'crux'},\n",
+       " {'bevy', 'levy'},\n",
+       " {'ogle', 'ogre'},\n",
+       " {'idol', 'idyl'},\n",
+       " {'also', 'alto', 'auto'},\n",
+       " {'used', 'user', 'uses'},\n",
+       " {'idle', 'idly', 'isle'},\n",
+       " {'eddy', 'edge', 'edgy'},\n",
+       " {'opal', 'oral', 'oval'},\n",
+       " {'icon', 'ikon', 'iron'},\n",
+       " {'afar', 'agar', 'ajar'},\n",
+       " {'each', 'etch', 'inch', 'itch'},\n",
+       " {'high', 'nigh', 'sigh', 'sign'},\n",
+       " {'abbe', 'able', 'ably', 'ally', 'axle'},\n",
+       " {'info', 'into', 'onto', 'undo', 'unto'},\n",
+       " {'ache', 'achy', 'acme', 'acne', 'acre', 'ashy'}]"
+      ]
+     },
+     "execution_count": 76,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "sorted((r for r in reachables if len(r) > 1 if len(r) < 10), key=len)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 80,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "'adze; agog; ague; ahoy; alga; ammo; amok; anal; ankh; apse; aqua; aura; avow; awol; bozo; ebbs; echo; ecru; emus; ends; envy; epee; epic; espy; euro; evil; exam; expo; guru; hymn; ibex; iffy; imam; iota; isms; judo; kiwi; liar; luau; lynx; mayo; meow; myna; nova; obey; oboe; odor; ohms; okra; oleo; once; onyx; orgy; ovum; rely; rhea; semi; sexy; stye; sync; taxi; tofu; tuft; tutu; twos; ugly; ulna; upon; urge; uric; urns; void; wiki; yeti; zebu'"
+      ]
+     },
+     "execution_count": 80,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "'; '.join(sorted(list(r)[0] for r in reachables if len(r) == 1))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 33,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2489,7 +2517,7 @@
        "['buns', 'bunk', 'punk']"
       ]
      },
-     "execution_count": 83,
+     "execution_count": 33,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2500,7 +2528,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 84,
+   "execution_count": 34,
    "metadata": {
     "collapsed": true
    },
@@ -2515,7 +2543,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 85,
+   "execution_count": 35,
    "metadata": {
     "collapsed": true
    },
@@ -2538,7 +2566,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 86,
+   "execution_count": 36,
    "metadata": {
     "collapsed": true
    },
@@ -2549,35 +2577,33 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 87,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 37,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "['late', 'lats', 'lets', 'leas', 'seas', 'seam', 'swam', 'sway']\n",
-      "['leap', 'heap', 'hear', 'dear', 'deer']\n",
-      "['peel', 'peek', 'perk', 'park', 'nark']\n",
-      "['sing', 'sang', 'sand', 'said', 'sail', 'hail', 'haul']\n",
-      "['vats', 'bats', 'bets', 'bees', 'been', 'teen', 'then', 'thin', 'this', 'thus', 'thud']\n",
-      "['sues', 'sees', 'seen', 'sewn', 'hewn']\n",
-      "['rash', 'bash', 'bast', 'bait', 'bail', 'hail', 'hair', 'heir']\n",
-      "['apex', 'aped', 'sped', 'seed', 'deed', 'dead', 'deal', 'veal']\n",
-      "['gulf', 'golf', 'gold', 'bold', 'bond', 'bony', 'tony']\n",
-      "['snag', 'shag', 'shat', 'seat', 'peat', 'pent', 'pint', 'mint']\n",
-      "['rife', 'rime', 'rims', 'rums', 'cums', 'cuss']\n",
-      "['diss', 'kiss', 'kits']\n",
-      "['gyps', 'gaps', 'gads', 'wads', 'wade', 'wide', 'tide']\n",
-      "['bilk', 'bill', 'bell', 'tell', 'teal', 'tear', 'tzar']\n",
-      "['logo', 'loge', 'lode', 'lade', 'jade', 'jape']\n",
-      "['hunt', 'bunt', 'buns', 'nuns', 'nubs']\n",
-      "['glow', 'glop', 'plop', 'prop', 'prep', 'peep', 'keep']\n",
-      "['iamb', 'lamb', 'lams', 'laps', 'lips', 'pips']\n",
-      "['pain', 'lain', 'laid', 'land', 'lend', 'vend', 'veld']\n",
-      "['fake', 'bake', 'bare', 'bars', 'ears', 'errs', 'ergs', 'eggs', 'egos']\n"
+      "['army', 'arms', 'aims', 'aids', 'bids', 'bias', 'boas', 'boat', 'goat', 'gnat', 'gnaw']\n",
+      "['hoes', 'toes', 'toms', 'tams', 'tame']\n",
+      "['vane', 'vine', 'wine', 'wire', 'wiry', 'airy', 'awry', 'away']\n",
+      "['mate', 'late', 'lane', 'land', 'laid', 'lain']\n",
+      "['heal', 'head', 'bead', 'bend', 'bond', 'bone']\n",
+      "['dune', 'dine', 'dins', 'dies', 'died', 'tied']\n",
+      "['ions', 'dons', 'does', 'hoes', 'hoed', 'heed']\n",
+      "['puck', 'pick', 'pink', 'mink', 'mine']\n",
+      "['need', 'deed', 'died', 'dies', 'dims', 'dams', 'days', 'drys']\n",
+      "['pore', 'core', 'code', 'cods', 'cuds']\n",
+      "['mote', 'mite', 'mile', 'wile', 'wise']\n",
+      "['wait', 'wail', 'mail', 'mall', 'male']\n",
+      "['wail', 'bail', 'ball', 'boll', 'bolt', 'boot', 'boom', 'zoom']\n",
+      "['beat', 'beet', 'bees', 'bets', 'bats', 'cats']\n",
+      "['tore', 'tire', 'tile', 'vile', 'vise', 'visa']\n",
+      "['went', 'pent', 'pant']\n",
+      "['lick', 'sick', 'sics', 'sips', 'sops', 'oops']\n",
+      "['womb', 'tomb', 'toms', 'toes', 'does', 'dyes', 'ayes', 'apes', 'aped']\n",
+      "['cure', 'sure']\n",
+      "['cute', 'cuts', 'guts', 'guys', 'gays']\n"
      ]
     }
    ],
@@ -2590,9 +2616,7 @@
   {
    "cell_type": "code",
    "execution_count": 38,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2612,9 +2636,7 @@
   {
    "cell_type": "code",
    "execution_count": 39,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2634,14 +2656,12 @@
   {
    "cell_type": "code",
    "execution_count": 40,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "['hate', 'have', 'hove', 'love']"
+       "[2204]"
       ]
      },
      "execution_count": 40,
@@ -2650,20 +2670,18 @@
     }
    ],
    "source": [
-    "astar_search('hate', 'love')"
+    "[len(r) for r in reachables if 'stay' in r ]"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": 41,
-   "metadata": {
-    "collapsed": false
-   },
+   "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "['wars', 'ware', 'wave', 'wove', 'love']"
+       "['hate', 'have', 'hove', 'love']"
       ]
      },
      "execution_count": 41,
@@ -2672,52 +2690,40 @@
     }
    ],
    "source": [
-    "astar_search('wars', 'love')"
+    "astar_search('hate', 'love')"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 61,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 42,
+   "metadata": {},
    "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
-      "Wall time: 210 µs\n"
-     ]
-    },
     {
      "data": {
       "text/plain": [
-       "5"
+       "['wars', 'ware', 'wave', 'wove', 'love']"
       ]
      },
-     "execution_count": 61,
+     "execution_count": 42,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
-    "%time len(astar_search('wars', 'love'))"
+    "astar_search('wars', 'love')"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 62,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 43,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
       "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
-      "Wall time: 252 µs\n"
+      "Wall time: 185 µs\n"
      ]
     },
     {
@@ -2726,88 +2732,93 @@
        "5"
       ]
      },
-     "execution_count": 62,
+     "execution_count": 43,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
-    "%time len(astar_search_closed('wars', 'love'))"
+    "%time len(astar_search('wars', 'love'))"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 63,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 44,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "CPU times: user 24 ms, sys: 0 ns, total: 24 ms\n",
-      "Wall time: 24.2 ms\n"
+      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
+      "Wall time: 398 µs\n"
      ]
     },
     {
      "data": {
       "text/plain": [
-       "404"
+       "5"
       ]
      },
-     "execution_count": 63,
+     "execution_count": 44,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
-    "%time len(dfs_search('wars', 'love'))"
+    "%time len(astar_search_closed('wars', 'love'))"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 64,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 45,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "CPU times: user 5min 20s, sys: 76 ms, total: 5min 20s\n",
-      "Wall time: 5min 20s\n"
+      "CPU times: user 32 ms, sys: 0 ns, total: 32 ms\n",
+      "Wall time: 32.3 ms\n"
      ]
     },
     {
      "data": {
       "text/plain": [
-       "5"
+       "404"
       ]
      },
-     "execution_count": 64,
+     "execution_count": 45,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
-    "%time len(bfs_search('wars', 'love'))"
+    "%time len(dfs_search('wars', 'love'))"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 65,
+   "execution_count": 46,
    "metadata": {
-    "collapsed": false
+    "collapsed": true
    },
+   "outputs": [],
+   "source": [
+    "# %time len(bfs_search('wars', 'love'))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 47,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "CPU times: user 1.44 s, sys: 0 ns, total: 1.44 s\n",
-      "Wall time: 1.43 s\n"
+      "CPU times: user 212 ms, sys: 0 ns, total: 212 ms\n",
+      "Wall time: 213 ms\n"
      ]
     },
     {
@@ -2816,7 +2827,7 @@
        "5"
       ]
      },
-     "execution_count": 65,
+     "execution_count": 47,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2827,10 +2838,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 42,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 48,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2838,7 +2847,7 @@
        "['fear', 'feat', 'fest', 'lest', 'lost', 'lose', 'love']"
       ]
      },
-     "execution_count": 42,
+     "execution_count": 48,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2849,10 +2858,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 43,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 49,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2860,7 +2867,7 @@
        "['fail', 'fall', 'pall', 'pals', 'pass']"
       ]
      },
-     "execution_count": 43,
+     "execution_count": 49,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2871,10 +2878,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 44,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 50,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2882,7 +2887,7 @@
        "['star', 'soar', 'boar', 'boor', 'boon', 'born']"
       ]
      },
-     "execution_count": 44,
+     "execution_count": 50,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2893,10 +2898,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 45,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 51,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2914,7 +2917,7 @@
        " 'pass']"
       ]
      },
-     "execution_count": 45,
+     "execution_count": 51,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2925,10 +2928,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 46,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 52,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2949,7 +2950,7 @@
        " 'past']"
       ]
      },
-     "execution_count": 46,
+     "execution_count": 52,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2960,10 +2961,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 47,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 53,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2971,7 +2970,7 @@
        "[1]"
       ]
      },
-     "execution_count": 47,
+     "execution_count": 53,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -2982,10 +2981,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 48,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 54,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -2993,7 +2990,7 @@
        "[2204]"
       ]
      },
-     "execution_count": 48,
+     "execution_count": 54,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -3004,16 +3001,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 49,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 55,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "1 loop, best of 3: 7.9 s per loop\n"
+      "1 loop, best of 3: 8.21 s per loop\n"
      ]
     }
    ],
@@ -3024,16 +3019,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 50,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 56,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "10 loops, best of 3: 141 ms per loop\n"
+      "10 loops, best of 3: 145 ms per loop\n"
      ]
     }
    ],
@@ -3044,10 +3037,8 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 51,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 57,
+   "metadata": {},
    "outputs": [
     {
      "data": {
@@ -3064,7 +3055,7 @@
        " 'exit']"
       ]
      },
-     "execution_count": 51,
+     "execution_count": 57,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -3075,55 +3066,31 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 88,
+   "execution_count": 58,
    "metadata": {
-    "collapsed": false
+    "collapsed": true
    },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "{2: [['heel', 'keel'], ['wane', 'wave'], ['cell', 'sell'], ['cons', 'cobs']],\n",
-       " 3: [['hank', 'haws'], ['bars', 'bets'], ['rats', 'paws'], ['lock', 'hack']],\n",
-       " 4: [['rule', 'sore'], ['wavy', 'rape'], ['peas', 'ping'], ['bond', 'toll']],\n",
-       " 5: [['cope', 'yowl'], ['lose', 'loci'], ['rump', 'dash'], ['four', 'dyes']],\n",
-       " 6: [['boon', 'sell'], ['lots', 'pomp'], ['cola', 'turn'], ['boos', 'laid']],\n",
-       " 7: [['eave', 'inns'], ['meek', 'mere'], ['keys', 'wily'], ['slam', 'yore']],\n",
-       " 8: [['hack', 'flip'], ['crag', 'huge'], ['flux', 'gill'], ['play', 'busy']],\n",
-       " 9: [['lacy', 'whey'], ['wren', 'rook'], ['lire', 'drip'], ['grab', 'lame']],\n",
-       " 10: [['over', 'turn'], ['worn', 'anew'], ['stow', 'elks'], ['ergo', 'rich']],\n",
-       " 11: [['bask', 'idea'], ['gabs', 'thud'], ['idea', 'clod'], ['mark', 'ibis']],\n",
-       " 12: [['umps', 'torn'], ['futz', 'shun'], ['abut', 'face'], ['slug', 'open']],\n",
-       " 13: [['umps', 'skin'], ['chum', 'rats'], ['fury', 'chum'], ['omen', 'zany']],\n",
-       " 14: [['chug', 'gaff'], ['atom', 'fizz']],\n",
-       " 15: [['chug', 'oxen']]}"
-      ]
-     },
-     "execution_count": 88,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
+   "outputs": [],
    "source": [
-    "solutions = {}\n",
-    "for _ in range(10000):\n",
-    "    start, goal = random.sample(bigset, 2)\n",
-    "    solution = astar_search_closed(start, goal)\n",
-    "    sl = len(solution)\n",
-    "    if sl not in solutions:\n",
-    "        solutions[sl] = []\n",
-    "    if len(solutions[sl]) < 4:\n",
-    "        solutions[sl].append([start, goal])\n",
+    "# solutions = {}\n",
+    "# for _ in range(10000):\n",
+    "#     start, goal = random.sample(bigset, 2)\n",
+    "#     solution = astar_search_closed(start, goal)\n",
+    "#     sl = len(solution)\n",
+    "#     if sl not in solutions:\n",
+    "#         solutions[sl] = []\n",
+    "#     if len(solutions[sl]) < 4:\n",
+    "#         solutions[sl].append([start, goal])\n",
     "        \n",
-    "#     if len(solution) >= 10:\n",
-    "#         solutions += [solution]\n",
+    "# #     if len(solution) >= 10:\n",
+    "# #         solutions += [solution]\n",
     "        \n",
-    "solutions"
+    "# solutions"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 91,
+   "execution_count": 59,
    "metadata": {
     "collapsed": true
    },
@@ -3148,38 +3115,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 54,
-   "metadata": {
-    "collapsed": false
-   },
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "[('amen', 'doff', 15), ('chug', 'jinn', 14), ('amen', 'flog', 14)]"
-      ]
-     },
-     "execution_count": 54,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
-   "source": [
-    "[(s[0], s[-1], len(s)) for s in solutions if len(s) >= 14]"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": 55,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 60,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "1 loop, best of 3: 360 ms per loop\n"
+      "1 loop, best of 3: 334 ms per loop\n"
      ]
     }
    ],
@@ -3190,17 +3133,15 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 56,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 61,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "CPU times: user 384 ms, sys: 0 ns, total: 384 ms\n",
-      "Wall time: 385 ms\n"
+      "CPU times: user 344 ms, sys: 0 ns, total: 344 ms\n",
+      "Wall time: 342 ms\n"
      ]
     },
     {
@@ -3209,7 +3150,7 @@
        "14"
       ]
      },
-     "execution_count": 56,
+     "execution_count": 61,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -3220,17 +3161,15 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 57,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 62,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "CPU times: user 124 ms, sys: 0 ns, total: 124 ms\n",
-      "Wall time: 121 ms\n"
+      "CPU times: user 92 ms, sys: 0 ns, total: 92 ms\n",
+      "Wall time: 93.7 ms\n"
      ]
     },
     {
@@ -3239,7 +3178,7 @@
        "15"
       ]
      },
-     "execution_count": 57,
+     "execution_count": 62,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -3250,17 +3189,15 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 58,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 63,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
       "CPU times: user 32 ms, sys: 0 ns, total: 32 ms\n",
-      "Wall time: 32.4 ms\n"
+      "Wall time: 32.8 ms\n"
      ]
     },
     {
@@ -3269,7 +3206,7 @@
        "14"
       ]
      },
-     "execution_count": 58,
+     "execution_count": 63,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -3280,17 +3217,15 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 59,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 64,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
       "CPU times: user 16 ms, sys: 0 ns, total: 16 ms\n",
-      "Wall time: 17.1 ms\n"
+      "Wall time: 16.4 ms\n"
      ]
     },
     {
@@ -3299,7 +3234,7 @@
        "14"
       ]
      },
-     "execution_count": 59,
+     "execution_count": 64,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -3310,17 +3245,15 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 73,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 65,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "CPU times: user 268 ms, sys: 4 ms, total: 272 ms\n",
-      "Wall time: 272 ms\n"
+      "CPU times: user 256 ms, sys: 0 ns, total: 256 ms\n",
+      "Wall time: 253 ms\n"
      ]
     },
     {
@@ -3329,7 +3262,7 @@
        "14"
       ]
      },
-     "execution_count": 73,
+     "execution_count": 65,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -3340,17 +3273,15 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 74,
-   "metadata": {
-    "collapsed": false
-   },
+   "execution_count": 66,
+   "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "CPU times: user 64 ms, sys: 0 ns, total: 64 ms\n",
-      "Wall time: 64.1 ms\n"
+      "CPU times: user 36 ms, sys: 0 ns, total: 36 ms\n",
+      "Wall time: 34.2 ms\n"
      ]
     },
     {
@@ -3359,7 +3290,7 @@
        "14"
       ]
      },
-     "execution_count": 74,
+     "execution_count": 66,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -3368,6 +3299,133 @@
     "%time len(astar_search_closed('imps', 'pros'))"
    ]
   },
+  {
+   "cell_type": "code",
+   "execution_count": 67,
+   "metadata": {},
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "bash bush True\n",
+      "rush bush True\n"
+     ]
+    },
+    {
+     "data": {
+      "text/plain": [
+       "2"
+      ]
+     },
+     "execution_count": 67,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "nb_count = collections.Counter()\n",
+    "for w in neighbours['rash']:\n",
+    "    for w2 in neighbours[w]:\n",
+    "        if w2 == 'bush': print(w, w2, w2 not in neighbours['rash'])\n",
+    "        if w2 != 'rash' and w2 not in neighbours['rash']:\n",
+    "            nb_count.update([w2])\n",
+    "nb_count.most_common(1)[0][1]"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 68,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "['gush', 'hush', 'lush', 'mush', 'push', 'tush', 'bosh']"
+      ]
+     },
+     "execution_count": 68,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "[w for w in neighbours['bush'] if w in nb_count]"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 69,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "('nose', 2)"
+      ]
+     },
+     "execution_count": 69,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "best_start = ''\n",
+    "best_overlap_count = 0\n",
+    "for w0 in neighbours:    \n",
+    "    nb_count = collections.Counter()\n",
+    "    for w in neighbours[w0]:\n",
+    "        for w2 in neighbours[w]:\n",
+    "            if w2 != w0 and w2 not in neighbours[w0]:\n",
+    "                nb_count.update([w2])\n",
+    "    if len(nb_count) > 0:\n",
+    "        if nb_count.most_common(1)[0][1] > best_overlap_count:\n",
+    "            best_start = w0\n",
+    "            best_overlap_count = nb_count.most_common(1)[0][1]\n",
+    "        \n",
+    "best_start, best_overlap_count"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 70,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "'grew'"
+      ]
+     },
+     "execution_count": 70,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "w0"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 71,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "{'bash', 'rush'}"
+      ]
+     },
+     "execution_count": 71,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "set(neighbours['rash']) & set(neighbours['bush'])"
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": null,
@@ -3394,7 +3452,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
-   "version": "3.5.2"
+   "version": "3.5.2+"
   }
  },
  "nbformat": 4,