08-word-chains/word-chain-solution.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Word chains\n",
   8     "\n",
   9     "\"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",
  10     "\n",
  11     "For instance, you can transform 'rash' to 'jags' like this:\n",
  12     "\n",
  13     "```\n",
  14     "rash\n",
  15     "Bash\n",
  16     "basS\n",
  17     "baGs\n",
  18     "Jags\n",
  19     "```\n",
  20     "\n",
  21     "(the capital letter is the one changed in each step).\n",
  22     "\n",
  23     "## Part 1\n",
  24     "\n",
  25     "Given this [list of words](words4.txt), what is the minimum number of steps to go from `vice` to `wars`?"
  26    ]
  27   },
  28   {
  29    "cell_type": "code",
  30    "execution_count": 1,
  31    "metadata": {
  32     "collapsed": true
  33    },
  34    "outputs": [],
  35    "source": [
  36     "import string\n",
  37     "import heapq"
  38    ]
  39   },
  40   {
  41    "cell_type": "code",
  42    "execution_count": 2,
  43    "metadata": {
  44     "collapsed": false
  45    },
  46    "outputs": [
  47     {
  48      "data": {
  49       "text/plain": [
  50        "2336"
  51       ]
  52      },
  53      "execution_count": 2,
  54      "metadata": {},
  55      "output_type": "execute_result"
  56     }
  57    ],
  58    "source": [
  59     "words = [w.strip() for w in open('08-words.txt').readlines()]\n",
  60     "len(words)"
  61    ]
  62   },
  63   {
  64    "cell_type": "code",
  65    "execution_count": 3,
  66    "metadata": {
  67     "collapsed": true
  68    },
  69    "outputs": [],
  70    "source": [
  71     "def adjacents(word):\n",
  72     "    return [word[0:i] + l + word[i+1:]\n",
  73     "           for i in range(len(word))\n",
  74     "           for l in string.ascii_lowercase\n",
  75     "           if l != word[i]]"
  76    ]
  77   },
  78   {
  79    "cell_type": "code",
  80    "execution_count": 4,
  81    "metadata": {
  82     "collapsed": true
  83    },
  84    "outputs": [],
  85    "source": [
  86     "neighbours = {w: [n for n in adjacents(w) if n in words]\n",
  87     "             for w in words}"
  88    ]
  89   },
  90   {
  91    "cell_type": "code",
  92    "execution_count": 5,
  93    "metadata": {
  94     "collapsed": true
  95    },
  96    "outputs": [],
  97    "source": [
  98     "def distance(w1, w2):\n",
  99     "    return sum(1 for i in range(len(w1))\n",
 100     "               if w1[i] != w2[i])"
 101    ]
 102   },
 103   {
 104    "cell_type": "code",
 105    "execution_count": 6,
 106    "metadata": {
 107     "collapsed": true
 108    },
 109    "outputs": [],
 110    "source": [
 111     "# def extend(chain):\n",
 112     "#     return [chain + [s] for s in neighbours[chain[-1]]\n",
 113     "#            if s not in chain]"
 114    ]
 115   },
 116   {
 117    "cell_type": "code",
 118    "execution_count": 7,
 119    "metadata": {
 120     "collapsed": true
 121    },
 122    "outputs": [],
 123    "source": [
 124     "def extend(chain, closed=None):\n",
 125     "    if closed:\n",
 126     "        nbrs = set(neighbours[chain[-1]]) - closed\n",
 127     "    else:\n",
 128     "        nbrs = neighbours[chain[-1]]\n",
 129     "    return [chain + [s] for s in nbrs\n",
 130     "           if s not in chain]"
 131    ]
 132   },
 133   {
 134    "cell_type": "code",
 135    "execution_count": 8,
 136    "metadata": {
 137     "collapsed": true
 138    },
 139    "outputs": [],
 140    "source": [
 141     "def extend_raw(chain):\n",
 142     "    nbrs = [w for w in adjacents(chain[-1]) if w in words]\n",
 143     "    return [chain + [s] for s in nbrs\n",
 144     "           if s not in chain]"
 145    ]
 146   },
 147   {
 148    "cell_type": "code",
 149    "execution_count": 9,
 150    "metadata": {
 151     "collapsed": true
 152    },
 153    "outputs": [],
 154    "source": [
 155     "def bfs_search(start, goal, debug=False):\n",
 156     "    agenda = [[start]]\n",
 157     "    finished = False\n",
 158     "    while not finished and agenda:\n",
 159     "        current = agenda[0]\n",
 160     "        if debug:\n",
 161     "            print(current)\n",
 162     "        if current[-1] == goal:\n",
 163     "            finished = True\n",
 164     "        else:\n",
 165     "            successors = extend(current)\n",
 166     "            agenda = agenda[1:] + successors\n",
 167     "    if agenda:\n",
 168     "        return current\n",
 169     "    else:\n",
 170     "        return None        "
 171    ]
 172   },
 173   {
 174    "cell_type": "code",
 175    "execution_count": 10,
 176    "metadata": {
 177     "collapsed": true
 178    },
 179    "outputs": [],
 180    "source": [
 181     "def bfs_search_closed(start, goal, debug=False):\n",
 182     "    agenda = [[start]]\n",
 183     "    closed = set()\n",
 184     "    finished = False\n",
 185     "    while not finished and agenda:\n",
 186     "        current = agenda[0]\n",
 187     "        if debug:\n",
 188     "            print(current)\n",
 189     "        if current[-1] == goal:\n",
 190     "            finished = True\n",
 191     "        else:\n",
 192     "            closed.add(current[-1])\n",
 193     "            successors = extend(current, closed)\n",
 194     "            agenda = agenda[1:] + successors\n",
 195     "    if agenda:\n",
 196     "        return current\n",
 197     "    else:\n",
 198     "        return None   "
 199    ]
 200   },
 201   {
 202    "cell_type": "code",
 203    "execution_count": 11,
 204    "metadata": {
 205     "collapsed": true
 206    },
 207    "outputs": [],
 208    "source": [
 209     "def dfs_search(start, goal, debug=False):\n",
 210     "    agenda = [[start]]\n",
 211     "    finished = False\n",
 212     "    while not finished and agenda:\n",
 213     "        current = agenda[0]\n",
 214     "        if debug:\n",
 215     "            print(current)\n",
 216     "        if current[-1] == goal:\n",
 217     "            finished = True\n",
 218     "        else:\n",
 219     "            successors = extend(current)\n",
 220     "            agenda = successors + agenda[1:]\n",
 221     "    if agenda:\n",
 222     "        return current\n",
 223     "    else:\n",
 224     "        return None        "
 225    ]
 226   },
 227   {
 228    "cell_type": "code",
 229    "execution_count": 12,
 230    "metadata": {
 231     "collapsed": true
 232    },
 233    "outputs": [],
 234    "source": [
 235     "def astar_search(start, goal, debug=False):\n",
 236     "    agenda = [(distance(start, goal), [start])]\n",
 237     "    heapq.heapify(agenda)\n",
 238     "    finished = False\n",
 239     "    while not finished and agenda:\n",
 240     "        _, current = heapq.heappop(agenda)\n",
 241     "        if debug:\n",
 242     "            print(current)\n",
 243     "        if current[-1] == goal:\n",
 244     "            finished = True\n",
 245     "        else:\n",
 246     "            successors = extend(current)\n",
 247     "            for s in successors:\n",
 248     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
 249     "    if agenda:\n",
 250     "        return current\n",
 251     "    else:\n",
 252     "        return None        "
 253    ]
 254   },
 255   {
 256    "cell_type": "code",
 257    "execution_count": 13,
 258    "metadata": {
 259     "collapsed": true
 260    },
 261    "outputs": [],
 262    "source": [
 263     "# Uses direct lookup of successors, rather than using cached neighbours in the dict\n",
 264     "def astar_search_raw(start, goal, debug=False):\n",
 265     "    agenda = [(distance(start, goal), [start])]\n",
 266     "    heapq.heapify(agenda)\n",
 267     "    finished = False\n",
 268     "    while not finished and agenda:\n",
 269     "        _, current = heapq.heappop(agenda)\n",
 270     "        if debug:\n",
 271     "            print(current)\n",
 272     "        if current[-1] == goal:\n",
 273     "            finished = True\n",
 274     "        else:\n",
 275     "            successors = extend_raw(current) # Difference here\n",
 276     "            for s in successors:\n",
 277     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
 278     "    if agenda:\n",
 279     "        return current\n",
 280     "    else:\n",
 281     "        return None        "
 282    ]
 283   },
 284   {
 285    "cell_type": "code",
 286    "execution_count": 14,
 287    "metadata": {
 288     "collapsed": true
 289    },
 290    "outputs": [],
 291    "source": [
 292     "def astar_search_closed(start, goal, debug=False):\n",
 293     "    agenda = [(distance(start, goal), [start])]\n",
 294     "    heapq.heapify(agenda)\n",
 295     "    closed = set()\n",
 296     "    finished = False\n",
 297     "    while not finished and agenda:\n",
 298     "        _, current = heapq.heappop(agenda)\n",
 299     "        if debug:\n",
 300     "            print(current)\n",
 301     "        if current[-1] == goal:\n",
 302     "            finished = True\n",
 303     "        else:\n",
 304     "            closed.add(current[-1])\n",
 305     "            successors = extend(current, closed)\n",
 306     "            for s in successors:\n",
 307     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
 308     "    if agenda:\n",
 309     "        return current\n",
 310     "    else:\n",
 311     "        return None   "
 312    ]
 313   },
 314   {
 315    "cell_type": "code",
 316    "execution_count": 15,
 317    "metadata": {
 318     "collapsed": false
 319    },
 320    "outputs": [
 321     {
 322      "data": {
 323       "text/plain": [
 324        "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
 325       ]
 326      },
 327      "execution_count": 15,
 328      "metadata": {},
 329      "output_type": "execute_result"
 330     }
 331    ],
 332    "source": [
 333     "astar_search('vice', 'wars')"
 334    ]
 335   },
 336   {
 337    "cell_type": "code",
 338    "execution_count": 16,
 339    "metadata": {
 340     "collapsed": false
 341    },
 342    "outputs": [
 343     {
 344      "data": {
 345       "text/plain": [
 346        "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
 347       ]
 348      },
 349      "execution_count": 16,
 350      "metadata": {},
 351      "output_type": "execute_result"
 352     }
 353    ],
 354    "source": [
 355     "astar_search_raw('vice', 'wars')"
 356    ]
 357   },
 358   {
 359    "cell_type": "code",
 360    "execution_count": 17,
 361    "metadata": {
 362     "collapsed": false
 363    },
 364    "outputs": [
 365     {
 366      "data": {
 367       "text/plain": [
 368        "6"
 369       ]
 370      },
 371      "execution_count": 17,
 372      "metadata": {},
 373      "output_type": "execute_result"
 374     }
 375    ],
 376    "source": [
 377     "len(astar_search('vice', 'wars'))"
 378    ]
 379   },
 380   {
 381    "cell_type": "code",
 382    "execution_count": 18,
 383    "metadata": {
 384     "collapsed": false
 385    },
 386    "outputs": [
 387     {
 388      "ename": "KeyboardInterrupt",
 389      "evalue": "",
 390      "output_type": "error",
 391      "traceback": [
 392       "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
 393       "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
 394       "\u001b[0;32m<ipython-input-18-77e0f8036978>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbfs_search\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'vice'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'wars'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
 395       "\u001b[0;32m<ipython-input-9-0c5cf399e032>\u001b[0m in \u001b[0;36mbfs_search\u001b[0;34m(start, goal, debug)\u001b[0m\n\u001b[1;32m     10\u001b[0m         \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m             \u001b[0msuccessors\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mextend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcurrent\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m             \u001b[0magenda\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0magenda\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0msuccessors\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0magenda\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mcurrent\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
 396       "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
 397      ]
 398     }
 399    ],
 400    "source": [
 401     "len(bfs_search('vice', 'wars'))"
 402    ]
 403   },
 404   {
 405    "cell_type": "code",
 406    "execution_count": 19,
 407    "metadata": {
 408     "collapsed": false
 409    },
 410    "outputs": [
 411     {
 412      "data": {
 413       "text/plain": [
 414        "6"
 415       ]
 416      },
 417      "execution_count": 19,
 418      "metadata": {},
 419      "output_type": "execute_result"
 420     }
 421    ],
 422    "source": [
 423     "len(bfs_search_closed('vice', 'wars'))"
 424    ]
 425   },
 426   {
 427    "cell_type": "code",
 428    "execution_count": 20,
 429    "metadata": {
 430     "collapsed": false
 431    },
 432    "outputs": [
 433     {
 434      "data": {
 435       "text/plain": [
 436        "793"
 437       ]
 438      },
 439      "execution_count": 20,
 440      "metadata": {},
 441      "output_type": "execute_result"
 442     }
 443    ],
 444    "source": [
 445     "len(dfs_search('vice', 'wars'))"
 446    ]
 447   },
 448   {
 449    "cell_type": "code",
 450    "execution_count": 21,
 451    "metadata": {
 452     "collapsed": false
 453    },
 454    "outputs": [
 455     {
 456      "name": "stdout",
 457      "output_type": "stream",
 458      "text": [
 459       "1000 loops, best of 3: 225 µs per loop\n"
 460      ]
 461     }
 462    ],
 463    "source": [
 464     "%%timeit\n",
 465     "astar_search('vice', 'wars')"
 466    ]
 467   },
 468   {
 469    "cell_type": "code",
 470    "execution_count": 22,
 471    "metadata": {
 472     "collapsed": false
 473    },
 474    "outputs": [
 475     {
 476      "name": "stdout",
 477      "output_type": "stream",
 478      "text": [
 479       "10 loops, best of 3: 22.1 ms per loop\n"
 480      ]
 481     }
 482    ],
 483    "source": [
 484     "%%timeit\n",
 485     "astar_search_raw('vice', 'wars')"
 486    ]
 487   },
 488   {
 489    "cell_type": "code",
 490    "execution_count": 23,
 491    "metadata": {
 492     "collapsed": false
 493    },
 494    "outputs": [
 495     {
 496      "name": "stdout",
 497      "output_type": "stream",
 498      "text": [
 499       "1000 loops, best of 3: 280 µs per loop\n"
 500      ]
 501     }
 502    ],
 503    "source": [
 504     "%%timeit\n",
 505     "astar_search_closed('vice', 'wars')"
 506    ]
 507   },
 508   {
 509    "cell_type": "code",
 510    "execution_count": 24,
 511    "metadata": {
 512     "collapsed": false
 513    },
 514    "outputs": [
 515     {
 516      "ename": "KeyboardInterrupt",
 517      "evalue": "",
 518      "output_type": "error",
 519      "traceback": [
 520       "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
 521       "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
 522       "\u001b[0;32m<ipython-input-24-ec1214959874>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mget_ipython\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrun_cell_magic\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'timeit'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m''\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"bfs_search('vice', 'wars')\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
 523       "\u001b[0;32m/usr/local/lib/python3.5/dist-packages/IPython/core/interactiveshell.py\u001b[0m in \u001b[0;36mrun_cell_magic\u001b[0;34m(self, magic_name, line, cell)\u001b[0m\n\u001b[1;32m   2113\u001b[0m             \u001b[0mmagic_arg_s\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvar_expand\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mline\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstack_depth\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   2114\u001b[0m             \u001b[0;32mwith\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbuiltin_trap\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 2115\u001b[0;31m                 \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfn\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmagic_arg_s\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcell\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   2116\u001b[0m             \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   2117\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
 524       "\u001b[0;32m<decorator-gen-58>\u001b[0m in \u001b[0;36mtimeit\u001b[0;34m(self, line, cell)\u001b[0m\n",
 525       "\u001b[0;32m/usr/local/lib/python3.5/dist-packages/IPython/core/magic.py\u001b[0m in \u001b[0;36m<lambda>\u001b[0;34m(f, *a, **k)\u001b[0m\n\u001b[1;32m    186\u001b[0m     \u001b[0;31m# but it's overkill for just that one bit of state.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    187\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mmagic_deco\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0marg\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 188\u001b[0;31m         \u001b[0mcall\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mlambda\u001b[0m \u001b[0mf\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mf\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    189\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    190\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mcallable\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0marg\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
 526       "\u001b[0;32m/usr/local/lib/python3.5/dist-packages/IPython/core/magics/execution.py\u001b[0m in \u001b[0;36mtimeit\u001b[0;34m(self, line, cell)\u001b[0m\n\u001b[1;32m   1042\u001b[0m             \u001b[0mnumber\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1043\u001b[0m             \u001b[0;32mfor\u001b[0m \u001b[0m_\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m10\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1044\u001b[0;31m                 \u001b[0mtime_number\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtimer\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtimeit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnumber\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1045\u001b[0m                 \u001b[0mworst_tuning\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mworst_tuning\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtime_number\u001b[0m \u001b[0;34m/\u001b[0m \u001b[0mnumber\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1046\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mtime_number\u001b[0m \u001b[0;34m>=\u001b[0m \u001b[0;36m0.2\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
 527       "\u001b[0;32m/usr/local/lib/python3.5/dist-packages/IPython/core/magics/execution.py\u001b[0m in \u001b[0;36mtimeit\u001b[0;34m(self, number)\u001b[0m\n\u001b[1;32m    137\u001b[0m         \u001b[0mgc\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdisable\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    138\u001b[0m         \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 139\u001b[0;31m             \u001b[0mtiming\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minner\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mit\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtimer\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    140\u001b[0m         \u001b[0;32mfinally\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    141\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mgcold\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
 528       "\u001b[0;32m<magic-timeit>\u001b[0m in \u001b[0;36minner\u001b[0;34m(_it, _timer)\u001b[0m\n",
 529       "\u001b[0;32m<ipython-input-9-0c5cf399e032>\u001b[0m in \u001b[0;36mbfs_search\u001b[0;34m(start, goal, debug)\u001b[0m\n\u001b[1;32m     10\u001b[0m         \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m             \u001b[0msuccessors\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mextend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcurrent\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m             \u001b[0magenda\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0magenda\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0msuccessors\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0magenda\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mcurrent\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
 530       "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
 531      ]
 532     }
 533    ],
 534    "source": [
 535     "%%timeit\n",
 536     "bfs_search('vice', 'wars')"
 537    ]
 538   },
 539   {
 540    "cell_type": "code",
 541    "execution_count": 25,
 542    "metadata": {
 543     "collapsed": false
 544    },
 545    "outputs": [
 546     {
 547      "name": "stdout",
 548      "output_type": "stream",
 549      "text": [
 550       "1 loop, best of 3: 1.12 s per loop\n"
 551      ]
 552     }
 553    ],
 554    "source": [
 555     "%%timeit\n",
 556     "bfs_search_closed('vice', 'wars')"
 557    ]
 558   },
 559   {
 560    "cell_type": "code",
 561    "execution_count": 26,
 562    "metadata": {
 563     "collapsed": false
 564    },
 565    "outputs": [
 566     {
 567      "name": "stdout",
 568      "output_type": "stream",
 569      "text": [
 570       "10 loops, best of 3: 127 ms per loop\n"
 571      ]
 572     }
 573    ],
 574    "source": [
 575     "%%timeit\n",
 576     "dfs_search('vice', 'wars')"
 577    ]
 578   },
 579   {
 580    "cell_type": "markdown",
 581    "metadata": {},
 582    "source": [
 583     "## Part 2\n",
 584     "\n",
 585     "The example shows that `jags` is reachable in four steps from `rash`. There are 11 words one step away from `rash`: \n",
 586     "`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, and `wash`. \n",
 587     "\n",
 588     "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",
 589     "\n",
 590     "There are 180 words reachable in up to three steps from `rash`.\n",
 591     "\n",
 592     "How many words are reachable in up to ten steps from `vice`?"
 593    ]
 594   },
 595   {
 596    "cell_type": "code",
 597    "execution_count": 27,
 598    "metadata": {
 599     "collapsed": true
 600    },
 601    "outputs": [],
 602    "source": [
 603     "def reachable_in(word, n, trim_extras=False):\n",
 604     "    reachable = set()\n",
 605     "    boundary = set([word])\n",
 606     "    for i in range(n):\n",
 607     "        extras = set()\n",
 608     "        for w in boundary:\n",
 609     "            extras.update(neighbours[w])\n",
 610     "        if trim_extras:\n",
 611     "            extras.difference_update(reachable)\n",
 612     "        reachable.update(boundary)\n",
 613     "        boundary = extras.copy()\n",
 614     "    return reachable.union(extras).difference(set([word]))"
 615    ]
 616   },
 617   {
 618    "cell_type": "code",
 619    "execution_count": 28,
 620    "metadata": {
 621     "collapsed": false,
 622     "scrolled": true
 623    },
 624    "outputs": [
 625     {
 626      "data": {
 627       "text/plain": [
 628        "(11,\n",
 629        " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
 630       ]
 631      },
 632      "execution_count": 28,
 633      "metadata": {},
 634      "output_type": "execute_result"
 635     }
 636    ],
 637    "source": [
 638     "len(reachable_in('rash', 1)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 1)))"
 639    ]
 640   },
 641   {
 642    "cell_type": "code",
 643    "execution_count": 29,
 644    "metadata": {
 645     "collapsed": false,
 646     "scrolled": true
 647    },
 648    "outputs": [
 649     {
 650      "data": {
 651       "text/plain": [
 652        "(47,\n",
 653        " '`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`')"
 654       ]
 655      },
 656      "execution_count": 29,
 657      "metadata": {},
 658      "output_type": "execute_result"
 659     }
 660    ],
 661    "source": [
 662     "len(reachable_in('rash', 2)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 2)))"
 663    ]
 664   },
 665   {
 666    "cell_type": "code",
 667    "execution_count": 30,
 668    "metadata": {
 669     "collapsed": false,
 670     "scrolled": true
 671    },
 672    "outputs": [
 673     {
 674      "data": {
 675       "text/plain": [
 676        "180"
 677       ]
 678      },
 679      "execution_count": 30,
 680      "metadata": {},
 681      "output_type": "execute_result"
 682     }
 683    ],
 684    "source": [
 685     "len(reachable_in('rash', 3))"
 686    ]
 687   },
 688   {
 689    "cell_type": "code",
 690    "execution_count": 31,
 691    "metadata": {
 692     "collapsed": false,
 693     "scrolled": true
 694    },
 695    "outputs": [
 696     {
 697      "data": {
 698       "text/plain": [
 699        "2195"
 700       ]
 701      },
 702      "execution_count": 31,
 703      "metadata": {},
 704      "output_type": "execute_result"
 705     }
 706    ],
 707    "source": [
 708     "len(reachable_in('rash', 10))"
 709    ]
 710   },
 711   {
 712    "cell_type": "code",
 713    "execution_count": 32,
 714    "metadata": {
 715     "collapsed": false,
 716     "scrolled": true
 717    },
 718    "outputs": [
 719     {
 720      "data": {
 721       "text/plain": [
 722        "2192"
 723       ]
 724      },
 725      "execution_count": 32,
 726      "metadata": {},
 727      "output_type": "execute_result"
 728     }
 729    ],
 730    "source": [
 731     "len(reachable_in('vice', 10))"
 732    ]
 733   },
 734   {
 735    "cell_type": "code",
 736    "execution_count": 33,
 737    "metadata": {
 738     "collapsed": false,
 739     "scrolled": true
 740    },
 741    "outputs": [
 742     {
 743      "name": "stdout",
 744      "output_type": "stream",
 745      "text": [
 746       "100 loops, best of 3: 9.26 ms per loop\n"
 747      ]
 748     }
 749    ],
 750    "source": [
 751     "%%timeit\n",
 752     "len(reachable_in('rash', 10))"
 753    ]
 754   },
 755   {
 756    "cell_type": "code",
 757    "execution_count": 34,
 758    "metadata": {
 759     "collapsed": false,
 760     "scrolled": true
 761    },
 762    "outputs": [
 763     {
 764      "name": "stdout",
 765      "output_type": "stream",
 766      "text": [
 767       "100 loops, best of 3: 3.64 ms per loop\n"
 768      ]
 769     }
 770    ],
 771    "source": [
 772     "%%timeit\n",
 773     "len(reachable_in('rash', 10, trim_extras=True))"
 774    ]
 775   },
 776   {
 777    "cell_type": "code",
 778    "execution_count": null,
 779    "metadata": {
 780     "collapsed": true
 781    },
 782    "outputs": [],
 783    "source": []
 784   }
 785  ],
 786  "metadata": {
 787   "kernelspec": {
 788    "display_name": "Python 3",
 789    "language": "python",
 790    "name": "python3"
 791   },
 792   "language_info": {
 793    "codemirror_mode": {
 794     "name": "ipython",
 795     "version": 3
 796    },
 797    "file_extension": ".py",
 798    "mimetype": "text/x-python",
 799    "name": "python",
 800    "nbconvert_exporter": "python",
 801    "pygments_lexer": "ipython3",
 802    "version": "3.5.2"
 803   }
 804  },
 805  "nbformat": 4,
 806  "nbformat_minor": 2
 807 }