" 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": 19,
- "metadata": {},
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# len(bfs_search('vice', 'wars'))"
"name": "stdout",
"output_type": "stream",
"text": [
- "10000 loops, best of 3: 153 µs per loop\n"
+ "10000 loops, best of 3: 154 µs per loop\n"
]
}
],
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 15.7 ms per loop\n"
+ "100 loops, best of 3: 16.3 ms per loop\n"
]
}
],
"name": "stdout",
"output_type": "stream",
"text": [
- "10000 loops, best of 3: 165 µs per loop\n"
+ "10000 loops, best of 3: 169 µs per loop\n"
]
}
],
{
"cell_type": "code",
"execution_count": 25,
- "metadata": {},
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# %%timeit\n",
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 446 ms per loop\n"
+ "1 loop, best of 3: 1.09 s per loop\n"
]
}
],
"name": "stdout",
"output_type": "stream",
"text": [
- "10 loops, best of 3: 91.4 ms per loop\n"
+ "10 loops, best of 3: 93.1 ms per loop\n"
]
}
],
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 5.84 ms per loop\n"
+ "100 loops, best of 3: 6 ms per loop\n"
]
}
],
"name": "stdout",
"output_type": "stream",
"text": [
- "100 loops, best of 3: 2.79 ms per loop\n"
+ "100 loops, best of 3: 2.8 ms per loop\n"
]
}
],
{
"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'"
+ "'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": 43,
"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 2.28 s, sys: 4 ms, total: 2.29 s\n",
+ "Wall time: 2.29 s\n"
]
},
{
"data": {
"text/plain": [
- "['coax', 'coat', 'chat', 'shat', 'spat', 'spay', 'stay']"
+ "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
]
},
"execution_count": 45,
{
"cell_type": "code",
"execution_count": 46,
- "metadata": {},
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# %time bfs_search('coax', 'stay')"
{
"cell_type": "code",
"execution_count": 48,
- "metadata": {},
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# %time bfs_search('czar', 'stay')"
{
"cell_type": "code",
"execution_count": 49,
- "metadata": {},
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# %time bfs_search('coax', 'stay')"
projects / ou-summer-of-code-2017.git / blobdiff