X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=08-word-chains%2Fword-chain-solution.ipynb;h=3f28b2ce6a2cf2be94e89103ef5d521103e081bf;hb=a3695711a670f04d92097fc0d664eba25685ebdf;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..3f28b2c 100644
--- a/08-word-chains/word-chain-solution.ipynb
+++ b/08-word-chains/word-chain-solution.ipynb
@@ -40,9 +40,7 @@
{
"cell_type": "code",
"execution_count": 2,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
@@ -56,7 +54,7 @@
}
],
"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)"
]
},
@@ -314,9 +312,7 @@
{
"cell_type": "code",
"execution_count": 15,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
@@ -336,9 +332,7 @@
{
"cell_type": "code",
"execution_count": 16,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
@@ -358,14 +352,12 @@
{
"cell_type": "code",
"execution_count": 17,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
"text/plain": [
- "6"
+ "['boon', 'boot', 'bolt', 'belt', 'bell', 'sell']"
]
},
"execution_count": 17,
@@ -374,39 +366,42 @@
}
],
"source": [
- "len(astar_search('vice', 'wars'))"
+ "astar_search_raw('boon', 'sell')"
]
},
{
"cell_type": "code",
"execution_count": 18,
- "metadata": {
- "collapsed": false
- },
+ "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": 18,
+ "metadata": {},
+ "output_type": "execute_result"
}
],
"source": [
- "len(bfs_search('vice', 'wars'))"
+ "len(astar_search('vice', 'wars'))"
]
},
{
"cell_type": "code",
"execution_count": 19,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "# len(bfs_search('vice', 'wars'))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 20,
+ "metadata": {},
"outputs": [
{
"data": {
@@ -414,7 +409,7 @@
"6"
]
},
- "execution_count": 19,
+ "execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
@@ -425,10 +420,8 @@
},
{
"cell_type": "code",
- "execution_count": 20,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 21,
+ "metadata": {},
"outputs": [
{
"data": {
@@ -436,7 +429,7 @@
"793"
]
},
- "execution_count": 20,
+ "execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
@@ -447,16 +440,14 @@
},
{
"cell_type": "code",
- "execution_count": 21,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 22,
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1000 loops, best of 3: 225 µs per loop\n"
+ "10000 loops, best of 3: 153 µs per loop\n"
]
}
],
@@ -467,16 +458,14 @@
},
{
"cell_type": "code",
- "execution_count": 22,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 23,
+ "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.7 ms per loop\n"
]
}
],
@@ -487,16 +476,14 @@
},
{
"cell_type": "code",
- "execution_count": 23,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 24,
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1000 loops, best of 3: 280 µs per loop\n"
+ "10000 loops, best of 3: 165 µs per loop\n"
]
}
],
@@ -507,47 +494,24 @@
},
{
"cell_type": "code",
- "execution_count": 24,
- "metadata": {
- "collapsed": false
- },
- "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: "
- ]
- }
- ],
+ "execution_count": 25,
+ "metadata": {},
+ "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": 26,
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 1.12 s per loop\n"
+ "1 loop, best of 3: 446 ms per loop\n"
]
}
],
@@ -558,16 +522,14 @@
},
{
"cell_type": "code",
- "execution_count": 26,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 27,
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "10 loops, best of 3: 127 ms per loop\n"
+ "10 loops, best of 3: 91.4 ms per loop\n"
]
}
],
@@ -594,7 +556,7 @@
},
{
"cell_type": "code",
- "execution_count": 27,
+ "execution_count": 28,
"metadata": {
"collapsed": true
},
@@ -616,9 +578,38 @@
},
{
"cell_type": "code",
- "execution_count": 28,
+ "execution_count": 29,
+ "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": 29,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "neighbours['rash']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 30,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
@@ -629,7 +620,7 @@
" '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
]
},
- "execution_count": 28,
+ "execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
@@ -640,9 +631,31 @@
},
{
"cell_type": "code",
- "execution_count": 29,
+ "execution_count": 31,
+ "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": 31,
+ "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": 32,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
@@ -653,7 +666,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": 32,
"metadata": {},
"output_type": "execute_result"
}
@@ -664,9 +677,31 @@
},
{
"cell_type": "code",
- "execution_count": 30,
+ "execution_count": 33,
+ "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": 33,
+ "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": 34,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
@@ -676,7 +711,7 @@
"180"
]
},
- "execution_count": 30,
+ "execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
@@ -687,9 +722,8 @@
},
{
"cell_type": "code",
- "execution_count": 31,
+ "execution_count": 35,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
@@ -699,7 +733,7 @@
"2195"
]
},
- "execution_count": 31,
+ "execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
@@ -710,9 +744,8 @@
},
{
"cell_type": "code",
- "execution_count": 32,
+ "execution_count": 36,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
@@ -722,7 +755,7 @@
"2192"
]
},
- "execution_count": 32,
+ "execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
@@ -733,9 +766,8 @@
},
{
"cell_type": "code",
- "execution_count": 33,
+ "execution_count": 37,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
@@ -743,7 +775,7 @@
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 9.26 ms per loop\n"
+ "100 loops, best of 3: 5.84 ms per loop\n"
]
}
],
@@ -754,9 +786,8 @@
},
{
"cell_type": "code",
- "execution_count": 34,
+ "execution_count": 38,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
@@ -764,7 +795,7 @@
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 3.64 ms per loop\n"
+ "100 loops, best of 3: 2.79 ms per loop\n"
]
}
],
@@ -773,6 +804,206 @@
"len(reachable_in('rash', 10, trim_extras=True))"
]
},
+ {
+ "cell_type": "code",
+ "execution_count": 39,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2188"
+ ]
+ },
+ "execution_count": 39,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('stay', 10))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 40,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2193"
+ ]
+ },
+ "execution_count": 40,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('coax', 10))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 41,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "280"
+ ]
+ },
+ "execution_count": 41,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "stay5 = reachable_in('stay', 4)\n",
+ "len(stay5)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 42,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "296"
+ ]
+ },
+ "execution_count": 42,
+ "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": 43,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'akin moot mead clef yens bees sewn yous grow pelt less sacs pens gout pegs heel whom reel gent czar boot whim lens toot dial goat prop boob dock fret help blue bell sits lead vial vent reed mean need poor cent peek bras lets wees bolt knit foul boos twin baas boss toad bier frog tout hews dell week fell pier omit coup skid whet trig newt peps prom leap atop mews quit hair leek wets rood know book geek teed moat yeps draw sort goad tens door skis weed whip troy lean club pets crow dent sows suck bout well reek floe bogs test sues dram deem legs tram spec peep room hoot flee shoe stem airs teem rent pert peel belt char sped sics moan loot prod lent heft next boom bias chow said news beep step dyer herd sick deep send boys stay leak yock mewl very bops fled moor aloe dual sots peck teen tent whir nest bows coat pout beef sued shes brew jell grey trap glue feed doer been flue drab whit bran hemp saws boon blur coot beet jets text thaw keen jock eery mock foam heed brow deed rend drag crew feet thin grab bend chip veep grad pled tees crab veil chit cell fees meet jeez went goop load self keep emit rock crop sack chin soon pock meek tell yell pews pest soil bled knot pees gees jeep gets loam sill berm chop than glib brag lock hock plus crag bloc prim foot root coop cock twit brad pent soft leis bent hell bobs fist gram term held vets wiry perk flea clue shoo brat bets peed loan yews knob geed poop nets beck fest suet best felt chew lees prep leaf weep unit melt'"
+ ]
+ },
+ "execution_count": 43,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "' '.join(extras)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 44,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
+ ]
+ },
+ "execution_count": 44,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "astar_search('coax', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 45,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "CPU times: user 1.54 s, sys: 0 ns, total: 1.54 s\n",
+ "Wall time: 1.54 s\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "['coax', 'coat', 'chat', 'shat', 'spat', 'spay', 'stay']"
+ ]
+ },
+ "execution_count": 45,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "%time bfs_search_closed('coax', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 46,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "# %time bfs_search('coax', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 47,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
+ ]
+ },
+ "execution_count": 47,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "astar_search('czar', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 48,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "# %time bfs_search('czar', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 49,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "# %time bfs_search('coax', 'stay')"
+ ]
+ },
{
"cell_type": "code",
"execution_count": null,
@@ -799,7 +1030,7 @@
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
- "version": "3.5.2"
+ "version": "3.5.2+"
}
},
"nbformat": 4,