"cells": [
{
"cell_type": "code",
- "execution_count": 1,
+ "execution_count": 4,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 2,
+ "execution_count": 5,
"metadata": {
"collapsed": false
},
"2336"
]
},
- "execution_count": 2,
+ "execution_count": 5,
"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-offices.txt').readlines()]\n",
"len(words)"
]
},
{
"cell_type": "code",
- "execution_count": 3,
+ "execution_count": 6,
"metadata": {
"collapsed": false
},
" 'achy']"
]
},
- "execution_count": 3,
+ "execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 4,
+ "execution_count": 7,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 5,
+ "execution_count": 8,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 6,
+ "execution_count": 9,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 7,
+ "execution_count": 10,
"metadata": {
"collapsed": false
},
"['able']"
]
},
- "execution_count": 7,
+ "execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 8,
+ "execution_count": 11,
"metadata": {
"collapsed": false
},
"['axle', 'abbe', 'ably']"
]
},
- "execution_count": 8,
+ "execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 9,
+ "execution_count": 12,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 10,
+ "execution_count": 13,
"metadata": {
"collapsed": false
},
"0"
]
},
- "execution_count": 10,
+ "execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 11,
+ "execution_count": 14,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 12,
+ "execution_count": 15,
"metadata": {
"collapsed": false
},
"[['abbe', 'able']]"
]
},
- "execution_count": 12,
+ "execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 13,
+ "execution_count": 16,
"metadata": {
"collapsed": false
},
"[['abbe', 'able', 'axle'], ['abbe', 'able', 'ably']]"
]
},
- "execution_count": 13,
+ "execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 14,
+ "execution_count": 17,
"metadata": {
"collapsed": false
},
"[['abbe', 'able', 'ably', 'ally']]"
]
},
- "execution_count": 14,
+ "execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 15,
+ "execution_count": 18,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 16,
+ "execution_count": 19,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 17,
+ "execution_count": 20,
"metadata": {
"collapsed": false
},
"['abbe', 'able', 'ably', 'ally']"
]
},
- "execution_count": 17,
+ "execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 18,
+ "execution_count": 21,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 19,
+ "execution_count": 22,
"metadata": {
"collapsed": false
},
"['abbe', 'able', 'ably', 'ally']"
]
},
- "execution_count": 19,
+ "execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 20,
+ "execution_count": 23,
"metadata": {
"collapsed": false
},
"['cart', 'cant', 'cans', 'vans']"
]
},
- "execution_count": 20,
+ "execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 21,
+ "execution_count": 24,
"metadata": {
"collapsed": false
},
"['cart', 'cant', 'cane', 'vane']"
]
},
- "execution_count": 21,
+ "execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 22,
+ "execution_count": 25,
"metadata": {
"collapsed": false
},
" 'vane']"
]
},
- "execution_count": 22,
+ "execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 23,
+ "execution_count": 26,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 24,
+ "execution_count": 27,
"metadata": {
"collapsed": false
},
"['cart', 'cant', 'cane', 'vane']"
]
},
- "execution_count": 24,
+ "execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 25,
+ "execution_count": 28,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 26,
+ "execution_count": 29,
"metadata": {
"collapsed": false
},
"['cart', 'cant', 'cane', 'vane']"
]
},
- "execution_count": 26,
+ "execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 77,
+ "execution_count": 30,
"metadata": {
"collapsed": false
},
"94"
]
},
- "execution_count": 77,
+ "execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 78,
+ "execution_count": 31,
"metadata": {
"collapsed": false
},
"2204"
]
},
- "execution_count": 78,
+ "execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 79,
+ "execution_count": 32,
"metadata": {
"collapsed": false
},
"1"
]
},
- "execution_count": 79,
+ "execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 80,
+ "execution_count": 33,
"metadata": {
"collapsed": false,
"scrolled": true
"Counter({1: 75, 2: 6, 3: 7, 4: 2, 5: 2, 6: 1, 2204: 1})"
]
},
- "execution_count": 80,
+ "execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 81,
+ "execution_count": 34,
"metadata": {
"collapsed": false
},
"[5]"
]
},
- "execution_count": 81,
+ "execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 82,
+ "execution_count": 35,
"metadata": {
"collapsed": false
},
"[{'abbe', 'able', 'ably', 'ally', 'axle'}]"
]
},
- "execution_count": 82,
+ "execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 83,
+ "execution_count": 36,
"metadata": {
"collapsed": false
},
"['buns', 'bunk', 'punk']"
]
},
- "execution_count": 83,
+ "execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 84,
+ "execution_count": 37,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 85,
+ "execution_count": 38,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 86,
+ "execution_count": 39,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 87,
+ "execution_count": 40,
"metadata": {
"collapsed": false
},
"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"
+ "['bops', 'bogs', 'begs', 'bees', 'byes', 'eyes', 'eyed']\n",
+ "['foal', 'foil', 'fail']\n",
+ "['bush', 'bash', 'base', 'bale', 'ball', 'boll']\n",
+ "['rift', 'lift', 'life', 'live', 'give', 'gave']\n",
+ "['club', 'clue', 'flue', 'flee', 'fled', 'pled', 'pied', 'lied', 'lien', 'mien']\n",
+ "['rung', 'dung', 'ding', 'dins', 'dies', 'lies', 'lien']\n",
+ "['baas', 'bags', 'bugs', 'bums', 'sums', 'sumo']\n",
+ "['fits', 'bits', 'bins', 'bind']\n",
+ "['lids', 'bids', 'bias', 'boas', 'boat', 'boot', 'soot', 'snot', 'snob']\n",
+ "['cake', 'came', 'cams', 'caws', 'cows', 'tows']\n",
+ "['tort', 'toot', 'trot', 'troy', 'tray', 'tram', 'cram']\n",
+ "['sews', 'pews', 'pees', 'peed', 'pied']\n",
+ "['lack', 'hack', 'hawk', 'haws', 'hows', 'tows']\n",
+ "['dots', 'dons', 'dens', 'dent', 'pent', 'pest', 'peso']\n",
+ "['ekes', 'eyes', 'byes', 'bees', 'beet', 'bent', 'lent', 'lept']\n",
+ "['ruin', 'rain', 'gain', 'grin', 'grid', 'arid', 'acid', 'aced', 'iced']\n",
+ "['sing', 'sins', 'bins', 'bias', 'bras', 'bray', 'tray', 'trap']\n",
+ "['lira', 'lire', 'wire', 'wise', 'wish']\n",
+ "['gash', 'cash', 'case', 'cape', 'rape']\n",
+ "['crop', 'coop', 'coot', 'loot', 'loft']\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 38,
+ "execution_count": 41,
"metadata": {
"collapsed": false
},
"['cops', 'coos', 'coon', 'coin', 'chin', 'thin', 'this', 'thus', 'thug']"
]
},
- "execution_count": 38,
+ "execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 39,
+ "execution_count": 42,
"metadata": {
"collapsed": false
},
"[2204]"
]
},
- "execution_count": 39,
+ "execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 40,
+ "execution_count": 73,
"metadata": {
"collapsed": false
},
{
"data": {
"text/plain": [
- "['hate', 'have', 'hove', 'love']"
+ "[2204]"
]
},
- "execution_count": 40,
+ "execution_count": 73,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
- "astar_search('hate', 'love')"
+ "[len(r) for r in reachables if 'stay' in r ]"
]
},
{
"cell_type": "code",
- "execution_count": 41,
+ "execution_count": 43,
"metadata": {
"collapsed": false
},
{
"data": {
"text/plain": [
- "['wars', 'ware', 'wave', 'wove', 'love']"
+ "['hate', 'have', 'hove', 'love']"
]
},
- "execution_count": 41,
+ "execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
- "astar_search('wars', 'love')"
+ "astar_search('hate', 'love')"
]
},
{
"cell_type": "code",
- "execution_count": 61,
+ "execution_count": 44,
"metadata": {
"collapsed": false
},
"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": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
- "%time len(astar_search('wars', 'love'))"
+ "astar_search('wars', 'love')"
]
},
{
"cell_type": "code",
- "execution_count": 62,
+ "execution_count": 45,
"metadata": {
"collapsed": false
},
"output_type": "stream",
"text": [
"CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
- "Wall time: 252 µs\n"
+ "Wall time: 850 µs\n"
]
},
{
"5"
]
},
- "execution_count": 62,
+ "execution_count": 45,
"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,
+ "execution_count": 46,
"metadata": {
"collapsed": false
},
"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: 353 µs\n"
]
},
{
"data": {
"text/plain": [
- "404"
+ "5"
]
},
- "execution_count": 63,
+ "execution_count": 46,
"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,
+ "execution_count": 47,
"metadata": {
"collapsed": false
},
"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 76 ms, sys: 0 ns, total: 76 ms\n",
+ "Wall time: 75.1 ms\n"
]
},
{
"data": {
"text/plain": [
- "5"
+ "404"
]
},
- "execution_count": 64,
+ "execution_count": 47,
"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": null,
"metadata": {
"collapsed": false
},
- "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"
- ]
- },
- {
- "data": {
- "text/plain": [
- "5"
- ]
- },
- "execution_count": 65,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
+ "outputs": [],
+ "source": [
+ "# %time len(bfs_search('wars', 'love'))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [],
"source": [
"%time len(bfs_search_closed('wars', 'love'))"
]
},
{
"cell_type": "code",
- "execution_count": 42,
+ "execution_count": 50,
"metadata": {
"collapsed": false
},
"['fear', 'feat', 'fest', 'lest', 'lost', 'lose', 'love']"
]
},
- "execution_count": 42,
+ "execution_count": 50,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 43,
+ "execution_count": 51,
"metadata": {
"collapsed": false
},
"['fail', 'fall', 'pall', 'pals', 'pass']"
]
},
- "execution_count": 43,
+ "execution_count": 51,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 44,
+ "execution_count": 52,
"metadata": {
"collapsed": false
},
"['star', 'soar', 'boar', 'boor', 'boon', 'born']"
]
},
- "execution_count": 44,
+ "execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 45,
+ "execution_count": 53,
"metadata": {
"collapsed": false
},
" 'pass']"
]
},
- "execution_count": 45,
+ "execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 46,
+ "execution_count": 54,
"metadata": {
"collapsed": false
},
" 'past']"
]
},
- "execution_count": 46,
+ "execution_count": 54,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 47,
+ "execution_count": 55,
"metadata": {
"collapsed": false
},
"[1]"
]
},
- "execution_count": 47,
+ "execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 48,
+ "execution_count": 56,
"metadata": {
"collapsed": false
},
"[2204]"
]
},
- "execution_count": 48,
+ "execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 49,
+ "execution_count": 57,
"metadata": {
"collapsed": false
},
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 7.9 s per loop\n"
+ "1 loop, best of 3: 12.3 s per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 50,
+ "execution_count": 58,
"metadata": {
"collapsed": false
},
"name": "stdout",
"output_type": "stream",
"text": [
- "10 loops, best of 3: 141 ms per loop\n"
+ "1 loop, best of 3: 200 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 51,
+ "execution_count": 59,
"metadata": {
"collapsed": false
},
" 'exit']"
]
},
- "execution_count": 51,
+ "execution_count": 59,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 88,
+ "execution_count": 60,
"metadata": {
"collapsed": false
},
{
"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']]}"
+ "{2: [['exes', 'exec'], ['rush', 'tush'], ['wile', 'wily'], ['shoo', 'shot']],\n",
+ " 3: [['bins', 'fink'], ['waft', 'wand'], ['heel', 'jell'], ['tent', 'west']],\n",
+ " 4: [['yore', 'polo'], ['hale', 'case'], ['horn', 'look'], ['tang', 'nuns']],\n",
+ " 5: [['crab', 'baas'], ['yens', 'dead'], ['work', 'paps'], ['tune', 'zaps']],\n",
+ " 6: [['mist', 'sold'], ['bats', 'sort'], ['leek', 'mads'], ['loop', 'dome']],\n",
+ " 7: [['rime', 'hoof'], ['grim', 'reed'], ['lies', 'eave'], ['ties', 'whiz']],\n",
+ " 8: [['drag', 'lied'], ['ages', 'yawl'], ['earl', 'deal'], ['gins', 'scab']],\n",
+ " 9: [['tyre', 'swum'], ['dike', 'flux'], ['hour', 'laze'], ['trek', 'bait']],\n",
+ " 10: [['ides', 'rasp'], ['egos', 'racy'], ['shim', 'ills'], ['bark', 'arty']],\n",
+ " 11: [['ergo', 'apex'], ['whey', 'owns'], ['anew', 'rapt'], ['thug', 'bate']],\n",
+ " 12: [['ream', 'imps'], ['meat', 'umps'], ['daze', 'knee'], ['clay', 'over']],\n",
+ " 13: [['oxen', 'blab'], ['blip', 'omen'], ['twig', 'ibis'], ['chew', 'umps']],\n",
+ " 14: [['amen', 'blip'], ['umps', 'futz'], ['amps', 'glib'], ['chum', 'whys']],\n",
+ " 15: [['thug', 'ibis']]}"
]
},
- "execution_count": 88,
+ "execution_count": 60,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 91,
+ "execution_count": 64,
"metadata": {
"collapsed": true
},
},
{
"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,
+ "execution_count": 66,
"metadata": {
"collapsed": false
},
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 360 ms per loop\n"
+ "1 loop, best of 3: 487 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 56,
+ "execution_count": 67,
"metadata": {
"collapsed": false
},
"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 768 ms, sys: 0 ns, total: 768 ms\n",
+ "Wall time: 768 ms\n"
]
},
{
"14"
]
},
- "execution_count": 56,
+ "execution_count": 67,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 57,
+ "execution_count": 68,
"metadata": {
"collapsed": false
},
"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 176 ms, sys: 0 ns, total: 176 ms\n",
+ "Wall time: 176 ms\n"
]
},
{
"15"
]
},
- "execution_count": 57,
+ "execution_count": 68,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 58,
+ "execution_count": 69,
"metadata": {
"collapsed": false
},
"name": "stdout",
"output_type": "stream",
"text": [
- "CPU times: user 32 ms, sys: 0 ns, total: 32 ms\n",
- "Wall time: 32.4 ms\n"
+ "CPU times: user 72 ms, sys: 0 ns, total: 72 ms\n",
+ "Wall time: 70.6 ms\n"
]
},
{
"14"
]
},
- "execution_count": 58,
+ "execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 59,
+ "execution_count": 70,
"metadata": {
"collapsed": false
},
"name": "stdout",
"output_type": "stream",
"text": [
- "CPU times: user 16 ms, sys: 0 ns, total: 16 ms\n",
- "Wall time: 17.1 ms\n"
+ "CPU times: user 32 ms, sys: 0 ns, total: 32 ms\n",
+ "Wall time: 35.7 ms\n"
]
},
{
"14"
]
},
- "execution_count": 59,
+ "execution_count": 70,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 73,
+ "execution_count": 71,
"metadata": {
"collapsed": false
},
"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 376 ms, sys: 4 ms, total: 380 ms\n",
+ "Wall time: 382 ms\n"
]
},
{
"14"
]
},
- "execution_count": 73,
+ "execution_count": 71,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 74,
+ "execution_count": 72,
"metadata": {
"collapsed": false
},
"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 72 ms, sys: 4 ms, total: 76 ms\n",
+ "Wall time: 76.9 ms\n"
]
},
{
"14"
]
},
- "execution_count": 74,
+ "execution_count": 72,
"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-offices.txt').readlines()]\n",
"len(words)"
]
},
{
"data": {
"text/plain": [
- "6"
+ "['boon', 'boot', 'bolt', 'belt', 'bell', 'sell']"
]
},
"execution_count": 17,
}
],
"source": [
- "len(astar_search('vice', 'wars'))"
+ "astar_search_raw('boon', 'sell')"
]
},
{
},
"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'))"
]
},
{
"metadata": {
"collapsed": false
},
+ "outputs": [],
+ "source": [
+ "# len(bfs_search('vice', 'wars'))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 20,
+ "metadata": {
+ "collapsed": false
+ },
"outputs": [
{
"data": {
"6"
]
},
- "execution_count": 19,
+ "execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 20,
+ "execution_count": 21,
"metadata": {
"collapsed": false
},
"793"
]
},
- "execution_count": 20,
+ "execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 21,
+ "execution_count": 22,
"metadata": {
"collapsed": false
},
"name": "stdout",
"output_type": "stream",
"text": [
- "1000 loops, best of 3: 225 µs per loop\n"
+ "1000 loops, best of 3: 273 µs per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 22,
+ "execution_count": 23,
"metadata": {
"collapsed": false
},
"name": "stdout",
"output_type": "stream",
"text": [
- "10 loops, best of 3: 22.1 ms per loop\n"
+ "10 loops, best of 3: 25.6 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 23,
+ "execution_count": 24,
"metadata": {
"collapsed": false
},
"name": "stdout",
"output_type": "stream",
"text": [
- "1000 loops, best of 3: 280 µs per loop\n"
+ "1000 loops, best of 3: 300 µs per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 24,
+ "execution_count": 25,
"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: "
- ]
- }
- ],
+ "outputs": [],
"source": [
- "%%timeit\n",
- "bfs_search('vice', 'wars')"
+ "# %%timeit\n",
+ "# bfs_search('vice', 'wars')"
]
},
{
"cell_type": "code",
- "execution_count": 25,
+ "execution_count": 26,
"metadata": {
"collapsed": false
},
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 1.12 s per loop\n"
+ "1 loop, best of 3: 664 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 26,
+ "execution_count": 27,
"metadata": {
"collapsed": false
},
"name": "stdout",
"output_type": "stream",
"text": [
- "10 loops, best of 3: 127 ms per loop\n"
+ "10 loops, best of 3: 147 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 27,
+ "execution_count": 28,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 28,
+ "execution_count": 52,
+ "metadata": {
+ "collapsed": false
+ },
+ "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": 52,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "neighbours['rash']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 29,
"metadata": {
"collapsed": false,
"scrolled": true
" '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
]
},
- "execution_count": 28,
+ "execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 29,
+ "execution_count": 47,
+ "metadata": {
+ "collapsed": false,
+ "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": 47,
+ "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": 30,
"metadata": {
"collapsed": false,
"scrolled": true
" '`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": 30,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 30,
+ "execution_count": 51,
+ "metadata": {
+ "collapsed": false,
+ "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": 51,
+ "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": 31,
"metadata": {
"collapsed": false,
"scrolled": true
"180"
]
},
- "execution_count": 30,
+ "execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 31,
+ "execution_count": 32,
"metadata": {
"collapsed": false,
"scrolled": true
"2195"
]
},
- "execution_count": 31,
+ "execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 32,
+ "execution_count": 33,
"metadata": {
"collapsed": false,
"scrolled": true
"2192"
]
},
- "execution_count": 32,
+ "execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 33,
+ "execution_count": 34,
"metadata": {
"collapsed": false,
"scrolled": true
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 9.26 ms per loop\n"
+ "100 loops, best of 3: 8.95 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 34,
+ "execution_count": 35,
"metadata": {
"collapsed": false,
"scrolled": true
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 3.64 ms per loop\n"
+ "100 loops, best of 3: 4.14 ms per loop\n"
]
}
],
"len(reachable_in('rash', 10, trim_extras=True))"
]
},
+ {
+ "cell_type": "code",
+ "execution_count": 36,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2188"
+ ]
+ },
+ "execution_count": 36,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('stay', 10))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 37,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2193"
+ ]
+ },
+ "execution_count": 37,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('coax', 10))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 38,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "280"
+ ]
+ },
+ "execution_count": 38,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "stay5 = reachable_in('stay', 4)\n",
+ "len(stay5)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 39,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "296"
+ ]
+ },
+ "execution_count": 39,
+ "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": 40,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'leak drab twin glib yell jets heed prep dram step grey keep sacs hock bloc bees hews bend chit sots rent knit brat bobs news gram boot baas grad beet door keen toot mewl plus dial bows jeep boom aloe fret need foul beep brew peek veep poop blue weep akin coop lead foot deed hoot teem quit chop teed bias moor sack atop went bier vets teen pout eery leaf drag belt crag peed czar gees veil whip bout jock wees twit beck boos tell vial pees brag tout sped weed geed load book crop text deem shes mead mock very sewn feet sows cell leis dell hemp week yens than mean send chin sill reek wiry knot reed crew peps pest stem melt room coup yews dock less suck boon clef emit bras loot boob pegs pews bran thin well geek boss term pled whir feed whom rock foam dent glue mews rood goat next sort tens goop stay soft perk troy held meet fees best lees reel gent nest brow spec fest coat leek sues pier moot knob test bogs boys said heft hell flee thaw clue prom self felt hair shoe airs cent whet pock gets pent sics pelt bent club berm saws pets blur prod bops whim sick bell trap lets herd help chip loan sued pens dyer peep peel dual sits suet flue goad toad brad peck moan fell cock been whit lens leap omit wets char crow gout frog shoo nets fist root prim lean jell trig coot flea prop meek beef loam bolt chow skid chew crab floe yeps moat tram vent bets jeez soil soon yous unit newt lock bled deep fled tent tees poor heel grab skis rend lent draw know grow doer yock pert legs'"
+ ]
+ },
+ "execution_count": 40,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "' '.join(extras)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 41,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
+ ]
+ },
+ "execution_count": 41,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "astar_search('coax', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 42,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "CPU times: user 2.35 s, sys: 0 ns, total: 2.35 s\n",
+ "Wall time: 2.35 s\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "['coax', 'coat', 'chat', 'shat', 'slat', 'slay', 'stay']"
+ ]
+ },
+ "execution_count": 42,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "%time bfs_search_closed('coax', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 48,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [],
+ "source": [
+ "# %time bfs_search('coax', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 44,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
+ ]
+ },
+ "execution_count": 44,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "astar_search('czar', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 49,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [],
+ "source": [
+ "# %time bfs_search('czar', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 50,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [],
+ "source": [
+ "# %time bfs_search('coax', 'stay')"
+ ]
+ },
{
"cell_type": "code",
"execution_count": null,
projects / ou-summer-of-code-2017.git / commitdiff