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": 2,
  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": 3,
  43    "metadata": {},
  44    "outputs": [
  45     {
  46      "data": {
  47       "text/plain": [
  48        "2336"
  49       ]
  50      },
  51      "execution_count": 3,
  52      "metadata": {},
  53      "output_type": "execute_result"
  54     }
  55    ],
  56    "source": [
  57     "words = [w.strip() for w in open('08-rooms.txt').readlines()]\n",
  58     "len(words)"
  59    ]
  60   },
  61   {
  62    "cell_type": "code",
  63    "execution_count": 4,
  64    "metadata": {
  65     "collapsed": true
  66    },
  67    "outputs": [],
  68    "source": [
  69     "def adjacents(word):\n",
  70     "    return [word[0:i] + l + word[i+1:]\n",
  71     "           for i in range(len(word))\n",
  72     "           for l in string.ascii_lowercase\n",
  73     "           if l != word[i]]"
  74    ]
  75   },
  76   {
  77    "cell_type": "code",
  78    "execution_count": 5,
  79    "metadata": {
  80     "collapsed": true
  81    },
  82    "outputs": [],
  83    "source": [
  84     "neighbours = {w: [n for n in adjacents(w) if n in words]\n",
  85     "             for w in words}"
  86    ]
  87   },
  88   {
  89    "cell_type": "code",
  90    "execution_count": 6,
  91    "metadata": {
  92     "collapsed": true
  93    },
  94    "outputs": [],
  95    "source": [
  96     "def distance(w1, w2):\n",
  97     "    return sum(1 for i in range(len(w1))\n",
  98     "               if w1[i] != w2[i])"
  99    ]
 100   },
 101   {
 102    "cell_type": "code",
 103    "execution_count": 7,
 104    "metadata": {
 105     "collapsed": true
 106    },
 107    "outputs": [],
 108    "source": [
 109     "# def extend(chain):\n",
 110     "#     return [chain + [s] for s in neighbours[chain[-1]]\n",
 111     "#            if s not in chain]"
 112    ]
 113   },
 114   {
 115    "cell_type": "code",
 116    "execution_count": 8,
 117    "metadata": {
 118     "collapsed": true
 119    },
 120    "outputs": [],
 121    "source": [
 122     "def extend(chain, closed=None):\n",
 123     "    if closed:\n",
 124     "        nbrs = set(neighbours[chain[-1]]) - closed\n",
 125     "    else:\n",
 126     "        nbrs = neighbours[chain[-1]]\n",
 127     "    return [chain + [s] for s in nbrs\n",
 128     "           if s not in chain]"
 129    ]
 130   },
 131   {
 132    "cell_type": "code",
 133    "execution_count": 9,
 134    "metadata": {
 135     "collapsed": true
 136    },
 137    "outputs": [],
 138    "source": [
 139     "def extend_raw(chain):\n",
 140     "    nbrs = [w for w in adjacents(chain[-1]) if w in words]\n",
 141     "    return [chain + [s] for s in nbrs\n",
 142     "           if s not in chain]"
 143    ]
 144   },
 145   {
 146    "cell_type": "code",
 147    "execution_count": 10,
 148    "metadata": {
 149     "collapsed": true
 150    },
 151    "outputs": [],
 152    "source": [
 153     "def bfs_search(start, goal, debug=False):\n",
 154     "    agenda = [[start]]\n",
 155     "    finished = False\n",
 156     "    while not finished and agenda:\n",
 157     "        current = agenda[0]\n",
 158     "        if debug:\n",
 159     "            print(current)\n",
 160     "        if current[-1] == goal:\n",
 161     "            finished = True\n",
 162     "        else:\n",
 163     "            successors = extend(current)\n",
 164     "            agenda = agenda[1:] + successors\n",
 165     "    if finished:\n",
 166     "        return current\n",
 167     "    else:\n",
 168     "        return None        "
 169    ]
 170   },
 171   {
 172    "cell_type": "code",
 173    "execution_count": 11,
 174    "metadata": {
 175     "collapsed": true
 176    },
 177    "outputs": [],
 178    "source": [
 179     "def bfs_search_closed(start, goal, debug=False):\n",
 180     "    agenda = [[start]]\n",
 181     "    closed = set()\n",
 182     "    finished = False\n",
 183     "    while not finished and agenda:\n",
 184     "        current = agenda[0]\n",
 185     "        if debug:\n",
 186     "            print(current)\n",
 187     "        if current[-1] == goal:\n",
 188     "            finished = True\n",
 189     "        else:\n",
 190     "            closed.add(current[-1])\n",
 191     "            successors = extend(current, closed)\n",
 192     "            agenda = agenda[1:] + successors\n",
 193     "    if finished:\n",
 194     "        return current\n",
 195     "    else:\n",
 196     "        return None   "
 197    ]
 198   },
 199   {
 200    "cell_type": "code",
 201    "execution_count": 12,
 202    "metadata": {
 203     "collapsed": true
 204    },
 205    "outputs": [],
 206    "source": [
 207     "def dfs_search(start, goal, debug=False):\n",
 208     "    agenda = [[start]]\n",
 209     "    finished = False\n",
 210     "    while not finished and agenda:\n",
 211     "        current = agenda[0]\n",
 212     "        if debug:\n",
 213     "            print(current)\n",
 214     "        if current[-1] == goal:\n",
 215     "            finished = True\n",
 216     "        else:\n",
 217     "            successors = extend(current)\n",
 218     "            agenda = successors + agenda[1:]\n",
 219     "    if finished:\n",
 220     "        return current\n",
 221     "    else:\n",
 222     "        return None        "
 223    ]
 224   },
 225   {
 226    "cell_type": "code",
 227    "execution_count": 13,
 228    "metadata": {
 229     "collapsed": true
 230    },
 231    "outputs": [],
 232    "source": [
 233     "def astar_search(start, goal, debug=False):\n",
 234     "    agenda = [(distance(start, goal), [start])]\n",
 235     "    heapq.heapify(agenda)\n",
 236     "    finished = False\n",
 237     "    while not finished and agenda:\n",
 238     "        _, current = heapq.heappop(agenda)\n",
 239     "        if debug:\n",
 240     "            print(current)\n",
 241     "        if current[-1] == goal:\n",
 242     "            finished = True\n",
 243     "        else:\n",
 244     "            successors = extend(current)\n",
 245     "            for s in successors:\n",
 246     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
 247     "    if finished:\n",
 248     "        return current\n",
 249     "    else:\n",
 250     "        return None        "
 251    ]
 252   },
 253   {
 254    "cell_type": "code",
 255    "execution_count": 14,
 256    "metadata": {
 257     "collapsed": true
 258    },
 259    "outputs": [],
 260    "source": [
 261     "# Uses direct lookup of successors, rather than using cached neighbours in the dict\n",
 262     "def astar_search_raw(start, goal, debug=False):\n",
 263     "    agenda = [(distance(start, goal), [start])]\n",
 264     "    heapq.heapify(agenda)\n",
 265     "    finished = False\n",
 266     "    while not finished and agenda:\n",
 267     "        _, current = heapq.heappop(agenda)\n",
 268     "        if debug:\n",
 269     "            print(current)\n",
 270     "        if current[-1] == goal:\n",
 271     "            finished = True\n",
 272     "        else:\n",
 273     "            successors = extend_raw(current) # Difference here\n",
 274     "            for s in successors:\n",
 275     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
 276     "    if finished:\n",
 277     "        return current\n",
 278     "    else:\n",
 279     "        return None        "
 280    ]
 281   },
 282   {
 283    "cell_type": "code",
 284    "execution_count": 15,
 285    "metadata": {
 286     "collapsed": true
 287    },
 288    "outputs": [],
 289    "source": [
 290     "def astar_search_closed(start, goal, debug=False):\n",
 291     "    agenda = [(distance(start, goal), [start])]\n",
 292     "    heapq.heapify(agenda)\n",
 293     "    closed = set()\n",
 294     "    finished = False\n",
 295     "    while not finished and agenda:\n",
 296     "        _, current = heapq.heappop(agenda)\n",
 297     "        if debug:\n",
 298     "            print(current)\n",
 299     "        if current[-1] == goal:\n",
 300     "            finished = True\n",
 301     "        else:\n",
 302     "            closed.add(current[-1])\n",
 303     "            successors = extend(current, closed)\n",
 304     "            for s in successors:\n",
 305     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
 306     "    if finished:\n",
 307     "        return current\n",
 308     "    else:\n",
 309     "        return None   "
 310    ]
 311   },
 312   {
 313    "cell_type": "code",
 314    "execution_count": 16,
 315    "metadata": {},
 316    "outputs": [
 317     {
 318      "data": {
 319       "text/plain": [
 320        "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
 321       ]
 322      },
 323      "execution_count": 16,
 324      "metadata": {},
 325      "output_type": "execute_result"
 326     }
 327    ],
 328    "source": [
 329     "astar_search('vice', 'wars')"
 330    ]
 331   },
 332   {
 333    "cell_type": "code",
 334    "execution_count": 17,
 335    "metadata": {},
 336    "outputs": [
 337     {
 338      "data": {
 339       "text/plain": [
 340        "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
 341       ]
 342      },
 343      "execution_count": 17,
 344      "metadata": {},
 345      "output_type": "execute_result"
 346     }
 347    ],
 348    "source": [
 349     "astar_search_raw('vice', 'wars')"
 350    ]
 351   },
 352   {
 353    "cell_type": "code",
 354    "execution_count": 18,
 355    "metadata": {},
 356    "outputs": [
 357     {
 358      "data": {
 359       "text/plain": [
 360        "['boon', 'boot', 'bolt', 'belt', 'bell', 'sell']"
 361       ]
 362      },
 363      "execution_count": 18,
 364      "metadata": {},
 365      "output_type": "execute_result"
 366     }
 367    ],
 368    "source": [
 369     "astar_search_raw('boon', 'sell')"
 370    ]
 371   },
 372   {
 373    "cell_type": "code",
 374    "execution_count": 19,
 375    "metadata": {},
 376    "outputs": [
 377     {
 378      "data": {
 379       "text/plain": [
 380        "6"
 381       ]
 382      },
 383      "execution_count": 19,
 384      "metadata": {},
 385      "output_type": "execute_result"
 386     }
 387    ],
 388    "source": [
 389     "len(astar_search('vice', 'wars'))"
 390    ]
 391   },
 392   {
 393    "cell_type": "code",
 394    "execution_count": 20,
 395    "metadata": {
 396     "collapsed": true
 397    },
 398    "outputs": [],
 399    "source": [
 400     "# len(bfs_search('vice', 'wars'))"
 401    ]
 402   },
 403   {
 404    "cell_type": "code",
 405    "execution_count": 21,
 406    "metadata": {},
 407    "outputs": [
 408     {
 409      "data": {
 410       "text/plain": [
 411        "6"
 412       ]
 413      },
 414      "execution_count": 21,
 415      "metadata": {},
 416      "output_type": "execute_result"
 417     }
 418    ],
 419    "source": [
 420     "len(bfs_search_closed('vice', 'wars'))"
 421    ]
 422   },
 423   {
 424    "cell_type": "code",
 425    "execution_count": 22,
 426    "metadata": {},
 427    "outputs": [
 428     {
 429      "data": {
 430       "text/plain": [
 431        "793"
 432       ]
 433      },
 434      "execution_count": 22,
 435      "metadata": {},
 436      "output_type": "execute_result"
 437     }
 438    ],
 439    "source": [
 440     "len(dfs_search('vice', 'wars'))"
 441    ]
 442   },
 443   {
 444    "cell_type": "code",
 445    "execution_count": 23,
 446    "metadata": {},
 447    "outputs": [
 448     {
 449      "name": "stdout",
 450      "output_type": "stream",
 451      "text": [
 452       "10000 loops, best of 3: 157 µs per loop\n"
 453      ]
 454     }
 455    ],
 456    "source": [
 457     "%%timeit\n",
 458     "astar_search('vice', 'wars')"
 459    ]
 460   },
 461   {
 462    "cell_type": "code",
 463    "execution_count": 24,
 464    "metadata": {},
 465    "outputs": [
 466     {
 467      "name": "stdout",
 468      "output_type": "stream",
 469      "text": [
 470       "100 loops, best of 3: 15.5 ms per loop\n"
 471      ]
 472     }
 473    ],
 474    "source": [
 475     "%%timeit\n",
 476     "astar_search_raw('vice', 'wars')"
 477    ]
 478   },
 479   {
 480    "cell_type": "code",
 481    "execution_count": 25,
 482    "metadata": {},
 483    "outputs": [
 484     {
 485      "name": "stdout",
 486      "output_type": "stream",
 487      "text": [
 488       "10000 loops, best of 3: 166 µs per loop\n"
 489      ]
 490     }
 491    ],
 492    "source": [
 493     "%%timeit\n",
 494     "astar_search_closed('vice', 'wars')"
 495    ]
 496   },
 497   {
 498    "cell_type": "code",
 499    "execution_count": 26,
 500    "metadata": {
 501     "collapsed": true
 502    },
 503    "outputs": [],
 504    "source": [
 505     "# %%timeit\n",
 506     "# bfs_search('vice', 'wars')"
 507    ]
 508   },
 509   {
 510    "cell_type": "code",
 511    "execution_count": 27,
 512    "metadata": {},
 513    "outputs": [
 514     {
 515      "name": "stdout",
 516      "output_type": "stream",
 517      "text": [
 518       "1 loop, best of 3: 554 ms per loop\n"
 519      ]
 520     }
 521    ],
 522    "source": [
 523     "%%timeit\n",
 524     "bfs_search_closed('vice', 'wars')"
 525    ]
 526   },
 527   {
 528    "cell_type": "code",
 529    "execution_count": 28,
 530    "metadata": {},
 531    "outputs": [
 532     {
 533      "name": "stdout",
 534      "output_type": "stream",
 535      "text": [
 536       "10 loops, best of 3: 90.6 ms per loop\n"
 537      ]
 538     }
 539    ],
 540    "source": [
 541     "%%timeit\n",
 542     "dfs_search('vice', 'wars')"
 543    ]
 544   },
 545   {
 546    "cell_type": "markdown",
 547    "metadata": {},
 548    "source": [
 549     "## Part 2\n",
 550     "\n",
 551     "The example shows that `jags` is reachable in four steps from `rash`. There are 11 words one step away from `rash`: \n",
 552     "`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, and `wash`. \n",
 553     "\n",
 554     "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",
 555     "\n",
 556     "There are 180 words reachable in up to three steps from `rash`.\n",
 557     "\n",
 558     "How many words are reachable in up to ten steps from `vice`?"
 559    ]
 560   },
 561   {
 562    "cell_type": "code",
 563    "execution_count": 29,
 564    "metadata": {
 565     "collapsed": true
 566    },
 567    "outputs": [],
 568    "source": [
 569     "def reachable_in(word, n, trim_extras=False):\n",
 570     "    reachable = set()\n",
 571     "    boundary = set([word])\n",
 572     "    for i in range(n):\n",
 573     "        extras = set()\n",
 574     "        for w in boundary:\n",
 575     "            extras.update(neighbours[w])\n",
 576     "        if trim_extras:\n",
 577     "            extras.difference_update(reachable)\n",
 578     "        reachable.update(boundary)\n",
 579     "        boundary = extras.copy()\n",
 580     "    return reachable.union(extras).difference(set([word]))"
 581    ]
 582   },
 583   {
 584    "cell_type": "code",
 585    "execution_count": 30,
 586    "metadata": {},
 587    "outputs": [
 588     {
 589      "data": {
 590       "text/plain": [
 591        "['bash',\n",
 592        " 'cash',\n",
 593        " 'dash',\n",
 594        " 'gash',\n",
 595        " 'hash',\n",
 596        " 'lash',\n",
 597        " 'mash',\n",
 598        " 'sash',\n",
 599        " 'wash',\n",
 600        " 'rush',\n",
 601        " 'rasp']"
 602       ]
 603      },
 604      "execution_count": 30,
 605      "metadata": {},
 606      "output_type": "execute_result"
 607     }
 608    ],
 609    "source": [
 610     "neighbours['rash']"
 611    ]
 612   },
 613   {
 614    "cell_type": "code",
 615    "execution_count": 31,
 616    "metadata": {
 617     "scrolled": true
 618    },
 619    "outputs": [
 620     {
 621      "data": {
 622       "text/plain": [
 623        "(11,\n",
 624        " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
 625       ]
 626      },
 627      "execution_count": 31,
 628      "metadata": {},
 629      "output_type": "execute_result"
 630     }
 631    ],
 632    "source": [
 633     "len(reachable_in('rash', 1)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 1)))"
 634    ]
 635   },
 636   {
 637    "cell_type": "code",
 638    "execution_count": 32,
 639    "metadata": {
 640     "scrolled": true
 641    },
 642    "outputs": [
 643     {
 644      "data": {
 645       "text/plain": [
 646        "(11,\n",
 647        " '<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>')"
 648       ]
 649      },
 650      "execution_count": 32,
 651      "metadata": {},
 652      "output_type": "execute_result"
 653     }
 654    ],
 655    "source": [
 656     "len(reachable_in('rash', 1)), ', '.join(sorted('<code>{}</code>'.format(r) for r in reachable_in('rash', 1)))"
 657    ]
 658   },
 659   {
 660    "cell_type": "code",
 661    "execution_count": 33,
 662    "metadata": {
 663     "scrolled": true
 664    },
 665    "outputs": [
 666     {
 667      "data": {
 668       "text/plain": [
 669        "(47,\n",
 670        " '`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`')"
 671       ]
 672      },
 673      "execution_count": 33,
 674      "metadata": {},
 675      "output_type": "execute_result"
 676     }
 677    ],
 678    "source": [
 679     "len(reachable_in('rash', 2)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 2)))"
 680    ]
 681   },
 682   {
 683    "cell_type": "code",
 684    "execution_count": 34,
 685    "metadata": {
 686     "scrolled": true
 687    },
 688    "outputs": [
 689     {
 690      "data": {
 691       "text/plain": [
 692        "(47,\n",
 693        " '<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>')"
 694       ]
 695      },
 696      "execution_count": 34,
 697      "metadata": {},
 698      "output_type": "execute_result"
 699     }
 700    ],
 701    "source": [
 702     "len(reachable_in('rash', 2)), ', '.join(sorted('<code>{}</code>'.format(r) for r in reachable_in('rash', 2)))"
 703    ]
 704   },
 705   {
 706    "cell_type": "code",
 707    "execution_count": 35,
 708    "metadata": {
 709     "scrolled": true
 710    },
 711    "outputs": [
 712     {
 713      "data": {
 714       "text/plain": [
 715        "180"
 716       ]
 717      },
 718      "execution_count": 35,
 719      "metadata": {},
 720      "output_type": "execute_result"
 721     }
 722    ],
 723    "source": [
 724     "len(reachable_in('rash', 3))"
 725    ]
 726   },
 727   {
 728    "cell_type": "code",
 729    "execution_count": 36,
 730    "metadata": {
 731     "scrolled": true
 732    },
 733    "outputs": [
 734     {
 735      "data": {
 736       "text/plain": [
 737        "2195"
 738       ]
 739      },
 740      "execution_count": 36,
 741      "metadata": {},
 742      "output_type": "execute_result"
 743     }
 744    ],
 745    "source": [
 746     "len(reachable_in('rash', 10))"
 747    ]
 748   },
 749   {
 750    "cell_type": "code",
 751    "execution_count": 37,
 752    "metadata": {
 753     "scrolled": true
 754    },
 755    "outputs": [
 756     {
 757      "data": {
 758       "text/plain": [
 759        "2192"
 760       ]
 761      },
 762      "execution_count": 37,
 763      "metadata": {},
 764      "output_type": "execute_result"
 765     }
 766    ],
 767    "source": [
 768     "len(reachable_in('vice', 10))"
 769    ]
 770   },
 771   {
 772    "cell_type": "code",
 773    "execution_count": 38,
 774    "metadata": {
 775     "scrolled": true
 776    },
 777    "outputs": [
 778     {
 779      "name": "stdout",
 780      "output_type": "stream",
 781      "text": [
 782       "100 loops, best of 3: 5.81 ms per loop\n"
 783      ]
 784     }
 785    ],
 786    "source": [
 787     "%%timeit\n",
 788     "len(reachable_in('rash', 10))"
 789    ]
 790   },
 791   {
 792    "cell_type": "code",
 793    "execution_count": 39,
 794    "metadata": {
 795     "scrolled": true
 796    },
 797    "outputs": [
 798     {
 799      "name": "stdout",
 800      "output_type": "stream",
 801      "text": [
 802       "100 loops, best of 3: 2.71 ms per loop\n"
 803      ]
 804     }
 805    ],
 806    "source": [
 807     "%%timeit\n",
 808     "len(reachable_in('rash', 10, trim_extras=True))"
 809    ]
 810   },
 811   {
 812    "cell_type": "code",
 813    "execution_count": 40,
 814    "metadata": {},
 815    "outputs": [
 816     {
 817      "data": {
 818       "text/plain": [
 819        "2188"
 820       ]
 821      },
 822      "execution_count": 40,
 823      "metadata": {},
 824      "output_type": "execute_result"
 825     }
 826    ],
 827    "source": [
 828     "len(reachable_in('stay', 10))"
 829    ]
 830   },
 831   {
 832    "cell_type": "code",
 833    "execution_count": 41,
 834    "metadata": {},
 835    "outputs": [
 836     {
 837      "data": {
 838       "text/plain": [
 839        "2193"
 840       ]
 841      },
 842      "execution_count": 41,
 843      "metadata": {},
 844      "output_type": "execute_result"
 845     }
 846    ],
 847    "source": [
 848     "len(reachable_in('coax', 10))"
 849    ]
 850   },
 851   {
 852    "cell_type": "code",
 853    "execution_count": 42,
 854    "metadata": {},
 855    "outputs": [
 856     {
 857      "data": {
 858       "text/plain": [
 859        "280"
 860       ]
 861      },
 862      "execution_count": 42,
 863      "metadata": {},
 864      "output_type": "execute_result"
 865     }
 866    ],
 867    "source": [
 868     "stay5 = reachable_in('stay', 4)\n",
 869     "len(stay5)"
 870    ]
 871   },
 872   {
 873    "cell_type": "code",
 874    "execution_count": 43,
 875    "metadata": {},
 876    "outputs": [
 877     {
 878      "data": {
 879       "text/plain": [
 880        "296"
 881       ]
 882      },
 883      "execution_count": 43,
 884      "metadata": {},
 885      "output_type": "execute_result"
 886     }
 887    ],
 888    "source": [
 889     "extras = set()\n",
 890     "for w in stay5:\n",
 891     "    extras.update(neighbours[w])\n",
 892     "extras.difference_update(stay5)\n",
 893     "len(extras)"
 894    ]
 895   },
 896   {
 897    "cell_type": "code",
 898    "execution_count": 44,
 899    "metadata": {},
 900    "outputs": [
 901     {
 902      "data": {
 903       "text/plain": [
 904        "'know step yeps test pout book beck poor boos veep teed gent saws dyer hemp soon deem legs bets twit whim belt rock well bled whet prop spec weep peed loan week clef feed lock yens vent doer less teem toot yews blur clue pert pegs brew flea trig vets sued felt perk bobs brat tens beef leap bloc shoo moan boob jeez suet sits rood drag goat stay chip fled fist than loot pets suck peek pled heel hair sill prep char knot lens meek trap jeep beet crew draw tell nets peep meet sows glue bees bent pelt whit need foot bran chop gram chew teen veil lent gees fret soft leis pent gets weed keen reek news prim drab wets sics deed bows pier akin pock geed grey bogs goad skis peck prod loam keep pens hoot best reed yous sewn been tram pest whom bout unit deep boot dual lees omit peel sues berm dock yock shes lets mock grow jell whip lean thin sots geek stem floe tees sort fees gout mead dram said twin prom bras bier heft foul root fell melt bops coup coot atop brad chin moot shoe sacs chit hell door lead feet boon bolt leaf bell bias eery goop reel text boom herd rent leek rend club self send sick term airs frog yell next czar plus mean brow foam crow troy nest heed dell load glib peps cent chow pees bend jock held tent soil poop moor sped emit boss fest crop mews knit tout crag knob grab thaw vial sack help jets very boys flue whir newt wiry beep room pews crab baas cock coop hock blue flee moat skid quit dial brag cell aloe grad hews went leak toad wees mewl coat dent'"
 905       ]
 906      },
 907      "execution_count": 44,
 908      "metadata": {},
 909      "output_type": "execute_result"
 910     }
 911    ],
 912    "source": [
 913     "' '.join(extras)"
 914    ]
 915   },
 916   {
 917    "cell_type": "code",
 918    "execution_count": 45,
 919    "metadata": {},
 920    "outputs": [
 921     {
 922      "data": {
 923       "text/plain": [
 924        "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
 925       ]
 926      },
 927      "execution_count": 45,
 928      "metadata": {},
 929      "output_type": "execute_result"
 930     }
 931    ],
 932    "source": [
 933     "astar_search('coax', 'stay')"
 934    ]
 935   },
 936   {
 937    "cell_type": "code",
 938    "execution_count": 46,
 939    "metadata": {},
 940    "outputs": [
 941     {
 942      "name": "stdout",
 943      "output_type": "stream",
 944      "text": [
 945       "CPU times: user 620 ms, sys: 4 ms, total: 624 ms\n",
 946       "Wall time: 624 ms\n"
 947      ]
 948     },
 949     {
 950      "data": {
 951       "text/plain": [
 952        "['coax', 'coat', 'chat', 'shat', 'spat', 'spay', 'stay']"
 953       ]
 954      },
 955      "execution_count": 46,
 956      "metadata": {},
 957      "output_type": "execute_result"
 958     }
 959    ],
 960    "source": [
 961     "%time bfs_search_closed('coax', 'stay')"
 962    ]
 963   },
 964   {
 965    "cell_type": "code",
 966    "execution_count": 47,
 967    "metadata": {
 968     "collapsed": true
 969    },
 970    "outputs": [],
 971    "source": [
 972     "# %time bfs_search('coax', 'stay')"
 973    ]
 974   },
 975   {
 976    "cell_type": "code",
 977    "execution_count": 48,
 978    "metadata": {},
 979    "outputs": [
 980     {
 981      "data": {
 982       "text/plain": [
 983        "['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
 984       ]
 985      },
 986      "execution_count": 48,
 987      "metadata": {},
 988      "output_type": "execute_result"
 989     }
 990    ],
 991    "source": [
 992     "astar_search('czar', 'stay')"
 993    ]
 994   },
 995   {
 996    "cell_type": "code",
 997    "execution_count": 49,
 998    "metadata": {
 999     "collapsed": true
1000    },
1001    "outputs": [],
1002    "source": [
1003     "# %time bfs_search('czar', 'stay')"
1004    ]
1005   },
1006   {
1007    "cell_type": "code",
1008    "execution_count": 50,
1009    "metadata": {
1010     "collapsed": true
1011    },
1012    "outputs": [],
1013    "source": [
1014     "# %time bfs_search('coax', 'stay')"
1015    ]
1016   },
1017   {
1018    "cell_type": "code",
1019    "execution_count": 79,
1020    "metadata": {},
1021    "outputs": [
1022     {
1023      "data": {
1024       "text/plain": [
1025        "185"
1026       ]
1027      },
1028      "execution_count": 79,
1029      "metadata": {},
1030      "output_type": "execute_result"
1031     }
1032    ],
1033    "source": [
1034     "rushn = reachable_in('rush', 3)\n",
1035     "rushn.add('rush')\n",
1036     "len(rushn)"
1037    ]
1038   },
1039   {
1040    "cell_type": "code",
1041    "execution_count": 80,
1042    "metadata": {
1043     "scrolled": true
1044    },
1045    "outputs": [],
1046    "source": [
1047     "links = set()\n",
1048     "for w in rushn:\n",
1049     "    for n in neighbours[w]:\n",
1050     "        if n in rushn:\n",
1051     "            links.add(frozenset((n, w)))\n",
1052     "\n",
1053     "with open('rush3.dot', 'w') as f:\n",
1054     "    f.write('graph g {\\n')\n",
1055     "    for l in links:\n",
1056     "        lt = tuple(l)\n",
1057     "        f.write('\"{}\" -- \"{}\";\\n'.format(lt[0], lt[1]))\n",
1058     "    f.write('}\\n')"
1059    ]
1060   },
1061   {
1062    "cell_type": "code",
1063    "execution_count": null,
1064    "metadata": {
1065     "collapsed": true
1066    },
1067    "outputs": [],
1068    "source": []
1069   }
1070  ],
1071  "metadata": {
1072   "kernelspec": {
1073    "display_name": "Python 3",
1074    "language": "python",
1075    "name": "python3"
1076   },
1077   "language_info": {
1078    "codemirror_mode": {
1079     "name": "ipython",
1080     "version": 3
1081    },
1082    "file_extension": ".py",
1083    "mimetype": "text/x-python",
1084    "name": "python",
1085    "nbconvert_exporter": "python",
1086    "pygments_lexer": "ipython3",
1087    "version": "3.5.2+"
1088   }
1089  },
1090  "nbformat": 4,
1091  "nbformat_minor": 2
1092 }