{
"cell_type": "code",
"execution_count": 2,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
}
],
"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)"
]
},
" else:\n",
" successors = extend(current)\n",
" agenda = agenda[1:] + successors\n",
- " if agenda:\n",
+ " if finished:\n",
" return current\n",
" else:\n",
" return None "
" 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 "
" else:\n",
" successors = extend(current)\n",
" agenda = successors + agenda[1:]\n",
- " if agenda:\n",
+ " if finished:\n",
" return current\n",
" else:\n",
" return None "
" 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 "
" 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 "
" 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
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 16,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 17,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 18,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
"cell_type": "code",
"execution_count": 19,
"metadata": {
- "collapsed": false
+ "collapsed": true
},
"outputs": [],
"source": [
{
"cell_type": "code",
"execution_count": 20,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 21,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"data": {
{
"cell_type": "code",
"execution_count": 22,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1000 loops, best of 3: 273 µs per loop\n"
+ "10000 loops, best of 3: 154 µs per loop\n"
]
}
],
{
"cell_type": "code",
"execution_count": 23,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "10 loops, best of 3: 25.6 ms per loop\n"
+ "100 loops, best of 3: 16.3 ms per loop\n"
]
}
],
{
"cell_type": "code",
"execution_count": 24,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1000 loops, best of 3: 300 µs per loop\n"
+ "10000 loops, best of 3: 169 µs per loop\n"
]
}
],
"cell_type": "code",
"execution_count": 25,
"metadata": {
- "collapsed": false
+ "collapsed": true
},
"outputs": [],
"source": [
{
"cell_type": "code",
"execution_count": 26,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 664 ms per loop\n"
+ "1 loop, best of 3: 1.09 s per loop\n"
]
}
],
{
"cell_type": "code",
"execution_count": 27,
- "metadata": {
- "collapsed": false
- },
+ "metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "10 loops, best of 3: 147 ms per loop\n"
+ "10 loops, best of 3: 93.1 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 52,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 29,
+ "metadata": {},
"outputs": [
{
"data": {
" 'rasp']"
]
},
- "execution_count": 52,
+ "execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 29,
+ "execution_count": 30,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
" '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
]
},
- "execution_count": 29,
+ "execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 47,
+ "execution_count": 31,
"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": 31,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 30,
+ "execution_count": 32,
"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": 32,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 51,
+ "execution_count": 33,
"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": 33,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 31,
+ "execution_count": 34,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"180"
]
},
- "execution_count": 31,
+ "execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 32,
+ "execution_count": 35,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"2195"
]
},
- "execution_count": 32,
+ "execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 33,
+ "execution_count": 36,
"metadata": {
- "collapsed": false,
"scrolled": true
},
"outputs": [
"2192"
]
},
- "execution_count": 33,
+ "execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 34,
+ "execution_count": 37,
"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: 6 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 35,
+ "execution_count": 38,
"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.8 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 36,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 39,
+ "metadata": {},
"outputs": [
{
"data": {
"2188"
]
},
- "execution_count": 36,
+ "execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 37,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 40,
+ "metadata": {},
"outputs": [
{
"data": {
"2193"
]
},
- "execution_count": 37,
+ "execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 38,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 41,
+ "metadata": {},
"outputs": [
{
"data": {
"280"
]
},
- "execution_count": 38,
+ "execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 39,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 42,
+ "metadata": {},
"outputs": [
{
"data": {
"296"
]
},
- "execution_count": 39,
+ "execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 40,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 43,
+ "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'"
+ "'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'"
]
},
- "execution_count": 40,
+ "execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 41,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 44,
+ "metadata": {},
"outputs": [
{
"data": {
"['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
]
},
- "execution_count": 41,
+ "execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 42,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 45,
+ "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 2.28 s, sys: 4 ms, total: 2.29 s\n",
+ "Wall time: 2.29 s\n"
]
},
{
"data": {
"text/plain": [
- "['coax', 'coat', 'chat', 'shat', 'slat', 'slay', 'stay']"
+ "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
]
},
- "execution_count": 42,
+ "execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 48,
+ "execution_count": 46,
"metadata": {
- "collapsed": false
+ "collapsed": true
},
"outputs": [],
"source": [
},
{
"cell_type": "code",
- "execution_count": 44,
- "metadata": {
- "collapsed": false
- },
+ "execution_count": 47,
+ "metadata": {},
"outputs": [
{
"data": {
"['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
]
},
- "execution_count": 44,
+ "execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 49,
+ "execution_count": 48,
"metadata": {
- "collapsed": false
+ "collapsed": true
},
"outputs": [],
"source": [
},
{
"cell_type": "code",
- "execution_count": 50,
+ "execution_count": 49,
"metadata": {
- "collapsed": false
+ "collapsed": true
},
"outputs": [],
"source": [
"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