},
{
"cell_type": "code",
- "execution_count": 1,
+ "execution_count": 2,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 2,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 3,
+ "metadata": {},
"outputs": [
{
"data": {
"2336"
]
},
- "execution_count": 2,
+ "execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
- "words = [w.strip() for w in open('08-offices.txt').readlines()]\n",
+ "words = [w.strip() for w in open('08-rooms.txt').readlines()]\n",
"len(words)"
]
},
{
"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,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 16,
+ "metadata": {},
"outputs": [
{
"data": {
"['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
]
},
- "execution_count": 15,
+ "execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 16,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 17,
+ "metadata": {},
"outputs": [
{
"data": {
"['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
]
},
- "execution_count": 16,
+ "execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 17,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 18,
+ "metadata": {},
"outputs": [
{
"data": {
"['boon', 'boot', 'bolt', 'belt', 'bell', 'sell']"
]
},
- "execution_count": 17,
+ "execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 18,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 19,
+ "metadata": {},
"outputs": [
{
"data": {
"6"
]
},
- "execution_count": 18,
+ "execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 19,
+ "execution_count": 20,
"metadata": {
- "collapsed": false
+ "collapsed": true
},
"outputs": [],
"source": [
},
{
"cell_type": "code",
- "execution_count": 20,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 21,
+ "metadata": {},
"outputs": [
{
"data": {
"6"
]
},
- "execution_count": 20,
+ "execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 21,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 22,
+ "metadata": {},
"outputs": [
{
"data": {
"793"
]
},
- "execution_count": 21,
+ "execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 22,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 23,
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1000 loops, best of 3: 273 µs per loop\n"
+ "10000 loops, best of 3: 157 µs per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 23,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 24,
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "10 loops, best of 3: 25.6 ms per loop\n"
+ "100 loops, best of 3: 15.5 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 24,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 25,
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1000 loops, best of 3: 300 µ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": false
+ "collapsed": true
},
"outputs": [],
"source": [
},
{
"cell_type": "code",
- "execution_count": 26,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 27,
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 664 ms per loop\n"
+ "1 loop, best of 3: 554 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 27,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 28,
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "10 loops, best of 3: 147 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": 52,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 30,
+ "metadata": {},
"outputs": [
{
"data": {
" 'rasp']"
]
},
- "execution_count": 52,
+ "execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 29,
+ "execution_count": 31,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
" '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
]
},
- "execution_count": 29,
+ "execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 47,
+ "execution_count": 32,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
" '<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,
+ "execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 30,
+ "execution_count": 33,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
" '`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": 30,
+ "execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 51,
+ "execution_count": 34,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
" '<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,
+ "execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 31,
+ "execution_count": 35,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"180"
]
},
- "execution_count": 31,
+ "execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 32,
+ "execution_count": 36,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"2195"
]
},
- "execution_count": 32,
+ "execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 33,
+ "execution_count": 37,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"2192"
]
},
- "execution_count": 33,
+ "execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 34,
+ "execution_count": 38,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 8.95 ms per loop\n"
+ "100 loops, best of 3: 5.81 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 35,
+ "execution_count": 39,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 4.14 ms per loop\n"
+ "100 loops, best of 3: 2.71 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 36,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 40,
+ "metadata": {},
"outputs": [
{
"data": {
"2188"
]
},
- "execution_count": 36,
+ "execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 37,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 41,
+ "metadata": {},
"outputs": [
{
"data": {
"2193"
]
},
- "execution_count": 37,
+ "execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 38,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 42,
+ "metadata": {},
"outputs": [
{
"data": {
"280"
]
},
- "execution_count": 38,
+ "execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 39,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 43,
+ "metadata": {},
"outputs": [
{
"data": {
"296"
]
},
- "execution_count": 39,
+ "execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 40,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 44,
+ "metadata": {},
"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'"
+ "'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": 40,
+ "execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 41,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 45,
+ "metadata": {},
"outputs": [
{
"data": {
"['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
]
},
- "execution_count": 41,
+ "execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 42,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 46,
+ "metadata": {},
"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"
+ "CPU times: user 620 ms, sys: 4 ms, total: 624 ms\n",
+ "Wall time: 624 ms\n"
]
},
{
"data": {
"text/plain": [
- "['coax', 'coat', 'chat', 'shat', 'slat', 'slay', 'stay']"
+ "['coax', 'coat', 'chat', 'shat', 'spat', 'spay', 'stay']"
]
},
- "execution_count": 42,
+ "execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 48,
+ "execution_count": 47,
"metadata": {
- "collapsed": false
+ "collapsed": true
},
"outputs": [],
"source": [
},
{
"cell_type": "code",
- "execution_count": 44,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 48,
+ "metadata": {},
"outputs": [
{
"data": {
"['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
]
},
- "execution_count": 44,
+ "execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
"cell_type": "code",
"execution_count": 49,
"metadata": {
- "collapsed": false
+ "collapsed": true
},
"outputs": [],
"source": [
"cell_type": "code",
"execution_count": 50,
"metadata": {
- "collapsed": false
+ "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,
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
- "version": "3.5.2"
+ "version": "3.5.2+"
}
},
"nbformat": 4,
projects / ou-summer-of-code-2017.git / blobdiff