},
{
"cell_type": "code",
- "execution_count": 1,
+ "execution_count": 2,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 2,
+ "execution_count": 3,
"metadata": {},
"outputs": [
{
"2336"
]
},
- "execution_count": 2,
+ "execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 3,
+ "execution_count": 4,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 4,
+ "execution_count": 5,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 5,
+ "execution_count": 6,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 6,
+ "execution_count": 7,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 7,
+ "execution_count": 8,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 8,
+ "execution_count": 9,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 9,
+ "execution_count": 10,
"metadata": {
"collapsed": true
},
" else:\n",
" successors = extend(current)\n",
" agenda = agenda[1:] + successors\n",
- " if agenda:\n",
+ " if finished:\n",
" return current\n",
" else:\n",
" return None "
},
{
"cell_type": "code",
- "execution_count": 10,
+ "execution_count": 11,
"metadata": {
"collapsed": true
},
" 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 "
},
{
"cell_type": "code",
- "execution_count": 11,
+ "execution_count": 12,
"metadata": {
"collapsed": true
},
" else:\n",
" successors = extend(current)\n",
" agenda = successors + agenda[1:]\n",
- " if agenda:\n",
+ " if finished:\n",
" return current\n",
" else:\n",
" return None "
},
{
"cell_type": "code",
- "execution_count": 12,
+ "execution_count": 13,
"metadata": {
"collapsed": true
},
" 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 "
},
{
"cell_type": "code",
- "execution_count": 13,
+ "execution_count": 14,
"metadata": {
"collapsed": true
},
" successors = extend_raw(current) # Difference here\n",
" for s in successors:\n",
" heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
- " if agenda:\n",
+ " if finished:\n",
" return current\n",
" else:\n",
" return None "
},
{
"cell_type": "code",
- "execution_count": 14,
+ "execution_count": 15,
"metadata": {
"collapsed": true
},
" 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 "
},
{
"cell_type": "code",
- "execution_count": 15,
+ "execution_count": 16,
"metadata": {},
"outputs": [
{
"['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
]
},
- "execution_count": 15,
+ "execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 16,
+ "execution_count": 17,
"metadata": {},
"outputs": [
{
"['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
]
},
- "execution_count": 16,
+ "execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 17,
+ "execution_count": 18,
"metadata": {},
"outputs": [
{
"['boon', 'boot', 'bolt', 'belt', 'bell', 'sell']"
]
},
- "execution_count": 17,
+ "execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 18,
+ "execution_count": 19,
"metadata": {},
"outputs": [
{
"6"
]
},
- "execution_count": 18,
+ "execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 19,
- "metadata": {},
+ "execution_count": 20,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# len(bfs_search('vice', 'wars'))"
},
{
"cell_type": "code",
- "execution_count": 20,
+ "execution_count": 21,
"metadata": {},
"outputs": [
{
"6"
]
},
- "execution_count": 20,
+ "execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 21,
+ "execution_count": 22,
"metadata": {},
"outputs": [
{
"793"
]
},
- "execution_count": 21,
+ "execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 22,
+ "execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "10000 loops, best of 3: 153 µs per loop\n"
+ "10000 loops, best of 3: 157 µs per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 23,
+ "execution_count": 24,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 15.7 ms per loop\n"
+ "100 loops, best of 3: 15.5 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 24,
+ "execution_count": 25,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "10000 loops, best of 3: 165 µs per loop\n"
+ "10000 loops, best of 3: 166 µs per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 25,
- "metadata": {},
+ "execution_count": 26,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# %%timeit\n",
},
{
"cell_type": "code",
- "execution_count": 26,
+ "execution_count": 27,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 446 ms per loop\n"
+ "1 loop, best of 3: 554 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 27,
+ "execution_count": 28,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "10 loops, best of 3: 91.4 ms per loop\n"
+ "10 loops, best of 3: 90.6 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 28,
+ "execution_count": 29,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 29,
+ "execution_count": 30,
"metadata": {},
"outputs": [
{
" 'rasp']"
]
},
- "execution_count": 29,
+ "execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 30,
+ "execution_count": 31,
"metadata": {
"scrolled": true
},
" '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
]
},
- "execution_count": 30,
+ "execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 31,
+ "execution_count": 32,
"metadata": {
"scrolled": true
},
" '<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,
+ "execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 32,
+ "execution_count": 33,
"metadata": {
"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": 32,
+ "execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 33,
+ "execution_count": 34,
"metadata": {
"scrolled": true
},
" '<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,
+ "execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 34,
+ "execution_count": 35,
"metadata": {
"scrolled": true
},
"180"
]
},
- "execution_count": 34,
+ "execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 35,
+ "execution_count": 36,
"metadata": {
"scrolled": true
},
"2195"
]
},
- "execution_count": 35,
+ "execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 36,
+ "execution_count": 37,
"metadata": {
"scrolled": true
},
"2192"
]
},
- "execution_count": 36,
+ "execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 37,
+ "execution_count": 38,
"metadata": {
"scrolled": true
},
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 5.84 ms per loop\n"
+ "100 loops, best of 3: 5.81 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 38,
+ "execution_count": 39,
"metadata": {
"scrolled": true
},
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 2.79 ms per loop\n"
+ "100 loops, best of 3: 2.71 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 39,
+ "execution_count": 40,
"metadata": {},
"outputs": [
{
"2188"
]
},
- "execution_count": 39,
+ "execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 40,
+ "execution_count": 41,
"metadata": {},
"outputs": [
{
"2193"
]
},
- "execution_count": 40,
+ "execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 41,
+ "execution_count": 42,
"metadata": {},
"outputs": [
{
"280"
]
},
- "execution_count": 41,
+ "execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 42,
+ "execution_count": 43,
"metadata": {},
"outputs": [
{
"296"
]
},
- "execution_count": 42,
+ "execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 43,
+ "execution_count": 44,
"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'"
+ "'know step yeps test pout book beck poor boos veep teed gent saws dyer hemp soon deem legs bets twit whim belt rock well bled whet prop spec weep peed loan week clef feed lock yens vent doer less teem toot yews blur clue pert pegs brew flea trig vets sued felt perk bobs brat tens beef leap bloc shoo moan boob jeez suet sits rood drag goat stay chip fled fist than loot pets suck peek pled heel hair sill prep char knot lens meek trap jeep beet crew draw tell nets peep meet sows glue bees bent pelt whit need foot bran chop gram chew teen veil lent gees fret soft leis pent gets weed keen reek news prim drab wets sics deed bows pier akin pock geed grey bogs goad skis peck prod loam keep pens hoot best reed yous sewn been tram pest whom bout unit deep boot dual lees omit peel sues berm dock yock shes lets mock grow jell whip lean thin sots geek stem floe tees sort fees gout mead dram said twin prom bras bier heft foul root fell melt bops coup coot atop brad chin moot shoe sacs chit hell door lead feet boon bolt leaf bell bias eery goop reel text boom herd rent leek rend club self send sick term airs frog yell next czar plus mean brow foam crow troy nest heed dell load glib peps cent chow pees bend jock held tent soil poop moor sped emit boss fest crop mews knit tout crag knob grab thaw vial sack help jets very boys flue whir newt wiry beep room pews crab baas cock coop hock blue flee moat skid quit dial brag cell aloe grad hews went leak toad wees mewl coat dent'"
]
},
- "execution_count": 43,
+ "execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 44,
+ "execution_count": 45,
"metadata": {},
"outputs": [
{
"['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
]
},
- "execution_count": 44,
+ "execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 45,
+ "execution_count": 46,
"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"
+ "CPU times: user 620 ms, sys: 4 ms, total: 624 ms\n",
+ "Wall time: 624 ms\n"
]
},
{
"['coax', 'coat', 'chat', 'shat', 'spat', 'spay', 'stay']"
]
},
- "execution_count": 45,
+ "execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 46,
- "metadata": {},
+ "execution_count": 47,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# %time bfs_search('coax', 'stay')"
},
{
"cell_type": "code",
- "execution_count": 47,
+ "execution_count": 48,
"metadata": {},
"outputs": [
{
"['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
]
},
- "execution_count": 47,
+ "execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 48,
- "metadata": {},
+ "execution_count": 49,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# %time bfs_search('czar', 'stay')"
},
{
"cell_type": "code",
- "execution_count": 49,
- "metadata": {},
+ "execution_count": 50,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# %time bfs_search('coax', 'stay')"
]
},
+ {
+ "cell_type": "code",
+ "execution_count": 79,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "185"
+ ]
+ },
+ "execution_count": 79,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "rushn = reachable_in('rush', 3)\n",
+ "rushn.add('rush')\n",
+ "len(rushn)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 80,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [],
+ "source": [
+ "links = set()\n",
+ "for w in rushn:\n",
+ " for n in neighbours[w]:\n",
+ " if n in rushn:\n",
+ " links.add(frozenset((n, w)))\n",
+ "\n",
+ "with open('rush3.dot', 'w') as f:\n",
+ " f.write('graph g {\\n')\n",
+ " for l in links:\n",
+ " lt = tuple(l)\n",
+ " f.write('\"{}\" -- \"{}\";\\n'.format(lt[0], lt[1]))\n",
+ " f.write('}\\n')"
+ ]
+ },
{
"cell_type": "code",
"execution_count": null,
projects / ou-summer-of-code-2017.git / blobdiff