{
 "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": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import string\n",
    "import heapq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2336"
      ]
     },
     "execution_count": 2,
     "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": 3,
   "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": 4,
   "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": 5,
   "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": 6,
   "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": 7,
   "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": 8,
   "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": 9,
   "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 agenda:\n",
    "        return current\n",
    "    else:\n",
    "        return None        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "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 agenda:\n",
    "        return current\n",
    "    else:\n",
    "        return None   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "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 agenda:\n",
    "        return current\n",
    "    else:\n",
    "        return None        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "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 agenda:\n",
    "        return current\n",
    "    else:\n",
    "        return None        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "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 agenda:\n",
    "        return current\n",
    "    else:\n",
    "        return None        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "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 agenda:\n",
    "        return current\n",
    "    else:\n",
    "        return None   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('vice', 'wars')"
   ]
  },
  {
   "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_raw('vice', 'wars')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['boon', 'boot', 'bolt', 'belt', 'bell', 'sell']"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search_raw('boon', 'sell')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(astar_search('vice', 'wars'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# len(bfs_search('vice', 'wars'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(bfs_search_closed('vice', 'wars'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "793"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(dfs_search('vice', 'wars'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000 loops, best of 3: 153 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search('vice', 'wars')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 15.7 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search_raw('vice', 'wars')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000 loops, best of 3: 165 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search_closed('vice', 'wars')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# %%timeit\n",
    "# bfs_search('vice', 'wars')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 446 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "bfs_search_closed('vice', 'wars')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 91.4 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": 28,
   "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": 29,
   "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": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbours['rash']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(11,\n",
       " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
      ]
     },
     "execution_count": 30,
     "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": 31,
   "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": 31,
     "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": 32,
   "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": 32,
     "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": 33,
   "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": 33,
     "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": 34,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "180"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(reachable_in('rash', 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2195"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(reachable_in('rash', 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2192"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(reachable_in('vice', 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 5.84 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "len(reachable_in('rash', 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 2.79 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "len(reachable_in('rash', 10, trim_extras=True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2188"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(reachable_in('stay', 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2193"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(reachable_in('coax', 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "280"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stay5 = reachable_in('stay', 4)\n",
    "len(stay5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "296"
      ]
     },
     "execution_count": 42,
     "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": 43,
   "metadata": {},
   "outputs": [
    {
     "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'"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "' '.join(extras)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('coax', 'stay')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "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"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['coax', 'coat', 'chat', 'shat', 'spat', 'spay', 'stay']"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time bfs_search_closed('coax', 'stay')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "# %time bfs_search('coax', 'stay')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('czar', 'stay')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "# %time bfs_search('czar', 'stay')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "# %time bfs_search('coax', 'stay')"
   ]
  },
  {
   "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
}