},
{
"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
},
},
{
"cell_type": "code",
- "execution_count": 10,
+ "execution_count": 11,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 11,
+ "execution_count": 12,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 12,
+ "execution_count": 13,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 13,
+ "execution_count": 14,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 14,
+ "execution_count": 15,
"metadata": {
"collapsed": true
},
},
{
"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,
+ "execution_count": 20,
"metadata": {
"collapsed": true
},
},
{
"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: 154 µ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: 16.3 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: 169 µs per loop\n"
+ "10000 loops, best of 3: 166 µs per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 25,
+ "execution_count": 26,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 26,
+ "execution_count": 27,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 1.09 s 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: 93.1 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: 6 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.8 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": [
- "'troy peck thaw bobs fist whim deed foam herd skid cell meet lens cock lean been tees cent veil glue hell hoot jeep atop whet chew crow dual keen test reed bolt coop weep went dell lent pens prop leek chop pock knob bend dent gent bloc pets whom brew gout brat clue sacs nets gram wiry blur gees crop glib bets thin knit dram hair jeez soon sort leaf prim hemp deep yews loan bows wees rock newt mock baas leak twin sots bogs sick geed yock peel airs crew know beet pier foot melt less prep toad prom pews brow grad pees suet sued prod lees dock frog term tent sack root stay chin feet twit tram pert coat reel floe deem teem need boss moat book bias lock said best loam goop spec boon bras boys grey pelt nest jets well perk mead heel tens fled czar trap mewl brad teen very belt boom chit pent shes soil next toot crab jock foul held heft help coot berm moan char boot omit hock unit akin load boob lead beep plus sewn bees chow knot vial bled drag bell doer pest saws peed news aloe goad moot tout text tell fret gets chip rent whir bout coup pegs flea poop room peek wets hews grow dyer whit sics self than club week peep clef beef poor step brag rood vent sill legs send shoo bops sits flue emit stem grab shoe eery leap whip door yens heed felt yous quit meek bran teed moor veep loot geek bier goat weed flee pout skis blue yell yeps reek trig feed draw rend soft bent crag mews sues leis fees drab mean peps suck dial fest vets lets sped keep jell beck boos fell pled sows'"
+ "'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 2.28 s, sys: 4 ms, total: 2.29 s\n",
- "Wall time: 2.29 s\n"
+ "CPU times: user 620 ms, sys: 4 ms, total: 624 ms\n",
+ "Wall time: 624 ms\n"
]
},
{
"data": {
"text/plain": [
- "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
+ "['coax', 'coat', 'chat', 'shat', 'spat', 'spay', 'stay']"
]
},
- "execution_count": 45,
+ "execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 46,
+ "execution_count": 47,
"metadata": {
"collapsed": true
},
},
{
"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,
+ "execution_count": 49,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 49,
+ "execution_count": 50,
"metadata": {
"collapsed": true
},
"# %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