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-offices.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        "['boon', 'boot', 'bolt', 'belt', 'bell', 'sell']"
 369       ]
 370      },
 371      "execution_count": 17,
 372      "metadata": {},
 373      "output_type": "execute_result"
 374     }
 375    ],
 376    "source": [
 377     "astar_search_raw('boon', 'sell')"
 378    ]
 379   },
 380   {
 381    "cell_type": "code",
 382    "execution_count": 18,
 383    "metadata": {
 384     "collapsed": false
 385    },
 386    "outputs": [
 387     {
 388      "data": {
 389       "text/plain": [
 390        "6"
 391       ]
 392      },
 393      "execution_count": 18,
 394      "metadata": {},
 395      "output_type": "execute_result"
 396     }
 397    ],
 398    "source": [
 399     "len(astar_search('vice', 'wars'))"
 400    ]
 401   },
 402   {
 403    "cell_type": "code",
 404    "execution_count": 19,
 405    "metadata": {
 406     "collapsed": false
 407    },
 408    "outputs": [],
 409    "source": [
 410     "# len(bfs_search('vice', 'wars'))"
 411    ]
 412   },
 413   {
 414    "cell_type": "code",
 415    "execution_count": 20,
 416    "metadata": {
 417     "collapsed": false
 418    },
 419    "outputs": [
 420     {
 421      "data": {
 422       "text/plain": [
 423        "6"
 424       ]
 425      },
 426      "execution_count": 20,
 427      "metadata": {},
 428      "output_type": "execute_result"
 429     }
 430    ],
 431    "source": [
 432     "len(bfs_search_closed('vice', 'wars'))"
 433    ]
 434   },
 435   {
 436    "cell_type": "code",
 437    "execution_count": 21,
 438    "metadata": {
 439     "collapsed": false
 440    },
 441    "outputs": [
 442     {
 443      "data": {
 444       "text/plain": [
 445        "793"
 446       ]
 447      },
 448      "execution_count": 21,
 449      "metadata": {},
 450      "output_type": "execute_result"
 451     }
 452    ],
 453    "source": [
 454     "len(dfs_search('vice', 'wars'))"
 455    ]
 456   },
 457   {
 458    "cell_type": "code",
 459    "execution_count": 22,
 460    "metadata": {
 461     "collapsed": false
 462    },
 463    "outputs": [
 464     {
 465      "name": "stdout",
 466      "output_type": "stream",
 467      "text": [
 468       "1000 loops, best of 3: 273 µs per loop\n"
 469      ]
 470     }
 471    ],
 472    "source": [
 473     "%%timeit\n",
 474     "astar_search('vice', 'wars')"
 475    ]
 476   },
 477   {
 478    "cell_type": "code",
 479    "execution_count": 23,
 480    "metadata": {
 481     "collapsed": false
 482    },
 483    "outputs": [
 484     {
 485      "name": "stdout",
 486      "output_type": "stream",
 487      "text": [
 488       "10 loops, best of 3: 25.6 ms per loop\n"
 489      ]
 490     }
 491    ],
 492    "source": [
 493     "%%timeit\n",
 494     "astar_search_raw('vice', 'wars')"
 495    ]
 496   },
 497   {
 498    "cell_type": "code",
 499    "execution_count": 24,
 500    "metadata": {
 501     "collapsed": false
 502    },
 503    "outputs": [
 504     {
 505      "name": "stdout",
 506      "output_type": "stream",
 507      "text": [
 508       "1000 loops, best of 3: 300 µs per loop\n"
 509      ]
 510     }
 511    ],
 512    "source": [
 513     "%%timeit\n",
 514     "astar_search_closed('vice', 'wars')"
 515    ]
 516   },
 517   {
 518    "cell_type": "code",
 519    "execution_count": 25,
 520    "metadata": {
 521     "collapsed": false
 522    },
 523    "outputs": [],
 524    "source": [
 525     "# %%timeit\n",
 526     "# bfs_search('vice', 'wars')"
 527    ]
 528   },
 529   {
 530    "cell_type": "code",
 531    "execution_count": 26,
 532    "metadata": {
 533     "collapsed": false
 534    },
 535    "outputs": [
 536     {
 537      "name": "stdout",
 538      "output_type": "stream",
 539      "text": [
 540       "1 loop, best of 3: 664 ms per loop\n"
 541      ]
 542     }
 543    ],
 544    "source": [
 545     "%%timeit\n",
 546     "bfs_search_closed('vice', 'wars')"
 547    ]
 548   },
 549   {
 550    "cell_type": "code",
 551    "execution_count": 27,
 552    "metadata": {
 553     "collapsed": false
 554    },
 555    "outputs": [
 556     {
 557      "name": "stdout",
 558      "output_type": "stream",
 559      "text": [
 560       "10 loops, best of 3: 147 ms per loop\n"
 561      ]
 562     }
 563    ],
 564    "source": [
 565     "%%timeit\n",
 566     "dfs_search('vice', 'wars')"
 567    ]
 568   },
 569   {
 570    "cell_type": "markdown",
 571    "metadata": {},
 572    "source": [
 573     "## Part 2\n",
 574     "\n",
 575     "The example shows that `jags` is reachable in four steps from `rash`. There are 11 words one step away from `rash`: \n",
 576     "`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, and `wash`. \n",
 577     "\n",
 578     "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",
 579     "\n",
 580     "There are 180 words reachable in up to three steps from `rash`.\n",
 581     "\n",
 582     "How many words are reachable in up to ten steps from `vice`?"
 583    ]
 584   },
 585   {
 586    "cell_type": "code",
 587    "execution_count": 28,
 588    "metadata": {
 589     "collapsed": true
 590    },
 591    "outputs": [],
 592    "source": [
 593     "def reachable_in(word, n, trim_extras=False):\n",
 594     "    reachable = set()\n",
 595     "    boundary = set([word])\n",
 596     "    for i in range(n):\n",
 597     "        extras = set()\n",
 598     "        for w in boundary:\n",
 599     "            extras.update(neighbours[w])\n",
 600     "        if trim_extras:\n",
 601     "            extras.difference_update(reachable)\n",
 602     "        reachable.update(boundary)\n",
 603     "        boundary = extras.copy()\n",
 604     "    return reachable.union(extras).difference(set([word]))"
 605    ]
 606   },
 607   {
 608    "cell_type": "code",
 609    "execution_count": 52,
 610    "metadata": {
 611     "collapsed": false
 612    },
 613    "outputs": [
 614     {
 615      "data": {
 616       "text/plain": [
 617        "['bash',\n",
 618        " 'cash',\n",
 619        " 'dash',\n",
 620        " 'gash',\n",
 621        " 'hash',\n",
 622        " 'lash',\n",
 623        " 'mash',\n",
 624        " 'sash',\n",
 625        " 'wash',\n",
 626        " 'rush',\n",
 627        " 'rasp']"
 628       ]
 629      },
 630      "execution_count": 52,
 631      "metadata": {},
 632      "output_type": "execute_result"
 633     }
 634    ],
 635    "source": [
 636     "neighbours['rash']"
 637    ]
 638   },
 639   {
 640    "cell_type": "code",
 641    "execution_count": 29,
 642    "metadata": {
 643     "collapsed": false,
 644     "scrolled": true
 645    },
 646    "outputs": [
 647     {
 648      "data": {
 649       "text/plain": [
 650        "(11,\n",
 651        " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
 652       ]
 653      },
 654      "execution_count": 29,
 655      "metadata": {},
 656      "output_type": "execute_result"
 657     }
 658    ],
 659    "source": [
 660     "len(reachable_in('rash', 1)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 1)))"
 661    ]
 662   },
 663   {
 664    "cell_type": "code",
 665    "execution_count": 47,
 666    "metadata": {
 667     "collapsed": false,
 668     "scrolled": true
 669    },
 670    "outputs": [
 671     {
 672      "data": {
 673       "text/plain": [
 674        "(11,\n",
 675        " '<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>')"
 676       ]
 677      },
 678      "execution_count": 47,
 679      "metadata": {},
 680      "output_type": "execute_result"
 681     }
 682    ],
 683    "source": [
 684     "len(reachable_in('rash', 1)), ', '.join(sorted('<code>{}</code>'.format(r) for r in reachable_in('rash', 1)))"
 685    ]
 686   },
 687   {
 688    "cell_type": "code",
 689    "execution_count": 30,
 690    "metadata": {
 691     "collapsed": false,
 692     "scrolled": true
 693    },
 694    "outputs": [
 695     {
 696      "data": {
 697       "text/plain": [
 698        "(47,\n",
 699        " '`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`')"
 700       ]
 701      },
 702      "execution_count": 30,
 703      "metadata": {},
 704      "output_type": "execute_result"
 705     }
 706    ],
 707    "source": [
 708     "len(reachable_in('rash', 2)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 2)))"
 709    ]
 710   },
 711   {
 712    "cell_type": "code",
 713    "execution_count": 51,
 714    "metadata": {
 715     "collapsed": false,
 716     "scrolled": true
 717    },
 718    "outputs": [
 719     {
 720      "data": {
 721       "text/plain": [
 722        "(47,\n",
 723        " '<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>')"
 724       ]
 725      },
 726      "execution_count": 51,
 727      "metadata": {},
 728      "output_type": "execute_result"
 729     }
 730    ],
 731    "source": [
 732     "len(reachable_in('rash', 2)), ', '.join(sorted('<code>{}</code>'.format(r) for r in reachable_in('rash', 2)))"
 733    ]
 734   },
 735   {
 736    "cell_type": "code",
 737    "execution_count": 31,
 738    "metadata": {
 739     "collapsed": false,
 740     "scrolled": true
 741    },
 742    "outputs": [
 743     {
 744      "data": {
 745       "text/plain": [
 746        "180"
 747       ]
 748      },
 749      "execution_count": 31,
 750      "metadata": {},
 751      "output_type": "execute_result"
 752     }
 753    ],
 754    "source": [
 755     "len(reachable_in('rash', 3))"
 756    ]
 757   },
 758   {
 759    "cell_type": "code",
 760    "execution_count": 32,
 761    "metadata": {
 762     "collapsed": false,
 763     "scrolled": true
 764    },
 765    "outputs": [
 766     {
 767      "data": {
 768       "text/plain": [
 769        "2195"
 770       ]
 771      },
 772      "execution_count": 32,
 773      "metadata": {},
 774      "output_type": "execute_result"
 775     }
 776    ],
 777    "source": [
 778     "len(reachable_in('rash', 10))"
 779    ]
 780   },
 781   {
 782    "cell_type": "code",
 783    "execution_count": 33,
 784    "metadata": {
 785     "collapsed": false,
 786     "scrolled": true
 787    },
 788    "outputs": [
 789     {
 790      "data": {
 791       "text/plain": [
 792        "2192"
 793       ]
 794      },
 795      "execution_count": 33,
 796      "metadata": {},
 797      "output_type": "execute_result"
 798     }
 799    ],
 800    "source": [
 801     "len(reachable_in('vice', 10))"
 802    ]
 803   },
 804   {
 805    "cell_type": "code",
 806    "execution_count": 34,
 807    "metadata": {
 808     "collapsed": false,
 809     "scrolled": true
 810    },
 811    "outputs": [
 812     {
 813      "name": "stdout",
 814      "output_type": "stream",
 815      "text": [
 816       "100 loops, best of 3: 8.95 ms per loop\n"
 817      ]
 818     }
 819    ],
 820    "source": [
 821     "%%timeit\n",
 822     "len(reachable_in('rash', 10))"
 823    ]
 824   },
 825   {
 826    "cell_type": "code",
 827    "execution_count": 35,
 828    "metadata": {
 829     "collapsed": false,
 830     "scrolled": true
 831    },
 832    "outputs": [
 833     {
 834      "name": "stdout",
 835      "output_type": "stream",
 836      "text": [
 837       "100 loops, best of 3: 4.14 ms per loop\n"
 838      ]
 839     }
 840    ],
 841    "source": [
 842     "%%timeit\n",
 843     "len(reachable_in('rash', 10, trim_extras=True))"
 844    ]
 845   },
 846   {
 847    "cell_type": "code",
 848    "execution_count": 36,
 849    "metadata": {
 850     "collapsed": false
 851    },
 852    "outputs": [
 853     {
 854      "data": {
 855       "text/plain": [
 856        "2188"
 857       ]
 858      },
 859      "execution_count": 36,
 860      "metadata": {},
 861      "output_type": "execute_result"
 862     }
 863    ],
 864    "source": [
 865     "len(reachable_in('stay', 10))"
 866    ]
 867   },
 868   {
 869    "cell_type": "code",
 870    "execution_count": 37,
 871    "metadata": {
 872     "collapsed": false
 873    },
 874    "outputs": [
 875     {
 876      "data": {
 877       "text/plain": [
 878        "2193"
 879       ]
 880      },
 881      "execution_count": 37,
 882      "metadata": {},
 883      "output_type": "execute_result"
 884     }
 885    ],
 886    "source": [
 887     "len(reachable_in('coax', 10))"
 888    ]
 889   },
 890   {
 891    "cell_type": "code",
 892    "execution_count": 38,
 893    "metadata": {
 894     "collapsed": false
 895    },
 896    "outputs": [
 897     {
 898      "data": {
 899       "text/plain": [
 900        "280"
 901       ]
 902      },
 903      "execution_count": 38,
 904      "metadata": {},
 905      "output_type": "execute_result"
 906     }
 907    ],
 908    "source": [
 909     "stay5 = reachable_in('stay', 4)\n",
 910     "len(stay5)"
 911    ]
 912   },
 913   {
 914    "cell_type": "code",
 915    "execution_count": 39,
 916    "metadata": {
 917     "collapsed": false
 918    },
 919    "outputs": [
 920     {
 921      "data": {
 922       "text/plain": [
 923        "296"
 924       ]
 925      },
 926      "execution_count": 39,
 927      "metadata": {},
 928      "output_type": "execute_result"
 929     }
 930    ],
 931    "source": [
 932     "extras = set()\n",
 933     "for w in stay5:\n",
 934     "    extras.update(neighbours[w])\n",
 935     "extras.difference_update(stay5)\n",
 936     "len(extras)"
 937    ]
 938   },
 939   {
 940    "cell_type": "code",
 941    "execution_count": 40,
 942    "metadata": {
 943     "collapsed": false
 944    },
 945    "outputs": [
 946     {
 947      "data": {
 948       "text/plain": [
 949        "'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'"
 950       ]
 951      },
 952      "execution_count": 40,
 953      "metadata": {},
 954      "output_type": "execute_result"
 955     }
 956    ],
 957    "source": [
 958     "' '.join(extras)"
 959    ]
 960   },
 961   {
 962    "cell_type": "code",
 963    "execution_count": 41,
 964    "metadata": {
 965     "collapsed": false
 966    },
 967    "outputs": [
 968     {
 969      "data": {
 970       "text/plain": [
 971        "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
 972       ]
 973      },
 974      "execution_count": 41,
 975      "metadata": {},
 976      "output_type": "execute_result"
 977     }
 978    ],
 979    "source": [
 980     "astar_search('coax', 'stay')"
 981    ]
 982   },
 983   {
 984    "cell_type": "code",
 985    "execution_count": 42,
 986    "metadata": {
 987     "collapsed": false
 988    },
 989    "outputs": [
 990     {
 991      "name": "stdout",
 992      "output_type": "stream",
 993      "text": [
 994       "CPU times: user 2.35 s, sys: 0 ns, total: 2.35 s\n",
 995       "Wall time: 2.35 s\n"
 996      ]
 997     },
 998     {
 999      "data": {
1000       "text/plain": [
1001        "['coax', 'coat', 'chat', 'shat', 'slat', 'slay', 'stay']"
1002       ]
1003      },
1004      "execution_count": 42,
1005      "metadata": {},
1006      "output_type": "execute_result"
1007     }
1008    ],
1009    "source": [
1010     "%time bfs_search_closed('coax', 'stay')"
1011    ]
1012   },
1013   {
1014    "cell_type": "code",
1015    "execution_count": 48,
1016    "metadata": {
1017     "collapsed": false
1018    },
1019    "outputs": [],
1020    "source": [
1021     "# %time bfs_search('coax', 'stay')"
1022    ]
1023   },
1024   {
1025    "cell_type": "code",
1026    "execution_count": 44,
1027    "metadata": {
1028     "collapsed": false
1029    },
1030    "outputs": [
1031     {
1032      "data": {
1033       "text/plain": [
1034        "['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
1035       ]
1036      },
1037      "execution_count": 44,
1038      "metadata": {},
1039      "output_type": "execute_result"
1040     }
1041    ],
1042    "source": [
1043     "astar_search('czar', 'stay')"
1044    ]
1045   },
1046   {
1047    "cell_type": "code",
1048    "execution_count": 49,
1049    "metadata": {
1050     "collapsed": false
1051    },
1052    "outputs": [],
1053    "source": [
1054     "# %time bfs_search('czar', 'stay')"
1055    ]
1056   },
1057   {
1058    "cell_type": "code",
1059    "execution_count": 50,
1060    "metadata": {
1061     "collapsed": false
1062    },
1063    "outputs": [],
1064    "source": [
1065     "# %time bfs_search('coax', 'stay')"
1066    ]
1067   },
1068   {
1069    "cell_type": "code",
1070    "execution_count": null,
1071    "metadata": {
1072     "collapsed": true
1073    },
1074    "outputs": [],
1075    "source": []
1076   }
1077  ],
1078  "metadata": {
1079   "kernelspec": {
1080    "display_name": "Python 3",
1081    "language": "python",
1082    "name": "python3"
1083   },
1084   "language_info": {
1085    "codemirror_mode": {
1086     "name": "ipython",
1087     "version": 3
1088    },
1089    "file_extension": ".py",
1090    "mimetype": "text/x-python",
1091    "name": "python",
1092    "nbconvert_exporter": "python",
1093    "pygments_lexer": "ipython3",
1094    "version": "3.5.2"
1095   }
1096  },
1097  "nbformat": 4,
1098  "nbformat_minor": 2
1099 }