08-word-chains/visa-woes-solution.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Visa woes\n",
   8     "\n",
   9     "It seems there's been a problem with your visa, and the authorities have only just noticed, even though you're coming to the end of your holiday. There's no option but to navigate the bowels of the Foreign Ministry, to find the right series of offices to visit.\n",
  10     "\n",
  11     "For some reason known only to themselves, all the offices have a four-letter code that just happens to be an English word. (All the ministry office codes are given in the file [08-rooms.txt](08-rooms.txt).) An office will give you the authorisation to move to a different office if the codes differ by just one letter. For instance, the authorisation from office `rash` will allow you to move to the office `bash` and you can move from `able` to `axle`.\n",
  12     "\n",
  13     "You can move from office `rash` to `jags` by visiting five offices in total:\n",
  14     "\n",
  15     "```\n",
  16     "rash\n",
  17     "Bash\n",
  18     "basS\n",
  19     "baGs\n",
  20     "Jags\n",
  21     "```\n",
  22     "\n",
  23     "where the capital letters indicate the changed letters in each step. There are other ways of getting from `rash` to `jags`, but there is no shorter route.\n",
  24     "\n",
  25     "# Part 1\n",
  26     "\n",
  27     "Including the offices at both ends, what is the smallest number of offices do you have to visit to get from `coax` to `stay`?"
  28    ]
  29   },
  30   {
  31    "cell_type": "markdown",
  32    "metadata": {},
  33    "source": [
  34     "You may have found a route to your goal, but what if `stay` wasn't the right office? How many offices could you get in a few steps from a starting point?\n",
  35     "\n",
  36     "For example, there are 11 offices you can reach in one step from `rash`:\n",
  37     "\n",
  38     "`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`\n",
  39     "\n",
  40     "There are 47 distinct offices you could reach in up to two steps:\n",
  41     "\n",
  42     "`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`\n",
  43     "\n",
  44     "The there are 180 distinct offices reachable in up to three steps from `rash`.\n",
  45     "\n",
  46     "The ministry office codes are still given in the file [08-rooms.txt](08-rooms.txt).\n",
  47     "\n",
  48     "# Part 2\n",
  49     "\n",
  50     "How many different offices could you visit in no more than 10 steps from `coax`?"
  51    ]
  52   },
  53   {
  54    "cell_type": "markdown",
  55    "metadata": {},
  56    "source": [
  57     "# Worked example solution: part 1\n",
  58     "This is the first of two tasks intended to exercise skills developed in M269. In this case, this is about search. I won't go over the general idea of search itself here, as there are loads of tutorials online about it. Instead, I'll talk about the specific way I've implmeneted it in this solution.\n",
  59     "\n",
  60     "(See below for the <a href=\"#part2\">discussion of part 2</a>.)\n",
  61     "\n",
  62     "## Search\n",
  63     "The offices/words can be thought of as a graph of nodes and edges. Each word is a node, and there's an edge between two words if those words differ by one letter. The diagrams below show the connections between words that are one step and two steps away from 'rush'.\n",
  64     "\n",
  65     "| Words one step from 'rush' | Words two steps from 'rush' |\n",
  66     "| ------------- | ------------- |\n",
  67     "| <a href=\"rush1.dot.png\"><img src=\"rush1.dot.png\" alt=\"Words one step from 'rush'\" style=\"width: 200px;\"/></a>     | <a href=\"rush2.dot.png\"><img src=\"rush2.dot.png\" alt=\"Words two steps from 'rush'\" style=\"width: 200px;\"/></a> |\n",
  68     "\n",
  69     "The task is to find a path, a sequence of words, from the starting word to the destination. This is a classic search problem.\n",
  70     "\n",
  71     "The key data structure is the _agenda_, a set of partial routes. We take a partial route from the agenda and _extend_ it with the words/rooms reachable from the end of the partial route, giving a new set of partial routes. Those are added back into the agenda.\n",
  72     "\n",
  73     "Search finishes either when the partial route we're processing is a solution (i.e. goes form the origin to destination room) or the agenda becomes empty.\n",
  74     "\n",
  75     "For instance, say we're going from `ache` to `ashy`. The initial agenda consists of just one partial route, and that partial route contains just `ache`.\n",
  76     "\n",
  77     "```\n",
  78     "ache\n",
  79     "```\n",
  80     "\n",
  81     "We take that item off the agenda, extend it (with `acne`, `acme`, `acre`, and `achy` as neighbours of `ache`). When we add those four items to the agenda, we get \n",
  82     "\n",
  83     "```\n",
  84     "ache -> acne\n",
  85     "ache -> acme\n",
  86     "ache -> acre\n",
  87     "ache -> achy\n",
  88     "```\n",
  89     "\n",
  90     "We then proces the `ache -> acne` partial path, extending it with `acme` and `acre`, giving the agenda:\n",
  91     "\n",
  92     "```\n",
  93     "ache -> acme\n",
  94     "ache -> acre\n",
  95     "ache -> achy\n",
  96     "ache -> acne -> acme\n",
  97     "ache -> acne -> acre\n",
  98     "```\n",
  99     "\n",
 100     "(Note that while `ache` is adjacent to `acne`, we don't want to create a new partial path to `ache` as we've already visited it in this path.)\n",
 101     "\n",
 102     "We then proces the `ache -> acme` partial path, extending it with `acne` and `acre`, giving the agenda:\n",
 103     "\n",
 104     "```\n",
 105     "ache -> acre\n",
 106     "ache -> achy\n",
 107     "ache -> acne -> acme\n",
 108     "ache -> acne -> acre\n",
 109     "ache -> acme -> acne\n",
 110     "ache -> acme -> acre\n",
 111     "```\n",
 112     "\n",
 113     "We then do `ache -> acre` and `ache -> achy` to give:\n",
 114     "\n",
 115     "```\n",
 116     "ache -> acne -> acme\n",
 117     "ache -> acne -> acre\n",
 118     "ache -> acme -> acne\n",
 119     "ache -> acme -> acre\n",
 120     "ache -> acre -> acne\n",
 121     "ache -> acre -> acme\n",
 122     "ache -> achy -> ashy\n",
 123     "```\n",
 124     "\n",
 125     "`ache -> acne -> acme` has only one valid extension, so we get:\n",
 126     "\n",
 127     "```\n",
 128     "ache -> acne -> acre\n",
 129     "ache -> acme -> acne\n",
 130     "ache -> acme -> acre\n",
 131     "ache -> acre -> acne\n",
 132     "ache -> acre -> acme\n",
 133     "ache -> achy -> ashy\n",
 134     "ache -> acne -> acme -> acre\n",
 135     "```\n",
 136     "\n",
 137     "We process all the other partial paths in turn until we get to the agenda looking like:\n",
 138     "```\n",
 139     "ache -> achy -> ashy\n",
 140     "ache -> acne -> acme -> acre\n",
 141     "ache -> acne -> acre -> acme\n",
 142     "ache -> acme -> acne -> acre\n",
 143     "ache -> acme -> acre -> acne\n",
 144     "ache -> acre -> acne -> acme\n",
 145     "ache -> acre -> acme -> acne\n",
 146     "```\n",
 147     "At this point, the first partial path in the agenda is a solution, so we report success and return that path.\n",
 148     "\n",
 149     "With breadth-first search, we add the newly-discovered partial paths to the end of the agenda, meaning we go through the graph one layer at a time. If we add the new partial paths to the front of the agenda, we have depth-first search, where we explore one trail fully before backtracking and trying another.\n",
 150     "\n",
 151     "There are other clever things we can do, such as sorting the agenda by predicted distance to go, which can speed things up.\n",
 152     "\n",
 153     "## Agenda and paths\n",
 154     "As each partial path is a sequence of words in order, it makes sense to store it as a Python `list` of words. For breadth-first and depth-first searches, the agenda is a sequence of partial paths. Again, it makes sense to store this a a Python `list` of partial paths.\n",
 155     "\n",
 156     "For A* search, the agenda is sorted by the sum of path length and predicted cost to complete the path. In this case, it makes sense to represent the agenda by a priority queue, also known as a heap. I decided to use the standard Python `heapq` library, rather than the one used in M269. Partial paths are put on the heap with `heappush` and the partial path with the lowest cost is removed with `heappop`. \n",
 157     "\n",
 158     "## The graph of words\n",
 159     "How to represent the graph of words? In the input, the connections between words are implicit, so we need to write a little procedure that returns all the neighbouring words for the word passed in. \n",
 160     "\n",
 161     "There's also a choice here: to we calculate and store the explicit graph of words, or do we rediscover the neighbours every time we want to process a word? The first approach consumes space to reduce time; the second uses time to reduce space. \n",
 162     "\n",
 163     "In this case, as there are only 2300 words and 20,000 connections, it's not a lot of space. The search will be examining lots of nodes, so I took a decision to explicity cache all the word neighbour relations first, then just look them up as needed. \n",
 164     "\n",
 165     "(It turns out this wasn't a good idea in terms of raw perfromance. Generating the graph takes ~130ms, but seems to give just about no change in performance for any search algorithm. Ho hum, but an example of where a [premature optimistion](https://en.wikiquote.org/wiki/Donald_Knuth) turns out to be costly!)\n",
 166     "\n",
 167     "## Important optimisation: closed sets\n",
 168     "If you look at the diagrams and traces above, you'll see that the graph of words is very heavily connected, with several different routes from one word to another. But we often don't need to try out all these alternatives. If we're considering a partial route that ends at a particular word _w_, and we've already found another partial route to _w_ that's no longer than this one, there's no need to continue analysing this one. For instance, in the trace above, there's a route `ache -> acne -> acme`, but we've already found the route `ache -> acme`, so we can discard the `ache -> acne -> acme` alternative without worrying about missing possible solutions.\n",
 169     "\n",
 170     "If we use something like breadth-first search, we know that the first time we encounter a new word is the shortest path to that word. That means that all subsequent times we arrive that that word, we know we can discard that partial path. \n",
 171     "\n",
 172     "We maintain a `closed set` of the words we've already processed. We can use that set in two places. Either we check the partial path when we take it off the agenda, or we use the closed set to reduce the number of partial paths generated at each step. In the implementation below, I do the latter.\n",
 173     "\n",
 174     "## Another optimisation: `list` or `set` of words?\n",
 175     "The obvious way to represent the known words is as a list. But, we don't care about the order of items in the collection of words. All we do with them is check for existence of a word, and iterate through the whole collection. In these cases, the Python `set` is a much more efficient data structure than the Pyhton `list`, as it uses something like a `dict` underneath. This means membership checking is much faster while iteration takes about the same amount of time.\n",
 176     "\n",
 177     "Therefore, rather than using `list`s, we'll use `set`s where possible. In fact, as the set of words doesn't change, we can use the `frozenset` type to indicate that the set is immutable."
 178    ]
 179   },
 180   {
 181    "cell_type": "code",
 182    "execution_count": 116,
 183    "metadata": {
 184     "collapsed": true
 185    },
 186    "outputs": [],
 187    "source": [
 188     "import string\n",
 189     "import heapq"
 190    ]
 191   },
 192   {
 193    "cell_type": "code",
 194    "execution_count": 117,
 195    "metadata": {},
 196    "outputs": [
 197     {
 198      "data": {
 199       "text/plain": [
 200        "2336"
 201       ]
 202      },
 203      "execution_count": 117,
 204      "metadata": {},
 205      "output_type": "execute_result"
 206     }
 207    ],
 208    "source": [
 209     "words = frozenset(w.strip() for w in open('08-rooms.txt').readlines())\n",
 210     "len(words)"
 211    ]
 212   },
 213   {
 214    "cell_type": "code",
 215    "execution_count": 191,
 216    "metadata": {
 217     "collapsed": true
 218    },
 219    "outputs": [],
 220    "source": [
 221     "def adjacents(word):\n",
 222     "    return frozenset(word[0:i] + l + word[i+1:]\n",
 223     "           for i in range(len(word))\n",
 224     "           for l in string.ascii_lowercase\n",
 225     "           if l != word[i])"
 226    ]
 227   },
 228   {
 229    "cell_type": "code",
 230    "execution_count": 192,
 231    "metadata": {},
 232    "outputs": [
 233     {
 234      "name": "stdout",
 235      "output_type": "stream",
 236      "text": [
 237       "10 loops, best of 3: 130 ms per loop\n"
 238      ]
 239     }
 240    ],
 241    "source": [
 242     "%%timeit\n",
 243     "neighbours = {w: frozenset(n for n in adjacents(w) if n in words)\n",
 244     "             for w in words}"
 245    ]
 246   },
 247   {
 248    "cell_type": "code",
 249    "execution_count": 193,
 250    "metadata": {},
 251    "outputs": [
 252     {
 253      "data": {
 254       "text/plain": [
 255        "20092"
 256       ]
 257      },
 258      "execution_count": 193,
 259      "metadata": {},
 260      "output_type": "execute_result"
 261     }
 262    ],
 263    "source": [
 264     "sum(len(neighbours[w]) for w in neighbours)"
 265    ]
 266   },
 267   {
 268    "cell_type": "code",
 269    "execution_count": 233,
 270    "metadata": {
 271     "collapsed": true
 272    },
 273    "outputs": [],
 274    "source": [
 275     "def distance(w1, w2):\n",
 276     "    return sum(1 for i in range(len(w1))\n",
 277     "               if w1[i] != w2[i])"
 278    ]
 279   },
 280   {
 281    "cell_type": "code",
 282    "execution_count": 195,
 283    "metadata": {
 284     "collapsed": true
 285    },
 286    "outputs": [],
 287    "source": [
 288     "# def extend(chain):\n",
 289     "#     return [chain + [s] for s in neighbours[chain[-1]]\n",
 290     "#            if s not in chain]"
 291    ]
 292   },
 293   {
 294    "cell_type": "code",
 295    "execution_count": 196,
 296    "metadata": {
 297     "collapsed": true
 298    },
 299    "outputs": [],
 300    "source": [
 301     "def extend(chain, closed=None):\n",
 302     "    if closed:\n",
 303     "        nbrs = set(neighbours[chain[-1]]) - closed\n",
 304     "    else:\n",
 305     "        nbrs = neighbours[chain[-1]]\n",
 306     "    return [chain + [s] for s in nbrs\n",
 307     "           if s not in chain]"
 308    ]
 309   },
 310   {
 311    "cell_type": "code",
 312    "execution_count": 197,
 313    "metadata": {
 314     "collapsed": true
 315    },
 316    "outputs": [],
 317    "source": [
 318     "def extend_raw(chain, closed=None):\n",
 319     "    if closed:\n",
 320     "        nbrs = set(neighbours[chain[-1]]) - closed\n",
 321     "    else:\n",
 322     "        nbrs = neighbours[chain[-1]]\n",
 323     "    return [chain + [s] for s in nbrs\n",
 324     "           if s not in chain]"
 325    ]
 326   },
 327   {
 328    "cell_type": "code",
 329    "execution_count": 198,
 330    "metadata": {
 331     "collapsed": true
 332    },
 333    "outputs": [],
 334    "source": [
 335     "def bfs_search(start, goal, debug=False):\n",
 336     "    agenda = [[start]]\n",
 337     "    finished = False\n",
 338     "    while not finished and agenda:\n",
 339     "        current = agenda[0]\n",
 340     "        if debug:\n",
 341     "            print(current)\n",
 342     "        if current[-1] == goal:\n",
 343     "            finished = True\n",
 344     "        else:\n",
 345     "            successors = extend(current)\n",
 346     "            agenda = agenda[1:] + successors\n",
 347     "    if finished:\n",
 348     "        return current\n",
 349     "    else:\n",
 350     "        return None        "
 351    ]
 352   },
 353   {
 354    "cell_type": "code",
 355    "execution_count": 172,
 356    "metadata": {
 357     "collapsed": true
 358    },
 359    "outputs": [],
 360    "source": [
 361     "def bfs_search_raw(start, goal, debug=False):\n",
 362     "    agenda = [[start]]\n",
 363     "    finished = False\n",
 364     "    while not finished and agenda:\n",
 365     "        current = agenda[0]\n",
 366     "        if debug:\n",
 367     "            print(current)\n",
 368     "        if current[-1] == goal:\n",
 369     "            finished = True\n",
 370     "        else:\n",
 371     "            successors = extend_raw(current)\n",
 372     "            agenda = agenda[1:] + successors\n",
 373     "    if finished:\n",
 374     "        return current\n",
 375     "    else:\n",
 376     "        return None        "
 377    ]
 378   },
 379   {
 380    "cell_type": "code",
 381    "execution_count": 173,
 382    "metadata": {
 383     "collapsed": true
 384    },
 385    "outputs": [],
 386    "source": [
 387     "def bfs_search_closed(start, goal, debug=False):\n",
 388     "    agenda = [[start]]\n",
 389     "    closed = set()\n",
 390     "    finished = False\n",
 391     "    while not finished and agenda:\n",
 392     "        current = agenda[0]\n",
 393     "        if debug:\n",
 394     "            print(current)\n",
 395     "        if current[-1] == goal:\n",
 396     "            finished = True\n",
 397     "        else:\n",
 398     "            closed.add(current[-1])\n",
 399     "            successors = extend(current, closed)\n",
 400     "            agenda = agenda[1:] + successors\n",
 401     "    if finished:\n",
 402     "        return current\n",
 403     "    else:\n",
 404     "        return None   "
 405    ]
 406   },
 407   {
 408    "cell_type": "code",
 409    "execution_count": 181,
 410    "metadata": {
 411     "collapsed": true
 412    },
 413    "outputs": [],
 414    "source": [
 415     "def bfs_search_closed_raw(start, goal, debug=False):\n",
 416     "    agenda = [[start]]\n",
 417     "    closed = set()\n",
 418     "    finished = False\n",
 419     "    while not finished and agenda:\n",
 420     "        current = agenda[0]\n",
 421     "        if debug:\n",
 422     "            print(current)\n",
 423     "        if current[-1] == goal:\n",
 424     "            finished = True\n",
 425     "        else:\n",
 426     "            closed.add(current[-1])\n",
 427     "            successors = extend_raw(current, closed)\n",
 428     "            agenda = agenda[1:] + successors\n",
 429     "    if finished:\n",
 430     "        return current\n",
 431     "    else:\n",
 432     "        return None   "
 433    ]
 434   },
 435   {
 436    "cell_type": "code",
 437    "execution_count": 127,
 438    "metadata": {
 439     "collapsed": true
 440    },
 441    "outputs": [],
 442    "source": [
 443     "def dfs_search(start, goal, debug=False):\n",
 444     "    agenda = [[start]]\n",
 445     "    finished = False\n",
 446     "    while not finished and agenda:\n",
 447     "        current = agenda[0]\n",
 448     "        if debug:\n",
 449     "            print(current)\n",
 450     "        if current[-1] == goal:\n",
 451     "            finished = True\n",
 452     "        else:\n",
 453     "            successors = extend(current)\n",
 454     "            agenda = successors + agenda[1:]\n",
 455     "    if finished:\n",
 456     "        return current\n",
 457     "    else:\n",
 458     "        return None        "
 459    ]
 460   },
 461   {
 462    "cell_type": "code",
 463    "execution_count": 128,
 464    "metadata": {
 465     "collapsed": true
 466    },
 467    "outputs": [],
 468    "source": [
 469     "def astar_search(start, goal, debug=False):\n",
 470     "    agenda = [(distance(start, goal), [start])]\n",
 471     "    heapq.heapify(agenda)\n",
 472     "    finished = False\n",
 473     "    while not finished and agenda:\n",
 474     "        _, current = heapq.heappop(agenda)\n",
 475     "        if debug:\n",
 476     "            print(current)\n",
 477     "        if current[-1] == goal:\n",
 478     "            finished = True\n",
 479     "        else:\n",
 480     "            successors = extend(current)\n",
 481     "            for s in successors:\n",
 482     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
 483     "    if finished:\n",
 484     "        return current\n",
 485     "    else:\n",
 486     "        return None        "
 487    ]
 488   },
 489   {
 490    "cell_type": "code",
 491    "execution_count": 129,
 492    "metadata": {
 493     "collapsed": true
 494    },
 495    "outputs": [],
 496    "source": [
 497     "# Uses direct lookup of successors, rather than using cached neighbours in the dict\n",
 498     "def astar_search_raw(start, goal, debug=False):\n",
 499     "    agenda = [(distance(start, goal), [start])]\n",
 500     "    heapq.heapify(agenda)\n",
 501     "    finished = False\n",
 502     "    while not finished and agenda:\n",
 503     "        _, current = heapq.heappop(agenda)\n",
 504     "        if debug:\n",
 505     "            print(current)\n",
 506     "        if current[-1] == goal:\n",
 507     "            finished = True\n",
 508     "        else:\n",
 509     "            successors = extend_raw(current) # Difference here\n",
 510     "            for s in successors:\n",
 511     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
 512     "    if finished:\n",
 513     "        return current\n",
 514     "    else:\n",
 515     "        return None        "
 516    ]
 517   },
 518   {
 519    "cell_type": "code",
 520    "execution_count": 130,
 521    "metadata": {
 522     "collapsed": true
 523    },
 524    "outputs": [],
 525    "source": [
 526     "def astar_search_closed(start, goal, debug=False):\n",
 527     "    agenda = [(distance(start, goal), [start])]\n",
 528     "    heapq.heapify(agenda)\n",
 529     "    closed = set()\n",
 530     "    finished = False\n",
 531     "    while not finished and agenda:\n",
 532     "        _, current = heapq.heappop(agenda)\n",
 533     "        if debug:\n",
 534     "            print(current)\n",
 535     "        if current[-1] == goal:\n",
 536     "            finished = True\n",
 537     "        else:\n",
 538     "            closed.add(current[-1])\n",
 539     "            successors = extend(current, closed)\n",
 540     "            for s in successors:\n",
 541     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
 542     "    if finished:\n",
 543     "        return current\n",
 544     "    else:\n",
 545     "        return None   "
 546    ]
 547   },
 548   {
 549    "cell_type": "code",
 550    "execution_count": 234,
 551    "metadata": {},
 552    "outputs": [
 553     {
 554      "data": {
 555       "text/plain": [
 556        "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
 557       ]
 558      },
 559      "execution_count": 234,
 560      "metadata": {},
 561      "output_type": "execute_result"
 562     }
 563    ],
 564    "source": [
 565     "astar_search('coax', 'stay')"
 566    ]
 567   },
 568   {
 569    "cell_type": "code",
 570    "execution_count": 235,
 571    "metadata": {},
 572    "outputs": [
 573     {
 574      "data": {
 575       "text/plain": [
 576        "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
 577       ]
 578      },
 579      "execution_count": 235,
 580      "metadata": {},
 581      "output_type": "execute_result"
 582     }
 583    ],
 584    "source": [
 585     "astar_search_raw('vice', 'wars')"
 586    ]
 587   },
 588   {
 589    "cell_type": "code",
 590    "execution_count": 201,
 591    "metadata": {},
 592    "outputs": [
 593     {
 594      "data": {
 595       "text/plain": [
 596        "['boon', 'boot', 'bolt', 'belt', 'bell', 'sell']"
 597       ]
 598      },
 599      "execution_count": 201,
 600      "metadata": {},
 601      "output_type": "execute_result"
 602     }
 603    ],
 604    "source": [
 605     "astar_search_raw('boon', 'sell')"
 606    ]
 607   },
 608   {
 609    "cell_type": "code",
 610    "execution_count": 236,
 611    "metadata": {},
 612    "outputs": [
 613     {
 614      "data": {
 615       "text/plain": [
 616        "7"
 617       ]
 618      },
 619      "execution_count": 236,
 620      "metadata": {},
 621      "output_type": "execute_result"
 622     }
 623    ],
 624    "source": [
 625     "len(astar_search('coax', 'stay'))"
 626    ]
 627   },
 628   {
 629    "cell_type": "code",
 630    "execution_count": 203,
 631    "metadata": {
 632     "collapsed": true
 633    },
 634    "outputs": [],
 635    "source": [
 636     "# len(bfs_search('vice', 'wars'))"
 637    ]
 638   },
 639   {
 640    "cell_type": "code",
 641    "execution_count": 237,
 642    "metadata": {},
 643    "outputs": [
 644     {
 645      "data": {
 646       "text/plain": [
 647        "7"
 648       ]
 649      },
 650      "execution_count": 237,
 651      "metadata": {},
 652      "output_type": "execute_result"
 653     }
 654    ],
 655    "source": [
 656     "len(bfs_search_closed('coax', 'stay'))"
 657    ]
 658   },
 659   {
 660    "cell_type": "code",
 661    "execution_count": 238,
 662    "metadata": {},
 663    "outputs": [
 664     {
 665      "data": {
 666       "text/plain": [
 667        "458"
 668       ]
 669      },
 670      "execution_count": 238,
 671      "metadata": {},
 672      "output_type": "execute_result"
 673     }
 674    ],
 675    "source": [
 676     "len(dfs_search('coax', 'stay'))"
 677    ]
 678   },
 679   {
 680    "cell_type": "code",
 681    "execution_count": 239,
 682    "metadata": {},
 683    "outputs": [
 684     {
 685      "name": "stdout",
 686      "output_type": "stream",
 687      "text": [
 688       "1000 loops, best of 3: 605 µs per loop\n"
 689      ]
 690     }
 691    ],
 692    "source": [
 693     "%%timeit\n",
 694     "astar_search('coax', 'stay')"
 695    ]
 696   },
 697   {
 698    "cell_type": "code",
 699    "execution_count": 240,
 700    "metadata": {},
 701    "outputs": [
 702     {
 703      "name": "stdout",
 704      "output_type": "stream",
 705      "text": [
 706       "1000 loops, best of 3: 607 µs per loop\n"
 707      ]
 708     }
 709    ],
 710    "source": [
 711     "%%timeit\n",
 712     "astar_search_raw('coax', 'stay')"
 713    ]
 714   },
 715   {
 716    "cell_type": "code",
 717    "execution_count": 241,
 718    "metadata": {},
 719    "outputs": [
 720     {
 721      "name": "stdout",
 722      "output_type": "stream",
 723      "text": [
 724       "1000 loops, best of 3: 552 µs per loop\n"
 725      ]
 726     }
 727    ],
 728    "source": [
 729     "%%timeit\n",
 730     "astar_search_closed('coax', 'stay')"
 731    ]
 732   },
 733   {
 734    "cell_type": "code",
 735    "execution_count": 243,
 736    "metadata": {},
 737    "outputs": [
 738     {
 739      "name": "stdout",
 740      "output_type": "stream",
 741      "text": [
 742       "1 loop, best of 3: 4min 25s per loop\n"
 743      ]
 744     }
 745    ],
 746    "source": [
 747     "%%timeit\n",
 748     "bfs_search('coax', 'stay')"
 749    ]
 750   },
 751   {
 752    "cell_type": "code",
 753    "execution_count": 244,
 754    "metadata": {},
 755    "outputs": [
 756     {
 757      "name": "stdout",
 758      "output_type": "stream",
 759      "text": [
 760       "1 loop, best of 3: 4min 25s per loop\n"
 761      ]
 762     }
 763    ],
 764    "source": [
 765     "%%timeit\n",
 766     "bfs_search_raw('coax', 'stay')"
 767    ]
 768   },
 769   {
 770    "cell_type": "code",
 771    "execution_count": 245,
 772    "metadata": {},
 773    "outputs": [
 774     {
 775      "name": "stdout",
 776      "output_type": "stream",
 777      "text": [
 778       "1 loop, best of 3: 810 ms per loop\n"
 779      ]
 780     }
 781    ],
 782    "source": [
 783     "%%timeit\n",
 784     "bfs_search_closed('coax', 'stay')"
 785    ]
 786   },
 787   {
 788    "cell_type": "code",
 789    "execution_count": 246,
 790    "metadata": {},
 791    "outputs": [
 792     {
 793      "name": "stdout",
 794      "output_type": "stream",
 795      "text": [
 796       "1 loop, best of 3: 814 ms per loop\n"
 797      ]
 798     }
 799    ],
 800    "source": [
 801     "%%timeit\n",
 802     "bfs_search_closed_raw('coax', 'stay')"
 803    ]
 804   },
 805   {
 806    "cell_type": "code",
 807    "execution_count": 247,
 808    "metadata": {},
 809    "outputs": [
 810     {
 811      "name": "stdout",
 812      "output_type": "stream",
 813      "text": [
 814       "10 loops, best of 3: 26.8 ms per loop\n"
 815      ]
 816     }
 817    ],
 818    "source": [
 819     "%%timeit\n",
 820     "dfs_search('coax', 'stay')"
 821    ]
 822   },
 823   {
 824    "cell_type": "code",
 825    "execution_count": 248,
 826    "metadata": {},
 827    "outputs": [
 828     {
 829      "name": "stdout",
 830      "output_type": "stream",
 831      "text": [
 832       "1 loop, best of 3: 4.39 s per loop\n"
 833      ]
 834     }
 835    ],
 836    "source": [
 837     "%%timeit\n",
 838     "astar_search('amen', 'doff')"
 839    ]
 840   },
 841   {
 842    "cell_type": "code",
 843    "execution_count": 249,
 844    "metadata": {},
 845    "outputs": [
 846     {
 847      "name": "stdout",
 848      "output_type": "stream",
 849      "text": [
 850       "1 loop, best of 3: 4.4 s per loop\n"
 851      ]
 852     }
 853    ],
 854    "source": [
 855     "%%timeit\n",
 856     "astar_search_raw('amen', 'doff')"
 857    ]
 858   },
 859   {
 860    "cell_type": "code",
 861    "execution_count": 250,
 862    "metadata": {},
 863    "outputs": [
 864     {
 865      "name": "stdout",
 866      "output_type": "stream",
 867      "text": [
 868       "10 loops, best of 3: 87.4 ms per loop\n"
 869      ]
 870     }
 871    ],
 872    "source": [
 873     "%%timeit\n",
 874     "astar_search_closed('amen', 'doff')"
 875    ]
 876   },
 877   {
 878    "cell_type": "code",
 879    "execution_count": null,
 880    "metadata": {
 881     "collapsed": true
 882    },
 883    "outputs": [],
 884    "source": []
 885   },
 886   {
 887    "cell_type": "markdown",
 888    "metadata": {},
 889    "source": [
 890     "## Part 2\n",
 891     "\n",
 892     "The example shows that `jags` is reachable in four steps from `rash`. There are 11 words one step away from `rash`: \n",
 893     "`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, and `wash`. \n",
 894     "\n",
 895     "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",
 896     "\n",
 897     "There are 180 words reachable in up to three steps from `rash`.\n",
 898     "\n",
 899     "How many words are reachable in up to ten steps from `coax`?"
 900    ]
 901   },
 902   {
 903    "cell_type": "markdown",
 904    "metadata": {},
 905    "source": [
 906     "\n",
 907     "# <a name=\"part2\"></a>Worked example solution: part 2\n",
 908     "After all the mucking around with search algorithms, this is actually much easier. It's all to do with building up sets.\n",
 909     "\n",
 910     "The basic idea is to maintain a `set` of reachable words which is extended in passes. In each pass, we find all the neighbours of all the words in the reachable word set, and add those neighbours to the set of reachable words. We just do the number of passes specified in in the task.\n",
 911     "\n",
 912     "In the code below, `reachable` is set of reachable words and `extras` is the set of new words found. As an optimisation, I use the set `boundary` to hold the words added in the previous pass, as the new words to add to `reachable` must be neighbours of a word in the `boundary`: all words that are neighbours of the 'interior' of the set of reachable words have already been added. so there's no need to process them again.\n",
 913     "\n",
 914     "The `trim_extras` flag is for another optimisation: eacy time we add some more words to `extras`, remove words which are already in `reachable`. That will make the later update of `reachable` faster.\n",
 915     "\n",
 916     "This approach is quick, as its based on sets and set membership checking, which is a fast process.\n",
 917     "\n",
 918     "This also suggests another way of solving part 1. Start at depth 1, and find all the words reachable at that depth. If the target word is in the reachable set, report success. If not, increment the depth and find the reachable words again.\n",
 919     "\n",
 920     "This approach does give the right answer of the minimal distance from source to goal words, but it doesn't give any information about the route to take to go from one word to another; the route is something returned by the search algorithms above."
 921    ]
 922   },
 923   {
 924    "cell_type": "code",
 925    "execution_count": 217,
 926    "metadata": {
 927     "collapsed": true
 928    },
 929    "outputs": [],
 930    "source": [
 931     "def reachable_in(word, n, trim_extras=False):\n",
 932     "    reachable = set()\n",
 933     "    boundary = set([word])\n",
 934     "    for i in range(n):\n",
 935     "        extras = set()\n",
 936     "        for w in boundary:\n",
 937     "            extras.update(neighbours[w])\n",
 938     "        if trim_extras:\n",
 939     "            extras.difference_update(reachable)\n",
 940     "        reachable.update(boundary)\n",
 941     "        boundary = extras.copy()\n",
 942     "    return reachable.union(extras).difference(set([word]))"
 943    ]
 944   },
 945   {
 946    "cell_type": "code",
 947    "execution_count": 218,
 948    "metadata": {},
 949    "outputs": [
 950     {
 951      "data": {
 952       "text/plain": [
 953        "['bash',\n",
 954        " 'cash',\n",
 955        " 'dash',\n",
 956        " 'gash',\n",
 957        " 'hash',\n",
 958        " 'lash',\n",
 959        " 'mash',\n",
 960        " 'sash',\n",
 961        " 'wash',\n",
 962        " 'rush',\n",
 963        " 'rasp']"
 964       ]
 965      },
 966      "execution_count": 218,
 967      "metadata": {},
 968      "output_type": "execute_result"
 969     }
 970    ],
 971    "source": [
 972     "neighbours['rash']"
 973    ]
 974   },
 975   {
 976    "cell_type": "code",
 977    "execution_count": 219,
 978    "metadata": {
 979     "scrolled": true
 980    },
 981    "outputs": [
 982     {
 983      "data": {
 984       "text/plain": [
 985        "(11,\n",
 986        " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
 987       ]
 988      },
 989      "execution_count": 219,
 990      "metadata": {},
 991      "output_type": "execute_result"
 992     }
 993    ],
 994    "source": [
 995     "len(reachable_in('rash', 1)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 1)))"
 996    ]
 997   },
 998   {
 999    "cell_type": "code",
1000    "execution_count": 220,
1001    "metadata": {
1002     "scrolled": true
1003    },
1004    "outputs": [
1005     {
1006      "data": {
1007       "text/plain": [
1008        "(11,\n",
1009        " '<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>')"
1010       ]
1011      },
1012      "execution_count": 220,
1013      "metadata": {},
1014      "output_type": "execute_result"
1015     }
1016    ],
1017    "source": [
1018     "len(reachable_in('rash', 1)), ', '.join(sorted('<code>{}</code>'.format(r) for r in reachable_in('rash', 1)))"
1019    ]
1020   },
1021   {
1022    "cell_type": "code",
1023    "execution_count": 221,
1024    "metadata": {
1025     "scrolled": true
1026    },
1027    "outputs": [
1028     {
1029      "data": {
1030       "text/plain": [
1031        "(47,\n",
1032        " '`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`')"
1033       ]
1034      },
1035      "execution_count": 221,
1036      "metadata": {},
1037      "output_type": "execute_result"
1038     }
1039    ],
1040    "source": [
1041     "len(reachable_in('rash', 2)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 2)))"
1042    ]
1043   },
1044   {
1045    "cell_type": "code",
1046    "execution_count": 222,
1047    "metadata": {
1048     "scrolled": true
1049    },
1050    "outputs": [
1051     {
1052      "data": {
1053       "text/plain": [
1054        "(47,\n",
1055        " '<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>')"
1056       ]
1057      },
1058      "execution_count": 222,
1059      "metadata": {},
1060      "output_type": "execute_result"
1061     }
1062    ],
1063    "source": [
1064     "len(reachable_in('rash', 2)), ', '.join(sorted('<code>{}</code>'.format(r) for r in reachable_in('rash', 2)))"
1065    ]
1066   },
1067   {
1068    "cell_type": "code",
1069    "execution_count": 223,
1070    "metadata": {
1071     "scrolled": true
1072    },
1073    "outputs": [
1074     {
1075      "data": {
1076       "text/plain": [
1077        "180"
1078       ]
1079      },
1080      "execution_count": 223,
1081      "metadata": {},
1082      "output_type": "execute_result"
1083     }
1084    ],
1085    "source": [
1086     "len(reachable_in('rash', 3))"
1087    ]
1088   },
1089   {
1090    "cell_type": "code",
1091    "execution_count": 224,
1092    "metadata": {
1093     "scrolled": true
1094    },
1095    "outputs": [
1096     {
1097      "data": {
1098       "text/plain": [
1099        "2195"
1100       ]
1101      },
1102      "execution_count": 224,
1103      "metadata": {},
1104      "output_type": "execute_result"
1105     }
1106    ],
1107    "source": [
1108     "len(reachable_in('rash', 10))"
1109    ]
1110   },
1111   {
1112    "cell_type": "code",
1113    "execution_count": 225,
1114    "metadata": {
1115     "scrolled": true
1116    },
1117    "outputs": [
1118     {
1119      "data": {
1120       "text/plain": [
1121        "2192"
1122       ]
1123      },
1124      "execution_count": 225,
1125      "metadata": {},
1126      "output_type": "execute_result"
1127     }
1128    ],
1129    "source": [
1130     "len(reachable_in('vice', 10))"
1131    ]
1132   },
1133   {
1134    "cell_type": "code",
1135    "execution_count": 226,
1136    "metadata": {
1137     "scrolled": true
1138    },
1139    "outputs": [
1140     {
1141      "name": "stdout",
1142      "output_type": "stream",
1143      "text": [
1144       "100 loops, best of 3: 6.2 ms per loop\n"
1145      ]
1146     }
1147    ],
1148    "source": [
1149     "%%timeit\n",
1150     "len(reachable_in('rash', 10))"
1151    ]
1152   },
1153   {
1154    "cell_type": "code",
1155    "execution_count": 227,
1156    "metadata": {
1157     "scrolled": true
1158    },
1159    "outputs": [
1160     {
1161      "name": "stdout",
1162      "output_type": "stream",
1163      "text": [
1164       "100 loops, best of 3: 2.92 ms per loop\n"
1165      ]
1166     }
1167    ],
1168    "source": [
1169     "%%timeit\n",
1170     "len(reachable_in('rash', 10, trim_extras=True))"
1171    ]
1172   },
1173   {
1174    "cell_type": "code",
1175    "execution_count": 155,
1176    "metadata": {},
1177    "outputs": [
1178     {
1179      "data": {
1180       "text/plain": [
1181        "2188"
1182       ]
1183      },
1184      "execution_count": 155,
1185      "metadata": {},
1186      "output_type": "execute_result"
1187     }
1188    ],
1189    "source": [
1190     "len(reachable_in('stay', 10))"
1191    ]
1192   },
1193   {
1194    "cell_type": "code",
1195    "execution_count": 156,
1196    "metadata": {},
1197    "outputs": [
1198     {
1199      "data": {
1200       "text/plain": [
1201        "2193"
1202       ]
1203      },
1204      "execution_count": 156,
1205      "metadata": {},
1206      "output_type": "execute_result"
1207     }
1208    ],
1209    "source": [
1210     "len(reachable_in('coax', 10))"
1211    ]
1212   },
1213   {
1214    "cell_type": "code",
1215    "execution_count": 232,
1216    "metadata": {},
1217    "outputs": [
1218     {
1219      "data": {
1220       "text/plain": [
1221        "(True, 1)"
1222       ]
1223      },
1224      "execution_count": 232,
1225      "metadata": {},
1226      "output_type": "execute_result"
1227     }
1228    ],
1229    "source": [
1230     "dist = 0\n",
1231     "found = False\n",
1232     "\n",
1233     "while not found and distance < 50:\n",
1234     "    dist += 1\n",
1235     "    others = reachable_in('coax', distance)\n",
1236     "    if 'stay' in others:\n",
1237     "        found = True\n",
1238     "\n",
1239     "found, dist"
1240    ]
1241   },
1242   {
1243    "cell_type": "code",
1244    "execution_count": 229,
1245    "metadata": {},
1246    "outputs": [
1247     {
1248      "name": "stdout",
1249      "output_type": "stream",
1250      "text": [
1251       "1000 loops, best of 3: 1.26 ms per loop\n"
1252      ]
1253     }
1254    ],
1255    "source": [
1256     "%%timeit\n",
1257     "distance = 0\n",
1258     "found = False\n",
1259     "\n",
1260     "while not found and distance < 50:\n",
1261     "    distance += 1\n",
1262     "    others = reachable_in('coax', distance)\n",
1263     "    if 'stay' in others:\n",
1264     "        found = True\n",
1265     "\n",
1266     "found, distance"
1267    ]
1268   },
1269   {
1270    "cell_type": "code",
1271    "execution_count": 157,
1272    "metadata": {},
1273    "outputs": [
1274     {
1275      "data": {
1276       "text/plain": [
1277        "280"
1278       ]
1279      },
1280      "execution_count": 157,
1281      "metadata": {},
1282      "output_type": "execute_result"
1283     }
1284    ],
1285    "source": [
1286     "stay5 = reachable_in('stay', 4)\n",
1287     "len(stay5)"
1288    ]
1289   },
1290   {
1291    "cell_type": "code",
1292    "execution_count": 158,
1293    "metadata": {},
1294    "outputs": [
1295     {
1296      "data": {
1297       "text/plain": [
1298        "296"
1299       ]
1300      },
1301      "execution_count": 158,
1302      "metadata": {},
1303      "output_type": "execute_result"
1304     }
1305    ],
1306    "source": [
1307     "extras = set()\n",
1308     "for w in stay5:\n",
1309     "    extras.update(neighbours[w])\n",
1310     "extras.difference_update(stay5)\n",
1311     "len(extras)"
1312    ]
1313   },
1314   {
1315    "cell_type": "code",
1316    "execution_count": 159,
1317    "metadata": {},
1318    "outputs": [
1319     {
1320      "data": {
1321       "text/plain": [
1322        "'brow chit bees hoot weep cock sots dock boob book boys brag bled eery sows cent crow mead aloe coup wiry less goat well vent deed rood moor belt atop bows draw prep chip sewn whom plus bets sued wets mean news czar newt fees chow reek flue troy pled geek boot akin lock bout leek fell feed shoe club heed bolt root peel thin yock vets crew load wees clue brad been meet pert boos beet legs mews self hock moot tell toad lead shoo jell teed sill skis veil glue went step test crop text peck bran teen crab pier bogs boss leis grow lent quit foam bras prod knot trap cell dram very goad felt chop sack omit poop pelt drag gram peps yens jeep brat prim jets goop tees deep dual bobs beef sits baas dyer lets leaf gees feet chew rend sues gent whet chin whip berm whim yell trig blue peek prop leak lean bent yeps bier drab bell foot heel boon fret moan send tens jock brew crag thaw sick beck gets bend pest loan geed herd skid toot grab pees hair poor rock best bloc pens coat bias fest heft mock lees loot gout sped sics tout frog nest flee meek stay weed doer stem peep hews grad peed knit keep pegs next twin blur coop week saws perk lens suet pews foul char vial soil term flea leap pent coot sort nets keen loam beep soft boom twit jeez glib teem than prom yews need veep shes bops dent moat hemp held reed whir whit deem know clef reel soon pock room tent floe pout help fist knob dell melt yous sacs unit door spec said hell mewl emit tram suck grey pets rent fled airs dial'"
1323       ]
1324      },
1325      "execution_count": 159,
1326      "metadata": {},
1327      "output_type": "execute_result"
1328     }
1329    ],
1330    "source": [
1331     "' '.join(extras)"
1332    ]
1333   },
1334   {
1335    "cell_type": "code",
1336    "execution_count": 160,
1337    "metadata": {},
1338    "outputs": [
1339     {
1340      "data": {
1341       "text/plain": [
1342        "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
1343       ]
1344      },
1345      "execution_count": 160,
1346      "metadata": {},
1347      "output_type": "execute_result"
1348     }
1349    ],
1350    "source": [
1351     "astar_search('coax', 'stay')"
1352    ]
1353   },
1354   {
1355    "cell_type": "code",
1356    "execution_count": 161,
1357    "metadata": {},
1358    "outputs": [
1359     {
1360      "name": "stdout",
1361      "output_type": "stream",
1362      "text": [
1363       "CPU times: user 848 ms, sys: 0 ns, total: 848 ms\n",
1364       "Wall time: 849 ms\n"
1365      ]
1366     },
1367     {
1368      "data": {
1369       "text/plain": [
1370        "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
1371       ]
1372      },
1373      "execution_count": 161,
1374      "metadata": {},
1375      "output_type": "execute_result"
1376     }
1377    ],
1378    "source": [
1379     "%time bfs_search_closed('coax', 'stay')"
1380    ]
1381   },
1382   {
1383    "cell_type": "code",
1384    "execution_count": 162,
1385    "metadata": {
1386     "collapsed": true
1387    },
1388    "outputs": [],
1389    "source": [
1390     "# %time bfs_search('coax', 'stay')"
1391    ]
1392   },
1393   {
1394    "cell_type": "code",
1395    "execution_count": 163,
1396    "metadata": {},
1397    "outputs": [
1398     {
1399      "data": {
1400       "text/plain": [
1401        "['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
1402       ]
1403      },
1404      "execution_count": 163,
1405      "metadata": {},
1406      "output_type": "execute_result"
1407     }
1408    ],
1409    "source": [
1410     "astar_search('czar', 'stay')"
1411    ]
1412   },
1413   {
1414    "cell_type": "code",
1415    "execution_count": 164,
1416    "metadata": {
1417     "collapsed": true
1418    },
1419    "outputs": [],
1420    "source": [
1421     "# %time bfs_search('czar', 'stay')"
1422    ]
1423   },
1424   {
1425    "cell_type": "code",
1426    "execution_count": 165,
1427    "metadata": {
1428     "collapsed": true
1429    },
1430    "outputs": [],
1431    "source": [
1432     "# %time bfs_search('coax', 'stay')"
1433    ]
1434   },
1435   {
1436    "cell_type": "code",
1437    "execution_count": 166,
1438    "metadata": {},
1439    "outputs": [
1440     {
1441      "data": {
1442       "text/plain": [
1443        "185"
1444       ]
1445      },
1446      "execution_count": 166,
1447      "metadata": {},
1448      "output_type": "execute_result"
1449     }
1450    ],
1451    "source": [
1452     "rushn = reachable_in('rush', 3)\n",
1453     "rushn.add('rush')\n",
1454     "len(rushn)"
1455    ]
1456   },
1457   {
1458    "cell_type": "code",
1459    "execution_count": 167,
1460    "metadata": {
1461     "collapsed": true,
1462     "scrolled": true
1463    },
1464    "outputs": [],
1465    "source": [
1466     "links = set()\n",
1467     "for w in rushn:\n",
1468     "    for n in neighbours[w]:\n",
1469     "        if n in rushn:\n",
1470     "            links.add(frozenset((n, w)))\n",
1471     "\n",
1472     "with open('rush3.dot', 'w') as f:\n",
1473     "    f.write('graph g {\\n')\n",
1474     "    for l in links:\n",
1475     "        lt = tuple(l)\n",
1476     "        f.write('\"{}\" -- \"{}\";\\n'.format(lt[0], lt[1]))\n",
1477     "    f.write('}\\n')"
1478    ]
1479   },
1480   {
1481    "cell_type": "code",
1482    "execution_count": null,
1483    "metadata": {
1484     "collapsed": true
1485    },
1486    "outputs": [],
1487    "source": []
1488   }
1489  ],
1490  "metadata": {
1491   "kernelspec": {
1492    "display_name": "Python 3",
1493    "language": "python",
1494    "name": "python3"
1495   },
1496   "language_info": {
1497    "codemirror_mode": {
1498     "name": "ipython",
1499     "version": 3
1500    },
1501    "file_extension": ".py",
1502    "mimetype": "text/x-python",
1503    "name": "python",
1504    "nbconvert_exporter": "python",
1505    "pygments_lexer": "ipython3",
1506    "version": "3.5.3"
1507   }
1508  },
1509  "nbformat": 4,
1510  "nbformat_minor": 2
1511 }