{
 "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": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2336"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = [w.strip() for w in open('08-offices.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": {
    "collapsed": false
   },
   "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": {
    "collapsed": false
   },
   "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": {
    "collapsed": false
   },
   "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": {
    "collapsed": false
   },
   "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": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# len(bfs_search('vice', 'wars'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "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": {
    "collapsed": false
   },
   "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": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000 loops, best of 3: 273 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search('vice', 'wars')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 25.6 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search_raw('vice', 'wars')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000 loops, best of 3: 300 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search_closed('vice', 'wars')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# %%timeit\n",
    "# bfs_search('vice', 'wars')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 664 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "bfs_search_closed('vice', 'wars')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 147 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": 52,
   "metadata": {
    "collapsed": false
   },
   "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": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbours['rash']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(11,\n",
       " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
      ]
     },
     "execution_count": 29,
     "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": 47,
   "metadata": {
    "collapsed": false,
    "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": 47,
     "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": 30,
   "metadata": {
    "collapsed": false,
    "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": 30,
     "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": 51,
   "metadata": {
    "collapsed": false,
    "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": 51,
     "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": 31,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "180"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(reachable_in('rash', 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2195"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(reachable_in('rash', 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2192"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(reachable_in('vice', 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 8.95 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "len(reachable_in('rash', 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 4.14 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "len(reachable_in('rash', 10, trim_extras=True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2188"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(reachable_in('stay', 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2193"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(reachable_in('coax', 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "280"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stay5 = reachable_in('stay', 4)\n",
    "len(stay5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "296"
      ]
     },
     "execution_count": 39,
     "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": 40,
   "metadata": {
    "collapsed": false
   },
   "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'"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "' '.join(extras)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('coax', 'stay')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "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"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['coax', 'coat', 'chat', 'shat', 'slat', 'slay', 'stay']"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time bfs_search_closed('coax', 'stay')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# %time bfs_search('coax', 'stay')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('czar', 'stay')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# %time bfs_search('czar', 'stay')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "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
}