+++ /dev/null
-{
- "cells": [
- {
- "cell_type": "markdown",
- "metadata": {},
- "source": [
- "# Word chains\n",
- "\n",
- "\"Word chain\" puzzles are where you transform one word into another, by changing one letter at a time, with all the intermediate steps being valid words. \n",
- "\n",
- "For instance, you can transform 'rash' to 'jags' like this:\n",
- "\n",
- "```\n",
- "rash\n",
- "Bash\n",
- "basS\n",
- "baGs\n",
- "Jags\n",
- "```\n",
- "\n",
- "(the capital letter is the one changed in each step).\n",
- "\n",
- "## Part 1\n",
- "\n",
- "Given this [list of words](words4.txt), what is the minimum number of steps to go from `vice` to `wars`?"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 2,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "import string\n",
- "import heapq"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 3,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "2336"
- ]
- },
- "execution_count": 3,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "words = [w.strip() for w in open('08-rooms.txt').readlines()]\n",
- "len(words)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 4,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "def adjacents(word):\n",
- " return [word[0:i] + l + word[i+1:]\n",
- " for i in range(len(word))\n",
- " for l in string.ascii_lowercase\n",
- " if l != word[i]]"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 5,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "neighbours = {w: [n for n in adjacents(w) if n in words]\n",
- " for w in words}"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 6,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "def distance(w1, w2):\n",
- " return sum(1 for i in range(len(w1))\n",
- " if w1[i] != w2[i])"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 7,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "# def extend(chain):\n",
- "# return [chain + [s] for s in neighbours[chain[-1]]\n",
- "# if s not in chain]"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 8,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "def extend(chain, closed=None):\n",
- " if closed:\n",
- " nbrs = set(neighbours[chain[-1]]) - closed\n",
- " else:\n",
- " nbrs = neighbours[chain[-1]]\n",
- " return [chain + [s] for s in nbrs\n",
- " if s not in chain]"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 9,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "def extend_raw(chain):\n",
- " nbrs = [w for w in adjacents(chain[-1]) if w in words]\n",
- " return [chain + [s] for s in nbrs\n",
- " if s not in chain]"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 10,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "def bfs_search(start, goal, debug=False):\n",
- " agenda = [[start]]\n",
- " finished = False\n",
- " while not finished and agenda:\n",
- " current = agenda[0]\n",
- " if debug:\n",
- " print(current)\n",
- " if current[-1] == goal:\n",
- " finished = True\n",
- " else:\n",
- " successors = extend(current)\n",
- " agenda = agenda[1:] + successors\n",
- " if finished:\n",
- " return current\n",
- " else:\n",
- " return None "
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 11,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "def bfs_search_closed(start, goal, debug=False):\n",
- " agenda = [[start]]\n",
- " closed = set()\n",
- " finished = False\n",
- " while not finished and agenda:\n",
- " current = agenda[0]\n",
- " if debug:\n",
- " print(current)\n",
- " if current[-1] == goal:\n",
- " finished = True\n",
- " else:\n",
- " closed.add(current[-1])\n",
- " successors = extend(current, closed)\n",
- " agenda = agenda[1:] + successors\n",
- " if finished:\n",
- " return current\n",
- " else:\n",
- " return None "
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 12,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "def dfs_search(start, goal, debug=False):\n",
- " agenda = [[start]]\n",
- " finished = False\n",
- " while not finished and agenda:\n",
- " current = agenda[0]\n",
- " if debug:\n",
- " print(current)\n",
- " if current[-1] == goal:\n",
- " finished = True\n",
- " else:\n",
- " successors = extend(current)\n",
- " agenda = successors + agenda[1:]\n",
- " if finished:\n",
- " return current\n",
- " else:\n",
- " return None "
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 13,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "def astar_search(start, goal, debug=False):\n",
- " agenda = [(distance(start, goal), [start])]\n",
- " heapq.heapify(agenda)\n",
- " finished = False\n",
- " while not finished and agenda:\n",
- " _, current = heapq.heappop(agenda)\n",
- " if debug:\n",
- " print(current)\n",
- " if current[-1] == goal:\n",
- " finished = True\n",
- " else:\n",
- " successors = extend(current)\n",
- " for s in successors:\n",
- " heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
- " if finished:\n",
- " return current\n",
- " else:\n",
- " return None "
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 14,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "# Uses direct lookup of successors, rather than using cached neighbours in the dict\n",
- "def astar_search_raw(start, goal, debug=False):\n",
- " agenda = [(distance(start, goal), [start])]\n",
- " heapq.heapify(agenda)\n",
- " finished = False\n",
- " while not finished and agenda:\n",
- " _, current = heapq.heappop(agenda)\n",
- " if debug:\n",
- " print(current)\n",
- " if current[-1] == goal:\n",
- " finished = True\n",
- " else:\n",
- " 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 finished:\n",
- " return current\n",
- " else:\n",
- " return None "
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 15,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "def astar_search_closed(start, goal, debug=False):\n",
- " agenda = [(distance(start, goal), [start])]\n",
- " heapq.heapify(agenda)\n",
- " closed = set()\n",
- " finished = False\n",
- " while not finished and agenda:\n",
- " _, current = heapq.heappop(agenda)\n",
- " if debug:\n",
- " print(current)\n",
- " if current[-1] == goal:\n",
- " finished = True\n",
- " else:\n",
- " closed.add(current[-1])\n",
- " successors = extend(current, closed)\n",
- " for s in successors:\n",
- " heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
- " if finished:\n",
- " return current\n",
- " else:\n",
- " return None "
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 16,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
- ]
- },
- "execution_count": 16,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "astar_search('vice', 'wars')"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 17,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
- ]
- },
- "execution_count": 17,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "astar_search_raw('vice', 'wars')"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 18,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "['boon', 'boot', 'bolt', 'belt', 'bell', 'sell']"
- ]
- },
- "execution_count": 18,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "astar_search_raw('boon', 'sell')"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 19,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "6"
- ]
- },
- "execution_count": 19,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "len(astar_search('vice', 'wars'))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 20,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "# len(bfs_search('vice', 'wars'))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 21,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "6"
- ]
- },
- "execution_count": 21,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "len(bfs_search_closed('vice', 'wars'))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 22,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "793"
- ]
- },
- "execution_count": 22,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "len(dfs_search('vice', 'wars'))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 23,
- "metadata": {},
- "outputs": [
- {
- "name": "stdout",
- "output_type": "stream",
- "text": [
- "10000 loops, best of 3: 157 µs per loop\n"
- ]
- }
- ],
- "source": [
- "%%timeit\n",
- "astar_search('vice', 'wars')"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 24,
- "metadata": {},
- "outputs": [
- {
- "name": "stdout",
- "output_type": "stream",
- "text": [
- "100 loops, best of 3: 15.5 ms per loop\n"
- ]
- }
- ],
- "source": [
- "%%timeit\n",
- "astar_search_raw('vice', 'wars')"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 25,
- "metadata": {},
- "outputs": [
- {
- "name": "stdout",
- "output_type": "stream",
- "text": [
- "10000 loops, best of 3: 166 µs per loop\n"
- ]
- }
- ],
- "source": [
- "%%timeit\n",
- "astar_search_closed('vice', 'wars')"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 26,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "# %%timeit\n",
- "# bfs_search('vice', 'wars')"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 27,
- "metadata": {},
- "outputs": [
- {
- "name": "stdout",
- "output_type": "stream",
- "text": [
- "1 loop, best of 3: 554 ms per loop\n"
- ]
- }
- ],
- "source": [
- "%%timeit\n",
- "bfs_search_closed('vice', 'wars')"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 28,
- "metadata": {},
- "outputs": [
- {
- "name": "stdout",
- "output_type": "stream",
- "text": [
- "10 loops, best of 3: 90.6 ms per loop\n"
- ]
- }
- ],
- "source": [
- "%%timeit\n",
- "dfs_search('vice', 'wars')"
- ]
- },
- {
- "cell_type": "markdown",
- "metadata": {},
- "source": [
- "## Part 2\n",
- "\n",
- "The example shows that `jags` is reachable in four steps from `rash`. There are 11 words one step away from `rash`: \n",
- "`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, and `wash`. \n",
- "\n",
- "There are 47 words reachable in one or two steps from `rash`. They are `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`, and `wish`.\n",
- "\n",
- "There are 180 words reachable in up to three steps from `rash`.\n",
- "\n",
- "How many words are reachable in up to ten steps from `vice`?"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 29,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "def reachable_in(word, n, trim_extras=False):\n",
- " reachable = set()\n",
- " boundary = set([word])\n",
- " for i in range(n):\n",
- " extras = set()\n",
- " for w in boundary:\n",
- " extras.update(neighbours[w])\n",
- " if trim_extras:\n",
- " extras.difference_update(reachable)\n",
- " reachable.update(boundary)\n",
- " boundary = extras.copy()\n",
- " return reachable.union(extras).difference(set([word]))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 30,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "['bash',\n",
- " 'cash',\n",
- " 'dash',\n",
- " 'gash',\n",
- " 'hash',\n",
- " 'lash',\n",
- " 'mash',\n",
- " 'sash',\n",
- " 'wash',\n",
- " 'rush',\n",
- " 'rasp']"
- ]
- },
- "execution_count": 30,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "neighbours['rash']"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 31,
- "metadata": {
- "scrolled": true
- },
- "outputs": [
- {
- "data": {
- "text/plain": [
- "(11,\n",
- " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
- ]
- },
- "execution_count": 31,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "len(reachable_in('rash', 1)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 1)))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 32,
- "metadata": {
- "scrolled": true
- },
- "outputs": [
- {
- "data": {
- "text/plain": [
- "(11,\n",
- " '<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": 32,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "len(reachable_in('rash', 1)), ', '.join(sorted('<code>{}</code>'.format(r) for r in reachable_in('rash', 1)))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 33,
- "metadata": {
- "scrolled": true
- },
- "outputs": [
- {
- "data": {
- "text/plain": [
- "(47,\n",
- " '`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": 33,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "len(reachable_in('rash', 2)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 2)))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 34,
- "metadata": {
- "scrolled": true
- },
- "outputs": [
- {
- "data": {
- "text/plain": [
- "(47,\n",
- " '<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": 34,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "len(reachable_in('rash', 2)), ', '.join(sorted('<code>{}</code>'.format(r) for r in reachable_in('rash', 2)))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 35,
- "metadata": {
- "scrolled": true
- },
- "outputs": [
- {
- "data": {
- "text/plain": [
- "180"
- ]
- },
- "execution_count": 35,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "len(reachable_in('rash', 3))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 36,
- "metadata": {
- "scrolled": true
- },
- "outputs": [
- {
- "data": {
- "text/plain": [
- "2195"
- ]
- },
- "execution_count": 36,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "len(reachable_in('rash', 10))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 37,
- "metadata": {
- "scrolled": true
- },
- "outputs": [
- {
- "data": {
- "text/plain": [
- "2192"
- ]
- },
- "execution_count": 37,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "len(reachable_in('vice', 10))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 38,
- "metadata": {
- "scrolled": true
- },
- "outputs": [
- {
- "name": "stdout",
- "output_type": "stream",
- "text": [
- "100 loops, best of 3: 5.81 ms per loop\n"
- ]
- }
- ],
- "source": [
- "%%timeit\n",
- "len(reachable_in('rash', 10))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 39,
- "metadata": {
- "scrolled": true
- },
- "outputs": [
- {
- "name": "stdout",
- "output_type": "stream",
- "text": [
- "100 loops, best of 3: 2.71 ms per loop\n"
- ]
- }
- ],
- "source": [
- "%%timeit\n",
- "len(reachable_in('rash', 10, trim_extras=True))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 40,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "2188"
- ]
- },
- "execution_count": 40,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "len(reachable_in('stay', 10))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 41,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "2193"
- ]
- },
- "execution_count": 41,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "len(reachable_in('coax', 10))"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 42,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "280"
- ]
- },
- "execution_count": 42,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "stay5 = reachable_in('stay', 4)\n",
- "len(stay5)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 43,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "296"
- ]
- },
- "execution_count": 43,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "extras = set()\n",
- "for w in stay5:\n",
- " extras.update(neighbours[w])\n",
- "extras.difference_update(stay5)\n",
- "len(extras)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 44,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "'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": 44,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "' '.join(extras)"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 45,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
- ]
- },
- "execution_count": 45,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "astar_search('coax', 'stay')"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 46,
- "metadata": {},
- "outputs": [
- {
- "name": "stdout",
- "output_type": "stream",
- "text": [
- "CPU times: user 620 ms, sys: 4 ms, total: 624 ms\n",
- "Wall time: 624 ms\n"
- ]
- },
- {
- "data": {
- "text/plain": [
- "['coax', 'coat', 'chat', 'shat', 'spat', 'spay', 'stay']"
- ]
- },
- "execution_count": 46,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "%time bfs_search_closed('coax', 'stay')"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 47,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "# %time bfs_search('coax', 'stay')"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 48,
- "metadata": {},
- "outputs": [
- {
- "data": {
- "text/plain": [
- "['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
- ]
- },
- "execution_count": 48,
- "metadata": {},
- "output_type": "execute_result"
- }
- ],
- "source": [
- "astar_search('czar', 'stay')"
- ]
- },
- {
- "cell_type": "code",
- "execution_count": 49,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": [
- "# %time bfs_search('czar', 'stay')"
- ]
- },
- {
- "cell_type": "code",
- "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,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
- "source": []
- }
- ],
- "metadata": {
- "kernelspec": {
- "display_name": "Python 3",
- "language": "python",
- "name": "python3"
- },
- "language_info": {
- "codemirror_mode": {
- "name": "ipython",
- "version": 3
- },
- "file_extension": ".py",
- "mimetype": "text/x-python",
- "name": "python",
- "nbconvert_exporter": "python",
- "pygments_lexer": "ipython3",
- "version": "3.5.2+"
- }
- },
- "nbformat": 4,
- "nbformat_minor": 2
-}
projects / ou-summer-of-code-2017.git / blobdiff