08-word-chains/explore-word-chain-4.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 1,
   6    "metadata": {
   7     "collapsed": true
   8    },
   9    "outputs": [],
  10    "source": [
  11     "import string\n",
  12     "import heapq\n",
  13     "import collections\n",
  14     "import random"
  15    ]
  16   },
  17   {
  18    "cell_type": "code",
  19    "execution_count": 3,
  20    "metadata": {},
  21    "outputs": [
  22     {
  23      "data": {
  24       "text/plain": [
  25        "2336"
  26       ]
  27      },
  28      "execution_count": 3,
  29      "metadata": {},
  30      "output_type": "execute_result"
  31     }
  32    ],
  33    "source": [
  34     "words = [w.strip() for w in open('08-rooms.txt').readlines()]\n",
  35     "len(words)"
  36    ]
  37   },
  38   {
  39    "cell_type": "code",
  40    "execution_count": 4,
  41    "metadata": {},
  42    "outputs": [
  43     {
  44      "data": {
  45       "text/plain": [
  46        "['abbe',\n",
  47        " 'abed',\n",
  48        " 'abet',\n",
  49        " 'able',\n",
  50        " 'ably',\n",
  51        " 'abut',\n",
  52        " 'aced',\n",
  53        " 'aces',\n",
  54        " 'ache',\n",
  55        " 'achy']"
  56       ]
  57      },
  58      "execution_count": 4,
  59      "metadata": {},
  60      "output_type": "execute_result"
  61     }
  62    ],
  63    "source": [
  64     "words[:10]"
  65    ]
  66   },
  67   {
  68    "cell_type": "code",
  69    "execution_count": 5,
  70    "metadata": {
  71     "collapsed": true
  72    },
  73    "outputs": [],
  74    "source": [
  75     "def adjacents_explicit(word):\n",
  76     "    neighbours = []\n",
  77     "    for i in range(len(word)):\n",
  78     "        for l in string.ascii_lowercase:\n",
  79     "            if l != word[i]:\n",
  80     "                neighbours.append(word[0:i] + l + word[i+1:])\n",
  81     "    return neighbours"
  82    ]
  83   },
  84   {
  85    "cell_type": "code",
  86    "execution_count": 6,
  87    "metadata": {
  88     "collapsed": true
  89    },
  90    "outputs": [],
  91    "source": [
  92     "def adjacents(word):\n",
  93     "    return [word[0:i] + l + word[i+1:]\n",
  94     "           for i in range(len(word))\n",
  95     "           for l in string.ascii_lowercase\n",
  96     "           if l != word[i]]"
  97    ]
  98   },
  99   {
 100    "cell_type": "code",
 101    "execution_count": 7,
 102    "metadata": {
 103     "collapsed": true
 104    },
 105    "outputs": [],
 106    "source": [
 107     "neighbours = {w: [n for n in adjacents(w) if n in words]\n",
 108     "             for w in words}"
 109    ]
 110   },
 111   {
 112    "cell_type": "code",
 113    "execution_count": 8,
 114    "metadata": {},
 115    "outputs": [
 116     {
 117      "data": {
 118       "text/plain": [
 119        "['able']"
 120       ]
 121      },
 122      "execution_count": 8,
 123      "metadata": {},
 124      "output_type": "execute_result"
 125     }
 126    ],
 127    "source": [
 128     "neighbours['abbe']"
 129    ]
 130   },
 131   {
 132    "cell_type": "code",
 133    "execution_count": 9,
 134    "metadata": {},
 135    "outputs": [
 136     {
 137      "data": {
 138       "text/plain": [
 139        "['axle', 'abbe', 'ably']"
 140       ]
 141      },
 142      "execution_count": 9,
 143      "metadata": {},
 144      "output_type": "execute_result"
 145     }
 146    ],
 147    "source": [
 148     "neighbours['able']"
 149    ]
 150   },
 151   {
 152    "cell_type": "code",
 153    "execution_count": 10,
 154    "metadata": {
 155     "collapsed": true
 156    },
 157    "outputs": [],
 158    "source": [
 159     "def distance(w1, w2):\n",
 160     "    return sum(1 for i in range(len(w1))\n",
 161     "               if w1[i] != w2[i])"
 162    ]
 163   },
 164   {
 165    "cell_type": "code",
 166    "execution_count": 11,
 167    "metadata": {},
 168    "outputs": [
 169     {
 170      "data": {
 171       "text/plain": [
 172        "0"
 173       ]
 174      },
 175      "execution_count": 11,
 176      "metadata": {},
 177      "output_type": "execute_result"
 178     }
 179    ],
 180    "source": [
 181     "distance('abbe', 'abbe')"
 182    ]
 183   },
 184   {
 185    "cell_type": "code",
 186    "execution_count": 12,
 187    "metadata": {
 188     "collapsed": true
 189    },
 190    "outputs": [],
 191    "source": [
 192     "def extend(chain, closed=None):\n",
 193     "    if closed:\n",
 194     "        nbrs = set(neighbours[chain[-1]]) - closed\n",
 195     "    else:\n",
 196     "        nbrs = neighbours[chain[-1]]\n",
 197     "    return [chain + [s] for s in nbrs\n",
 198     "           if s not in chain]"
 199    ]
 200   },
 201   {
 202    "cell_type": "code",
 203    "execution_count": 13,
 204    "metadata": {},
 205    "outputs": [
 206     {
 207      "data": {
 208       "text/plain": [
 209        "[['abbe', 'able']]"
 210       ]
 211      },
 212      "execution_count": 13,
 213      "metadata": {},
 214      "output_type": "execute_result"
 215     }
 216    ],
 217    "source": [
 218     "extend(['abbe'])"
 219    ]
 220   },
 221   {
 222    "cell_type": "code",
 223    "execution_count": 14,
 224    "metadata": {},
 225    "outputs": [
 226     {
 227      "data": {
 228       "text/plain": [
 229        "[['abbe', 'able', 'axle'], ['abbe', 'able', 'ably']]"
 230       ]
 231      },
 232      "execution_count": 14,
 233      "metadata": {},
 234      "output_type": "execute_result"
 235     }
 236    ],
 237    "source": [
 238     "extend(['abbe', 'able'])"
 239    ]
 240   },
 241   {
 242    "cell_type": "code",
 243    "execution_count": 15,
 244    "metadata": {},
 245    "outputs": [
 246     {
 247      "data": {
 248       "text/plain": [
 249        "[['abbe', 'able', 'ably', 'ally']]"
 250       ]
 251      },
 252      "execution_count": 15,
 253      "metadata": {},
 254      "output_type": "execute_result"
 255     }
 256    ],
 257    "source": [
 258     "extend(['abbe', 'able', 'ably'])"
 259    ]
 260   },
 261   {
 262    "cell_type": "code",
 263    "execution_count": 16,
 264    "metadata": {
 265     "collapsed": true
 266    },
 267    "outputs": [],
 268    "source": [
 269     "def bfs_search(start, goal, debug=False):\n",
 270     "    agenda = [[start]]\n",
 271     "    finished = False\n",
 272     "    while not finished and agenda:\n",
 273     "        current = agenda[0]\n",
 274     "        if debug:\n",
 275     "            print(current)\n",
 276     "        if current[-1] == goal:\n",
 277     "            finished = True\n",
 278     "        else:\n",
 279     "            successors = extend(current)\n",
 280     "            agenda = agenda[1:] + successors\n",
 281     "    if agenda:\n",
 282     "        return current\n",
 283     "    else:\n",
 284     "        return None        "
 285    ]
 286   },
 287   {
 288    "cell_type": "code",
 289    "execution_count": 17,
 290    "metadata": {
 291     "collapsed": true
 292    },
 293    "outputs": [],
 294    "source": [
 295     "def bfs_search_closed(start, goal, debug=False):\n",
 296     "    agenda = [[start]]\n",
 297     "    closed = set()\n",
 298     "    finished = False\n",
 299     "    while not finished and agenda:\n",
 300     "        current = agenda[0]\n",
 301     "        if debug:\n",
 302     "            print(current)\n",
 303     "        if current[-1] == goal:\n",
 304     "            finished = True\n",
 305     "        else:\n",
 306     "            closed.add(current[-1])\n",
 307     "            successors = extend(current, closed)\n",
 308     "            agenda = agenda[1:] + successors\n",
 309     "    if agenda:\n",
 310     "        return current\n",
 311     "    else:\n",
 312     "        return None        "
 313    ]
 314   },
 315   {
 316    "cell_type": "code",
 317    "execution_count": 18,
 318    "metadata": {},
 319    "outputs": [
 320     {
 321      "name": "stdout",
 322      "output_type": "stream",
 323      "text": [
 324       "['abbe']\n",
 325       "['abbe', 'able']\n",
 326       "['abbe', 'able', 'axle']\n",
 327       "['abbe', 'able', 'ably']\n",
 328       "['abbe', 'able', 'ably', 'ally']\n"
 329      ]
 330     },
 331     {
 332      "data": {
 333       "text/plain": [
 334        "['abbe', 'able', 'ably', 'ally']"
 335       ]
 336      },
 337      "execution_count": 18,
 338      "metadata": {},
 339      "output_type": "execute_result"
 340     }
 341    ],
 342    "source": [
 343     "bfs_search('abbe', 'ally', debug=True)"
 344    ]
 345   },
 346   {
 347    "cell_type": "code",
 348    "execution_count": 19,
 349    "metadata": {
 350     "collapsed": true
 351    },
 352    "outputs": [],
 353    "source": [
 354     "def dfs_search(start, goal, debug=False):\n",
 355     "    agenda = [[start]]\n",
 356     "    finished = False\n",
 357     "    while not finished and agenda:\n",
 358     "        current = agenda[0]\n",
 359     "        if debug:\n",
 360     "            print(current)\n",
 361     "        if current[-1] == goal:\n",
 362     "            finished = True\n",
 363     "        else:\n",
 364     "            successors = extend(current)\n",
 365     "            agenda = successors + agenda[1:]\n",
 366     "    if agenda:\n",
 367     "        return current\n",
 368     "    else:\n",
 369     "        return None        "
 370    ]
 371   },
 372   {
 373    "cell_type": "code",
 374    "execution_count": 20,
 375    "metadata": {},
 376    "outputs": [
 377     {
 378      "name": "stdout",
 379      "output_type": "stream",
 380      "text": [
 381       "['abbe']\n",
 382       "['abbe', 'able']\n",
 383       "['abbe', 'able', 'axle']\n",
 384       "['abbe', 'able', 'ably']\n",
 385       "['abbe', 'able', 'ably', 'ally']\n"
 386      ]
 387     },
 388     {
 389      "data": {
 390       "text/plain": [
 391        "['abbe', 'able', 'ably', 'ally']"
 392       ]
 393      },
 394      "execution_count": 20,
 395      "metadata": {},
 396      "output_type": "execute_result"
 397     }
 398    ],
 399    "source": [
 400     "dfs_search('abbe', 'ally', debug=True)"
 401    ]
 402   },
 403   {
 404    "cell_type": "code",
 405    "execution_count": 21,
 406    "metadata": {},
 407    "outputs": [
 408     {
 409      "name": "stdout",
 410      "output_type": "stream",
 411      "text": [
 412       "['cart']\n",
 413       "['cart', 'dart']\n",
 414       "['cart', 'hart']\n",
 415       "['cart', 'mart']\n",
 416       "['cart', 'part']\n",
 417       "['cart', 'tart']\n",
 418       "['cart', 'wart']\n",
 419       "['cart', 'curt']\n",
 420       "['cart', 'cant']\n",
 421       "['cart', 'cast']\n",
 422       "['cart', 'card']\n",
 423       "['cart', 'care']\n",
 424       "['cart', 'carp']\n",
 425       "['cart', 'cars']\n",
 426       "['cart', 'dart', 'hart']\n",
 427       "['cart', 'dart', 'mart']\n",
 428       "['cart', 'dart', 'part']\n",
 429       "['cart', 'dart', 'tart']\n",
 430       "['cart', 'dart', 'wart']\n",
 431       "['cart', 'dart', 'dirt']\n",
 432       "['cart', 'dart', 'daft']\n",
 433       "['cart', 'dart', 'dare']\n",
 434       "['cart', 'dart', 'dark']\n",
 435       "['cart', 'dart', 'darn']\n",
 436       "['cart', 'hart', 'dart']\n",
 437       "['cart', 'hart', 'mart']\n",
 438       "['cart', 'hart', 'part']\n",
 439       "['cart', 'hart', 'tart']\n",
 440       "['cart', 'hart', 'wart']\n",
 441       "['cart', 'hart', 'hurt']\n",
 442       "['cart', 'hart', 'haft']\n",
 443       "['cart', 'hart', 'halt']\n",
 444       "['cart', 'hart', 'hard']\n",
 445       "['cart', 'hart', 'hare']\n",
 446       "['cart', 'hart', 'hark']\n",
 447       "['cart', 'hart', 'harm']\n",
 448       "['cart', 'hart', 'harp']\n",
 449       "['cart', 'mart', 'dart']\n",
 450       "['cart', 'mart', 'hart']\n",
 451       "['cart', 'mart', 'part']\n",
 452       "['cart', 'mart', 'tart']\n",
 453       "['cart', 'mart', 'wart']\n",
 454       "['cart', 'mart', 'malt']\n",
 455       "['cart', 'mart', 'mast']\n",
 456       "['cart', 'mart', 'matt']\n",
 457       "['cart', 'mart', 'mare']\n",
 458       "['cart', 'mart', 'mark']\n",
 459       "['cart', 'mart', 'mars']\n",
 460       "['cart', 'part', 'dart']\n",
 461       "['cart', 'part', 'hart']\n",
 462       "['cart', 'part', 'mart']\n",
 463       "['cart', 'part', 'tart']\n",
 464       "['cart', 'part', 'wart']\n",
 465       "['cart', 'part', 'pert']\n",
 466       "['cart', 'part', 'port']\n",
 467       "['cart', 'part', 'pact']\n",
 468       "['cart', 'part', 'pant']\n",
 469       "['cart', 'part', 'past']\n",
 470       "['cart', 'part', 'pare']\n",
 471       "['cart', 'part', 'park']\n",
 472       "['cart', 'part', 'pars']\n",
 473       "['cart', 'tart', 'dart']\n",
 474       "['cart', 'tart', 'hart']\n",
 475       "['cart', 'tart', 'mart']\n",
 476       "['cart', 'tart', 'part']\n",
 477       "['cart', 'tart', 'wart']\n",
 478       "['cart', 'tart', 'tort']\n",
 479       "['cart', 'tart', 'tact']\n",
 480       "['cart', 'tart', 'taut']\n",
 481       "['cart', 'tart', 'tare']\n",
 482       "['cart', 'tart', 'taro']\n",
 483       "['cart', 'tart', 'tarp']\n",
 484       "['cart', 'tart', 'tars']\n",
 485       "['cart', 'wart', 'dart']\n",
 486       "['cart', 'wart', 'hart']\n",
 487       "['cart', 'wart', 'mart']\n",
 488       "['cart', 'wart', 'part']\n",
 489       "['cart', 'wart', 'tart']\n",
 490       "['cart', 'wart', 'waft']\n",
 491       "['cart', 'wart', 'wait']\n",
 492       "['cart', 'wart', 'want']\n",
 493       "['cart', 'wart', 'watt']\n",
 494       "['cart', 'wart', 'ward']\n",
 495       "['cart', 'wart', 'ware']\n",
 496       "['cart', 'wart', 'warm']\n",
 497       "['cart', 'wart', 'warn']\n",
 498       "['cart', 'wart', 'warp']\n",
 499       "['cart', 'wart', 'wars']\n",
 500       "['cart', 'wart', 'wary']\n",
 501       "['cart', 'curt', 'hurt']\n",
 502       "['cart', 'curt', 'cult']\n",
 503       "['cart', 'curt', 'curb']\n",
 504       "['cart', 'curt', 'curd']\n",
 505       "['cart', 'curt', 'cure']\n",
 506       "['cart', 'curt', 'curl']\n",
 507       "['cart', 'curt', 'curs']\n",
 508       "['cart', 'cant', 'pant']\n",
 509       "['cart', 'cant', 'rant']\n",
 510       "['cart', 'cant', 'want']\n",
 511       "['cart', 'cant', 'cent']\n",
 512       "['cart', 'cant', 'cast']\n",
 513       "['cart', 'cant', 'cane']\n",
 514       "['cart', 'cant', 'cans']\n",
 515       "['cart', 'cast', 'bast']\n",
 516       "['cart', 'cast', 'east']\n",
 517       "['cart', 'cast', 'fast']\n",
 518       "['cart', 'cast', 'last']\n",
 519       "['cart', 'cast', 'mast']\n",
 520       "['cart', 'cast', 'past']\n",
 521       "['cart', 'cast', 'vast']\n",
 522       "['cart', 'cast', 'cost']\n",
 523       "['cart', 'cast', 'cyst']\n",
 524       "['cart', 'cast', 'cant']\n",
 525       "['cart', 'cast', 'case']\n",
 526       "['cart', 'cast', 'cash']\n",
 527       "['cart', 'cast', 'cask']\n",
 528       "['cart', 'card', 'bard']\n",
 529       "['cart', 'card', 'hard']\n",
 530       "['cart', 'card', 'lard']\n",
 531       "['cart', 'card', 'ward']\n",
 532       "['cart', 'card', 'yard']\n",
 533       "['cart', 'card', 'cord']\n",
 534       "['cart', 'card', 'curd']\n",
 535       "['cart', 'card', 'care']\n",
 536       "['cart', 'card', 'carp']\n",
 537       "['cart', 'card', 'cars']\n",
 538       "['cart', 'care', 'bare']\n",
 539       "['cart', 'care', 'dare']\n",
 540       "['cart', 'care', 'fare']\n",
 541       "['cart', 'care', 'hare']\n",
 542       "['cart', 'care', 'mare']\n",
 543       "['cart', 'care', 'pare']\n",
 544       "['cart', 'care', 'rare']\n",
 545       "['cart', 'care', 'tare']\n",
 546       "['cart', 'care', 'ware']\n",
 547       "['cart', 'care', 'core']\n",
 548       "['cart', 'care', 'cure']\n",
 549       "['cart', 'care', 'cafe']\n",
 550       "['cart', 'care', 'cage']\n",
 551       "['cart', 'care', 'cake']\n",
 552       "['cart', 'care', 'came']\n",
 553       "['cart', 'care', 'cane']\n",
 554       "['cart', 'care', 'cape']\n",
 555       "['cart', 'care', 'case']\n",
 556       "['cart', 'care', 'cave']\n",
 557       "['cart', 'care', 'card']\n",
 558       "['cart', 'care', 'carp']\n",
 559       "['cart', 'care', 'cars']\n",
 560       "['cart', 'carp', 'harp']\n",
 561       "['cart', 'carp', 'tarp']\n",
 562       "['cart', 'carp', 'warp']\n",
 563       "['cart', 'carp', 'camp']\n",
 564       "['cart', 'carp', 'card']\n",
 565       "['cart', 'carp', 'care']\n",
 566       "['cart', 'carp', 'cars']\n",
 567       "['cart', 'cars', 'bars']\n",
 568       "['cart', 'cars', 'ears']\n",
 569       "['cart', 'cars', 'jars']\n",
 570       "['cart', 'cars', 'mars']\n",
 571       "['cart', 'cars', 'oars']\n",
 572       "['cart', 'cars', 'pars']\n",
 573       "['cart', 'cars', 'tars']\n",
 574       "['cart', 'cars', 'wars']\n",
 575       "['cart', 'cars', 'curs']\n",
 576       "['cart', 'cars', 'cabs']\n",
 577       "['cart', 'cars', 'cads']\n",
 578       "['cart', 'cars', 'cams']\n",
 579       "['cart', 'cars', 'cans']\n",
 580       "['cart', 'cars', 'caps']\n",
 581       "['cart', 'cars', 'cats']\n",
 582       "['cart', 'cars', 'caws']\n",
 583       "['cart', 'cars', 'card']\n",
 584       "['cart', 'cars', 'care']\n",
 585       "['cart', 'cars', 'carp']\n",
 586       "['cart', 'dart', 'hart', 'mart']\n",
 587       "['cart', 'dart', 'hart', 'part']\n",
 588       "['cart', 'dart', 'hart', 'tart']\n",
 589       "['cart', 'dart', 'hart', 'wart']\n",
 590       "['cart', 'dart', 'hart', 'hurt']\n",
 591       "['cart', 'dart', 'hart', 'haft']\n",
 592       "['cart', 'dart', 'hart', 'halt']\n",
 593       "['cart', 'dart', 'hart', 'hard']\n",
 594       "['cart', 'dart', 'hart', 'hare']\n",
 595       "['cart', 'dart', 'hart', 'hark']\n",
 596       "['cart', 'dart', 'hart', 'harm']\n",
 597       "['cart', 'dart', 'hart', 'harp']\n",
 598       "['cart', 'dart', 'mart', 'hart']\n",
 599       "['cart', 'dart', 'mart', 'part']\n",
 600       "['cart', 'dart', 'mart', 'tart']\n",
 601       "['cart', 'dart', 'mart', 'wart']\n",
 602       "['cart', 'dart', 'mart', 'malt']\n",
 603       "['cart', 'dart', 'mart', 'mast']\n",
 604       "['cart', 'dart', 'mart', 'matt']\n",
 605       "['cart', 'dart', 'mart', 'mare']\n",
 606       "['cart', 'dart', 'mart', 'mark']\n",
 607       "['cart', 'dart', 'mart', 'mars']\n",
 608       "['cart', 'dart', 'part', 'hart']\n",
 609       "['cart', 'dart', 'part', 'mart']\n",
 610       "['cart', 'dart', 'part', 'tart']\n",
 611       "['cart', 'dart', 'part', 'wart']\n",
 612       "['cart', 'dart', 'part', 'pert']\n",
 613       "['cart', 'dart', 'part', 'port']\n",
 614       "['cart', 'dart', 'part', 'pact']\n",
 615       "['cart', 'dart', 'part', 'pant']\n",
 616       "['cart', 'dart', 'part', 'past']\n",
 617       "['cart', 'dart', 'part', 'pare']\n",
 618       "['cart', 'dart', 'part', 'park']\n",
 619       "['cart', 'dart', 'part', 'pars']\n",
 620       "['cart', 'dart', 'tart', 'hart']\n",
 621       "['cart', 'dart', 'tart', 'mart']\n",
 622       "['cart', 'dart', 'tart', 'part']\n",
 623       "['cart', 'dart', 'tart', 'wart']\n",
 624       "['cart', 'dart', 'tart', 'tort']\n",
 625       "['cart', 'dart', 'tart', 'tact']\n",
 626       "['cart', 'dart', 'tart', 'taut']\n",
 627       "['cart', 'dart', 'tart', 'tare']\n",
 628       "['cart', 'dart', 'tart', 'taro']\n",
 629       "['cart', 'dart', 'tart', 'tarp']\n",
 630       "['cart', 'dart', 'tart', 'tars']\n",
 631       "['cart', 'dart', 'wart', 'hart']\n",
 632       "['cart', 'dart', 'wart', 'mart']\n",
 633       "['cart', 'dart', 'wart', 'part']\n",
 634       "['cart', 'dart', 'wart', 'tart']\n",
 635       "['cart', 'dart', 'wart', 'waft']\n",
 636       "['cart', 'dart', 'wart', 'wait']\n",
 637       "['cart', 'dart', 'wart', 'want']\n",
 638       "['cart', 'dart', 'wart', 'watt']\n",
 639       "['cart', 'dart', 'wart', 'ward']\n",
 640       "['cart', 'dart', 'wart', 'ware']\n",
 641       "['cart', 'dart', 'wart', 'warm']\n",
 642       "['cart', 'dart', 'wart', 'warn']\n",
 643       "['cart', 'dart', 'wart', 'warp']\n",
 644       "['cart', 'dart', 'wart', 'wars']\n",
 645       "['cart', 'dart', 'wart', 'wary']\n",
 646       "['cart', 'dart', 'dirt', 'girt']\n",
 647       "['cart', 'dart', 'dirt', 'diet']\n",
 648       "['cart', 'dart', 'dirt', 'dint']\n",
 649       "['cart', 'dart', 'dirt', 'dire']\n",
 650       "['cart', 'dart', 'dirt', 'dirk']\n",
 651       "['cart', 'dart', 'daft', 'haft']\n",
 652       "['cart', 'dart', 'daft', 'raft']\n",
 653       "['cart', 'dart', 'daft', 'waft']\n",
 654       "['cart', 'dart', 'daft', 'deft']\n",
 655       "['cart', 'dart', 'dare', 'bare']\n",
 656       "['cart', 'dart', 'dare', 'care']\n",
 657       "['cart', 'dart', 'dare', 'fare']\n",
 658       "['cart', 'dart', 'dare', 'hare']\n",
 659       "['cart', 'dart', 'dare', 'mare']\n",
 660       "['cart', 'dart', 'dare', 'pare']\n",
 661       "['cart', 'dart', 'dare', 'rare']\n",
 662       "['cart', 'dart', 'dare', 'tare']\n",
 663       "['cart', 'dart', 'dare', 'ware']\n",
 664       "['cart', 'dart', 'dare', 'dire']\n",
 665       "['cart', 'dart', 'dare', 'dale']\n",
 666       "['cart', 'dart', 'dare', 'dame']\n",
 667       "['cart', 'dart', 'dare', 'date']\n",
 668       "['cart', 'dart', 'dare', 'daze']\n",
 669       "['cart', 'dart', 'dare', 'dark']\n",
 670       "['cart', 'dart', 'dare', 'darn']\n",
 671       "['cart', 'dart', 'dark', 'bark']\n",
 672       "['cart', 'dart', 'dark', 'hark']\n",
 673       "['cart', 'dart', 'dark', 'lark']\n",
 674       "['cart', 'dart', 'dark', 'mark']\n",
 675       "['cart', 'dart', 'dark', 'nark']\n",
 676       "['cart', 'dart', 'dark', 'park']\n",
 677       "['cart', 'dart', 'dark', 'dirk']\n",
 678       "['cart', 'dart', 'dark', 'dork']\n",
 679       "['cart', 'dart', 'dark', 'dank']\n",
 680       "['cart', 'dart', 'dark', 'dare']\n",
 681       "['cart', 'dart', 'dark', 'darn']\n",
 682       "['cart', 'dart', 'darn', 'barn']\n",
 683       "['cart', 'dart', 'darn', 'earn']\n",
 684       "['cart', 'dart', 'darn', 'warn']\n",
 685       "['cart', 'dart', 'darn', 'yarn']\n",
 686       "['cart', 'dart', 'darn', 'damn']\n",
 687       "['cart', 'dart', 'darn', 'dawn']\n",
 688       "['cart', 'dart', 'darn', 'dare']\n",
 689       "['cart', 'dart', 'darn', 'dark']\n",
 690       "['cart', 'hart', 'dart', 'mart']\n",
 691       "['cart', 'hart', 'dart', 'part']\n",
 692       "['cart', 'hart', 'dart', 'tart']\n",
 693       "['cart', 'hart', 'dart', 'wart']\n",
 694       "['cart', 'hart', 'dart', 'dirt']\n",
 695       "['cart', 'hart', 'dart', 'daft']\n",
 696       "['cart', 'hart', 'dart', 'dare']\n",
 697       "['cart', 'hart', 'dart', 'dark']\n",
 698       "['cart', 'hart', 'dart', 'darn']\n",
 699       "['cart', 'hart', 'mart', 'dart']\n",
 700       "['cart', 'hart', 'mart', 'part']\n",
 701       "['cart', 'hart', 'mart', 'tart']\n",
 702       "['cart', 'hart', 'mart', 'wart']\n",
 703       "['cart', 'hart', 'mart', 'malt']\n",
 704       "['cart', 'hart', 'mart', 'mast']\n",
 705       "['cart', 'hart', 'mart', 'matt']\n",
 706       "['cart', 'hart', 'mart', 'mare']\n",
 707       "['cart', 'hart', 'mart', 'mark']\n",
 708       "['cart', 'hart', 'mart', 'mars']\n",
 709       "['cart', 'hart', 'part', 'dart']\n",
 710       "['cart', 'hart', 'part', 'mart']\n",
 711       "['cart', 'hart', 'part', 'tart']\n",
 712       "['cart', 'hart', 'part', 'wart']\n",
 713       "['cart', 'hart', 'part', 'pert']\n",
 714       "['cart', 'hart', 'part', 'port']\n",
 715       "['cart', 'hart', 'part', 'pact']\n",
 716       "['cart', 'hart', 'part', 'pant']\n",
 717       "['cart', 'hart', 'part', 'past']\n",
 718       "['cart', 'hart', 'part', 'pare']\n",
 719       "['cart', 'hart', 'part', 'park']\n",
 720       "['cart', 'hart', 'part', 'pars']\n",
 721       "['cart', 'hart', 'tart', 'dart']\n",
 722       "['cart', 'hart', 'tart', 'mart']\n",
 723       "['cart', 'hart', 'tart', 'part']\n",
 724       "['cart', 'hart', 'tart', 'wart']\n",
 725       "['cart', 'hart', 'tart', 'tort']\n",
 726       "['cart', 'hart', 'tart', 'tact']\n",
 727       "['cart', 'hart', 'tart', 'taut']\n",
 728       "['cart', 'hart', 'tart', 'tare']\n",
 729       "['cart', 'hart', 'tart', 'taro']\n",
 730       "['cart', 'hart', 'tart', 'tarp']\n",
 731       "['cart', 'hart', 'tart', 'tars']\n",
 732       "['cart', 'hart', 'wart', 'dart']\n",
 733       "['cart', 'hart', 'wart', 'mart']\n",
 734       "['cart', 'hart', 'wart', 'part']\n",
 735       "['cart', 'hart', 'wart', 'tart']\n",
 736       "['cart', 'hart', 'wart', 'waft']\n",
 737       "['cart', 'hart', 'wart', 'wait']\n",
 738       "['cart', 'hart', 'wart', 'want']\n",
 739       "['cart', 'hart', 'wart', 'watt']\n",
 740       "['cart', 'hart', 'wart', 'ward']\n",
 741       "['cart', 'hart', 'wart', 'ware']\n",
 742       "['cart', 'hart', 'wart', 'warm']\n",
 743       "['cart', 'hart', 'wart', 'warn']\n",
 744       "['cart', 'hart', 'wart', 'warp']\n",
 745       "['cart', 'hart', 'wart', 'wars']\n",
 746       "['cart', 'hart', 'wart', 'wary']\n",
 747       "['cart', 'hart', 'hurt', 'curt']\n",
 748       "['cart', 'hart', 'hurt', 'hunt']\n",
 749       "['cart', 'hart', 'hurt', 'hurl']\n",
 750       "['cart', 'hart', 'haft', 'daft']\n",
 751       "['cart', 'hart', 'haft', 'raft']\n",
 752       "['cart', 'hart', 'haft', 'waft']\n",
 753       "['cart', 'hart', 'haft', 'heft']\n",
 754       "['cart', 'hart', 'haft', 'halt']\n",
 755       "['cart', 'hart', 'halt', 'malt']\n",
 756       "['cart', 'hart', 'halt', 'salt']\n",
 757       "['cart', 'hart', 'halt', 'hilt']\n",
 758       "['cart', 'hart', 'halt', 'haft']\n",
 759       "['cart', 'hart', 'halt', 'hale']\n",
 760       "['cart', 'hart', 'halt', 'half']\n",
 761       "['cart', 'hart', 'halt', 'hall']\n",
 762       "['cart', 'hart', 'halt', 'halo']\n",
 763       "['cart', 'hart', 'hard', 'bard']\n",
 764       "['cart', 'hart', 'hard', 'card']\n",
 765       "['cart', 'hart', 'hard', 'lard']\n",
 766       "['cart', 'hart', 'hard', 'ward']\n",
 767       "['cart', 'hart', 'hard', 'yard']\n",
 768       "['cart', 'hart', 'hard', 'herd']\n",
 769       "['cart', 'hart', 'hard', 'hand']\n",
 770       "['cart', 'hart', 'hard', 'hare']\n",
 771       "['cart', 'hart', 'hard', 'hark']\n",
 772       "['cart', 'hart', 'hard', 'harm']\n",
 773       "['cart', 'hart', 'hard', 'harp']\n",
 774       "['cart', 'hart', 'hare', 'bare']\n",
 775       "['cart', 'hart', 'hare', 'care']\n",
 776       "['cart', 'hart', 'hare', 'dare']\n",
 777       "['cart', 'hart', 'hare', 'fare']\n",
 778       "['cart', 'hart', 'hare', 'mare']\n",
 779       "['cart', 'hart', 'hare', 'pare']\n",
 780       "['cart', 'hart', 'hare', 'rare']\n",
 781       "['cart', 'hart', 'hare', 'tare']\n",
 782       "['cart', 'hart', 'hare', 'ware']\n",
 783       "['cart', 'hart', 'hare', 'here']\n",
 784       "['cart', 'hart', 'hare', 'hire']\n",
 785       "['cart', 'hart', 'hare', 'hake']\n",
 786       "['cart', 'hart', 'hare', 'hale']\n",
 787       "['cart', 'hart', 'hare', 'hate']\n",
 788       "['cart', 'hart', 'hare', 'have']\n",
 789       "['cart', 'hart', 'hare', 'haze']\n",
 790       "['cart', 'hart', 'hare', 'hard']\n",
 791       "['cart', 'hart', 'hare', 'hark']\n",
 792       "['cart', 'hart', 'hare', 'harm']\n",
 793       "['cart', 'hart', 'hare', 'harp']\n",
 794       "['cart', 'hart', 'hark', 'bark']\n",
 795       "['cart', 'hart', 'hark', 'dark']\n",
 796       "['cart', 'hart', 'hark', 'lark']\n",
 797       "['cart', 'hart', 'hark', 'mark']\n",
 798       "['cart', 'hart', 'hark', 'nark']\n",
 799       "['cart', 'hart', 'hark', 'park']\n",
 800       "['cart', 'hart', 'hark', 'hack']\n",
 801       "['cart', 'hart', 'hark', 'hank']\n",
 802       "['cart', 'hart', 'hark', 'hawk']\n",
 803       "['cart', 'hart', 'hark', 'hard']\n",
 804       "['cart', 'hart', 'hark', 'hare']\n",
 805       "['cart', 'hart', 'hark', 'harm']\n",
 806       "['cart', 'hart', 'hark', 'harp']\n",
 807       "['cart', 'hart', 'harm', 'farm']\n",
 808       "['cart', 'hart', 'harm', 'warm']\n",
 809       "['cart', 'hart', 'harm', 'hard']\n",
 810       "['cart', 'hart', 'harm', 'hare']\n",
 811       "['cart', 'hart', 'harm', 'hark']\n",
 812       "['cart', 'hart', 'harm', 'harp']\n",
 813       "['cart', 'hart', 'harp', 'carp']\n",
 814       "['cart', 'hart', 'harp', 'tarp']\n",
 815       "['cart', 'hart', 'harp', 'warp']\n",
 816       "['cart', 'hart', 'harp', 'hasp']\n",
 817       "['cart', 'hart', 'harp', 'hard']\n",
 818       "['cart', 'hart', 'harp', 'hare']\n",
 819       "['cart', 'hart', 'harp', 'hark']\n",
 820       "['cart', 'hart', 'harp', 'harm']\n",
 821       "['cart', 'mart', 'dart', 'hart']\n",
 822       "['cart', 'mart', 'dart', 'part']\n",
 823       "['cart', 'mart', 'dart', 'tart']\n",
 824       "['cart', 'mart', 'dart', 'wart']\n",
 825       "['cart', 'mart', 'dart', 'dirt']\n",
 826       "['cart', 'mart', 'dart', 'daft']\n",
 827       "['cart', 'mart', 'dart', 'dare']\n",
 828       "['cart', 'mart', 'dart', 'dark']\n",
 829       "['cart', 'mart', 'dart', 'darn']\n",
 830       "['cart', 'mart', 'hart', 'dart']\n",
 831       "['cart', 'mart', 'hart', 'part']\n",
 832       "['cart', 'mart', 'hart', 'tart']\n",
 833       "['cart', 'mart', 'hart', 'wart']\n",
 834       "['cart', 'mart', 'hart', 'hurt']\n",
 835       "['cart', 'mart', 'hart', 'haft']\n",
 836       "['cart', 'mart', 'hart', 'halt']\n",
 837       "['cart', 'mart', 'hart', 'hard']\n",
 838       "['cart', 'mart', 'hart', 'hare']\n",
 839       "['cart', 'mart', 'hart', 'hark']\n",
 840       "['cart', 'mart', 'hart', 'harm']\n",
 841       "['cart', 'mart', 'hart', 'harp']\n",
 842       "['cart', 'mart', 'part', 'dart']\n",
 843       "['cart', 'mart', 'part', 'hart']\n",
 844       "['cart', 'mart', 'part', 'tart']\n",
 845       "['cart', 'mart', 'part', 'wart']\n",
 846       "['cart', 'mart', 'part', 'pert']\n",
 847       "['cart', 'mart', 'part', 'port']\n",
 848       "['cart', 'mart', 'part', 'pact']\n",
 849       "['cart', 'mart', 'part', 'pant']\n",
 850       "['cart', 'mart', 'part', 'past']\n",
 851       "['cart', 'mart', 'part', 'pare']\n",
 852       "['cart', 'mart', 'part', 'park']\n",
 853       "['cart', 'mart', 'part', 'pars']\n",
 854       "['cart', 'mart', 'tart', 'dart']\n",
 855       "['cart', 'mart', 'tart', 'hart']\n",
 856       "['cart', 'mart', 'tart', 'part']\n",
 857       "['cart', 'mart', 'tart', 'wart']\n",
 858       "['cart', 'mart', 'tart', 'tort']\n",
 859       "['cart', 'mart', 'tart', 'tact']\n",
 860       "['cart', 'mart', 'tart', 'taut']\n",
 861       "['cart', 'mart', 'tart', 'tare']\n",
 862       "['cart', 'mart', 'tart', 'taro']\n",
 863       "['cart', 'mart', 'tart', 'tarp']\n",
 864       "['cart', 'mart', 'tart', 'tars']\n",
 865       "['cart', 'mart', 'wart', 'dart']\n",
 866       "['cart', 'mart', 'wart', 'hart']\n",
 867       "['cart', 'mart', 'wart', 'part']\n",
 868       "['cart', 'mart', 'wart', 'tart']\n",
 869       "['cart', 'mart', 'wart', 'waft']\n",
 870       "['cart', 'mart', 'wart', 'wait']\n",
 871       "['cart', 'mart', 'wart', 'want']\n",
 872       "['cart', 'mart', 'wart', 'watt']\n",
 873       "['cart', 'mart', 'wart', 'ward']\n",
 874       "['cart', 'mart', 'wart', 'ware']\n",
 875       "['cart', 'mart', 'wart', 'warm']\n",
 876       "['cart', 'mart', 'wart', 'warn']\n",
 877       "['cart', 'mart', 'wart', 'warp']\n",
 878       "['cart', 'mart', 'wart', 'wars']\n",
 879       "['cart', 'mart', 'wart', 'wary']\n",
 880       "['cart', 'mart', 'malt', 'halt']\n",
 881       "['cart', 'mart', 'malt', 'salt']\n",
 882       "['cart', 'mart', 'malt', 'melt']\n",
 883       "['cart', 'mart', 'malt', 'mast']\n",
 884       "['cart', 'mart', 'malt', 'matt']\n",
 885       "['cart', 'mart', 'malt', 'male']\n",
 886       "['cart', 'mart', 'malt', 'mall']\n",
 887       "['cart', 'mart', 'mast', 'bast']\n",
 888       "['cart', 'mart', 'mast', 'cast']\n",
 889       "['cart', 'mart', 'mast', 'east']\n",
 890       "['cart', 'mart', 'mast', 'fast']\n",
 891       "['cart', 'mart', 'mast', 'last']\n",
 892       "['cart', 'mart', 'mast', 'past']\n",
 893       "['cart', 'mart', 'mast', 'vast']\n",
 894       "['cart', 'mart', 'mast', 'mist']\n",
 895       "['cart', 'mart', 'mast', 'most']\n",
 896       "['cart', 'mart', 'mast', 'must']\n",
 897       "['cart', 'mart', 'mast', 'malt']\n",
 898       "['cart', 'mart', 'mast', 'matt']\n",
 899       "['cart', 'mart', 'mast', 'mash']\n",
 900       "['cart', 'mart', 'mast', 'mask']\n",
 901       "['cart', 'mart', 'mast', 'mass']\n",
 902       "['cart', 'mart', 'matt', 'watt']\n",
 903       "['cart', 'mart', 'matt', 'mitt']\n",
 904       "['cart', 'mart', 'matt', 'mutt']\n",
 905       "['cart', 'mart', 'matt', 'malt']\n",
 906       "['cart', 'mart', 'matt', 'mast']\n",
 907       "['cart', 'mart', 'matt', 'mate']\n",
 908       "['cart', 'mart', 'matt', 'math']\n",
 909       "['cart', 'mart', 'matt', 'mats']\n",
 910       "['cart', 'mart', 'mare', 'bare']\n",
 911       "['cart', 'mart', 'mare', 'care']\n",
 912       "['cart', 'mart', 'mare', 'dare']\n",
 913       "['cart', 'mart', 'mare', 'fare']\n",
 914       "['cart', 'mart', 'mare', 'hare']\n",
 915       "['cart', 'mart', 'mare', 'pare']\n",
 916       "['cart', 'mart', 'mare', 'rare']\n",
 917       "['cart', 'mart', 'mare', 'tare']\n",
 918       "['cart', 'mart', 'mare', 'ware']\n",
 919       "['cart', 'mart', 'mare', 'mere']\n",
 920       "['cart', 'mart', 'mare', 'mire']\n",
 921       "['cart', 'mart', 'mare', 'more']\n",
 922       "['cart', 'mart', 'mare', 'mace']\n",
 923       "['cart', 'mart', 'mare', 'made']\n",
 924       "['cart', 'mart', 'mare', 'make']\n",
 925       "['cart', 'mart', 'mare', 'male']\n",
 926       "['cart', 'mart', 'mare', 'mane']\n",
 927       "['cart', 'mart', 'mare', 'mate']\n",
 928       "['cart', 'mart', 'mare', 'maze']\n",
 929       "['cart', 'mart', 'mare', 'mark']\n",
 930       "['cart', 'mart', 'mare', 'mars']\n",
 931       "['cart', 'mart', 'mark', 'bark']\n",
 932       "['cart', 'mart', 'mark', 'dark']\n",
 933       "['cart', 'mart', 'mark', 'hark']\n",
 934       "['cart', 'mart', 'mark', 'lark']\n",
 935       "['cart', 'mart', 'mark', 'nark']\n",
 936       "['cart', 'mart', 'mark', 'park']\n",
 937       "['cart', 'mart', 'mark', 'murk']\n",
 938       "['cart', 'mart', 'mark', 'mask']\n",
 939       "['cart', 'mart', 'mark', 'mare']\n",
 940       "['cart', 'mart', 'mark', 'mars']\n",
 941       "['cart', 'mart', 'mars', 'bars']\n",
 942       "['cart', 'mart', 'mars', 'cars']\n",
 943       "['cart', 'mart', 'mars', 'ears']\n",
 944       "['cart', 'mart', 'mars', 'jars']\n",
 945       "['cart', 'mart', 'mars', 'oars']\n",
 946       "['cart', 'mart', 'mars', 'pars']\n",
 947       "['cart', 'mart', 'mars', 'tars']\n",
 948       "['cart', 'mart', 'mars', 'wars']\n",
 949       "['cart', 'mart', 'mars', 'mads']\n",
 950       "['cart', 'mart', 'mars', 'mans']\n",
 951       "['cart', 'mart', 'mars', 'maps']\n",
 952       "['cart', 'mart', 'mars', 'mass']\n",
 953       "['cart', 'mart', 'mars', 'mats']\n",
 954       "['cart', 'mart', 'mars', 'maws']\n",
 955       "['cart', 'mart', 'mars', 'mare']\n",
 956       "['cart', 'mart', 'mars', 'mark']\n",
 957       "['cart', 'part', 'dart', 'hart']\n",
 958       "['cart', 'part', 'dart', 'mart']\n",
 959       "['cart', 'part', 'dart', 'tart']\n",
 960       "['cart', 'part', 'dart', 'wart']\n",
 961       "['cart', 'part', 'dart', 'dirt']\n",
 962       "['cart', 'part', 'dart', 'daft']\n",
 963       "['cart', 'part', 'dart', 'dare']\n",
 964       "['cart', 'part', 'dart', 'dark']\n",
 965       "['cart', 'part', 'dart', 'darn']\n",
 966       "['cart', 'part', 'hart', 'dart']\n",
 967       "['cart', 'part', 'hart', 'mart']\n",
 968       "['cart', 'part', 'hart', 'tart']\n",
 969       "['cart', 'part', 'hart', 'wart']\n",
 970       "['cart', 'part', 'hart', 'hurt']\n",
 971       "['cart', 'part', 'hart', 'haft']\n",
 972       "['cart', 'part', 'hart', 'halt']\n",
 973       "['cart', 'part', 'hart', 'hard']\n",
 974       "['cart', 'part', 'hart', 'hare']\n",
 975       "['cart', 'part', 'hart', 'hark']\n",
 976       "['cart', 'part', 'hart', 'harm']\n",
 977       "['cart', 'part', 'hart', 'harp']\n",
 978       "['cart', 'part', 'mart', 'dart']\n",
 979       "['cart', 'part', 'mart', 'hart']\n",
 980       "['cart', 'part', 'mart', 'tart']\n",
 981       "['cart', 'part', 'mart', 'wart']\n",
 982       "['cart', 'part', 'mart', 'malt']\n",
 983       "['cart', 'part', 'mart', 'mast']\n",
 984       "['cart', 'part', 'mart', 'matt']\n",
 985       "['cart', 'part', 'mart', 'mare']\n",
 986       "['cart', 'part', 'mart', 'mark']\n",
 987       "['cart', 'part', 'mart', 'mars']\n",
 988       "['cart', 'part', 'tart', 'dart']\n",
 989       "['cart', 'part', 'tart', 'hart']\n",
 990       "['cart', 'part', 'tart', 'mart']\n",
 991       "['cart', 'part', 'tart', 'wart']\n",
 992       "['cart', 'part', 'tart', 'tort']\n",
 993       "['cart', 'part', 'tart', 'tact']\n",
 994       "['cart', 'part', 'tart', 'taut']\n",
 995       "['cart', 'part', 'tart', 'tare']\n",
 996       "['cart', 'part', 'tart', 'taro']\n",
 997       "['cart', 'part', 'tart', 'tarp']\n",
 998       "['cart', 'part', 'tart', 'tars']\n",
 999       "['cart', 'part', 'wart', 'dart']\n",
1000       "['cart', 'part', 'wart', 'hart']\n",
1001       "['cart', 'part', 'wart', 'mart']\n",
1002       "['cart', 'part', 'wart', 'tart']\n",
1003       "['cart', 'part', 'wart', 'waft']\n",
1004       "['cart', 'part', 'wart', 'wait']\n",
1005       "['cart', 'part', 'wart', 'want']\n",
1006       "['cart', 'part', 'wart', 'watt']\n",
1007       "['cart', 'part', 'wart', 'ward']\n",
1008       "['cart', 'part', 'wart', 'ware']\n",
1009       "['cart', 'part', 'wart', 'warm']\n",
1010       "['cart', 'part', 'wart', 'warn']\n",
1011       "['cart', 'part', 'wart', 'warp']\n",
1012       "['cart', 'part', 'wart', 'wars']\n",
1013       "['cart', 'part', 'wart', 'wary']\n",
1014       "['cart', 'part', 'pert', 'port']\n",
1015       "['cart', 'part', 'pert', 'peat']\n",
1016       "['cart', 'part', 'pert', 'pelt']\n",
1017       "['cart', 'part', 'pert', 'pent']\n",
1018       "['cart', 'part', 'pert', 'pest']\n",
1019       "['cart', 'part', 'pert', 'perk']\n",
1020       "['cart', 'part', 'pert', 'perm']\n",
1021       "['cart', 'part', 'port', 'fort']\n",
1022       "['cart', 'part', 'port', 'sort']\n",
1023       "['cart', 'part', 'port', 'tort']\n",
1024       "['cart', 'part', 'port', 'pert']\n",
1025       "['cart', 'part', 'port', 'poet']\n",
1026       "['cart', 'part', 'port', 'post']\n",
1027       "['cart', 'part', 'port', 'pout']\n",
1028       "['cart', 'part', 'port', 'pore']\n",
1029       "['cart', 'part', 'port', 'pork']\n",
1030       "['cart', 'part', 'port', 'porn']\n",
1031       "['cart', 'part', 'pact', 'fact']\n",
1032       "['cart', 'part', 'pact', 'tact']\n",
1033       "['cart', 'part', 'pact', 'pant']\n",
1034       "['cart', 'part', 'pact', 'past']\n",
1035       "['cart', 'part', 'pact', 'pace']\n",
1036       "['cart', 'part', 'pact', 'pack']\n",
1037       "['cart', 'part', 'pant', 'cant']\n",
1038       "['cart', 'part', 'pant', 'rant']\n",
1039       "['cart', 'part', 'pant', 'want']\n",
1040       "['cart', 'part', 'pant', 'pent']\n",
1041       "['cart', 'part', 'pant', 'pint']\n",
1042       "['cart', 'part', 'pant', 'punt']\n",
1043       "['cart', 'part', 'pant', 'pact']\n",
1044       "['cart', 'part', 'pant', 'past']\n",
1045       "['cart', 'part', 'pant', 'pane']\n",
1046       "['cart', 'part', 'pant', 'pang']\n",
1047       "['cart', 'part', 'pant', 'pans']\n",
1048       "['cart', 'part', 'past', 'bast']\n",
1049       "['cart', 'part', 'past', 'cast']\n",
1050       "['cart', 'part', 'past', 'east']\n",
1051       "['cart', 'part', 'past', 'fast']\n",
1052       "['cart', 'part', 'past', 'last']\n",
1053       "['cart', 'part', 'past', 'mast']\n",
1054       "['cart', 'part', 'past', 'vast']\n",
1055       "['cart', 'part', 'past', 'pest']\n",
1056       "['cart', 'part', 'past', 'post']\n",
1057       "['cart', 'part', 'past', 'psst']\n",
1058       "['cart', 'part', 'past', 'pact']\n",
1059       "['cart', 'part', 'past', 'pant']\n",
1060       "['cart', 'part', 'past', 'pass']\n",
1061       "['cart', 'part', 'pare', 'bare']\n",
1062       "['cart', 'part', 'pare', 'care']\n",
1063       "['cart', 'part', 'pare', 'dare']\n",
1064       "['cart', 'part', 'pare', 'fare']\n",
1065       "['cart', 'part', 'pare', 'hare']\n",
1066       "['cart', 'part', 'pare', 'mare']\n",
1067       "['cart', 'part', 'pare', 'rare']\n",
1068       "['cart', 'part', 'pare', 'tare']\n",
1069       "['cart', 'part', 'pare', 'ware']\n",
1070       "['cart', 'part', 'pare', 'pore']\n",
1071       "['cart', 'part', 'pare', 'pure']\n",
1072       "['cart', 'part', 'pare', 'pyre']\n",
1073       "['cart', 'part', 'pare', 'pace']\n",
1074       "['cart', 'part', 'pare', 'page']\n",
1075       "['cart', 'part', 'pare', 'pale']\n",
1076       "['cart', 'part', 'pare', 'pane']\n",
1077       "['cart', 'part', 'pare', 'pate']\n",
1078       "['cart', 'part', 'pare', 'pave']\n",
1079       "['cart', 'part', 'pare', 'park']\n",
1080       "['cart', 'part', 'pare', 'pars']\n",
1081       "['cart', 'part', 'park', 'bark']\n",
1082       "['cart', 'part', 'park', 'dark']\n",
1083       "['cart', 'part', 'park', 'hark']\n",
1084       "['cart', 'part', 'park', 'lark']\n",
1085       "['cart', 'part', 'park', 'mark']\n",
1086       "['cart', 'part', 'park', 'nark']\n",
1087       "['cart', 'part', 'park', 'perk']\n",
1088       "['cart', 'part', 'park', 'pork']\n",
1089       "['cart', 'part', 'park', 'pack']\n",
1090       "['cart', 'part', 'park', 'pare']\n",
1091       "['cart', 'part', 'park', 'pars']\n",
1092       "['cart', 'part', 'pars', 'bars']\n",
1093       "['cart', 'part', 'pars', 'cars']\n",
1094       "['cart', 'part', 'pars', 'ears']\n"
1095      ]
1096     },
1097     {
1098      "name": "stdout",
1099      "output_type": "stream",
1100      "text": [
1101       "['cart', 'part', 'pars', 'jars']\n",
1102       "['cart', 'part', 'pars', 'mars']\n",
1103       "['cart', 'part', 'pars', 'oars']\n",
1104       "['cart', 'part', 'pars', 'tars']\n",
1105       "['cart', 'part', 'pars', 'wars']\n",
1106       "['cart', 'part', 'pars', 'pads']\n",
1107       "['cart', 'part', 'pars', 'pals']\n",
1108       "['cart', 'part', 'pars', 'pans']\n",
1109       "['cart', 'part', 'pars', 'paps']\n",
1110       "['cart', 'part', 'pars', 'pass']\n",
1111       "['cart', 'part', 'pars', 'pats']\n",
1112       "['cart', 'part', 'pars', 'paws']\n",
1113       "['cart', 'part', 'pars', 'pays']\n",
1114       "['cart', 'part', 'pars', 'pare']\n",
1115       "['cart', 'part', 'pars', 'park']\n",
1116       "['cart', 'tart', 'dart', 'hart']\n",
1117       "['cart', 'tart', 'dart', 'mart']\n",
1118       "['cart', 'tart', 'dart', 'part']\n",
1119       "['cart', 'tart', 'dart', 'wart']\n",
1120       "['cart', 'tart', 'dart', 'dirt']\n",
1121       "['cart', 'tart', 'dart', 'daft']\n",
1122       "['cart', 'tart', 'dart', 'dare']\n",
1123       "['cart', 'tart', 'dart', 'dark']\n",
1124       "['cart', 'tart', 'dart', 'darn']\n",
1125       "['cart', 'tart', 'hart', 'dart']\n",
1126       "['cart', 'tart', 'hart', 'mart']\n",
1127       "['cart', 'tart', 'hart', 'part']\n",
1128       "['cart', 'tart', 'hart', 'wart']\n",
1129       "['cart', 'tart', 'hart', 'hurt']\n",
1130       "['cart', 'tart', 'hart', 'haft']\n",
1131       "['cart', 'tart', 'hart', 'halt']\n",
1132       "['cart', 'tart', 'hart', 'hard']\n",
1133       "['cart', 'tart', 'hart', 'hare']\n",
1134       "['cart', 'tart', 'hart', 'hark']\n",
1135       "['cart', 'tart', 'hart', 'harm']\n",
1136       "['cart', 'tart', 'hart', 'harp']\n",
1137       "['cart', 'tart', 'mart', 'dart']\n",
1138       "['cart', 'tart', 'mart', 'hart']\n",
1139       "['cart', 'tart', 'mart', 'part']\n",
1140       "['cart', 'tart', 'mart', 'wart']\n",
1141       "['cart', 'tart', 'mart', 'malt']\n",
1142       "['cart', 'tart', 'mart', 'mast']\n",
1143       "['cart', 'tart', 'mart', 'matt']\n",
1144       "['cart', 'tart', 'mart', 'mare']\n",
1145       "['cart', 'tart', 'mart', 'mark']\n",
1146       "['cart', 'tart', 'mart', 'mars']\n",
1147       "['cart', 'tart', 'part', 'dart']\n",
1148       "['cart', 'tart', 'part', 'hart']\n",
1149       "['cart', 'tart', 'part', 'mart']\n",
1150       "['cart', 'tart', 'part', 'wart']\n",
1151       "['cart', 'tart', 'part', 'pert']\n",
1152       "['cart', 'tart', 'part', 'port']\n",
1153       "['cart', 'tart', 'part', 'pact']\n",
1154       "['cart', 'tart', 'part', 'pant']\n",
1155       "['cart', 'tart', 'part', 'past']\n",
1156       "['cart', 'tart', 'part', 'pare']\n",
1157       "['cart', 'tart', 'part', 'park']\n",
1158       "['cart', 'tart', 'part', 'pars']\n",
1159       "['cart', 'tart', 'wart', 'dart']\n",
1160       "['cart', 'tart', 'wart', 'hart']\n",
1161       "['cart', 'tart', 'wart', 'mart']\n",
1162       "['cart', 'tart', 'wart', 'part']\n",
1163       "['cart', 'tart', 'wart', 'waft']\n",
1164       "['cart', 'tart', 'wart', 'wait']\n",
1165       "['cart', 'tart', 'wart', 'want']\n",
1166       "['cart', 'tart', 'wart', 'watt']\n",
1167       "['cart', 'tart', 'wart', 'ward']\n",
1168       "['cart', 'tart', 'wart', 'ware']\n",
1169       "['cart', 'tart', 'wart', 'warm']\n",
1170       "['cart', 'tart', 'wart', 'warn']\n",
1171       "['cart', 'tart', 'wart', 'warp']\n",
1172       "['cart', 'tart', 'wart', 'wars']\n",
1173       "['cart', 'tart', 'wart', 'wary']\n",
1174       "['cart', 'tart', 'tort', 'fort']\n",
1175       "['cart', 'tart', 'tort', 'port']\n",
1176       "['cart', 'tart', 'tort', 'sort']\n",
1177       "['cart', 'tart', 'tort', 'toot']\n",
1178       "['cart', 'tart', 'tort', 'tost']\n",
1179       "['cart', 'tart', 'tort', 'tout']\n",
1180       "['cart', 'tart', 'tort', 'tore']\n",
1181       "['cart', 'tart', 'tort', 'torn']\n",
1182       "['cart', 'tart', 'tort', 'tors']\n",
1183       "['cart', 'tart', 'tact', 'fact']\n",
1184       "['cart', 'tart', 'tact', 'pact']\n",
1185       "['cart', 'tart', 'tact', 'taut']\n",
1186       "['cart', 'tart', 'tact', 'tack']\n",
1187       "['cart', 'tart', 'tact', 'taco']\n",
1188       "['cart', 'tart', 'taut', 'tout']\n",
1189       "['cart', 'tart', 'taut', 'tact']\n",
1190       "['cart', 'tart', 'tare', 'bare']\n",
1191       "['cart', 'tart', 'tare', 'care']\n",
1192       "['cart', 'tart', 'tare', 'dare']\n",
1193       "['cart', 'tart', 'tare', 'fare']\n",
1194       "['cart', 'tart', 'tare', 'hare']\n",
1195       "['cart', 'tart', 'tare', 'mare']\n",
1196       "['cart', 'tart', 'tare', 'pare']\n",
1197       "['cart', 'tart', 'tare', 'rare']\n",
1198       "['cart', 'tart', 'tare', 'ware']\n",
1199       "['cart', 'tart', 'tare', 'tire']\n",
1200       "['cart', 'tart', 'tare', 'tore']\n",
1201       "['cart', 'tart', 'tare', 'tyre']\n",
1202       "['cart', 'tart', 'tare', 'take']\n",
1203       "['cart', 'tart', 'tare', 'tale']\n",
1204       "['cart', 'tart', 'tare', 'tame']\n",
1205       "['cart', 'tart', 'tare', 'tape']\n",
1206       "['cart', 'tart', 'tare', 'taro']\n",
1207       "['cart', 'tart', 'tare', 'tarp']\n",
1208       "['cart', 'tart', 'tare', 'tars']\n",
1209       "['cart', 'tart', 'taro', 'tiro']\n",
1210       "['cart', 'tart', 'taro', 'tyro']\n",
1211       "['cart', 'tart', 'taro', 'taco']\n",
1212       "['cart', 'tart', 'taro', 'tare']\n",
1213       "['cart', 'tart', 'taro', 'tarp']\n",
1214       "['cart', 'tart', 'taro', 'tars']\n",
1215       "['cart', 'tart', 'tarp', 'carp']\n",
1216       "['cart', 'tart', 'tarp', 'harp']\n",
1217       "['cart', 'tart', 'tarp', 'warp']\n",
1218       "['cart', 'tart', 'tarp', 'tamp']\n",
1219       "['cart', 'tart', 'tarp', 'tare']\n",
1220       "['cart', 'tart', 'tarp', 'taro']\n",
1221       "['cart', 'tart', 'tarp', 'tars']\n",
1222       "['cart', 'tart', 'tars', 'bars']\n",
1223       "['cart', 'tart', 'tars', 'cars']\n",
1224       "['cart', 'tart', 'tars', 'ears']\n",
1225       "['cart', 'tart', 'tars', 'jars']\n",
1226       "['cart', 'tart', 'tars', 'mars']\n",
1227       "['cart', 'tart', 'tars', 'oars']\n",
1228       "['cart', 'tart', 'tars', 'pars']\n",
1229       "['cart', 'tart', 'tars', 'wars']\n",
1230       "['cart', 'tart', 'tars', 'tors']\n",
1231       "['cart', 'tart', 'tars', 'tabs']\n",
1232       "['cart', 'tart', 'tars', 'tads']\n",
1233       "['cart', 'tart', 'tars', 'tags']\n",
1234       "['cart', 'tart', 'tars', 'tams']\n",
1235       "['cart', 'tart', 'tars', 'tans']\n",
1236       "['cart', 'tart', 'tars', 'taps']\n",
1237       "['cart', 'tart', 'tars', 'tats']\n",
1238       "['cart', 'tart', 'tars', 'tare']\n",
1239       "['cart', 'tart', 'tars', 'taro']\n",
1240       "['cart', 'tart', 'tars', 'tarp']\n",
1241       "['cart', 'wart', 'dart', 'hart']\n",
1242       "['cart', 'wart', 'dart', 'mart']\n",
1243       "['cart', 'wart', 'dart', 'part']\n",
1244       "['cart', 'wart', 'dart', 'tart']\n",
1245       "['cart', 'wart', 'dart', 'dirt']\n",
1246       "['cart', 'wart', 'dart', 'daft']\n",
1247       "['cart', 'wart', 'dart', 'dare']\n",
1248       "['cart', 'wart', 'dart', 'dark']\n",
1249       "['cart', 'wart', 'dart', 'darn']\n",
1250       "['cart', 'wart', 'hart', 'dart']\n",
1251       "['cart', 'wart', 'hart', 'mart']\n",
1252       "['cart', 'wart', 'hart', 'part']\n",
1253       "['cart', 'wart', 'hart', 'tart']\n",
1254       "['cart', 'wart', 'hart', 'hurt']\n",
1255       "['cart', 'wart', 'hart', 'haft']\n",
1256       "['cart', 'wart', 'hart', 'halt']\n",
1257       "['cart', 'wart', 'hart', 'hard']\n",
1258       "['cart', 'wart', 'hart', 'hare']\n",
1259       "['cart', 'wart', 'hart', 'hark']\n",
1260       "['cart', 'wart', 'hart', 'harm']\n",
1261       "['cart', 'wart', 'hart', 'harp']\n",
1262       "['cart', 'wart', 'mart', 'dart']\n",
1263       "['cart', 'wart', 'mart', 'hart']\n",
1264       "['cart', 'wart', 'mart', 'part']\n",
1265       "['cart', 'wart', 'mart', 'tart']\n",
1266       "['cart', 'wart', 'mart', 'malt']\n",
1267       "['cart', 'wart', 'mart', 'mast']\n",
1268       "['cart', 'wart', 'mart', 'matt']\n",
1269       "['cart', 'wart', 'mart', 'mare']\n",
1270       "['cart', 'wart', 'mart', 'mark']\n",
1271       "['cart', 'wart', 'mart', 'mars']\n",
1272       "['cart', 'wart', 'part', 'dart']\n",
1273       "['cart', 'wart', 'part', 'hart']\n",
1274       "['cart', 'wart', 'part', 'mart']\n",
1275       "['cart', 'wart', 'part', 'tart']\n",
1276       "['cart', 'wart', 'part', 'pert']\n",
1277       "['cart', 'wart', 'part', 'port']\n",
1278       "['cart', 'wart', 'part', 'pact']\n",
1279       "['cart', 'wart', 'part', 'pant']\n",
1280       "['cart', 'wart', 'part', 'past']\n",
1281       "['cart', 'wart', 'part', 'pare']\n",
1282       "['cart', 'wart', 'part', 'park']\n",
1283       "['cart', 'wart', 'part', 'pars']\n",
1284       "['cart', 'wart', 'tart', 'dart']\n",
1285       "['cart', 'wart', 'tart', 'hart']\n",
1286       "['cart', 'wart', 'tart', 'mart']\n",
1287       "['cart', 'wart', 'tart', 'part']\n",
1288       "['cart', 'wart', 'tart', 'tort']\n",
1289       "['cart', 'wart', 'tart', 'tact']\n",
1290       "['cart', 'wart', 'tart', 'taut']\n",
1291       "['cart', 'wart', 'tart', 'tare']\n",
1292       "['cart', 'wart', 'tart', 'taro']\n",
1293       "['cart', 'wart', 'tart', 'tarp']\n",
1294       "['cart', 'wart', 'tart', 'tars']\n",
1295       "['cart', 'wart', 'waft', 'daft']\n",
1296       "['cart', 'wart', 'waft', 'haft']\n",
1297       "['cart', 'wart', 'waft', 'raft']\n",
1298       "['cart', 'wart', 'waft', 'weft']\n",
1299       "['cart', 'wart', 'waft', 'wait']\n",
1300       "['cart', 'wart', 'waft', 'want']\n",
1301       "['cart', 'wart', 'waft', 'watt']\n",
1302       "['cart', 'wart', 'wait', 'bait']\n",
1303       "['cart', 'wart', 'wait', 'gait']\n",
1304       "['cart', 'wart', 'wait', 'whit']\n",
1305       "['cart', 'wart', 'wait', 'writ']\n",
1306       "['cart', 'wart', 'wait', 'waft']\n",
1307       "['cart', 'wart', 'wait', 'want']\n",
1308       "['cart', 'wart', 'wait', 'watt']\n",
1309       "['cart', 'wart', 'wait', 'waif']\n",
1310       "['cart', 'wart', 'wait', 'wail']\n",
1311       "['cart', 'wart', 'want', 'cant']\n",
1312       "['cart', 'wart', 'want', 'pant']\n",
1313       "['cart', 'wart', 'want', 'rant']\n",
1314       "['cart', 'wart', 'want', 'went']\n",
1315       "['cart', 'wart', 'want', 'wont']\n",
1316       "['cart', 'wart', 'want', 'waft']\n",
1317       "['cart', 'wart', 'want', 'wait']\n",
1318       "['cart', 'wart', 'want', 'watt']\n",
1319       "['cart', 'wart', 'want', 'wand']\n",
1320       "['cart', 'wart', 'want', 'wane']\n",
1321       "['cart', 'wart', 'watt', 'matt']\n",
1322       "['cart', 'wart', 'watt', 'waft']\n",
1323       "['cart', 'wart', 'watt', 'wait']\n",
1324       "['cart', 'wart', 'watt', 'want']\n",
1325       "['cart', 'wart', 'ward', 'bard']\n",
1326       "['cart', 'wart', 'ward', 'card']\n",
1327       "['cart', 'wart', 'ward', 'hard']\n",
1328       "['cart', 'wart', 'ward', 'lard']\n",
1329       "['cart', 'wart', 'ward', 'yard']\n",
1330       "['cart', 'wart', 'ward', 'word']\n",
1331       "['cart', 'wart', 'ward', 'wand']\n",
1332       "['cart', 'wart', 'ward', 'ware']\n",
1333       "['cart', 'wart', 'ward', 'warm']\n",
1334       "['cart', 'wart', 'ward', 'warn']\n",
1335       "['cart', 'wart', 'ward', 'warp']\n",
1336       "['cart', 'wart', 'ward', 'wars']\n",
1337       "['cart', 'wart', 'ward', 'wary']\n",
1338       "['cart', 'wart', 'ware', 'bare']\n",
1339       "['cart', 'wart', 'ware', 'care']\n",
1340       "['cart', 'wart', 'ware', 'dare']\n",
1341       "['cart', 'wart', 'ware', 'fare']\n",
1342       "['cart', 'wart', 'ware', 'hare']\n",
1343       "['cart', 'wart', 'ware', 'mare']\n",
1344       "['cart', 'wart', 'ware', 'pare']\n",
1345       "['cart', 'wart', 'ware', 'rare']\n",
1346       "['cart', 'wart', 'ware', 'tare']\n",
1347       "['cart', 'wart', 'ware', 'were']\n",
1348       "['cart', 'wart', 'ware', 'wire']\n",
1349       "['cart', 'wart', 'ware', 'wore']\n",
1350       "['cart', 'wart', 'ware', 'wade']\n",
1351       "['cart', 'wart', 'ware', 'wage']\n",
1352       "['cart', 'wart', 'ware', 'wake']\n",
1353       "['cart', 'wart', 'ware', 'wale']\n",
1354       "['cart', 'wart', 'ware', 'wane']\n",
1355       "['cart', 'wart', 'ware', 'wave']\n",
1356       "['cart', 'wart', 'ware', 'ward']\n",
1357       "['cart', 'wart', 'ware', 'warm']\n",
1358       "['cart', 'wart', 'ware', 'warn']\n",
1359       "['cart', 'wart', 'ware', 'warp']\n",
1360       "['cart', 'wart', 'ware', 'wars']\n",
1361       "['cart', 'wart', 'ware', 'wary']\n",
1362       "['cart', 'wart', 'warm', 'farm']\n",
1363       "['cart', 'wart', 'warm', 'harm']\n",
1364       "['cart', 'wart', 'warm', 'worm']\n",
1365       "['cart', 'wart', 'warm', 'ward']\n",
1366       "['cart', 'wart', 'warm', 'ware']\n",
1367       "['cart', 'wart', 'warm', 'warn']\n",
1368       "['cart', 'wart', 'warm', 'warp']\n",
1369       "['cart', 'wart', 'warm', 'wars']\n",
1370       "['cart', 'wart', 'warm', 'wary']\n",
1371       "['cart', 'wart', 'warn', 'barn']\n",
1372       "['cart', 'wart', 'warn', 'darn']\n",
1373       "['cart', 'wart', 'warn', 'earn']\n",
1374       "['cart', 'wart', 'warn', 'yarn']\n",
1375       "['cart', 'wart', 'warn', 'worn']\n",
1376       "['cart', 'wart', 'warn', 'ward']\n",
1377       "['cart', 'wart', 'warn', 'ware']\n",
1378       "['cart', 'wart', 'warn', 'warm']\n",
1379       "['cart', 'wart', 'warn', 'warp']\n",
1380       "['cart', 'wart', 'warn', 'wars']\n",
1381       "['cart', 'wart', 'warn', 'wary']\n",
1382       "['cart', 'wart', 'warp', 'carp']\n",
1383       "['cart', 'wart', 'warp', 'harp']\n",
1384       "['cart', 'wart', 'warp', 'tarp']\n",
1385       "['cart', 'wart', 'warp', 'wasp']\n",
1386       "['cart', 'wart', 'warp', 'ward']\n",
1387       "['cart', 'wart', 'warp', 'ware']\n",
1388       "['cart', 'wart', 'warp', 'warm']\n",
1389       "['cart', 'wart', 'warp', 'warn']\n",
1390       "['cart', 'wart', 'warp', 'wars']\n",
1391       "['cart', 'wart', 'warp', 'wary']\n",
1392       "['cart', 'wart', 'wars', 'bars']\n",
1393       "['cart', 'wart', 'wars', 'cars']\n",
1394       "['cart', 'wart', 'wars', 'ears']\n",
1395       "['cart', 'wart', 'wars', 'jars']\n",
1396       "['cart', 'wart', 'wars', 'mars']\n",
1397       "['cart', 'wart', 'wars', 'oars']\n",
1398       "['cart', 'wart', 'wars', 'pars']\n",
1399       "['cart', 'wart', 'wars', 'tars']\n",
1400       "['cart', 'wart', 'wars', 'wads']\n",
1401       "['cart', 'wart', 'wars', 'wags']\n",
1402       "['cart', 'wart', 'wars', 'ways']\n",
1403       "['cart', 'wart', 'wars', 'ward']\n",
1404       "['cart', 'wart', 'wars', 'ware']\n",
1405       "['cart', 'wart', 'wars', 'warm']\n",
1406       "['cart', 'wart', 'wars', 'warn']\n",
1407       "['cart', 'wart', 'wars', 'warp']\n",
1408       "['cart', 'wart', 'wars', 'wary']\n",
1409       "['cart', 'wart', 'wary', 'nary']\n",
1410       "['cart', 'wart', 'wary', 'vary']\n",
1411       "['cart', 'wart', 'wary', 'wiry']\n",
1412       "['cart', 'wart', 'wary', 'wavy']\n",
1413       "['cart', 'wart', 'wary', 'waxy']\n",
1414       "['cart', 'wart', 'wary', 'ward']\n",
1415       "['cart', 'wart', 'wary', 'ware']\n",
1416       "['cart', 'wart', 'wary', 'warm']\n",
1417       "['cart', 'wart', 'wary', 'warn']\n",
1418       "['cart', 'wart', 'wary', 'warp']\n",
1419       "['cart', 'wart', 'wary', 'wars']\n",
1420       "['cart', 'curt', 'hurt', 'hart']\n",
1421       "['cart', 'curt', 'hurt', 'hunt']\n",
1422       "['cart', 'curt', 'hurt', 'hurl']\n",
1423       "['cart', 'curt', 'cult', 'colt']\n",
1424       "['cart', 'curt', 'cult', 'cull']\n",
1425       "['cart', 'curt', 'curb', 'curd']\n",
1426       "['cart', 'curt', 'curb', 'cure']\n",
1427       "['cart', 'curt', 'curb', 'curl']\n",
1428       "['cart', 'curt', 'curb', 'curs']\n",
1429       "['cart', 'curt', 'curd', 'turd']\n",
1430       "['cart', 'curt', 'curd', 'card']\n",
1431       "['cart', 'curt', 'curd', 'cord']\n",
1432       "['cart', 'curt', 'curd', 'cued']\n",
1433       "['cart', 'curt', 'curd', 'curb']\n",
1434       "['cart', 'curt', 'curd', 'cure']\n",
1435       "['cart', 'curt', 'curd', 'curl']\n",
1436       "['cart', 'curt', 'curd', 'curs']\n",
1437       "['cart', 'curt', 'cure', 'lure']\n",
1438       "['cart', 'curt', 'cure', 'pure']\n",
1439       "['cart', 'curt', 'cure', 'sure']\n",
1440       "['cart', 'curt', 'cure', 'care']\n",
1441       "['cart', 'curt', 'cure', 'core']\n",
1442       "['cart', 'curt', 'cure', 'cube']\n",
1443       "['cart', 'curt', 'cure', 'cute']\n",
1444       "['cart', 'curt', 'cure', 'curb']\n",
1445       "['cart', 'curt', 'cure', 'curd']\n",
1446       "['cart', 'curt', 'cure', 'curl']\n",
1447       "['cart', 'curt', 'cure', 'curs']\n",
1448       "['cart', 'curt', 'curl', 'furl']\n",
1449       "['cart', 'curt', 'curl', 'hurl']\n",
1450       "['cart', 'curt', 'curl', 'purl']\n",
1451       "['cart', 'curt', 'curl', 'cull']\n",
1452       "['cart', 'curt', 'curl', 'curb']\n",
1453       "['cart', 'curt', 'curl', 'curd']\n",
1454       "['cart', 'curt', 'curl', 'cure']\n",
1455       "['cart', 'curt', 'curl', 'curs']\n",
1456       "['cart', 'curt', 'curs', 'burs']\n",
1457       "['cart', 'curt', 'curs', 'furs']\n",
1458       "['cart', 'curt', 'curs', 'ours']\n",
1459       "['cart', 'curt', 'curs', 'cars']\n",
1460       "['cart', 'curt', 'curs', 'cubs']\n",
1461       "['cart', 'curt', 'curs', 'cuds']\n",
1462       "['cart', 'curt', 'curs', 'cues']\n",
1463       "['cart', 'curt', 'curs', 'cums']\n",
1464       "['cart', 'curt', 'curs', 'cups']\n",
1465       "['cart', 'curt', 'curs', 'cuss']\n",
1466       "['cart', 'curt', 'curs', 'cuts']\n",
1467       "['cart', 'curt', 'curs', 'curb']\n",
1468       "['cart', 'curt', 'curs', 'curd']\n",
1469       "['cart', 'curt', 'curs', 'cure']\n",
1470       "['cart', 'curt', 'curs', 'curl']\n",
1471       "['cart', 'cant', 'pant', 'rant']\n",
1472       "['cart', 'cant', 'pant', 'want']\n",
1473       "['cart', 'cant', 'pant', 'pent']\n",
1474       "['cart', 'cant', 'pant', 'pint']\n",
1475       "['cart', 'cant', 'pant', 'punt']\n",
1476       "['cart', 'cant', 'pant', 'pact']\n",
1477       "['cart', 'cant', 'pant', 'part']\n",
1478       "['cart', 'cant', 'pant', 'past']\n",
1479       "['cart', 'cant', 'pant', 'pane']\n",
1480       "['cart', 'cant', 'pant', 'pang']\n",
1481       "['cart', 'cant', 'pant', 'pans']\n",
1482       "['cart', 'cant', 'rant', 'pant']\n",
1483       "['cart', 'cant', 'rant', 'want']\n",
1484       "['cart', 'cant', 'rant', 'rent']\n",
1485       "['cart', 'cant', 'rant', 'runt']\n",
1486       "['cart', 'cant', 'rant', 'raft']\n",
1487       "['cart', 'cant', 'rant', 'rapt']\n",
1488       "['cart', 'cant', 'rant', 'rang']\n",
1489       "['cart', 'cant', 'rant', 'rank']\n",
1490       "['cart', 'cant', 'want', 'pant']\n",
1491       "['cart', 'cant', 'want', 'rant']\n",
1492       "['cart', 'cant', 'want', 'went']\n",
1493       "['cart', 'cant', 'want', 'wont']\n",
1494       "['cart', 'cant', 'want', 'waft']\n",
1495       "['cart', 'cant', 'want', 'wait']\n",
1496       "['cart', 'cant', 'want', 'wart']\n",
1497       "['cart', 'cant', 'want', 'watt']\n",
1498       "['cart', 'cant', 'want', 'wand']\n",
1499       "['cart', 'cant', 'want', 'wane']\n",
1500       "['cart', 'cant', 'cent', 'bent']\n",
1501       "['cart', 'cant', 'cent', 'dent']\n",
1502       "['cart', 'cant', 'cent', 'gent']\n",
1503       "['cart', 'cant', 'cent', 'lent']\n",
1504       "['cart', 'cant', 'cent', 'pent']\n",
1505       "['cart', 'cant', 'cent', 'rent']\n",
1506       "['cart', 'cant', 'cent', 'sent']\n",
1507       "['cart', 'cant', 'cent', 'tent']\n",
1508       "['cart', 'cant', 'cent', 'vent']\n",
1509       "['cart', 'cant', 'cent', 'went']\n",
1510       "['cart', 'cant', 'cast', 'bast']\n",
1511       "['cart', 'cant', 'cast', 'east']\n",
1512       "['cart', 'cant', 'cast', 'fast']\n",
1513       "['cart', 'cant', 'cast', 'last']\n",
1514       "['cart', 'cant', 'cast', 'mast']\n",
1515       "['cart', 'cant', 'cast', 'past']\n",
1516       "['cart', 'cant', 'cast', 'vast']\n",
1517       "['cart', 'cant', 'cast', 'cost']\n",
1518       "['cart', 'cant', 'cast', 'cyst']\n",
1519       "['cart', 'cant', 'cast', 'case']\n",
1520       "['cart', 'cant', 'cast', 'cash']\n",
1521       "['cart', 'cant', 'cast', 'cask']\n",
1522       "['cart', 'cant', 'cane', 'bane']\n",
1523       "['cart', 'cant', 'cane', 'lane']\n",
1524       "['cart', 'cant', 'cane', 'mane']\n",
1525       "['cart', 'cant', 'cane', 'pane']\n",
1526       "['cart', 'cant', 'cane', 'sane']\n",
1527       "['cart', 'cant', 'cane', 'vane']\n",
1528       "['cart', 'cant', 'cane', 'wane']\n",
1529       "['cart', 'cant', 'cane', 'cone']\n",
1530       "['cart', 'cant', 'cane', 'cafe']\n",
1531       "['cart', 'cant', 'cane', 'cage']\n",
1532       "['cart', 'cant', 'cane', 'cake']\n",
1533       "['cart', 'cant', 'cane', 'came']\n",
1534       "['cart', 'cant', 'cane', 'cape']\n",
1535       "['cart', 'cant', 'cane', 'care']\n",
1536       "['cart', 'cant', 'cane', 'case']\n",
1537       "['cart', 'cant', 'cane', 'cave']\n",
1538       "['cart', 'cant', 'cane', 'cans']\n",
1539       "['cart', 'cant', 'cans', 'bans']\n",
1540       "['cart', 'cant', 'cans', 'fans']\n",
1541       "['cart', 'cant', 'cans', 'mans']\n",
1542       "['cart', 'cant', 'cans', 'pans']\n",
1543       "['cart', 'cant', 'cans', 'sans']\n",
1544       "['cart', 'cant', 'cans', 'tans']\n",
1545       "['cart', 'cant', 'cans', 'vans']\n"
1546      ]
1547     },
1548     {
1549      "data": {
1550       "text/plain": [
1551        "['cart', 'cant', 'cans', 'vans']"
1552       ]
1553      },
1554      "execution_count": 21,
1555      "metadata": {},
1556      "output_type": "execute_result"
1557     }
1558    ],
1559    "source": [
1560     "bfs_search('cart', 'vans', debug=True)"
1561    ]
1562   },
1563   {
1564    "cell_type": "code",
1565    "execution_count": 22,
1566    "metadata": {},
1567    "outputs": [
1568     {
1569      "data": {
1570       "text/plain": [
1571        "['cart', 'cant', 'cane', 'vane']"
1572       ]
1573      },
1574      "execution_count": 22,
1575      "metadata": {},
1576      "output_type": "execute_result"
1577     }
1578    ],
1579    "source": [
1580     "bfs_search('cart', 'vane')"
1581    ]
1582   },
1583   {
1584    "cell_type": "code",
1585    "execution_count": 23,
1586    "metadata": {},
1587    "outputs": [
1588     {
1589      "data": {
1590       "text/plain": [
1591        "['cart',\n",
1592        " 'dart',\n",
1593        " 'hart',\n",
1594        " 'mart',\n",
1595        " 'part',\n",
1596        " 'tart',\n",
1597        " 'wart',\n",
1598        " 'waft',\n",
1599        " 'daft',\n",
1600        " 'haft',\n",
1601        " 'raft',\n",
1602        " 'rift',\n",
1603        " 'gift',\n",
1604        " 'lift',\n",
1605        " 'sift',\n",
1606        " 'soft',\n",
1607        " 'loft',\n",
1608        " 'left',\n",
1609        " 'deft',\n",
1610        " 'heft',\n",
1611        " 'weft',\n",
1612        " 'welt',\n",
1613        " 'belt',\n",
1614        " 'felt',\n",
1615        " 'gelt',\n",
1616        " 'melt',\n",
1617        " 'pelt',\n",
1618        " 'peat',\n",
1619        " 'beat',\n",
1620        " 'feat',\n",
1621        " 'heat',\n",
1622        " 'meat',\n",
1623        " 'neat',\n",
1624        " 'seat',\n",
1625        " 'teat',\n",
1626        " 'that',\n",
1627        " 'chat',\n",
1628        " 'shat',\n",
1629        " 'what',\n",
1630        " 'whet',\n",
1631        " 'whit',\n",
1632        " 'chit',\n",
1633        " 'chic',\n",
1634        " 'chid',\n",
1635        " 'chin',\n",
1636        " 'shin',\n",
1637        " 'thin',\n",
1638        " 'twin',\n",
1639        " 'twig',\n",
1640        " 'swig',\n",
1641        " 'swag',\n",
1642        " 'shag',\n",
1643        " 'slag',\n",
1644        " 'flag',\n",
1645        " 'flog',\n",
1646        " 'blog',\n",
1647        " 'clog',\n",
1648        " 'slog',\n",
1649        " 'smog',\n",
1650        " 'smug',\n",
1651        " 'slug',\n",
1652        " 'plug',\n",
1653        " 'plum',\n",
1654        " 'alum',\n",
1655        " 'glum',\n",
1656        " 'slum',\n",
1657        " 'scum',\n",
1658        " 'swum',\n",
1659        " 'swam',\n",
1660        " 'scam',\n",
1661        " 'seam',\n",
1662        " 'beam',\n",
1663        " 'ream',\n",
1664        " 'team',\n",
1665        " 'tram',\n",
1666        " 'cram',\n",
1667        " 'dram',\n",
1668        " 'gram',\n",
1669        " 'pram',\n",
1670        " 'prim',\n",
1671        " 'brim',\n",
1672        " 'grim',\n",
1673        " 'trim',\n",
1674        " 'trig',\n",
1675        " 'brig',\n",
1676        " 'brag',\n",
1677        " 'crag',\n",
1678        " 'drag',\n",
1679        " 'drug',\n",
1680        " 'drub',\n",
1681        " 'grub',\n",
1682        " 'grab',\n",
1683        " 'crab',\n",
1684        " 'drab',\n",
1685        " 'draw',\n",
1686        " 'craw',\n",
1687        " 'claw',\n",
1688        " 'flaw',\n",
1689        " 'slaw',\n",
1690        " 'slew',\n",
1691        " 'blew',\n",
1692        " 'clew',\n",
1693        " 'flew',\n",
1694        " 'flow',\n",
1695        " 'blow',\n",
1696        " 'glow',\n",
1697        " 'slow',\n",
1698        " 'scow',\n",
1699        " 'show',\n",
1700        " 'chow',\n",
1701        " 'crow',\n",
1702        " 'brow',\n",
1703        " 'grow',\n",
1704        " 'prow',\n",
1705        " 'prod',\n",
1706        " 'trod',\n",
1707        " 'trot',\n",
1708        " 'toot',\n",
1709        " 'boot',\n",
1710        " 'coot',\n",
1711        " 'foot',\n",
1712        " 'hoot',\n",
1713        " 'loot',\n",
1714        " 'moot',\n",
1715        " 'root',\n",
1716        " 'soot',\n",
1717        " 'shot',\n",
1718        " 'slot',\n",
1719        " 'blot',\n",
1720        " 'clot',\n",
1721        " 'plot',\n",
1722        " 'plod',\n",
1723        " 'clod',\n",
1724        " 'clad',\n",
1725        " 'glad',\n",
1726        " 'goad',\n",
1727        " 'load',\n",
1728        " 'road',\n",
1729        " 'toad',\n",
1730        " 'toed',\n",
1731        " 'coed',\n",
1732        " 'hoed',\n",
1733        " 'heed',\n",
1734        " 'deed',\n",
1735        " 'feed',\n",
1736        " 'geed',\n",
1737        " 'need',\n",
1738        " 'peed',\n",
1739        " 'reed',\n",
1740        " 'seed',\n",
1741        " 'teed',\n",
1742        " 'weed',\n",
1743        " 'weld',\n",
1744        " 'geld',\n",
1745        " 'held',\n",
1746        " 'meld',\n",
1747        " 'veld',\n",
1748        " 'vend',\n",
1749        " 'bend',\n",
1750        " 'fend',\n",
1751        " 'lend',\n",
1752        " 'mend',\n",
1753        " 'rend',\n",
1754        " 'send',\n",
1755        " 'tend',\n",
1756        " 'wend',\n",
1757        " 'wand',\n",
1758        " 'band',\n",
1759        " 'hand',\n",
1760        " 'land',\n",
1761        " 'sand',\n",
1762        " 'said',\n",
1763        " 'laid',\n",
1764        " 'maid',\n",
1765        " 'paid',\n",
1766        " 'raid',\n",
1767        " 'rail',\n",
1768        " 'bail',\n",
1769        " 'fail',\n",
1770        " 'hail',\n",
1771        " 'jail',\n",
1772        " 'mail',\n",
1773        " 'nail',\n",
1774        " 'pail',\n",
1775        " 'sail',\n",
1776        " 'tail',\n",
1777        " 'wail',\n",
1778        " 'wall',\n",
1779        " 'ball',\n",
1780        " 'call',\n",
1781        " 'fall',\n",
1782        " 'gall',\n",
1783        " 'hall',\n",
1784        " 'mall',\n",
1785        " 'pall',\n",
1786        " 'tall',\n",
1787        " 'tell',\n",
1788        " 'bell',\n",
1789        " 'cell',\n",
1790        " 'dell',\n",
1791        " 'fell',\n",
1792        " 'hell',\n",
1793        " 'jell',\n",
1794        " 'sell',\n",
1795        " 'well',\n",
1796        " 'yell',\n",
1797        " 'yelp',\n",
1798        " 'help',\n",
1799        " 'kelp',\n",
1800        " 'keep',\n",
1801        " 'beep',\n",
1802        " 'deep',\n",
1803        " 'jeep',\n",
1804        " 'peep',\n",
1805        " 'seep',\n",
1806        " 'veep',\n",
1807        " 'weep',\n",
1808        " 'week',\n",
1809        " 'geek',\n",
1810        " 'leek',\n",
1811        " 'meek',\n",
1812        " 'peek',\n",
1813        " 'reek',\n",
1814        " 'seek',\n",
1815        " 'seem',\n",
1816        " 'deem',\n",
1817        " 'teem',\n",
1818        " 'them',\n",
1819        " 'thee',\n",
1820        " 'tree',\n",
1821        " 'free',\n",
1822        " 'flee',\n",
1823        " 'glee',\n",
1824        " 'glue',\n",
1825        " 'blue',\n",
1826        " 'clue',\n",
1827        " 'flue',\n",
1828        " 'slue',\n",
1829        " 'sloe',\n",
1830        " 'aloe',\n",
1831        " 'floe',\n",
1832        " 'flop',\n",
1833        " 'clop',\n",
1834        " 'glop',\n",
1835        " 'plop',\n",
1836        " 'slop',\n",
1837        " 'shop',\n",
1838        " 'chop',\n",
1839        " 'coop',\n",
1840        " 'goop',\n",
1841        " 'hoop',\n",
1842        " 'loop',\n",
1843        " 'poop',\n",
1844        " 'prop',\n",
1845        " 'crop',\n",
1846        " 'drop',\n",
1847        " 'drip',\n",
1848        " 'grip',\n",
1849        " 'trip',\n",
1850        " 'trap',\n",
1851        " 'tray',\n",
1852        " 'bray',\n",
1853        " 'dray',\n",
1854        " 'fray',\n",
1855        " 'gray',\n",
1856        " 'pray',\n",
1857        " 'play',\n",
1858        " 'clay',\n",
1859        " 'flay',\n",
1860        " 'slay',\n",
1861        " 'spay',\n",
1862        " 'stay',\n",
1863        " 'sway',\n",
1864        " 'away',\n",
1865        " 'awry',\n",
1866        " 'aery',\n",
1867        " 'eery',\n",
1868        " 'very',\n",
1869        " 'vary',\n",
1870        " 'nary',\n",
1871        " 'wary',\n",
1872        " 'wiry',\n",
1873        " 'airy',\n",
1874        " 'airs',\n",
1875        " 'firs',\n",
1876        " 'sirs',\n",
1877        " 'sics',\n",
1878        " 'tics',\n",
1879        " 'ties',\n",
1880        " 'dies',\n",
1881        " 'hies',\n",
1882        " 'lies',\n",
1883        " 'pies',\n",
1884        " 'vies',\n",
1885        " 'vied',\n",
1886        " 'died',\n",
1887        " 'hied',\n",
1888        " 'lied',\n",
1889        " 'pied',\n",
1890        " 'tied',\n",
1891        " 'tier',\n",
1892        " 'bier',\n",
1893        " 'pier',\n",
1894        " 'peer',\n",
1895        " 'beer',\n",
1896        " 'deer',\n",
1897        " 'jeer',\n",
1898        " 'leer',\n",
1899        " 'seer',\n",
1900        " 'veer',\n",
1901        " 'weer',\n",
1902        " 'wear',\n",
1903        " 'bear',\n",
1904        " 'dear',\n",
1905        " 'fear',\n",
1906        " 'gear',\n",
1907        " 'hear',\n",
1908        " 'near',\n",
1909        " 'pear',\n",
1910        " 'rear',\n",
1911        " 'sear',\n",
1912        " 'tear',\n",
1913        " 'year',\n",
1914        " 'yeah',\n",
1915        " 'yeas',\n",
1916        " 'leas',\n",
1917        " 'peas',\n",
1918        " 'seas',\n",
1919        " 'teas',\n",
1920        " 'tees',\n",
1921        " 'bees',\n",
1922        " 'fees',\n",
1923        " 'gees',\n",
1924        " 'lees',\n",
1925        " 'pees',\n",
1926        " 'sees',\n",
1927        " 'wees',\n",
1928        " 'woes',\n",
1929        " 'does',\n",
1930        " 'foes',\n",
1931        " 'goes',\n",
1932        " 'hoes',\n",
1933        " 'noes',\n",
1934        " 'roes',\n",
1935        " 'toes',\n",
1936        " 'togs',\n",
1937        " 'bogs',\n",
1938        " 'cogs',\n",
1939        " 'dogs',\n",
1940        " 'fogs',\n",
1941        " 'hogs',\n",
1942        " 'jogs',\n",
1943        " 'logs',\n",
1944        " 'lags',\n",
1945        " 'bags',\n",
1946        " 'fags',\n",
1947        " 'gags',\n",
1948        " 'hags',\n",
1949        " 'jags',\n",
1950        " 'nags',\n",
1951        " 'rags',\n",
1952        " 'sags',\n",
1953        " 'tags',\n",
1954        " 'wags',\n",
1955        " 'wigs',\n",
1956        " 'digs',\n",
1957        " 'figs',\n",
1958        " 'gigs',\n",
1959        " 'jigs',\n",
1960        " 'pigs',\n",
1961        " 'rigs',\n",
1962        " 'rugs',\n",
1963        " 'bugs',\n",
1964        " 'hugs',\n",
1965        " 'jugs',\n",
1966        " 'lugs',\n",
1967        " 'mugs',\n",
1968        " 'pugs',\n",
1969        " 'tugs',\n",
1970        " 'tubs',\n",
1971        " 'cubs',\n",
1972        " 'dubs',\n",
1973        " 'hubs',\n",
1974        " 'nubs',\n",
1975        " 'pubs',\n",
1976        " 'rubs',\n",
1977        " 'subs',\n",
1978        " 'sobs',\n",
1979        " 'bobs',\n",
1980        " 'cobs',\n",
1981        " 'fobs',\n",
1982        " 'gobs',\n",
1983        " 'hobs',\n",
1984        " 'jobs',\n",
1985        " 'lobs',\n",
1986        " 'mobs',\n",
1987        " 'robs',\n",
1988        " 'ribs',\n",
1989        " 'bibs',\n",
1990        " 'fibs',\n",
1991        " 'jibs',\n",
1992        " 'nibs',\n",
1993        " 'nabs',\n",
1994        " 'cabs',\n",
1995        " 'dabs',\n",
1996        " 'gabs',\n",
1997        " 'jabs',\n",
1998        " 'labs',\n",
1999        " 'tabs',\n",
2000        " 'tads',\n",
2001        " 'cads',\n",
2002        " 'dads',\n",
2003        " 'fads',\n",
2004        " 'gads',\n",
2005        " 'lads',\n",
2006        " 'mads',\n",
2007        " 'pads',\n",
2008        " 'wads',\n",
2009        " 'weds',\n",
2010        " 'beds',\n",
2011        " 'feds',\n",
2012        " 'reds',\n",
2013        " 'rids',\n",
2014        " 'aids',\n",
2015        " 'bids',\n",
2016        " 'kids',\n",
2017        " 'lids',\n",
2018        " 'lips',\n",
2019        " 'dips',\n",
2020        " 'hips',\n",
2021        " 'nips',\n",
2022        " 'pips',\n",
2023        " 'rips',\n",
2024        " 'sips',\n",
2025        " 'tips',\n",
2026        " 'yips',\n",
2027        " 'zips',\n",
2028        " 'zaps',\n",
2029        " 'caps',\n",
2030        " 'gaps',\n",
2031        " 'laps',\n",
2032        " 'maps',\n",
2033        " 'naps',\n",
2034        " 'paps',\n",
2035        " 'raps',\n",
2036        " 'saps',\n",
2037        " 'taps',\n",
2038        " 'yaps',\n",
2039        " 'yeps',\n",
2040        " 'peps',\n",
2041        " 'reps',\n",
2042        " 'refs',\n",
2043        " 'reis',\n",
2044        " 'leis',\n",
2045        " 'legs',\n",
2046        " 'begs',\n",
2047        " 'kegs',\n",
2048        " 'megs',\n",
2049        " 'pegs',\n",
2050        " 'pens',\n",
2051        " 'dens',\n",
2052        " 'fens',\n",
2053        " 'hens',\n",
2054        " 'kens',\n",
2055        " 'lens',\n",
2056        " 'tens',\n",
2057        " 'wens',\n",
2058        " 'yens',\n",
2059        " 'yews',\n",
2060        " 'hews',\n",
2061        " 'mews',\n",
2062        " 'news',\n",
2063        " 'pews',\n",
2064        " 'sews',\n",
2065        " 'saws',\n",
2066        " 'caws',\n",
2067        " 'haws',\n",
2068        " 'jaws',\n",
2069        " 'laws',\n",
2070        " 'maws',\n",
2071        " 'paws',\n",
2072        " 'yaws',\n",
2073        " 'yaks',\n",
2074        " 'oaks',\n",
2075        " 'oafs',\n",
2076        " 'oars',\n",
2077        " 'bars',\n",
2078        " 'cars',\n",
2079        " 'ears',\n",
2080        " 'jars',\n",
2081        " 'mars',\n",
2082        " 'pars',\n",
2083        " 'tars',\n",
2084        " 'wars',\n",
2085        " 'ways',\n",
2086        " 'bays',\n",
2087        " 'days',\n",
2088        " 'gays',\n",
2089        " 'hays',\n",
2090        " 'jays',\n",
2091        " 'lays',\n",
2092        " 'nays',\n",
2093        " 'pays',\n",
2094        " 'rays',\n",
2095        " 'says',\n",
2096        " 'sacs',\n",
2097        " 'secs',\n",
2098        " 'sets',\n",
2099        " 'bets',\n",
2100        " 'gets',\n",
2101        " 'jets',\n",
2102        " 'lets',\n",
2103        " 'nets',\n",
2104        " 'pets',\n",
2105        " 'vets',\n",
2106        " 'wets',\n",
2107        " 'wits',\n",
2108        " 'bits',\n",
2109        " 'fits',\n",
2110        " 'hits',\n",
2111        " 'kits',\n",
2112        " 'nits',\n",
2113        " 'pits',\n",
2114        " 'sits',\n",
2115        " 'tits',\n",
2116        " 'tats',\n",
2117        " 'bats',\n",
2118        " 'cats',\n",
2119        " 'eats',\n",
2120        " 'fats',\n",
2121        " 'hats',\n",
2122        " 'lats',\n",
2123        " 'mats',\n",
2124        " 'oats',\n",
2125        " 'pats',\n",
2126        " 'rats',\n",
2127        " 'vats',\n",
2128        " 'vans',\n",
2129        " 'bans',\n",
2130        " 'cans',\n",
2131        " 'fans',\n",
2132        " 'mans',\n",
2133        " 'pans',\n",
2134        " 'sans',\n",
2135        " 'tans',\n",
2136        " 'tins',\n",
2137        " 'bins',\n",
2138        " 'dins',\n",
2139        " 'fins',\n",
2140        " 'gins',\n",
2141        " 'pins',\n",
2142        " 'sins',\n",
2143        " 'wins',\n",
2144        " 'wind',\n",
2145        " 'bind',\n",
2146        " 'find',\n",
2147        " 'hind',\n",
2148        " 'kind',\n",
2149        " 'mind',\n",
2150        " 'rind',\n",
2151        " 'ring',\n",
2152        " 'ding',\n",
2153        " 'king',\n",
2154        " 'ping',\n",
2155        " 'sing',\n",
2156        " 'ting',\n",
2157        " 'wing',\n",
2158        " 'wine',\n",
2159        " 'dine',\n",
2160        " 'fine',\n",
2161        " 'line',\n",
2162        " 'mine',\n",
2163        " 'nine',\n",
2164        " 'pine',\n",
2165        " 'sine',\n",
2166        " 'tine',\n",
2167        " 'vine',\n",
2168        " 'vane']"
2169       ]
2170      },
2171      "execution_count": 23,
2172      "metadata": {},
2173      "output_type": "execute_result"
2174     }
2175    ],
2176    "source": [
2177     "dfs_search('cart', 'vane')"
2178    ]
2179   },
2180   {
2181    "cell_type": "code",
2182    "execution_count": 24,
2183    "metadata": {
2184     "collapsed": true
2185    },
2186    "outputs": [],
2187    "source": [
2188     "def astar_search(start, goal, debug=False):\n",
2189     "    agenda = [(distance(start, goal), [start])]\n",
2190     "    heapq.heapify(agenda)\n",
2191     "    finished = False\n",
2192     "    while not finished and agenda:\n",
2193     "        _, current = heapq.heappop(agenda)\n",
2194     "        if debug:\n",
2195     "            print(current)\n",
2196     "        if current[-1] == goal:\n",
2197     "            finished = True\n",
2198     "        else:\n",
2199     "            successors = extend(current)\n",
2200     "            for s in successors:\n",
2201     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
2202     "    if agenda:\n",
2203     "        return current\n",
2204     "    else:\n",
2205     "        return None        "
2206    ]
2207   },
2208   {
2209    "cell_type": "code",
2210    "execution_count": 25,
2211    "metadata": {},
2212    "outputs": [
2213     {
2214      "name": "stdout",
2215      "output_type": "stream",
2216      "text": [
2217       "['cart']\n",
2218       "['cart', 'cant']\n",
2219       "['cart', 'cant', 'cane']\n",
2220       "['cart', 'cant', 'cane', 'vane']\n"
2221      ]
2222     },
2223     {
2224      "data": {
2225       "text/plain": [
2226        "['cart', 'cant', 'cane', 'vane']"
2227       ]
2228      },
2229      "execution_count": 25,
2230      "metadata": {},
2231      "output_type": "execute_result"
2232     }
2233    ],
2234    "source": [
2235     "astar_search('cart', 'vane', debug=True)"
2236    ]
2237   },
2238   {
2239    "cell_type": "code",
2240    "execution_count": 26,
2241    "metadata": {
2242     "collapsed": true
2243    },
2244    "outputs": [],
2245    "source": [
2246     "def astar_search_closed(start, goal, debug=False):\n",
2247     "    agenda = [(distance(start, goal), [start])]\n",
2248     "    heapq.heapify(agenda)\n",
2249     "    closed = set()\n",
2250     "    finished = False\n",
2251     "    while not finished and agenda:\n",
2252     "        _, current = heapq.heappop(agenda)\n",
2253     "        if debug:\n",
2254     "            print(current)\n",
2255     "        if current[-1] == goal:\n",
2256     "            finished = True\n",
2257     "        else:\n",
2258     "            closed.add(current[-1])\n",
2259     "            successors = extend(current, closed)\n",
2260     "            for s in successors:\n",
2261     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
2262     "    if agenda:\n",
2263     "        return current\n",
2264     "    else:\n",
2265     "        return None        "
2266    ]
2267   },
2268   {
2269    "cell_type": "code",
2270    "execution_count": 27,
2271    "metadata": {},
2272    "outputs": [
2273     {
2274      "name": "stdout",
2275      "output_type": "stream",
2276      "text": [
2277       "['cart']\n",
2278       "['cart', 'cant']\n",
2279       "['cart', 'cant', 'cane']\n",
2280       "['cart', 'cant', 'cane', 'vane']\n"
2281      ]
2282     },
2283     {
2284      "data": {
2285       "text/plain": [
2286        "['cart', 'cant', 'cane', 'vane']"
2287       ]
2288      },
2289      "execution_count": 27,
2290      "metadata": {},
2291      "output_type": "execute_result"
2292     }
2293    ],
2294    "source": [
2295     "astar_search_closed('cart', 'vane', debug=True)"
2296    ]
2297   },
2298   {
2299    "cell_type": "markdown",
2300    "metadata": {},
2301    "source": [
2302     "# Mutually-reachable sets\n",
2303     "\n",
2304     "Find the transitive closure of the `neighbours` relation, so we can see which words can be transformed into which other words."
2305    ]
2306   },
2307   {
2308    "cell_type": "code",
2309    "execution_count": 28,
2310    "metadata": {},
2311    "outputs": [
2312     {
2313      "data": {
2314       "text/plain": [
2315        "94"
2316       ]
2317      },
2318      "execution_count": 28,
2319      "metadata": {},
2320      "output_type": "execute_result"
2321     }
2322    ],
2323    "source": [
2324     "candidates = [set([k] + neighbours[k]) for k in neighbours]\n",
2325     "reachables = []\n",
2326     "while candidates:\n",
2327     "    current = set(candidates.pop())\n",
2328     "    altered = False\n",
2329     "    for other in candidates:\n",
2330     "        if current.intersection(other):\n",
2331     "            altered = True\n",
2332     "            current.update(other)\n",
2333     "            candidates.remove(other)\n",
2334     "    if altered:\n",
2335     "        candidates.append(current)\n",
2336     "    else:\n",
2337     "        reachables.append(current)\n",
2338     "\n",
2339     "len(reachables)"
2340    ]
2341   },
2342   {
2343    "cell_type": "code",
2344    "execution_count": 29,
2345    "metadata": {},
2346    "outputs": [
2347     {
2348      "data": {
2349       "text/plain": [
2350        "2204"
2351       ]
2352      },
2353      "execution_count": 29,
2354      "metadata": {},
2355      "output_type": "execute_result"
2356     }
2357    ],
2358    "source": [
2359     "len(max(reachables, key=len))"
2360    ]
2361   },
2362   {
2363    "cell_type": "code",
2364    "execution_count": 30,
2365    "metadata": {},
2366    "outputs": [
2367     {
2368      "data": {
2369       "text/plain": [
2370        "1"
2371       ]
2372      },
2373      "execution_count": 30,
2374      "metadata": {},
2375      "output_type": "execute_result"
2376     }
2377    ],
2378    "source": [
2379     "len(min(reachables, key=len))"
2380    ]
2381   },
2382   {
2383    "cell_type": "code",
2384    "execution_count": 31,
2385    "metadata": {
2386     "scrolled": true
2387    },
2388    "outputs": [
2389     {
2390      "data": {
2391       "text/plain": [
2392        "Counter({1: 75, 2: 6, 3: 7, 4: 2, 5: 2, 6: 1, 2204: 1})"
2393       ]
2394      },
2395      "execution_count": 31,
2396      "metadata": {},
2397      "output_type": "execute_result"
2398     }
2399    ],
2400    "source": [
2401     "collections.Counter(len(r) for r in reachables)"
2402    ]
2403   },
2404   {
2405    "cell_type": "code",
2406    "execution_count": 32,
2407    "metadata": {},
2408    "outputs": [
2409     {
2410      "data": {
2411       "text/plain": [
2412        "[5]"
2413       ]
2414      },
2415      "execution_count": 32,
2416      "metadata": {},
2417      "output_type": "execute_result"
2418     }
2419    ],
2420    "source": [
2421     "[len(r) for r in reachables if 'abbe' in r]"
2422    ]
2423   },
2424   {
2425    "cell_type": "code",
2426    "execution_count": 33,
2427    "metadata": {},
2428    "outputs": [
2429     {
2430      "data": {
2431       "text/plain": [
2432        "[{'abbe', 'able', 'ably', 'ally', 'axle'}]"
2433       ]
2434      },
2435      "execution_count": 33,
2436      "metadata": {},
2437      "output_type": "execute_result"
2438     }
2439    ],
2440    "source": [
2441     "[r for r in reachables if 'abbe' in r]"
2442    ]
2443   },
2444   {
2445    "cell_type": "code",
2446    "execution_count": 34,
2447    "metadata": {},
2448    "outputs": [
2449     {
2450      "data": {
2451       "text/plain": [
2452        "['buns', 'bunk', 'punk']"
2453       ]
2454      },
2455      "execution_count": 34,
2456      "metadata": {},
2457      "output_type": "execute_result"
2458     }
2459    ],
2460    "source": [
2461     "astar_search('buns', 'punk')"
2462    ]
2463   },
2464   {
2465    "cell_type": "code",
2466    "execution_count": 35,
2467    "metadata": {
2468     "collapsed": true
2469    },
2470    "outputs": [],
2471    "source": [
2472     "for a in reachables:\n",
2473     "    for b in reachables:\n",
2474     "        if a != b:\n",
2475     "            if not a.isdisjoint(b):\n",
2476     "                print(a, b)"
2477    ]
2478   },
2479   {
2480    "cell_type": "code",
2481    "execution_count": 36,
2482    "metadata": {
2483     "collapsed": true
2484    },
2485    "outputs": [],
2486    "source": [
2487     "# longest_chain = []\n",
2488     "# with open('all-chains-4.txt', 'w', 1) as f:\n",
2489     "#     for ws in reachables:\n",
2490     "#         for s in ws:\n",
2491     "#             for t in ws:\n",
2492     "#                 if s < t:\n",
2493     "#                     chain = astar_search(s, t)\n",
2494     "#                     if chain:\n",
2495     "#                         f.write('{}\\n'.format(chain))\n",
2496     "#                         if len(chain) > len(longest_chain):\n",
2497     "#                             longest_chain = chain\n",
2498     "\n",
2499     "# longest_chain"
2500    ]
2501   },
2502   {
2503    "cell_type": "code",
2504    "execution_count": 37,
2505    "metadata": {
2506     "collapsed": true
2507    },
2508    "outputs": [],
2509    "source": [
2510     "bigset = max(reachables, key=len)"
2511    ]
2512   },
2513   {
2514    "cell_type": "code",
2515    "execution_count": 38,
2516    "metadata": {},
2517    "outputs": [
2518     {
2519      "name": "stdout",
2520      "output_type": "stream",
2521      "text": [
2522       "['drip', 'grip', 'grit', 'gait', 'bait', 'bast', 'base', 'babe']\n",
2523       "['cape', 'cope', 'dope', 'dole', 'dolt']\n",
2524       "['laze', 'late', 'lats', 'pats']\n",
2525       "['zest', 'best', 'bust', 'buss', 'buds', 'suds']\n",
2526       "['gape', 'gaps', 'paps', 'peps', 'pees', 'peel']\n",
2527       "['yogi', 'yoga', 'toga', 'togs', 'tors', 'tore']\n",
2528       "['flux', 'flex', 'fled', 'feed', 'fees', 'foes', 'toes', 'toys']\n",
2529       "['bike', 'bake', 'base', 'bast', 'best', 'beet', 'feet']\n",
2530       "['tows', 'lows', 'laws', 'lams', 'lame']\n",
2531       "['jock', 'pock', 'pork', 'pore', 'pure']\n",
2532       "['tabu', 'tabs', 'cabs', 'caws', 'cows', 'cowl', 'coil', 'coif']\n",
2533       "['reek', 'week', 'wees', 'weds', 'wads', 'wadi']\n",
2534       "['gene', 'gone', 'gong', 'song']\n",
2535       "['mete', 'mate', 'bate', 'bats', 'baas', 'bras', 'brag', 'crag', 'cram']\n",
2536       "['gnus', 'anus', 'ants', 'acts', 'aces', 'ayes', 'byes', 'bees', 'been', 'teen']\n",
2537       "['comb', 'come', 'core', 'corn', 'torn', 'tern']\n",
2538       "['ouch', 'much', 'muck', 'buck', 'beck', 'beak', 'beat', 'teat', 'that', 'than', 'khan']\n",
2539       "['rids', 'reds', 'reps', 'peps', 'peas', 'peal', 'deal']\n",
2540       "['calm', 'balm', 'bald', 'bold', 'bolt', 'bout', 'tout']\n",
2541       "['toed', 'toad', 'goad', 'grad', 'gray', 'grey', 'grew']\n"
2542      ]
2543     }
2544    ],
2545    "source": [
2546     "for _ in range(20):\n",
2547     "    start, goal = random.sample(bigset, 2)\n",
2548     "    print(astar_search_closed(start, goal))"
2549    ]
2550   },
2551   {
2552    "cell_type": "code",
2553    "execution_count": 39,
2554    "metadata": {},
2555    "outputs": [
2556     {
2557      "data": {
2558       "text/plain": [
2559        "['cops', 'coos', 'coon', 'coin', 'chin', 'thin', 'this', 'thus', 'thug']"
2560       ]
2561      },
2562      "execution_count": 39,
2563      "metadata": {},
2564      "output_type": "execute_result"
2565     }
2566    ],
2567    "source": [
2568     "astar_search('cops', 'thug')"
2569    ]
2570   },
2571   {
2572    "cell_type": "code",
2573    "execution_count": 40,
2574    "metadata": {},
2575    "outputs": [
2576     {
2577      "data": {
2578       "text/plain": [
2579        "[2204]"
2580       ]
2581      },
2582      "execution_count": 40,
2583      "metadata": {},
2584      "output_type": "execute_result"
2585     }
2586    ],
2587    "source": [
2588     "[len(r) for r in reachables if 'love' in r if 'hate' in r]"
2589    ]
2590   },
2591   {
2592    "cell_type": "code",
2593    "execution_count": 41,
2594    "metadata": {},
2595    "outputs": [
2596     {
2597      "data": {
2598       "text/plain": [
2599        "[2204]"
2600       ]
2601      },
2602      "execution_count": 41,
2603      "metadata": {},
2604      "output_type": "execute_result"
2605     }
2606    ],
2607    "source": [
2608     "[len(r) for r in reachables if 'stay' in r ]"
2609    ]
2610   },
2611   {
2612    "cell_type": "code",
2613    "execution_count": 42,
2614    "metadata": {},
2615    "outputs": [
2616     {
2617      "data": {
2618       "text/plain": [
2619        "['hate', 'have', 'hove', 'love']"
2620       ]
2621      },
2622      "execution_count": 42,
2623      "metadata": {},
2624      "output_type": "execute_result"
2625     }
2626    ],
2627    "source": [
2628     "astar_search('hate', 'love')"
2629    ]
2630   },
2631   {
2632    "cell_type": "code",
2633    "execution_count": 43,
2634    "metadata": {},
2635    "outputs": [
2636     {
2637      "data": {
2638       "text/plain": [
2639        "['wars', 'ware', 'wave', 'wove', 'love']"
2640       ]
2641      },
2642      "execution_count": 43,
2643      "metadata": {},
2644      "output_type": "execute_result"
2645     }
2646    ],
2647    "source": [
2648     "astar_search('wars', 'love')"
2649    ]
2650   },
2651   {
2652    "cell_type": "code",
2653    "execution_count": 44,
2654    "metadata": {},
2655    "outputs": [
2656     {
2657      "name": "stdout",
2658      "output_type": "stream",
2659      "text": [
2660       "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
2661       "Wall time: 212 µs\n"
2662      ]
2663     },
2664     {
2665      "data": {
2666       "text/plain": [
2667        "5"
2668       ]
2669      },
2670      "execution_count": 44,
2671      "metadata": {},
2672      "output_type": "execute_result"
2673     }
2674    ],
2675    "source": [
2676     "%time len(astar_search('wars', 'love'))"
2677    ]
2678   },
2679   {
2680    "cell_type": "code",
2681    "execution_count": 45,
2682    "metadata": {},
2683    "outputs": [
2684     {
2685      "name": "stdout",
2686      "output_type": "stream",
2687      "text": [
2688       "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
2689       "Wall time: 203 µs\n"
2690      ]
2691     },
2692     {
2693      "data": {
2694       "text/plain": [
2695        "5"
2696       ]
2697      },
2698      "execution_count": 45,
2699      "metadata": {},
2700      "output_type": "execute_result"
2701     }
2702    ],
2703    "source": [
2704     "%time len(astar_search_closed('wars', 'love'))"
2705    ]
2706   },
2707   {
2708    "cell_type": "code",
2709    "execution_count": 46,
2710    "metadata": {},
2711    "outputs": [
2712     {
2713      "name": "stdout",
2714      "output_type": "stream",
2715      "text": [
2716       "CPU times: user 24 ms, sys: 0 ns, total: 24 ms\n",
2717       "Wall time: 23.2 ms\n"
2718      ]
2719     },
2720     {
2721      "data": {
2722       "text/plain": [
2723        "404"
2724       ]
2725      },
2726      "execution_count": 46,
2727      "metadata": {},
2728      "output_type": "execute_result"
2729     }
2730    ],
2731    "source": [
2732     "%time len(dfs_search('wars', 'love'))"
2733    ]
2734   },
2735   {
2736    "cell_type": "code",
2737    "execution_count": 47,
2738    "metadata": {
2739     "collapsed": true
2740    },
2741    "outputs": [],
2742    "source": [
2743     "# %time len(bfs_search('wars', 'love'))"
2744    ]
2745   },
2746   {
2747    "cell_type": "code",
2748    "execution_count": 48,
2749    "metadata": {},
2750    "outputs": [
2751     {
2752      "name": "stdout",
2753      "output_type": "stream",
2754      "text": [
2755       "CPU times: user 332 ms, sys: 0 ns, total: 332 ms\n",
2756       "Wall time: 331 ms\n"
2757      ]
2758     },
2759     {
2760      "data": {
2761       "text/plain": [
2762        "5"
2763       ]
2764      },
2765      "execution_count": 48,
2766      "metadata": {},
2767      "output_type": "execute_result"
2768     }
2769    ],
2770    "source": [
2771     "%time len(bfs_search_closed('wars', 'love'))"
2772    ]
2773   },
2774   {
2775    "cell_type": "code",
2776    "execution_count": 49,
2777    "metadata": {},
2778    "outputs": [
2779     {
2780      "data": {
2781       "text/plain": [
2782        "['fear', 'feat', 'fest', 'lest', 'lost', 'lose', 'love']"
2783       ]
2784      },
2785      "execution_count": 49,
2786      "metadata": {},
2787      "output_type": "execute_result"
2788     }
2789    ],
2790    "source": [
2791     "astar_search('fear', 'love')"
2792    ]
2793   },
2794   {
2795    "cell_type": "code",
2796    "execution_count": 50,
2797    "metadata": {},
2798    "outputs": [
2799     {
2800      "data": {
2801       "text/plain": [
2802        "['fail', 'fall', 'pall', 'pals', 'pass']"
2803       ]
2804      },
2805      "execution_count": 50,
2806      "metadata": {},
2807      "output_type": "execute_result"
2808     }
2809    ],
2810    "source": [
2811     "astar_search('fail', 'pass')"
2812    ]
2813   },
2814   {
2815    "cell_type": "code",
2816    "execution_count": 51,
2817    "metadata": {},
2818    "outputs": [
2819     {
2820      "data": {
2821       "text/plain": [
2822        "['star', 'soar', 'boar', 'boor', 'boon', 'born']"
2823       ]
2824      },
2825      "execution_count": 51,
2826      "metadata": {},
2827      "output_type": "execute_result"
2828     }
2829    ],
2830    "source": [
2831     "astar_search('star', 'born')"
2832    ]
2833   },
2834   {
2835    "cell_type": "code",
2836    "execution_count": 52,
2837    "metadata": {},
2838    "outputs": [
2839     {
2840      "data": {
2841       "text/plain": [
2842        "['open',\n",
2843        " 'oven',\n",
2844        " 'even',\n",
2845        " 'eves',\n",
2846        " 'eyes',\n",
2847        " 'byes',\n",
2848        " 'bees',\n",
2849        " 'begs',\n",
2850        " 'bags',\n",
2851        " 'bass',\n",
2852        " 'pass']"
2853       ]
2854      },
2855      "execution_count": 52,
2856      "metadata": {},
2857      "output_type": "execute_result"
2858     }
2859    ],
2860    "source": [
2861     "astar_search('open', 'pass')"
2862    ]
2863   },
2864   {
2865    "cell_type": "code",
2866    "execution_count": 53,
2867    "metadata": {},
2868    "outputs": [
2869     {
2870      "data": {
2871       "text/plain": [
2872        "['bass',\n",
2873        " 'lass',\n",
2874        " 'mass',\n",
2875        " 'sass',\n",
2876        " 'puss',\n",
2877        " 'pads',\n",
2878        " 'pals',\n",
2879        " 'pans',\n",
2880        " 'paps',\n",
2881        " 'pars',\n",
2882        " 'pats',\n",
2883        " 'paws',\n",
2884        " 'pays',\n",
2885        " 'past']"
2886       ]
2887      },
2888      "execution_count": 53,
2889      "metadata": {},
2890      "output_type": "execute_result"
2891     }
2892    ],
2893    "source": [
2894     "neighbours['pass']"
2895    ]
2896   },
2897   {
2898    "cell_type": "code",
2899    "execution_count": 54,
2900    "metadata": {},
2901    "outputs": [
2902     {
2903      "data": {
2904       "text/plain": [
2905        "[1]"
2906       ]
2907      },
2908      "execution_count": 54,
2909      "metadata": {},
2910      "output_type": "execute_result"
2911     }
2912    ],
2913    "source": [
2914     "[len(r) for r in reachables if 'exam' in r]"
2915    ]
2916   },
2917   {
2918    "cell_type": "code",
2919    "execution_count": 55,
2920    "metadata": {},
2921    "outputs": [
2922     {
2923      "data": {
2924       "text/plain": [
2925        "[2204]"
2926       ]
2927      },
2928      "execution_count": 55,
2929      "metadata": {},
2930      "output_type": "execute_result"
2931     }
2932    ],
2933    "source": [
2934     "[len(r) for r in reachables if 'star' in r if 'born' in r]"
2935    ]
2936   },
2937   {
2938    "cell_type": "code",
2939    "execution_count": 56,
2940    "metadata": {},
2941    "outputs": [
2942     {
2943      "name": "stdout",
2944      "output_type": "stream",
2945      "text": [
2946       "1 loop, best of 3: 8.08 s per loop\n"
2947      ]
2948     }
2949    ],
2950    "source": [
2951     "%%timeit\n",
2952     "astar_search('bats', 'exit')"
2953    ]
2954   },
2955   {
2956    "cell_type": "code",
2957    "execution_count": 57,
2958    "metadata": {},
2959    "outputs": [
2960     {
2961      "name": "stdout",
2962      "output_type": "stream",
2963      "text": [
2964       "10 loops, best of 3: 131 ms per loop\n"
2965      ]
2966     }
2967    ],
2968    "source": [
2969     "%%timeit\n",
2970     "astar_search_closed('bats', 'exit')"
2971    ]
2972   },
2973   {
2974    "cell_type": "code",
2975    "execution_count": 58,
2976    "metadata": {},
2977    "outputs": [
2978     {
2979      "data": {
2980       "text/plain": [
2981        "['bats',\n",
2982        " 'bans',\n",
2983        " 'band',\n",
2984        " 'sand',\n",
2985        " 'said',\n",
2986        " 'skid',\n",
2987        " 'skit',\n",
2988        " 'smit',\n",
2989        " 'emit',\n",
2990        " 'exit']"
2991       ]
2992      },
2993      "execution_count": 58,
2994      "metadata": {},
2995      "output_type": "execute_result"
2996     }
2997    ],
2998    "source": [
2999     "astar_search_closed('bats', 'exit')"
3000    ]
3001   },
3002   {
3003    "cell_type": "code",
3004    "execution_count": 68,
3005    "metadata": {},
3006    "outputs": [],
3007    "source": [
3008     "# solutions = {}\n",
3009     "# for _ in range(10000):\n",
3010     "#     start, goal = random.sample(bigset, 2)\n",
3011     "#     solution = astar_search_closed(start, goal)\n",
3012     "#     sl = len(solution)\n",
3013     "#     if sl not in solutions:\n",
3014     "#         solutions[sl] = []\n",
3015     "#     if len(solutions[sl]) < 4:\n",
3016     "#         solutions[sl].append([start, goal])\n",
3017     "        \n",
3018     "# #     if len(solution) >= 10:\n",
3019     "# #         solutions += [solution]\n",
3020     "        \n",
3021     "# solutions"
3022    ]
3023   },
3024   {
3025    "cell_type": "code",
3026    "execution_count": 60,
3027    "metadata": {
3028     "collapsed": true
3029    },
3030    "outputs": [],
3031    "source": [
3032     "solutions = {2: [['heel', 'keel'], ['wane', 'wave'], ['cell', 'sell'], ['cons', 'cobs']],\n",
3033     " 3: [['hank', 'haws'], ['bars', 'bets'], ['rats', 'paws'], ['lock', 'hack']],\n",
3034     " 4: [['rule', 'sore'], ['wavy', 'rape'], ['peas', 'ping'], ['bond', 'toll']],\n",
3035     " 5: [['cope', 'yowl'], ['lose', 'loci'], ['rump', 'dash'], ['four', 'dyes']],\n",
3036     " 6: [['boon', 'sell'], ['lots', 'pomp'], ['cola', 'turn'], ['boos', 'laid']],\n",
3037     " 7: [['eave', 'inns'], ['meek', 'mere'], ['keys', 'wily'], ['slam', 'yore']],\n",
3038     " 8: [['hack', 'flip'], ['crag', 'huge'], ['flux', 'gill'], ['play', 'busy']],\n",
3039     " 9: [['lacy', 'whey'], ['wren', 'rook'], ['lire', 'drip'], ['grab', 'lame']],\n",
3040     " 10: [['over', 'turn'], ['worn', 'anew'], ['stow', 'elks'], ['ergo', 'rich']],\n",
3041     " 11: [['bask', 'idea'], ['gabs', 'thud'], ['idea', 'clod'], ['mark', 'ibis']],\n",
3042     " 12: [['umps', 'torn'], ['futz', 'shun'], ['abut', 'face'], ['slug', 'open']],\n",
3043     " 13: [['umps', 'skin'], ['chum', 'rats'], ['fury', 'chum'], ['omen', 'zany']],\n",
3044     " 14: [['chug', 'gaff'], ['atom', 'fizz'], ['chug', 'jinn'], ['amen', 'flog'],\n",
3045     "     ['buzz', 'grog'], ['imps', 'pros']],\n",
3046     " 15: [['chug', 'oxen'], ['amen', 'doff']]}"
3047    ]
3048   },
3049   {
3050    "cell_type": "code",
3051    "execution_count": 61,
3052    "metadata": {},
3053    "outputs": [
3054     {
3055      "name": "stdout",
3056      "output_type": "stream",
3057      "text": [
3058       "1 loop, best of 3: 352 ms per loop\n"
3059      ]
3060     }
3061    ],
3062    "source": [
3063     "%%timeit\n",
3064     "astar_search_closed('blab', 'amen')"
3065    ]
3066   },
3067   {
3068    "cell_type": "code",
3069    "execution_count": 62,
3070    "metadata": {},
3071    "outputs": [
3072     {
3073      "name": "stdout",
3074      "output_type": "stream",
3075      "text": [
3076       "CPU times: user 452 ms, sys: 0 ns, total: 452 ms\n",
3077       "Wall time: 449 ms\n"
3078      ]
3079     },
3080     {
3081      "data": {
3082       "text/plain": [
3083        "14"
3084       ]
3085      },
3086      "execution_count": 62,
3087      "metadata": {},
3088      "output_type": "execute_result"
3089     }
3090    ],
3091    "source": [
3092     "%time len(astar_search_closed('blab', 'amen'))"
3093    ]
3094   },
3095   {
3096    "cell_type": "code",
3097    "execution_count": 63,
3098    "metadata": {},
3099    "outputs": [
3100     {
3101      "name": "stdout",
3102      "output_type": "stream",
3103      "text": [
3104       "CPU times: user 92 ms, sys: 0 ns, total: 92 ms\n",
3105       "Wall time: 91.5 ms\n"
3106      ]
3107     },
3108     {
3109      "data": {
3110       "text/plain": [
3111        "15"
3112       ]
3113      },
3114      "execution_count": 63,
3115      "metadata": {},
3116      "output_type": "execute_result"
3117     }
3118    ],
3119    "source": [
3120     "%time len(astar_search_closed('amen', 'doff'))"
3121    ]
3122   },
3123   {
3124    "cell_type": "code",
3125    "execution_count": 64,
3126    "metadata": {},
3127    "outputs": [
3128     {
3129      "name": "stdout",
3130      "output_type": "stream",
3131      "text": [
3132       "CPU times: user 32 ms, sys: 0 ns, total: 32 ms\n",
3133       "Wall time: 31.4 ms\n"
3134      ]
3135     },
3136     {
3137      "data": {
3138       "text/plain": [
3139        "14"
3140       ]
3141      },
3142      "execution_count": 64,
3143      "metadata": {},
3144      "output_type": "execute_result"
3145     }
3146    ],
3147    "source": [
3148     "%time len(astar_search_closed('chug', 'jinn'))"
3149    ]
3150   },
3151   {
3152    "cell_type": "code",
3153    "execution_count": 65,
3154    "metadata": {},
3155    "outputs": [
3156     {
3157      "name": "stdout",
3158      "output_type": "stream",
3159      "text": [
3160       "CPU times: user 16 ms, sys: 0 ns, total: 16 ms\n",
3161       "Wall time: 17.2 ms\n"
3162      ]
3163     },
3164     {
3165      "data": {
3166       "text/plain": [
3167        "14"
3168       ]
3169      },
3170      "execution_count": 65,
3171      "metadata": {},
3172      "output_type": "execute_result"
3173     }
3174    ],
3175    "source": [
3176     "%time len(astar_search_closed('amen', 'flog'))"
3177    ]
3178   },
3179   {
3180    "cell_type": "code",
3181    "execution_count": 66,
3182    "metadata": {},
3183    "outputs": [
3184     {
3185      "name": "stdout",
3186      "output_type": "stream",
3187      "text": [
3188       "CPU times: user 296 ms, sys: 4 ms, total: 300 ms\n",
3189       "Wall time: 299 ms\n"
3190      ]
3191     },
3192     {
3193      "data": {
3194       "text/plain": [
3195        "14"
3196       ]
3197      },
3198      "execution_count": 66,
3199      "metadata": {},
3200      "output_type": "execute_result"
3201     }
3202    ],
3203    "source": [
3204     "%time len(astar_search_closed('buzz', 'grog'))"
3205    ]
3206   },
3207   {
3208    "cell_type": "code",
3209    "execution_count": 67,
3210    "metadata": {},
3211    "outputs": [
3212     {
3213      "name": "stdout",
3214      "output_type": "stream",
3215      "text": [
3216       "CPU times: user 36 ms, sys: 0 ns, total: 36 ms\n",
3217       "Wall time: 34.5 ms\n"
3218      ]
3219     },
3220     {
3221      "data": {
3222       "text/plain": [
3223        "14"
3224       ]
3225      },
3226      "execution_count": 67,
3227      "metadata": {},
3228      "output_type": "execute_result"
3229     }
3230    ],
3231    "source": [
3232     "%time len(astar_search_closed('imps', 'pros'))"
3233    ]
3234   },
3235   {
3236    "cell_type": "code",
3237    "execution_count": 90,
3238    "metadata": {},
3239    "outputs": [
3240     {
3241      "name": "stdout",
3242      "output_type": "stream",
3243      "text": [
3244       "bash bush True\n",
3245       "rush bush True\n"
3246      ]
3247     },
3248     {
3249      "data": {
3250       "text/plain": [
3251        "2"
3252       ]
3253      },
3254      "execution_count": 90,
3255      "metadata": {},
3256      "output_type": "execute_result"
3257     }
3258    ],
3259    "source": [
3260     "nb_count = collections.Counter()\n",
3261     "for w in neighbours['rash']:\n",
3262     "    for w2 in neighbours[w]:\n",
3263     "        if w2 == 'bush': print(w, w2, w2 not in neighbours['rash'])\n",
3264     "        if w2 != 'rash' and w2 not in neighbours['rash']:\n",
3265     "            nb_count.update([w2])\n",
3266     "nb_count.most_common(1)[0][1]"
3267    ]
3268   },
3269   {
3270    "cell_type": "code",
3271    "execution_count": 91,
3272    "metadata": {},
3273    "outputs": [
3274     {
3275      "data": {
3276       "text/plain": [
3277        "['gush', 'hush', 'lush', 'mush', 'push', 'tush', 'bosh']"
3278       ]
3279      },
3280      "execution_count": 91,
3281      "metadata": {},
3282      "output_type": "execute_result"
3283     }
3284    ],
3285    "source": [
3286     "[w for w in neighbours['bush'] if w in nb_count]"
3287    ]
3288   },
3289   {
3290    "cell_type": "code",
3291    "execution_count": 89,
3292    "metadata": {},
3293    "outputs": [
3294     {
3295      "data": {
3296       "text/plain": [
3297        "('gibe', 2)"
3298       ]
3299      },
3300      "execution_count": 89,
3301      "metadata": {},
3302      "output_type": "execute_result"
3303     }
3304    ],
3305    "source": [
3306     "best_start = ''\n",
3307     "best_overlap_count = 0\n",
3308     "for w0 in neighbours:    \n",
3309     "    nb_count = collections.Counter()\n",
3310     "    for w in neighbours[w0]:\n",
3311     "        for w2 in neighbours[w]:\n",
3312     "            if w2 != w0 and w2 not in neighbours[w0]:\n",
3313     "                nb_count.update([w2])\n",
3314     "    if len(nb_count) > 0:\n",
3315     "        if nb_count.most_common(1)[0][1] > best_overlap_count:\n",
3316     "            best_start = w0\n",
3317     "            best_overlap_count = nb_count.most_common(1)[0][1]\n",
3318     "        \n",
3319     "best_start, best_overlap_count"
3320    ]
3321   },
3322   {
3323    "cell_type": "code",
3324    "execution_count": 88,
3325    "metadata": {},
3326    "outputs": [
3327     {
3328      "data": {
3329       "text/plain": [
3330        "'memo'"
3331       ]
3332      },
3333      "execution_count": 88,
3334      "metadata": {},
3335      "output_type": "execute_result"
3336     }
3337    ],
3338    "source": [
3339     "w0"
3340    ]
3341   },
3342   {
3343    "cell_type": "code",
3344    "execution_count": 76,
3345    "metadata": {},
3346    "outputs": [
3347     {
3348      "data": {
3349       "text/plain": [
3350        "{'bash', 'rush'}"
3351       ]
3352      },
3353      "execution_count": 76,
3354      "metadata": {},
3355      "output_type": "execute_result"
3356     }
3357    ],
3358    "source": [
3359     "set(neighbours['rash']) & set(neighbours['bush'])"
3360    ]
3361   },
3362   {
3363    "cell_type": "code",
3364    "execution_count": null,
3365    "metadata": {
3366     "collapsed": true
3367    },
3368    "outputs": [],
3369    "source": []
3370   }
3371  ],
3372  "metadata": {
3373   "kernelspec": {
3374    "display_name": "Python 3",
3375    "language": "python",
3376    "name": "python3"
3377   },
3378   "language_info": {
3379    "codemirror_mode": {
3380     "name": "ipython",
3381     "version": 3
3382    },
3383    "file_extension": ".py",
3384    "mimetype": "text/x-python",
3385    "name": "python",
3386    "nbconvert_exporter": "python",
3387    "pygments_lexer": "ipython3",
3388    "version": "3.5.2+"
3389   }
3390  },
3391  "nbformat": 4,
3392  "nbformat_minor": 2
3393 }