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

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 4,
   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": 5,
  20    "metadata": {},
  21    "outputs": [
  22     {
  23      "data": {
  24       "text/plain": [
  25        "2336"
  26       ]
  27      },
  28      "execution_count": 5,
  29      "metadata": {},
  30      "output_type": "execute_result"
  31     }
  32    ],
  33    "source": [
  34     "words = [w.strip() for w in open('08-offices.txt').readlines()]\n",
  35     "len(words)"
  36    ]
  37   },
  38   {
  39    "cell_type": "code",
  40    "execution_count": 6,
  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": 6,
  59      "metadata": {},
  60      "output_type": "execute_result"
  61     }
  62    ],
  63    "source": [
  64     "words[:10]"
  65    ]
  66   },
  67   {
  68    "cell_type": "code",
  69    "execution_count": 7,
  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": 8,
  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": 9,
 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": 10,
 114    "metadata": {},
 115    "outputs": [
 116     {
 117      "data": {
 118       "text/plain": [
 119        "['able']"
 120       ]
 121      },
 122      "execution_count": 10,
 123      "metadata": {},
 124      "output_type": "execute_result"
 125     }
 126    ],
 127    "source": [
 128     "neighbours['abbe']"
 129    ]
 130   },
 131   {
 132    "cell_type": "code",
 133    "execution_count": 11,
 134    "metadata": {},
 135    "outputs": [
 136     {
 137      "data": {
 138       "text/plain": [
 139        "['axle', 'abbe', 'ably']"
 140       ]
 141      },
 142      "execution_count": 11,
 143      "metadata": {},
 144      "output_type": "execute_result"
 145     }
 146    ],
 147    "source": [
 148     "neighbours['able']"
 149    ]
 150   },
 151   {
 152    "cell_type": "code",
 153    "execution_count": 12,
 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": 13,
 167    "metadata": {},
 168    "outputs": [
 169     {
 170      "data": {
 171       "text/plain": [
 172        "0"
 173       ]
 174      },
 175      "execution_count": 13,
 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": 14,
 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": 15,
 204    "metadata": {},
 205    "outputs": [
 206     {
 207      "data": {
 208       "text/plain": [
 209        "[['abbe', 'able']]"
 210       ]
 211      },
 212      "execution_count": 15,
 213      "metadata": {},
 214      "output_type": "execute_result"
 215     }
 216    ],
 217    "source": [
 218     "extend(['abbe'])"
 219    ]
 220   },
 221   {
 222    "cell_type": "code",
 223    "execution_count": 16,
 224    "metadata": {},
 225    "outputs": [
 226     {
 227      "data": {
 228       "text/plain": [
 229        "[['abbe', 'able', 'axle'], ['abbe', 'able', 'ably']]"
 230       ]
 231      },
 232      "execution_count": 16,
 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": 17,
 244    "metadata": {},
 245    "outputs": [
 246     {
 247      "data": {
 248       "text/plain": [
 249        "[['abbe', 'able', 'ably', 'ally']]"
 250       ]
 251      },
 252      "execution_count": 17,
 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": 18,
 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": 19,
 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": 20,
 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": 20,
 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": 21,
 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": 22,
 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": 22,
 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": 23,
 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       "['cart', 'part', 'pars', 'jars']\n",
1096       "['cart', 'part', 'pars', 'mars']\n",
1097       "['cart', 'part', 'pars', 'oars']\n",
1098       "['cart', 'part', 'pars', 'tars']\n",
1099       "['cart', 'part', 'pars', 'wars']\n",
1100       "['cart', 'part', 'pars', 'pads']\n",
1101       "['cart', 'part', 'pars', 'pals']\n",
1102       "['cart', 'part', 'pars', 'pans']\n",
1103       "['cart', 'part', 'pars', 'paps']\n",
1104       "['cart', 'part', 'pars', 'pass']\n",
1105       "['cart', 'part', 'pars', 'pats']\n",
1106       "['cart', 'part', 'pars', 'paws']\n",
1107       "['cart', 'part', 'pars', 'pays']\n",
1108       "['cart', 'part', 'pars', 'pare']\n",
1109       "['cart', 'part', 'pars', 'park']\n",
1110       "['cart', 'tart', 'dart', 'hart']\n",
1111       "['cart', 'tart', 'dart', 'mart']\n",
1112       "['cart', 'tart', 'dart', 'part']\n",
1113       "['cart', 'tart', 'dart', 'wart']\n",
1114       "['cart', 'tart', 'dart', 'dirt']\n",
1115       "['cart', 'tart', 'dart', 'daft']\n",
1116       "['cart', 'tart', 'dart', 'dare']\n",
1117       "['cart', 'tart', 'dart', 'dark']\n",
1118       "['cart', 'tart', 'dart', 'darn']\n",
1119       "['cart', 'tart', 'hart', 'dart']\n",
1120       "['cart', 'tart', 'hart', 'mart']\n",
1121       "['cart', 'tart', 'hart', 'part']\n",
1122       "['cart', 'tart', 'hart', 'wart']\n",
1123       "['cart', 'tart', 'hart', 'hurt']\n",
1124       "['cart', 'tart', 'hart', 'haft']\n",
1125       "['cart', 'tart', 'hart', 'halt']\n",
1126       "['cart', 'tart', 'hart', 'hard']\n",
1127       "['cart', 'tart', 'hart', 'hare']\n",
1128       "['cart', 'tart', 'hart', 'hark']\n",
1129       "['cart', 'tart', 'hart', 'harm']\n",
1130       "['cart', 'tart', 'hart', 'harp']\n",
1131       "['cart', 'tart', 'mart', 'dart']\n",
1132       "['cart', 'tart', 'mart', 'hart']\n",
1133       "['cart', 'tart', 'mart', 'part']\n",
1134       "['cart', 'tart', 'mart', 'wart']\n",
1135       "['cart', 'tart', 'mart', 'malt']\n",
1136       "['cart', 'tart', 'mart', 'mast']\n",
1137       "['cart', 'tart', 'mart', 'matt']\n",
1138       "['cart', 'tart', 'mart', 'mare']\n",
1139       "['cart', 'tart', 'mart', 'mark']\n",
1140       "['cart', 'tart', 'mart', 'mars']\n",
1141       "['cart', 'tart', 'part', 'dart']\n",
1142       "['cart', 'tart', 'part', 'hart']\n",
1143       "['cart', 'tart', 'part', 'mart']\n",
1144       "['cart', 'tart', 'part', 'wart']\n",
1145       "['cart', 'tart', 'part', 'pert']\n",
1146       "['cart', 'tart', 'part', 'port']\n",
1147       "['cart', 'tart', 'part', 'pact']\n",
1148       "['cart', 'tart', 'part', 'pant']\n",
1149       "['cart', 'tart', 'part', 'past']\n",
1150       "['cart', 'tart', 'part', 'pare']\n",
1151       "['cart', 'tart', 'part', 'park']\n",
1152       "['cart', 'tart', 'part', 'pars']\n",
1153       "['cart', 'tart', 'wart', 'dart']\n",
1154       "['cart', 'tart', 'wart', 'hart']\n",
1155       "['cart', 'tart', 'wart', 'mart']\n",
1156       "['cart', 'tart', 'wart', 'part']\n",
1157       "['cart', 'tart', 'wart', 'waft']\n",
1158       "['cart', 'tart', 'wart', 'wait']\n",
1159       "['cart', 'tart', 'wart', 'want']\n",
1160       "['cart', 'tart', 'wart', 'watt']\n",
1161       "['cart', 'tart', 'wart', 'ward']\n",
1162       "['cart', 'tart', 'wart', 'ware']\n",
1163       "['cart', 'tart', 'wart', 'warm']\n",
1164       "['cart', 'tart', 'wart', 'warn']\n",
1165       "['cart', 'tart', 'wart', 'warp']\n",
1166       "['cart', 'tart', 'wart', 'wars']\n",
1167       "['cart', 'tart', 'wart', 'wary']\n",
1168       "['cart', 'tart', 'tort', 'fort']\n",
1169       "['cart', 'tart', 'tort', 'port']\n",
1170       "['cart', 'tart', 'tort', 'sort']\n",
1171       "['cart', 'tart', 'tort', 'toot']\n",
1172       "['cart', 'tart', 'tort', 'tost']\n",
1173       "['cart', 'tart', 'tort', 'tout']\n",
1174       "['cart', 'tart', 'tort', 'tore']\n",
1175       "['cart', 'tart', 'tort', 'torn']\n",
1176       "['cart', 'tart', 'tort', 'tors']\n",
1177       "['cart', 'tart', 'tact', 'fact']\n",
1178       "['cart', 'tart', 'tact', 'pact']\n",
1179       "['cart', 'tart', 'tact', 'taut']\n",
1180       "['cart', 'tart', 'tact', 'tack']\n",
1181       "['cart', 'tart', 'tact', 'taco']\n",
1182       "['cart', 'tart', 'taut', 'tout']\n",
1183       "['cart', 'tart', 'taut', 'tact']\n",
1184       "['cart', 'tart', 'tare', 'bare']\n",
1185       "['cart', 'tart', 'tare', 'care']\n",
1186       "['cart', 'tart', 'tare', 'dare']\n",
1187       "['cart', 'tart', 'tare', 'fare']\n",
1188       "['cart', 'tart', 'tare', 'hare']\n",
1189       "['cart', 'tart', 'tare', 'mare']\n",
1190       "['cart', 'tart', 'tare', 'pare']\n",
1191       "['cart', 'tart', 'tare', 'rare']\n",
1192       "['cart', 'tart', 'tare', 'ware']\n",
1193       "['cart', 'tart', 'tare', 'tire']\n",
1194       "['cart', 'tart', 'tare', 'tore']\n",
1195       "['cart', 'tart', 'tare', 'tyre']\n",
1196       "['cart', 'tart', 'tare', 'take']\n",
1197       "['cart', 'tart', 'tare', 'tale']\n",
1198       "['cart', 'tart', 'tare', 'tame']\n",
1199       "['cart', 'tart', 'tare', 'tape']\n",
1200       "['cart', 'tart', 'tare', 'taro']\n",
1201       "['cart', 'tart', 'tare', 'tarp']\n",
1202       "['cart', 'tart', 'tare', 'tars']\n",
1203       "['cart', 'tart', 'taro', 'tiro']\n",
1204       "['cart', 'tart', 'taro', 'tyro']\n",
1205       "['cart', 'tart', 'taro', 'taco']\n",
1206       "['cart', 'tart', 'taro', 'tare']\n",
1207       "['cart', 'tart', 'taro', 'tarp']\n",
1208       "['cart', 'tart', 'taro', 'tars']\n",
1209       "['cart', 'tart', 'tarp', 'carp']\n",
1210       "['cart', 'tart', 'tarp', 'harp']\n",
1211       "['cart', 'tart', 'tarp', 'warp']\n",
1212       "['cart', 'tart', 'tarp', 'tamp']\n",
1213       "['cart', 'tart', 'tarp', 'tare']\n",
1214       "['cart', 'tart', 'tarp', 'taro']\n",
1215       "['cart', 'tart', 'tarp', 'tars']\n",
1216       "['cart', 'tart', 'tars', 'bars']\n",
1217       "['cart', 'tart', 'tars', 'cars']\n",
1218       "['cart', 'tart', 'tars', 'ears']\n",
1219       "['cart', 'tart', 'tars', 'jars']\n",
1220       "['cart', 'tart', 'tars', 'mars']\n",
1221       "['cart', 'tart', 'tars', 'oars']\n",
1222       "['cart', 'tart', 'tars', 'pars']\n",
1223       "['cart', 'tart', 'tars', 'wars']\n",
1224       "['cart', 'tart', 'tars', 'tors']\n",
1225       "['cart', 'tart', 'tars', 'tabs']\n",
1226       "['cart', 'tart', 'tars', 'tads']\n",
1227       "['cart', 'tart', 'tars', 'tags']\n",
1228       "['cart', 'tart', 'tars', 'tams']\n",
1229       "['cart', 'tart', 'tars', 'tans']\n",
1230       "['cart', 'tart', 'tars', 'taps']\n",
1231       "['cart', 'tart', 'tars', 'tats']\n",
1232       "['cart', 'tart', 'tars', 'tare']\n",
1233       "['cart', 'tart', 'tars', 'taro']\n",
1234       "['cart', 'tart', 'tars', 'tarp']\n",
1235       "['cart', 'wart', 'dart', 'hart']\n",
1236       "['cart', 'wart', 'dart', 'mart']\n",
1237       "['cart', 'wart', 'dart', 'part']\n",
1238       "['cart', 'wart', 'dart', 'tart']\n",
1239       "['cart', 'wart', 'dart', 'dirt']\n",
1240       "['cart', 'wart', 'dart', 'daft']\n",
1241       "['cart', 'wart', 'dart', 'dare']\n",
1242       "['cart', 'wart', 'dart', 'dark']\n",
1243       "['cart', 'wart', 'dart', 'darn']\n",
1244       "['cart', 'wart', 'hart', 'dart']\n",
1245       "['cart', 'wart', 'hart', 'mart']\n",
1246       "['cart', 'wart', 'hart', 'part']\n",
1247       "['cart', 'wart', 'hart', 'tart']\n",
1248       "['cart', 'wart', 'hart', 'hurt']\n",
1249       "['cart', 'wart', 'hart', 'haft']\n",
1250       "['cart', 'wart', 'hart', 'halt']\n",
1251       "['cart', 'wart', 'hart', 'hard']\n",
1252       "['cart', 'wart', 'hart', 'hare']\n",
1253       "['cart', 'wart', 'hart', 'hark']\n",
1254       "['cart', 'wart', 'hart', 'harm']\n",
1255       "['cart', 'wart', 'hart', 'harp']\n",
1256       "['cart', 'wart', 'mart', 'dart']\n",
1257       "['cart', 'wart', 'mart', 'hart']\n",
1258       "['cart', 'wart', 'mart', 'part']\n",
1259       "['cart', 'wart', 'mart', 'tart']\n",
1260       "['cart', 'wart', 'mart', 'malt']\n",
1261       "['cart', 'wart', 'mart', 'mast']\n",
1262       "['cart', 'wart', 'mart', 'matt']\n",
1263       "['cart', 'wart', 'mart', 'mare']\n",
1264       "['cart', 'wart', 'mart', 'mark']\n",
1265       "['cart', 'wart', 'mart', 'mars']\n",
1266       "['cart', 'wart', 'part', 'dart']\n",
1267       "['cart', 'wart', 'part', 'hart']\n",
1268       "['cart', 'wart', 'part', 'mart']\n",
1269       "['cart', 'wart', 'part', 'tart']\n",
1270       "['cart', 'wart', 'part', 'pert']\n",
1271       "['cart', 'wart', 'part', 'port']\n",
1272       "['cart', 'wart', 'part', 'pact']\n",
1273       "['cart', 'wart', 'part', 'pant']\n",
1274       "['cart', 'wart', 'part', 'past']\n",
1275       "['cart', 'wart', 'part', 'pare']\n",
1276       "['cart', 'wart', 'part', 'park']\n",
1277       "['cart', 'wart', 'part', 'pars']\n",
1278       "['cart', 'wart', 'tart', 'dart']\n",
1279       "['cart', 'wart', 'tart', 'hart']\n",
1280       "['cart', 'wart', 'tart', 'mart']\n",
1281       "['cart', 'wart', 'tart', 'part']\n",
1282       "['cart', 'wart', 'tart', 'tort']\n",
1283       "['cart', 'wart', 'tart', 'tact']\n",
1284       "['cart', 'wart', 'tart', 'taut']\n",
1285       "['cart', 'wart', 'tart', 'tare']\n",
1286       "['cart', 'wart', 'tart', 'taro']\n",
1287       "['cart', 'wart', 'tart', 'tarp']\n",
1288       "['cart', 'wart', 'tart', 'tars']\n",
1289       "['cart', 'wart', 'waft', 'daft']\n",
1290       "['cart', 'wart', 'waft', 'haft']\n",
1291       "['cart', 'wart', 'waft', 'raft']\n",
1292       "['cart', 'wart', 'waft', 'weft']\n",
1293       "['cart', 'wart', 'waft', 'wait']\n",
1294       "['cart', 'wart', 'waft', 'want']\n",
1295       "['cart', 'wart', 'waft', 'watt']\n",
1296       "['cart', 'wart', 'wait', 'bait']\n",
1297       "['cart', 'wart', 'wait', 'gait']\n",
1298       "['cart', 'wart', 'wait', 'whit']\n",
1299       "['cart', 'wart', 'wait', 'writ']\n",
1300       "['cart', 'wart', 'wait', 'waft']\n",
1301       "['cart', 'wart', 'wait', 'want']\n",
1302       "['cart', 'wart', 'wait', 'watt']\n",
1303       "['cart', 'wart', 'wait', 'waif']\n",
1304       "['cart', 'wart', 'wait', 'wail']\n",
1305       "['cart', 'wart', 'want', 'cant']\n",
1306       "['cart', 'wart', 'want', 'pant']\n",
1307       "['cart', 'wart', 'want', 'rant']\n",
1308       "['cart', 'wart', 'want', 'went']\n",
1309       "['cart', 'wart', 'want', 'wont']\n",
1310       "['cart', 'wart', 'want', 'waft']\n",
1311       "['cart', 'wart', 'want', 'wait']\n",
1312       "['cart', 'wart', 'want', 'watt']\n",
1313       "['cart', 'wart', 'want', 'wand']\n",
1314       "['cart', 'wart', 'want', 'wane']\n",
1315       "['cart', 'wart', 'watt', 'matt']\n",
1316       "['cart', 'wart', 'watt', 'waft']\n",
1317       "['cart', 'wart', 'watt', 'wait']\n",
1318       "['cart', 'wart', 'watt', 'want']\n",
1319       "['cart', 'wart', 'ward', 'bard']\n",
1320       "['cart', 'wart', 'ward', 'card']\n",
1321       "['cart', 'wart', 'ward', 'hard']\n",
1322       "['cart', 'wart', 'ward', 'lard']\n",
1323       "['cart', 'wart', 'ward', 'yard']\n",
1324       "['cart', 'wart', 'ward', 'word']\n",
1325       "['cart', 'wart', 'ward', 'wand']\n",
1326       "['cart', 'wart', 'ward', 'ware']\n",
1327       "['cart', 'wart', 'ward', 'warm']\n",
1328       "['cart', 'wart', 'ward', 'warn']\n",
1329       "['cart', 'wart', 'ward', 'warp']\n",
1330       "['cart', 'wart', 'ward', 'wars']\n",
1331       "['cart', 'wart', 'ward', 'wary']\n",
1332       "['cart', 'wart', 'ware', 'bare']\n",
1333       "['cart', 'wart', 'ware', 'care']\n",
1334       "['cart', 'wart', 'ware', 'dare']\n",
1335       "['cart', 'wart', 'ware', 'fare']\n",
1336       "['cart', 'wart', 'ware', 'hare']\n",
1337       "['cart', 'wart', 'ware', 'mare']\n",
1338       "['cart', 'wart', 'ware', 'pare']\n",
1339       "['cart', 'wart', 'ware', 'rare']\n",
1340       "['cart', 'wart', 'ware', 'tare']\n",
1341       "['cart', 'wart', 'ware', 'were']\n",
1342       "['cart', 'wart', 'ware', 'wire']\n",
1343       "['cart', 'wart', 'ware', 'wore']\n",
1344       "['cart', 'wart', 'ware', 'wade']\n",
1345       "['cart', 'wart', 'ware', 'wage']\n",
1346       "['cart', 'wart', 'ware', 'wake']\n",
1347       "['cart', 'wart', 'ware', 'wale']\n",
1348       "['cart', 'wart', 'ware', 'wane']\n",
1349       "['cart', 'wart', 'ware', 'wave']\n",
1350       "['cart', 'wart', 'ware', 'ward']\n",
1351       "['cart', 'wart', 'ware', 'warm']\n",
1352       "['cart', 'wart', 'ware', 'warn']\n",
1353       "['cart', 'wart', 'ware', 'warp']\n",
1354       "['cart', 'wart', 'ware', 'wars']\n",
1355       "['cart', 'wart', 'ware', 'wary']\n",
1356       "['cart', 'wart', 'warm', 'farm']\n",
1357       "['cart', 'wart', 'warm', 'harm']\n",
1358       "['cart', 'wart', 'warm', 'worm']\n",
1359       "['cart', 'wart', 'warm', 'ward']\n",
1360       "['cart', 'wart', 'warm', 'ware']\n",
1361       "['cart', 'wart', 'warm', 'warn']\n",
1362       "['cart', 'wart', 'warm', 'warp']\n",
1363       "['cart', 'wart', 'warm', 'wars']\n",
1364       "['cart', 'wart', 'warm', 'wary']\n",
1365       "['cart', 'wart', 'warn', 'barn']\n",
1366       "['cart', 'wart', 'warn', 'darn']\n",
1367       "['cart', 'wart', 'warn', 'earn']\n",
1368       "['cart', 'wart', 'warn', 'yarn']\n",
1369       "['cart', 'wart', 'warn', 'worn']\n",
1370       "['cart', 'wart', 'warn', 'ward']\n",
1371       "['cart', 'wart', 'warn', 'ware']\n",
1372       "['cart', 'wart', 'warn', 'warm']\n",
1373       "['cart', 'wart', 'warn', 'warp']\n",
1374       "['cart', 'wart', 'warn', 'wars']\n",
1375       "['cart', 'wart', 'warn', 'wary']\n",
1376       "['cart', 'wart', 'warp', 'carp']\n",
1377       "['cart', 'wart', 'warp', 'harp']\n",
1378       "['cart', 'wart', 'warp', 'tarp']\n",
1379       "['cart', 'wart', 'warp', 'wasp']\n",
1380       "['cart', 'wart', 'warp', 'ward']\n",
1381       "['cart', 'wart', 'warp', 'ware']\n",
1382       "['cart', 'wart', 'warp', 'warm']\n",
1383       "['cart', 'wart', 'warp', 'warn']\n",
1384       "['cart', 'wart', 'warp', 'wars']\n",
1385       "['cart', 'wart', 'warp', 'wary']\n",
1386       "['cart', 'wart', 'wars', 'bars']\n",
1387       "['cart', 'wart', 'wars', 'cars']\n",
1388       "['cart', 'wart', 'wars', 'ears']\n",
1389       "['cart', 'wart', 'wars', 'jars']\n",
1390       "['cart', 'wart', 'wars', 'mars']\n",
1391       "['cart', 'wart', 'wars', 'oars']\n",
1392       "['cart', 'wart', 'wars', 'pars']\n",
1393       "['cart', 'wart', 'wars', 'tars']\n",
1394       "['cart', 'wart', 'wars', 'wads']\n",
1395       "['cart', 'wart', 'wars', 'wags']\n",
1396       "['cart', 'wart', 'wars', 'ways']\n",
1397       "['cart', 'wart', 'wars', 'ward']\n",
1398       "['cart', 'wart', 'wars', 'ware']\n",
1399       "['cart', 'wart', 'wars', 'warm']\n",
1400       "['cart', 'wart', 'wars', 'warn']\n",
1401       "['cart', 'wart', 'wars', 'warp']\n",
1402       "['cart', 'wart', 'wars', 'wary']\n",
1403       "['cart', 'wart', 'wary', 'nary']\n",
1404       "['cart', 'wart', 'wary', 'vary']\n",
1405       "['cart', 'wart', 'wary', 'wiry']\n",
1406       "['cart', 'wart', 'wary', 'wavy']\n",
1407       "['cart', 'wart', 'wary', 'waxy']\n",
1408       "['cart', 'wart', 'wary', 'ward']\n",
1409       "['cart', 'wart', 'wary', 'ware']\n",
1410       "['cart', 'wart', 'wary', 'warm']\n",
1411       "['cart', 'wart', 'wary', 'warn']\n",
1412       "['cart', 'wart', 'wary', 'warp']\n",
1413       "['cart', 'wart', 'wary', 'wars']\n",
1414       "['cart', 'curt', 'hurt', 'hart']\n",
1415       "['cart', 'curt', 'hurt', 'hunt']\n",
1416       "['cart', 'curt', 'hurt', 'hurl']\n",
1417       "['cart', 'curt', 'cult', 'colt']\n",
1418       "['cart', 'curt', 'cult', 'cull']\n",
1419       "['cart', 'curt', 'curb', 'curd']\n",
1420       "['cart', 'curt', 'curb', 'cure']\n",
1421       "['cart', 'curt', 'curb', 'curl']\n",
1422       "['cart', 'curt', 'curb', 'curs']\n",
1423       "['cart', 'curt', 'curd', 'turd']\n",
1424       "['cart', 'curt', 'curd', 'card']\n",
1425       "['cart', 'curt', 'curd', 'cord']\n",
1426       "['cart', 'curt', 'curd', 'cued']\n",
1427       "['cart', 'curt', 'curd', 'curb']\n",
1428       "['cart', 'curt', 'curd', 'cure']\n",
1429       "['cart', 'curt', 'curd', 'curl']\n",
1430       "['cart', 'curt', 'curd', 'curs']\n",
1431       "['cart', 'curt', 'cure', 'lure']\n",
1432       "['cart', 'curt', 'cure', 'pure']\n",
1433       "['cart', 'curt', 'cure', 'sure']\n",
1434       "['cart', 'curt', 'cure', 'care']\n",
1435       "['cart', 'curt', 'cure', 'core']\n",
1436       "['cart', 'curt', 'cure', 'cube']\n",
1437       "['cart', 'curt', 'cure', 'cute']\n",
1438       "['cart', 'curt', 'cure', 'curb']\n",
1439       "['cart', 'curt', 'cure', 'curd']\n",
1440       "['cart', 'curt', 'cure', 'curl']\n",
1441       "['cart', 'curt', 'cure', 'curs']\n",
1442       "['cart', 'curt', 'curl', 'furl']\n",
1443       "['cart', 'curt', 'curl', 'hurl']\n",
1444       "['cart', 'curt', 'curl', 'purl']\n",
1445       "['cart', 'curt', 'curl', 'cull']\n",
1446       "['cart', 'curt', 'curl', 'curb']\n",
1447       "['cart', 'curt', 'curl', 'curd']\n",
1448       "['cart', 'curt', 'curl', 'cure']\n",
1449       "['cart', 'curt', 'curl', 'curs']\n",
1450       "['cart', 'curt', 'curs', 'burs']\n",
1451       "['cart', 'curt', 'curs', 'furs']\n",
1452       "['cart', 'curt', 'curs', 'ours']\n",
1453       "['cart', 'curt', 'curs', 'cars']\n",
1454       "['cart', 'curt', 'curs', 'cubs']\n",
1455       "['cart', 'curt', 'curs', 'cuds']\n",
1456       "['cart', 'curt', 'curs', 'cues']\n",
1457       "['cart', 'curt', 'curs', 'cums']\n",
1458       "['cart', 'curt', 'curs', 'cups']\n",
1459       "['cart', 'curt', 'curs', 'cuss']\n",
1460       "['cart', 'curt', 'curs', 'cuts']\n",
1461       "['cart', 'curt', 'curs', 'curb']\n",
1462       "['cart', 'curt', 'curs', 'curd']\n",
1463       "['cart', 'curt', 'curs', 'cure']\n",
1464       "['cart', 'curt', 'curs', 'curl']\n",
1465       "['cart', 'cant', 'pant', 'rant']\n",
1466       "['cart', 'cant', 'pant', 'want']\n",
1467       "['cart', 'cant', 'pant', 'pent']\n",
1468       "['cart', 'cant', 'pant', 'pint']\n",
1469       "['cart', 'cant', 'pant', 'punt']\n",
1470       "['cart', 'cant', 'pant', 'pact']\n",
1471       "['cart', 'cant', 'pant', 'part']\n",
1472       "['cart', 'cant', 'pant', 'past']\n",
1473       "['cart', 'cant', 'pant', 'pane']\n",
1474       "['cart', 'cant', 'pant', 'pang']\n",
1475       "['cart', 'cant', 'pant', 'pans']\n",
1476       "['cart', 'cant', 'rant', 'pant']\n",
1477       "['cart', 'cant', 'rant', 'want']\n",
1478       "['cart', 'cant', 'rant', 'rent']\n",
1479       "['cart', 'cant', 'rant', 'runt']\n",
1480       "['cart', 'cant', 'rant', 'raft']\n",
1481       "['cart', 'cant', 'rant', 'rapt']\n",
1482       "['cart', 'cant', 'rant', 'rang']\n",
1483       "['cart', 'cant', 'rant', 'rank']\n",
1484       "['cart', 'cant', 'want', 'pant']\n",
1485       "['cart', 'cant', 'want', 'rant']\n",
1486       "['cart', 'cant', 'want', 'went']\n",
1487       "['cart', 'cant', 'want', 'wont']\n",
1488       "['cart', 'cant', 'want', 'waft']\n",
1489       "['cart', 'cant', 'want', 'wait']\n",
1490       "['cart', 'cant', 'want', 'wart']\n",
1491       "['cart', 'cant', 'want', 'watt']\n",
1492       "['cart', 'cant', 'want', 'wand']\n",
1493       "['cart', 'cant', 'want', 'wane']\n",
1494       "['cart', 'cant', 'cent', 'bent']\n",
1495       "['cart', 'cant', 'cent', 'dent']\n",
1496       "['cart', 'cant', 'cent', 'gent']\n",
1497       "['cart', 'cant', 'cent', 'lent']\n",
1498       "['cart', 'cant', 'cent', 'pent']\n",
1499       "['cart', 'cant', 'cent', 'rent']\n",
1500       "['cart', 'cant', 'cent', 'sent']\n",
1501       "['cart', 'cant', 'cent', 'tent']\n",
1502       "['cart', 'cant', 'cent', 'vent']\n",
1503       "['cart', 'cant', 'cent', 'went']\n",
1504       "['cart', 'cant', 'cast', 'bast']\n",
1505       "['cart', 'cant', 'cast', 'east']\n",
1506       "['cart', 'cant', 'cast', 'fast']\n",
1507       "['cart', 'cant', 'cast', 'last']\n",
1508       "['cart', 'cant', 'cast', 'mast']\n",
1509       "['cart', 'cant', 'cast', 'past']\n",
1510       "['cart', 'cant', 'cast', 'vast']\n",
1511       "['cart', 'cant', 'cast', 'cost']\n",
1512       "['cart', 'cant', 'cast', 'cyst']\n",
1513       "['cart', 'cant', 'cast', 'case']\n",
1514       "['cart', 'cant', 'cast', 'cash']\n",
1515       "['cart', 'cant', 'cast', 'cask']\n",
1516       "['cart', 'cant', 'cane', 'bane']\n",
1517       "['cart', 'cant', 'cane', 'lane']\n",
1518       "['cart', 'cant', 'cane', 'mane']\n",
1519       "['cart', 'cant', 'cane', 'pane']\n",
1520       "['cart', 'cant', 'cane', 'sane']\n",
1521       "['cart', 'cant', 'cane', 'vane']\n",
1522       "['cart', 'cant', 'cane', 'wane']\n",
1523       "['cart', 'cant', 'cane', 'cone']\n",
1524       "['cart', 'cant', 'cane', 'cafe']\n",
1525       "['cart', 'cant', 'cane', 'cage']\n",
1526       "['cart', 'cant', 'cane', 'cake']\n",
1527       "['cart', 'cant', 'cane', 'came']\n",
1528       "['cart', 'cant', 'cane', 'cape']\n",
1529       "['cart', 'cant', 'cane', 'care']\n",
1530       "['cart', 'cant', 'cane', 'case']\n",
1531       "['cart', 'cant', 'cane', 'cave']\n",
1532       "['cart', 'cant', 'cane', 'cans']\n",
1533       "['cart', 'cant', 'cans', 'bans']\n",
1534       "['cart', 'cant', 'cans', 'fans']\n",
1535       "['cart', 'cant', 'cans', 'mans']\n",
1536       "['cart', 'cant', 'cans', 'pans']\n",
1537       "['cart', 'cant', 'cans', 'sans']\n",
1538       "['cart', 'cant', 'cans', 'tans']\n",
1539       "['cart', 'cant', 'cans', 'vans']\n"
1540      ]
1541     },
1542     {
1543      "data": {
1544       "text/plain": [
1545        "['cart', 'cant', 'cans', 'vans']"
1546       ]
1547      },
1548      "execution_count": 23,
1549      "metadata": {},
1550      "output_type": "execute_result"
1551     }
1552    ],
1553    "source": [
1554     "bfs_search('cart', 'vans', debug=True)"
1555    ]
1556   },
1557   {
1558    "cell_type": "code",
1559    "execution_count": 24,
1560    "metadata": {},
1561    "outputs": [
1562     {
1563      "data": {
1564       "text/plain": [
1565        "['cart', 'cant', 'cane', 'vane']"
1566       ]
1567      },
1568      "execution_count": 24,
1569      "metadata": {},
1570      "output_type": "execute_result"
1571     }
1572    ],
1573    "source": [
1574     "bfs_search('cart', 'vane')"
1575    ]
1576   },
1577   {
1578    "cell_type": "code",
1579    "execution_count": 25,
1580    "metadata": {},
1581    "outputs": [
1582     {
1583      "data": {
1584       "text/plain": [
1585        "['cart',\n",
1586        " 'dart',\n",
1587        " 'hart',\n",
1588        " 'mart',\n",
1589        " 'part',\n",
1590        " 'tart',\n",
1591        " 'wart',\n",
1592        " 'waft',\n",
1593        " 'daft',\n",
1594        " 'haft',\n",
1595        " 'raft',\n",
1596        " 'rift',\n",
1597        " 'gift',\n",
1598        " 'lift',\n",
1599        " 'sift',\n",
1600        " 'soft',\n",
1601        " 'loft',\n",
1602        " 'left',\n",
1603        " 'deft',\n",
1604        " 'heft',\n",
1605        " 'weft',\n",
1606        " 'welt',\n",
1607        " 'belt',\n",
1608        " 'felt',\n",
1609        " 'gelt',\n",
1610        " 'melt',\n",
1611        " 'pelt',\n",
1612        " 'peat',\n",
1613        " 'beat',\n",
1614        " 'feat',\n",
1615        " 'heat',\n",
1616        " 'meat',\n",
1617        " 'neat',\n",
1618        " 'seat',\n",
1619        " 'teat',\n",
1620        " 'that',\n",
1621        " 'chat',\n",
1622        " 'shat',\n",
1623        " 'what',\n",
1624        " 'whet',\n",
1625        " 'whit',\n",
1626        " 'chit',\n",
1627        " 'chic',\n",
1628        " 'chid',\n",
1629        " 'chin',\n",
1630        " 'shin',\n",
1631        " 'thin',\n",
1632        " 'twin',\n",
1633        " 'twig',\n",
1634        " 'swig',\n",
1635        " 'swag',\n",
1636        " 'shag',\n",
1637        " 'slag',\n",
1638        " 'flag',\n",
1639        " 'flog',\n",
1640        " 'blog',\n",
1641        " 'clog',\n",
1642        " 'slog',\n",
1643        " 'smog',\n",
1644        " 'smug',\n",
1645        " 'slug',\n",
1646        " 'plug',\n",
1647        " 'plum',\n",
1648        " 'alum',\n",
1649        " 'glum',\n",
1650        " 'slum',\n",
1651        " 'scum',\n",
1652        " 'swum',\n",
1653        " 'swam',\n",
1654        " 'scam',\n",
1655        " 'seam',\n",
1656        " 'beam',\n",
1657        " 'ream',\n",
1658        " 'team',\n",
1659        " 'tram',\n",
1660        " 'cram',\n",
1661        " 'dram',\n",
1662        " 'gram',\n",
1663        " 'pram',\n",
1664        " 'prim',\n",
1665        " 'brim',\n",
1666        " 'grim',\n",
1667        " 'trim',\n",
1668        " 'trig',\n",
1669        " 'brig',\n",
1670        " 'brag',\n",
1671        " 'crag',\n",
1672        " 'drag',\n",
1673        " 'drug',\n",
1674        " 'drub',\n",
1675        " 'grub',\n",
1676        " 'grab',\n",
1677        " 'crab',\n",
1678        " 'drab',\n",
1679        " 'draw',\n",
1680        " 'craw',\n",
1681        " 'claw',\n",
1682        " 'flaw',\n",
1683        " 'slaw',\n",
1684        " 'slew',\n",
1685        " 'blew',\n",
1686        " 'clew',\n",
1687        " 'flew',\n",
1688        " 'flow',\n",
1689        " 'blow',\n",
1690        " 'glow',\n",
1691        " 'slow',\n",
1692        " 'scow',\n",
1693        " 'show',\n",
1694        " 'chow',\n",
1695        " 'crow',\n",
1696        " 'brow',\n",
1697        " 'grow',\n",
1698        " 'prow',\n",
1699        " 'prod',\n",
1700        " 'trod',\n",
1701        " 'trot',\n",
1702        " 'toot',\n",
1703        " 'boot',\n",
1704        " 'coot',\n",
1705        " 'foot',\n",
1706        " 'hoot',\n",
1707        " 'loot',\n",
1708        " 'moot',\n",
1709        " 'root',\n",
1710        " 'soot',\n",
1711        " 'shot',\n",
1712        " 'slot',\n",
1713        " 'blot',\n",
1714        " 'clot',\n",
1715        " 'plot',\n",
1716        " 'plod',\n",
1717        " 'clod',\n",
1718        " 'clad',\n",
1719        " 'glad',\n",
1720        " 'goad',\n",
1721        " 'load',\n",
1722        " 'road',\n",
1723        " 'toad',\n",
1724        " 'toed',\n",
1725        " 'coed',\n",
1726        " 'hoed',\n",
1727        " 'heed',\n",
1728        " 'deed',\n",
1729        " 'feed',\n",
1730        " 'geed',\n",
1731        " 'need',\n",
1732        " 'peed',\n",
1733        " 'reed',\n",
1734        " 'seed',\n",
1735        " 'teed',\n",
1736        " 'weed',\n",
1737        " 'weld',\n",
1738        " 'geld',\n",
1739        " 'held',\n",
1740        " 'meld',\n",
1741        " 'veld',\n",
1742        " 'vend',\n",
1743        " 'bend',\n",
1744        " 'fend',\n",
1745        " 'lend',\n",
1746        " 'mend',\n",
1747        " 'rend',\n",
1748        " 'send',\n",
1749        " 'tend',\n",
1750        " 'wend',\n",
1751        " 'wand',\n",
1752        " 'band',\n",
1753        " 'hand',\n",
1754        " 'land',\n",
1755        " 'sand',\n",
1756        " 'said',\n",
1757        " 'laid',\n",
1758        " 'maid',\n",
1759        " 'paid',\n",
1760        " 'raid',\n",
1761        " 'rail',\n",
1762        " 'bail',\n",
1763        " 'fail',\n",
1764        " 'hail',\n",
1765        " 'jail',\n",
1766        " 'mail',\n",
1767        " 'nail',\n",
1768        " 'pail',\n",
1769        " 'sail',\n",
1770        " 'tail',\n",
1771        " 'wail',\n",
1772        " 'wall',\n",
1773        " 'ball',\n",
1774        " 'call',\n",
1775        " 'fall',\n",
1776        " 'gall',\n",
1777        " 'hall',\n",
1778        " 'mall',\n",
1779        " 'pall',\n",
1780        " 'tall',\n",
1781        " 'tell',\n",
1782        " 'bell',\n",
1783        " 'cell',\n",
1784        " 'dell',\n",
1785        " 'fell',\n",
1786        " 'hell',\n",
1787        " 'jell',\n",
1788        " 'sell',\n",
1789        " 'well',\n",
1790        " 'yell',\n",
1791        " 'yelp',\n",
1792        " 'help',\n",
1793        " 'kelp',\n",
1794        " 'keep',\n",
1795        " 'beep',\n",
1796        " 'deep',\n",
1797        " 'jeep',\n",
1798        " 'peep',\n",
1799        " 'seep',\n",
1800        " 'veep',\n",
1801        " 'weep',\n",
1802        " 'week',\n",
1803        " 'geek',\n",
1804        " 'leek',\n",
1805        " 'meek',\n",
1806        " 'peek',\n",
1807        " 'reek',\n",
1808        " 'seek',\n",
1809        " 'seem',\n",
1810        " 'deem',\n",
1811        " 'teem',\n",
1812        " 'them',\n",
1813        " 'thee',\n",
1814        " 'tree',\n",
1815        " 'free',\n",
1816        " 'flee',\n",
1817        " 'glee',\n",
1818        " 'glue',\n",
1819        " 'blue',\n",
1820        " 'clue',\n",
1821        " 'flue',\n",
1822        " 'slue',\n",
1823        " 'sloe',\n",
1824        " 'aloe',\n",
1825        " 'floe',\n",
1826        " 'flop',\n",
1827        " 'clop',\n",
1828        " 'glop',\n",
1829        " 'plop',\n",
1830        " 'slop',\n",
1831        " 'shop',\n",
1832        " 'chop',\n",
1833        " 'coop',\n",
1834        " 'goop',\n",
1835        " 'hoop',\n",
1836        " 'loop',\n",
1837        " 'poop',\n",
1838        " 'prop',\n",
1839        " 'crop',\n",
1840        " 'drop',\n",
1841        " 'drip',\n",
1842        " 'grip',\n",
1843        " 'trip',\n",
1844        " 'trap',\n",
1845        " 'tray',\n",
1846        " 'bray',\n",
1847        " 'dray',\n",
1848        " 'fray',\n",
1849        " 'gray',\n",
1850        " 'pray',\n",
1851        " 'play',\n",
1852        " 'clay',\n",
1853        " 'flay',\n",
1854        " 'slay',\n",
1855        " 'spay',\n",
1856        " 'stay',\n",
1857        " 'sway',\n",
1858        " 'away',\n",
1859        " 'awry',\n",
1860        " 'aery',\n",
1861        " 'eery',\n",
1862        " 'very',\n",
1863        " 'vary',\n",
1864        " 'nary',\n",
1865        " 'wary',\n",
1866        " 'wiry',\n",
1867        " 'airy',\n",
1868        " 'airs',\n",
1869        " 'firs',\n",
1870        " 'sirs',\n",
1871        " 'sics',\n",
1872        " 'tics',\n",
1873        " 'ties',\n",
1874        " 'dies',\n",
1875        " 'hies',\n",
1876        " 'lies',\n",
1877        " 'pies',\n",
1878        " 'vies',\n",
1879        " 'vied',\n",
1880        " 'died',\n",
1881        " 'hied',\n",
1882        " 'lied',\n",
1883        " 'pied',\n",
1884        " 'tied',\n",
1885        " 'tier',\n",
1886        " 'bier',\n",
1887        " 'pier',\n",
1888        " 'peer',\n",
1889        " 'beer',\n",
1890        " 'deer',\n",
1891        " 'jeer',\n",
1892        " 'leer',\n",
1893        " 'seer',\n",
1894        " 'veer',\n",
1895        " 'weer',\n",
1896        " 'wear',\n",
1897        " 'bear',\n",
1898        " 'dear',\n",
1899        " 'fear',\n",
1900        " 'gear',\n",
1901        " 'hear',\n",
1902        " 'near',\n",
1903        " 'pear',\n",
1904        " 'rear',\n",
1905        " 'sear',\n",
1906        " 'tear',\n",
1907        " 'year',\n",
1908        " 'yeah',\n",
1909        " 'yeas',\n",
1910        " 'leas',\n",
1911        " 'peas',\n",
1912        " 'seas',\n",
1913        " 'teas',\n",
1914        " 'tees',\n",
1915        " 'bees',\n",
1916        " 'fees',\n",
1917        " 'gees',\n",
1918        " 'lees',\n",
1919        " 'pees',\n",
1920        " 'sees',\n",
1921        " 'wees',\n",
1922        " 'woes',\n",
1923        " 'does',\n",
1924        " 'foes',\n",
1925        " 'goes',\n",
1926        " 'hoes',\n",
1927        " 'noes',\n",
1928        " 'roes',\n",
1929        " 'toes',\n",
1930        " 'togs',\n",
1931        " 'bogs',\n",
1932        " 'cogs',\n",
1933        " 'dogs',\n",
1934        " 'fogs',\n",
1935        " 'hogs',\n",
1936        " 'jogs',\n",
1937        " 'logs',\n",
1938        " 'lags',\n",
1939        " 'bags',\n",
1940        " 'fags',\n",
1941        " 'gags',\n",
1942        " 'hags',\n",
1943        " 'jags',\n",
1944        " 'nags',\n",
1945        " 'rags',\n",
1946        " 'sags',\n",
1947        " 'tags',\n",
1948        " 'wags',\n",
1949        " 'wigs',\n",
1950        " 'digs',\n",
1951        " 'figs',\n",
1952        " 'gigs',\n",
1953        " 'jigs',\n",
1954        " 'pigs',\n",
1955        " 'rigs',\n",
1956        " 'rugs',\n",
1957        " 'bugs',\n",
1958        " 'hugs',\n",
1959        " 'jugs',\n",
1960        " 'lugs',\n",
1961        " 'mugs',\n",
1962        " 'pugs',\n",
1963        " 'tugs',\n",
1964        " 'tubs',\n",
1965        " 'cubs',\n",
1966        " 'dubs',\n",
1967        " 'hubs',\n",
1968        " 'nubs',\n",
1969        " 'pubs',\n",
1970        " 'rubs',\n",
1971        " 'subs',\n",
1972        " 'sobs',\n",
1973        " 'bobs',\n",
1974        " 'cobs',\n",
1975        " 'fobs',\n",
1976        " 'gobs',\n",
1977        " 'hobs',\n",
1978        " 'jobs',\n",
1979        " 'lobs',\n",
1980        " 'mobs',\n",
1981        " 'robs',\n",
1982        " 'ribs',\n",
1983        " 'bibs',\n",
1984        " 'fibs',\n",
1985        " 'jibs',\n",
1986        " 'nibs',\n",
1987        " 'nabs',\n",
1988        " 'cabs',\n",
1989        " 'dabs',\n",
1990        " 'gabs',\n",
1991        " 'jabs',\n",
1992        " 'labs',\n",
1993        " 'tabs',\n",
1994        " 'tads',\n",
1995        " 'cads',\n",
1996        " 'dads',\n",
1997        " 'fads',\n",
1998        " 'gads',\n",
1999        " 'lads',\n",
2000        " 'mads',\n",
2001        " 'pads',\n",
2002        " 'wads',\n",
2003        " 'weds',\n",
2004        " 'beds',\n",
2005        " 'feds',\n",
2006        " 'reds',\n",
2007        " 'rids',\n",
2008        " 'aids',\n",
2009        " 'bids',\n",
2010        " 'kids',\n",
2011        " 'lids',\n",
2012        " 'lips',\n",
2013        " 'dips',\n",
2014        " 'hips',\n",
2015        " 'nips',\n",
2016        " 'pips',\n",
2017        " 'rips',\n",
2018        " 'sips',\n",
2019        " 'tips',\n",
2020        " 'yips',\n",
2021        " 'zips',\n",
2022        " 'zaps',\n",
2023        " 'caps',\n",
2024        " 'gaps',\n",
2025        " 'laps',\n",
2026        " 'maps',\n",
2027        " 'naps',\n",
2028        " 'paps',\n",
2029        " 'raps',\n",
2030        " 'saps',\n",
2031        " 'taps',\n",
2032        " 'yaps',\n",
2033        " 'yeps',\n",
2034        " 'peps',\n",
2035        " 'reps',\n",
2036        " 'refs',\n",
2037        " 'reis',\n",
2038        " 'leis',\n",
2039        " 'legs',\n",
2040        " 'begs',\n",
2041        " 'kegs',\n",
2042        " 'megs',\n",
2043        " 'pegs',\n",
2044        " 'pens',\n",
2045        " 'dens',\n",
2046        " 'fens',\n",
2047        " 'hens',\n",
2048        " 'kens',\n",
2049        " 'lens',\n",
2050        " 'tens',\n",
2051        " 'wens',\n",
2052        " 'yens',\n",
2053        " 'yews',\n",
2054        " 'hews',\n",
2055        " 'mews',\n",
2056        " 'news',\n",
2057        " 'pews',\n",
2058        " 'sews',\n",
2059        " 'saws',\n",
2060        " 'caws',\n",
2061        " 'haws',\n",
2062        " 'jaws',\n",
2063        " 'laws',\n",
2064        " 'maws',\n",
2065        " 'paws',\n",
2066        " 'yaws',\n",
2067        " 'yaks',\n",
2068        " 'oaks',\n",
2069        " 'oafs',\n",
2070        " 'oars',\n",
2071        " 'bars',\n",
2072        " 'cars',\n",
2073        " 'ears',\n",
2074        " 'jars',\n",
2075        " 'mars',\n",
2076        " 'pars',\n",
2077        " 'tars',\n",
2078        " 'wars',\n",
2079        " 'ways',\n",
2080        " 'bays',\n",
2081        " 'days',\n",
2082        " 'gays',\n",
2083        " 'hays',\n",
2084        " 'jays',\n",
2085        " 'lays',\n",
2086        " 'nays',\n",
2087        " 'pays',\n",
2088        " 'rays',\n",
2089        " 'says',\n",
2090        " 'sacs',\n",
2091        " 'secs',\n",
2092        " 'sets',\n",
2093        " 'bets',\n",
2094        " 'gets',\n",
2095        " 'jets',\n",
2096        " 'lets',\n",
2097        " 'nets',\n",
2098        " 'pets',\n",
2099        " 'vets',\n",
2100        " 'wets',\n",
2101        " 'wits',\n",
2102        " 'bits',\n",
2103        " 'fits',\n",
2104        " 'hits',\n",
2105        " 'kits',\n",
2106        " 'nits',\n",
2107        " 'pits',\n",
2108        " 'sits',\n",
2109        " 'tits',\n",
2110        " 'tats',\n",
2111        " 'bats',\n",
2112        " 'cats',\n",
2113        " 'eats',\n",
2114        " 'fats',\n",
2115        " 'hats',\n",
2116        " 'lats',\n",
2117        " 'mats',\n",
2118        " 'oats',\n",
2119        " 'pats',\n",
2120        " 'rats',\n",
2121        " 'vats',\n",
2122        " 'vans',\n",
2123        " 'bans',\n",
2124        " 'cans',\n",
2125        " 'fans',\n",
2126        " 'mans',\n",
2127        " 'pans',\n",
2128        " 'sans',\n",
2129        " 'tans',\n",
2130        " 'tins',\n",
2131        " 'bins',\n",
2132        " 'dins',\n",
2133        " 'fins',\n",
2134        " 'gins',\n",
2135        " 'pins',\n",
2136        " 'sins',\n",
2137        " 'wins',\n",
2138        " 'wind',\n",
2139        " 'bind',\n",
2140        " 'find',\n",
2141        " 'hind',\n",
2142        " 'kind',\n",
2143        " 'mind',\n",
2144        " 'rind',\n",
2145        " 'ring',\n",
2146        " 'ding',\n",
2147        " 'king',\n",
2148        " 'ping',\n",
2149        " 'sing',\n",
2150        " 'ting',\n",
2151        " 'wing',\n",
2152        " 'wine',\n",
2153        " 'dine',\n",
2154        " 'fine',\n",
2155        " 'line',\n",
2156        " 'mine',\n",
2157        " 'nine',\n",
2158        " 'pine',\n",
2159        " 'sine',\n",
2160        " 'tine',\n",
2161        " 'vine',\n",
2162        " 'vane']"
2163       ]
2164      },
2165      "execution_count": 25,
2166      "metadata": {},
2167      "output_type": "execute_result"
2168     }
2169    ],
2170    "source": [
2171     "dfs_search('cart', 'vane')"
2172    ]
2173   },
2174   {
2175    "cell_type": "code",
2176    "execution_count": 26,
2177    "metadata": {
2178     "collapsed": true
2179    },
2180    "outputs": [],
2181    "source": [
2182     "def astar_search(start, goal, debug=False):\n",
2183     "    agenda = [(distance(start, goal), [start])]\n",
2184     "    heapq.heapify(agenda)\n",
2185     "    finished = False\n",
2186     "    while not finished and agenda:\n",
2187     "        _, current = heapq.heappop(agenda)\n",
2188     "        if debug:\n",
2189     "            print(current)\n",
2190     "        if current[-1] == goal:\n",
2191     "            finished = True\n",
2192     "        else:\n",
2193     "            successors = extend(current)\n",
2194     "            for s in successors:\n",
2195     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
2196     "    if agenda:\n",
2197     "        return current\n",
2198     "    else:\n",
2199     "        return None        "
2200    ]
2201   },
2202   {
2203    "cell_type": "code",
2204    "execution_count": 27,
2205    "metadata": {},
2206    "outputs": [
2207     {
2208      "name": "stdout",
2209      "output_type": "stream",
2210      "text": [
2211       "['cart']\n",
2212       "['cart', 'cant']\n",
2213       "['cart', 'cant', 'cane']\n",
2214       "['cart', 'cant', 'cane', 'vane']\n"
2215      ]
2216     },
2217     {
2218      "data": {
2219       "text/plain": [
2220        "['cart', 'cant', 'cane', 'vane']"
2221       ]
2222      },
2223      "execution_count": 27,
2224      "metadata": {},
2225      "output_type": "execute_result"
2226     }
2227    ],
2228    "source": [
2229     "astar_search('cart', 'vane', debug=True)"
2230    ]
2231   },
2232   {
2233    "cell_type": "code",
2234    "execution_count": 28,
2235    "metadata": {
2236     "collapsed": true
2237    },
2238    "outputs": [],
2239    "source": [
2240     "def astar_search_closed(start, goal, debug=False):\n",
2241     "    agenda = [(distance(start, goal), [start])]\n",
2242     "    heapq.heapify(agenda)\n",
2243     "    closed = set()\n",
2244     "    finished = False\n",
2245     "    while not finished and agenda:\n",
2246     "        _, current = heapq.heappop(agenda)\n",
2247     "        if debug:\n",
2248     "            print(current)\n",
2249     "        if current[-1] == goal:\n",
2250     "            finished = True\n",
2251     "        else:\n",
2252     "            closed.add(current[-1])\n",
2253     "            successors = extend(current, closed)\n",
2254     "            for s in successors:\n",
2255     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
2256     "    if agenda:\n",
2257     "        return current\n",
2258     "    else:\n",
2259     "        return None        "
2260    ]
2261   },
2262   {
2263    "cell_type": "code",
2264    "execution_count": 29,
2265    "metadata": {},
2266    "outputs": [
2267     {
2268      "name": "stdout",
2269      "output_type": "stream",
2270      "text": [
2271       "['cart']\n",
2272       "['cart', 'cant']\n",
2273       "['cart', 'cant', 'cane']\n",
2274       "['cart', 'cant', 'cane', 'vane']\n"
2275      ]
2276     },
2277     {
2278      "data": {
2279       "text/plain": [
2280        "['cart', 'cant', 'cane', 'vane']"
2281       ]
2282      },
2283      "execution_count": 29,
2284      "metadata": {},
2285      "output_type": "execute_result"
2286     }
2287    ],
2288    "source": [
2289     "astar_search_closed('cart', 'vane', debug=True)"
2290    ]
2291   },
2292   {
2293    "cell_type": "markdown",
2294    "metadata": {},
2295    "source": [
2296     "# Mutually-reachable sets\n",
2297     "\n",
2298     "Find the transitive closure of the `neighbours` relation, so we can see which words can be transformed into which other words."
2299    ]
2300   },
2301   {
2302    "cell_type": "code",
2303    "execution_count": 30,
2304    "metadata": {},
2305    "outputs": [
2306     {
2307      "data": {
2308       "text/plain": [
2309        "94"
2310       ]
2311      },
2312      "execution_count": 30,
2313      "metadata": {},
2314      "output_type": "execute_result"
2315     }
2316    ],
2317    "source": [
2318     "candidates = [set([k] + neighbours[k]) for k in neighbours]\n",
2319     "reachables = []\n",
2320     "while candidates:\n",
2321     "    current = set(candidates.pop())\n",
2322     "    altered = False\n",
2323     "    for other in candidates:\n",
2324     "        if current.intersection(other):\n",
2325     "            altered = True\n",
2326     "            current.update(other)\n",
2327     "            candidates.remove(other)\n",
2328     "    if altered:\n",
2329     "        candidates.append(current)\n",
2330     "    else:\n",
2331     "        reachables.append(current)\n",
2332     "\n",
2333     "len(reachables)"
2334    ]
2335   },
2336   {
2337    "cell_type": "code",
2338    "execution_count": 31,
2339    "metadata": {},
2340    "outputs": [
2341     {
2342      "data": {
2343       "text/plain": [
2344        "2204"
2345       ]
2346      },
2347      "execution_count": 31,
2348      "metadata": {},
2349      "output_type": "execute_result"
2350     }
2351    ],
2352    "source": [
2353     "len(max(reachables, key=len))"
2354    ]
2355   },
2356   {
2357    "cell_type": "code",
2358    "execution_count": 32,
2359    "metadata": {},
2360    "outputs": [
2361     {
2362      "data": {
2363       "text/plain": [
2364        "1"
2365       ]
2366      },
2367      "execution_count": 32,
2368      "metadata": {},
2369      "output_type": "execute_result"
2370     }
2371    ],
2372    "source": [
2373     "len(min(reachables, key=len))"
2374    ]
2375   },
2376   {
2377    "cell_type": "code",
2378    "execution_count": 33,
2379    "metadata": {
2380     "scrolled": true
2381    },
2382    "outputs": [
2383     {
2384      "data": {
2385       "text/plain": [
2386        "Counter({1: 75, 2: 6, 3: 7, 4: 2, 5: 2, 6: 1, 2204: 1})"
2387       ]
2388      },
2389      "execution_count": 33,
2390      "metadata": {},
2391      "output_type": "execute_result"
2392     }
2393    ],
2394    "source": [
2395     "collections.Counter(len(r) for r in reachables)"
2396    ]
2397   },
2398   {
2399    "cell_type": "code",
2400    "execution_count": 34,
2401    "metadata": {},
2402    "outputs": [
2403     {
2404      "data": {
2405       "text/plain": [
2406        "[5]"
2407       ]
2408      },
2409      "execution_count": 34,
2410      "metadata": {},
2411      "output_type": "execute_result"
2412     }
2413    ],
2414    "source": [
2415     "[len(r) for r in reachables if 'abbe' in r]"
2416    ]
2417   },
2418   {
2419    "cell_type": "code",
2420    "execution_count": 35,
2421    "metadata": {},
2422    "outputs": [
2423     {
2424      "data": {
2425       "text/plain": [
2426        "[{'abbe', 'able', 'ably', 'ally', 'axle'}]"
2427       ]
2428      },
2429      "execution_count": 35,
2430      "metadata": {},
2431      "output_type": "execute_result"
2432     }
2433    ],
2434    "source": [
2435     "[r for r in reachables if 'abbe' in r]"
2436    ]
2437   },
2438   {
2439    "cell_type": "code",
2440    "execution_count": 36,
2441    "metadata": {},
2442    "outputs": [
2443     {
2444      "data": {
2445       "text/plain": [
2446        "['buns', 'bunk', 'punk']"
2447       ]
2448      },
2449      "execution_count": 36,
2450      "metadata": {},
2451      "output_type": "execute_result"
2452     }
2453    ],
2454    "source": [
2455     "astar_search('buns', 'punk')"
2456    ]
2457   },
2458   {
2459    "cell_type": "code",
2460    "execution_count": 37,
2461    "metadata": {
2462     "collapsed": true
2463    },
2464    "outputs": [],
2465    "source": [
2466     "for a in reachables:\n",
2467     "    for b in reachables:\n",
2468     "        if a != b:\n",
2469     "            if not a.isdisjoint(b):\n",
2470     "                print(a, b)"
2471    ]
2472   },
2473   {
2474    "cell_type": "code",
2475    "execution_count": 38,
2476    "metadata": {
2477     "collapsed": true
2478    },
2479    "outputs": [],
2480    "source": [
2481     "# longest_chain = []\n",
2482     "# with open('all-chains-4.txt', 'w', 1) as f:\n",
2483     "#     for ws in reachables:\n",
2484     "#         for s in ws:\n",
2485     "#             for t in ws:\n",
2486     "#                 if s < t:\n",
2487     "#                     chain = astar_search(s, t)\n",
2488     "#                     if chain:\n",
2489     "#                         f.write('{}\\n'.format(chain))\n",
2490     "#                         if len(chain) > len(longest_chain):\n",
2491     "#                             longest_chain = chain\n",
2492     "\n",
2493     "# longest_chain"
2494    ]
2495   },
2496   {
2497    "cell_type": "code",
2498    "execution_count": 39,
2499    "metadata": {
2500     "collapsed": true
2501    },
2502    "outputs": [],
2503    "source": [
2504     "bigset = max(reachables, key=len)"
2505    ]
2506   },
2507   {
2508    "cell_type": "code",
2509    "execution_count": 40,
2510    "metadata": {},
2511    "outputs": [
2512     {
2513      "name": "stdout",
2514      "output_type": "stream",
2515      "text": [
2516       "['bops', 'bogs', 'begs', 'bees', 'byes', 'eyes', 'eyed']\n",
2517       "['foal', 'foil', 'fail']\n",
2518       "['bush', 'bash', 'base', 'bale', 'ball', 'boll']\n",
2519       "['rift', 'lift', 'life', 'live', 'give', 'gave']\n",
2520       "['club', 'clue', 'flue', 'flee', 'fled', 'pled', 'pied', 'lied', 'lien', 'mien']\n",
2521       "['rung', 'dung', 'ding', 'dins', 'dies', 'lies', 'lien']\n",
2522       "['baas', 'bags', 'bugs', 'bums', 'sums', 'sumo']\n",
2523       "['fits', 'bits', 'bins', 'bind']\n",
2524       "['lids', 'bids', 'bias', 'boas', 'boat', 'boot', 'soot', 'snot', 'snob']\n",
2525       "['cake', 'came', 'cams', 'caws', 'cows', 'tows']\n",
2526       "['tort', 'toot', 'trot', 'troy', 'tray', 'tram', 'cram']\n",
2527       "['sews', 'pews', 'pees', 'peed', 'pied']\n",
2528       "['lack', 'hack', 'hawk', 'haws', 'hows', 'tows']\n",
2529       "['dots', 'dons', 'dens', 'dent', 'pent', 'pest', 'peso']\n",
2530       "['ekes', 'eyes', 'byes', 'bees', 'beet', 'bent', 'lent', 'lept']\n",
2531       "['ruin', 'rain', 'gain', 'grin', 'grid', 'arid', 'acid', 'aced', 'iced']\n",
2532       "['sing', 'sins', 'bins', 'bias', 'bras', 'bray', 'tray', 'trap']\n",
2533       "['lira', 'lire', 'wire', 'wise', 'wish']\n",
2534       "['gash', 'cash', 'case', 'cape', 'rape']\n",
2535       "['crop', 'coop', 'coot', 'loot', 'loft']\n"
2536      ]
2537     }
2538    ],
2539    "source": [
2540     "for _ in range(20):\n",
2541     "    start, goal = random.sample(bigset, 2)\n",
2542     "    print(astar_search_closed(start, goal))"
2543    ]
2544   },
2545   {
2546    "cell_type": "code",
2547    "execution_count": 41,
2548    "metadata": {},
2549    "outputs": [
2550     {
2551      "data": {
2552       "text/plain": [
2553        "['cops', 'coos', 'coon', 'coin', 'chin', 'thin', 'this', 'thus', 'thug']"
2554       ]
2555      },
2556      "execution_count": 41,
2557      "metadata": {},
2558      "output_type": "execute_result"
2559     }
2560    ],
2561    "source": [
2562     "astar_search('cops', 'thug')"
2563    ]
2564   },
2565   {
2566    "cell_type": "code",
2567    "execution_count": 42,
2568    "metadata": {},
2569    "outputs": [
2570     {
2571      "data": {
2572       "text/plain": [
2573        "[2204]"
2574       ]
2575      },
2576      "execution_count": 42,
2577      "metadata": {},
2578      "output_type": "execute_result"
2579     }
2580    ],
2581    "source": [
2582     "[len(r) for r in reachables if 'love' in r if 'hate' in r]"
2583    ]
2584   },
2585   {
2586    "cell_type": "code",
2587    "execution_count": 73,
2588    "metadata": {},
2589    "outputs": [
2590     {
2591      "data": {
2592       "text/plain": [
2593        "[2204]"
2594       ]
2595      },
2596      "execution_count": 73,
2597      "metadata": {},
2598      "output_type": "execute_result"
2599     }
2600    ],
2601    "source": [
2602     "[len(r) for r in reachables if 'stay' in r ]"
2603    ]
2604   },
2605   {
2606    "cell_type": "code",
2607    "execution_count": 43,
2608    "metadata": {},
2609    "outputs": [
2610     {
2611      "data": {
2612       "text/plain": [
2613        "['hate', 'have', 'hove', 'love']"
2614       ]
2615      },
2616      "execution_count": 43,
2617      "metadata": {},
2618      "output_type": "execute_result"
2619     }
2620    ],
2621    "source": [
2622     "astar_search('hate', 'love')"
2623    ]
2624   },
2625   {
2626    "cell_type": "code",
2627    "execution_count": 44,
2628    "metadata": {},
2629    "outputs": [
2630     {
2631      "data": {
2632       "text/plain": [
2633        "['wars', 'ware', 'wave', 'wove', 'love']"
2634       ]
2635      },
2636      "execution_count": 44,
2637      "metadata": {},
2638      "output_type": "execute_result"
2639     }
2640    ],
2641    "source": [
2642     "astar_search('wars', 'love')"
2643    ]
2644   },
2645   {
2646    "cell_type": "code",
2647    "execution_count": 45,
2648    "metadata": {},
2649    "outputs": [
2650     {
2651      "name": "stdout",
2652      "output_type": "stream",
2653      "text": [
2654       "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
2655       "Wall time: 850 µs\n"
2656      ]
2657     },
2658     {
2659      "data": {
2660       "text/plain": [
2661        "5"
2662       ]
2663      },
2664      "execution_count": 45,
2665      "metadata": {},
2666      "output_type": "execute_result"
2667     }
2668    ],
2669    "source": [
2670     "%time len(astar_search('wars', 'love'))"
2671    ]
2672   },
2673   {
2674    "cell_type": "code",
2675    "execution_count": 46,
2676    "metadata": {},
2677    "outputs": [
2678     {
2679      "name": "stdout",
2680      "output_type": "stream",
2681      "text": [
2682       "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
2683       "Wall time: 353 µs\n"
2684      ]
2685     },
2686     {
2687      "data": {
2688       "text/plain": [
2689        "5"
2690       ]
2691      },
2692      "execution_count": 46,
2693      "metadata": {},
2694      "output_type": "execute_result"
2695     }
2696    ],
2697    "source": [
2698     "%time len(astar_search_closed('wars', 'love'))"
2699    ]
2700   },
2701   {
2702    "cell_type": "code",
2703    "execution_count": 47,
2704    "metadata": {},
2705    "outputs": [
2706     {
2707      "name": "stdout",
2708      "output_type": "stream",
2709      "text": [
2710       "CPU times: user 76 ms, sys: 0 ns, total: 76 ms\n",
2711       "Wall time: 75.1 ms\n"
2712      ]
2713     },
2714     {
2715      "data": {
2716       "text/plain": [
2717        "404"
2718       ]
2719      },
2720      "execution_count": 47,
2721      "metadata": {},
2722      "output_type": "execute_result"
2723     }
2724    ],
2725    "source": [
2726     "%time len(dfs_search('wars', 'love'))"
2727    ]
2728   },
2729   {
2730    "cell_type": "code",
2731    "execution_count": null,
2732    "metadata": {},
2733    "outputs": [],
2734    "source": [
2735     "# %time len(bfs_search('wars', 'love'))"
2736    ]
2737   },
2738   {
2739    "cell_type": "code",
2740    "execution_count": null,
2741    "metadata": {},
2742    "outputs": [],
2743    "source": [
2744     "%time len(bfs_search_closed('wars', 'love'))"
2745    ]
2746   },
2747   {
2748    "cell_type": "code",
2749    "execution_count": 50,
2750    "metadata": {},
2751    "outputs": [
2752     {
2753      "data": {
2754       "text/plain": [
2755        "['fear', 'feat', 'fest', 'lest', 'lost', 'lose', 'love']"
2756       ]
2757      },
2758      "execution_count": 50,
2759      "metadata": {},
2760      "output_type": "execute_result"
2761     }
2762    ],
2763    "source": [
2764     "astar_search('fear', 'love')"
2765    ]
2766   },
2767   {
2768    "cell_type": "code",
2769    "execution_count": 51,
2770    "metadata": {},
2771    "outputs": [
2772     {
2773      "data": {
2774       "text/plain": [
2775        "['fail', 'fall', 'pall', 'pals', 'pass']"
2776       ]
2777      },
2778      "execution_count": 51,
2779      "metadata": {},
2780      "output_type": "execute_result"
2781     }
2782    ],
2783    "source": [
2784     "astar_search('fail', 'pass')"
2785    ]
2786   },
2787   {
2788    "cell_type": "code",
2789    "execution_count": 52,
2790    "metadata": {},
2791    "outputs": [
2792     {
2793      "data": {
2794       "text/plain": [
2795        "['star', 'soar', 'boar', 'boor', 'boon', 'born']"
2796       ]
2797      },
2798      "execution_count": 52,
2799      "metadata": {},
2800      "output_type": "execute_result"
2801     }
2802    ],
2803    "source": [
2804     "astar_search('star', 'born')"
2805    ]
2806   },
2807   {
2808    "cell_type": "code",
2809    "execution_count": 53,
2810    "metadata": {},
2811    "outputs": [
2812     {
2813      "data": {
2814       "text/plain": [
2815        "['open',\n",
2816        " 'oven',\n",
2817        " 'even',\n",
2818        " 'eves',\n",
2819        " 'eyes',\n",
2820        " 'byes',\n",
2821        " 'bees',\n",
2822        " 'begs',\n",
2823        " 'bags',\n",
2824        " 'bass',\n",
2825        " 'pass']"
2826       ]
2827      },
2828      "execution_count": 53,
2829      "metadata": {},
2830      "output_type": "execute_result"
2831     }
2832    ],
2833    "source": [
2834     "astar_search('open', 'pass')"
2835    ]
2836   },
2837   {
2838    "cell_type": "code",
2839    "execution_count": 54,
2840    "metadata": {},
2841    "outputs": [
2842     {
2843      "data": {
2844       "text/plain": [
2845        "['bass',\n",
2846        " 'lass',\n",
2847        " 'mass',\n",
2848        " 'sass',\n",
2849        " 'puss',\n",
2850        " 'pads',\n",
2851        " 'pals',\n",
2852        " 'pans',\n",
2853        " 'paps',\n",
2854        " 'pars',\n",
2855        " 'pats',\n",
2856        " 'paws',\n",
2857        " 'pays',\n",
2858        " 'past']"
2859       ]
2860      },
2861      "execution_count": 54,
2862      "metadata": {},
2863      "output_type": "execute_result"
2864     }
2865    ],
2866    "source": [
2867     "neighbours['pass']"
2868    ]
2869   },
2870   {
2871    "cell_type": "code",
2872    "execution_count": 55,
2873    "metadata": {},
2874    "outputs": [
2875     {
2876      "data": {
2877       "text/plain": [
2878        "[1]"
2879       ]
2880      },
2881      "execution_count": 55,
2882      "metadata": {},
2883      "output_type": "execute_result"
2884     }
2885    ],
2886    "source": [
2887     "[len(r) for r in reachables if 'exam' in r]"
2888    ]
2889   },
2890   {
2891    "cell_type": "code",
2892    "execution_count": 56,
2893    "metadata": {},
2894    "outputs": [
2895     {
2896      "data": {
2897       "text/plain": [
2898        "[2204]"
2899       ]
2900      },
2901      "execution_count": 56,
2902      "metadata": {},
2903      "output_type": "execute_result"
2904     }
2905    ],
2906    "source": [
2907     "[len(r) for r in reachables if 'star' in r if 'born' in r]"
2908    ]
2909   },
2910   {
2911    "cell_type": "code",
2912    "execution_count": 57,
2913    "metadata": {},
2914    "outputs": [
2915     {
2916      "name": "stdout",
2917      "output_type": "stream",
2918      "text": [
2919       "1 loop, best of 3: 12.3 s per loop\n"
2920      ]
2921     }
2922    ],
2923    "source": [
2924     "%%timeit\n",
2925     "astar_search('bats', 'exit')"
2926    ]
2927   },
2928   {
2929    "cell_type": "code",
2930    "execution_count": 58,
2931    "metadata": {},
2932    "outputs": [
2933     {
2934      "name": "stdout",
2935      "output_type": "stream",
2936      "text": [
2937       "1 loop, best of 3: 200 ms per loop\n"
2938      ]
2939     }
2940    ],
2941    "source": [
2942     "%%timeit\n",
2943     "astar_search_closed('bats', 'exit')"
2944    ]
2945   },
2946   {
2947    "cell_type": "code",
2948    "execution_count": 59,
2949    "metadata": {},
2950    "outputs": [
2951     {
2952      "data": {
2953       "text/plain": [
2954        "['bats',\n",
2955        " 'bans',\n",
2956        " 'band',\n",
2957        " 'sand',\n",
2958        " 'said',\n",
2959        " 'skid',\n",
2960        " 'skit',\n",
2961        " 'smit',\n",
2962        " 'emit',\n",
2963        " 'exit']"
2964       ]
2965      },
2966      "execution_count": 59,
2967      "metadata": {},
2968      "output_type": "execute_result"
2969     }
2970    ],
2971    "source": [
2972     "astar_search_closed('bats', 'exit')"
2973    ]
2974   },
2975   {
2976    "cell_type": "code",
2977    "execution_count": 60,
2978    "metadata": {},
2979    "outputs": [
2980     {
2981      "data": {
2982       "text/plain": [
2983        "{2: [['exes', 'exec'], ['rush', 'tush'], ['wile', 'wily'], ['shoo', 'shot']],\n",
2984        " 3: [['bins', 'fink'], ['waft', 'wand'], ['heel', 'jell'], ['tent', 'west']],\n",
2985        " 4: [['yore', 'polo'], ['hale', 'case'], ['horn', 'look'], ['tang', 'nuns']],\n",
2986        " 5: [['crab', 'baas'], ['yens', 'dead'], ['work', 'paps'], ['tune', 'zaps']],\n",
2987        " 6: [['mist', 'sold'], ['bats', 'sort'], ['leek', 'mads'], ['loop', 'dome']],\n",
2988        " 7: [['rime', 'hoof'], ['grim', 'reed'], ['lies', 'eave'], ['ties', 'whiz']],\n",
2989        " 8: [['drag', 'lied'], ['ages', 'yawl'], ['earl', 'deal'], ['gins', 'scab']],\n",
2990        " 9: [['tyre', 'swum'], ['dike', 'flux'], ['hour', 'laze'], ['trek', 'bait']],\n",
2991        " 10: [['ides', 'rasp'], ['egos', 'racy'], ['shim', 'ills'], ['bark', 'arty']],\n",
2992        " 11: [['ergo', 'apex'], ['whey', 'owns'], ['anew', 'rapt'], ['thug', 'bate']],\n",
2993        " 12: [['ream', 'imps'], ['meat', 'umps'], ['daze', 'knee'], ['clay', 'over']],\n",
2994        " 13: [['oxen', 'blab'], ['blip', 'omen'], ['twig', 'ibis'], ['chew', 'umps']],\n",
2995        " 14: [['amen', 'blip'], ['umps', 'futz'], ['amps', 'glib'], ['chum', 'whys']],\n",
2996        " 15: [['thug', 'ibis']]}"
2997       ]
2998      },
2999      "execution_count": 60,
3000      "metadata": {},
3001      "output_type": "execute_result"
3002     }
3003    ],
3004    "source": [
3005     "solutions = {}\n",
3006     "for _ in range(10000):\n",
3007     "    start, goal = random.sample(bigset, 2)\n",
3008     "    solution = astar_search_closed(start, goal)\n",
3009     "    sl = len(solution)\n",
3010     "    if sl not in solutions:\n",
3011     "        solutions[sl] = []\n",
3012     "    if len(solutions[sl]) < 4:\n",
3013     "        solutions[sl].append([start, goal])\n",
3014     "        \n",
3015     "#     if len(solution) >= 10:\n",
3016     "#         solutions += [solution]\n",
3017     "        \n",
3018     "solutions"
3019    ]
3020   },
3021   {
3022    "cell_type": "code",
3023    "execution_count": 64,
3024    "metadata": {
3025     "collapsed": true
3026    },
3027    "outputs": [],
3028    "source": [
3029     "solutions = {2: [['heel', 'keel'], ['wane', 'wave'], ['cell', 'sell'], ['cons', 'cobs']],\n",
3030     " 3: [['hank', 'haws'], ['bars', 'bets'], ['rats', 'paws'], ['lock', 'hack']],\n",
3031     " 4: [['rule', 'sore'], ['wavy', 'rape'], ['peas', 'ping'], ['bond', 'toll']],\n",
3032     " 5: [['cope', 'yowl'], ['lose', 'loci'], ['rump', 'dash'], ['four', 'dyes']],\n",
3033     " 6: [['boon', 'sell'], ['lots', 'pomp'], ['cola', 'turn'], ['boos', 'laid']],\n",
3034     " 7: [['eave', 'inns'], ['meek', 'mere'], ['keys', 'wily'], ['slam', 'yore']],\n",
3035     " 8: [['hack', 'flip'], ['crag', 'huge'], ['flux', 'gill'], ['play', 'busy']],\n",
3036     " 9: [['lacy', 'whey'], ['wren', 'rook'], ['lire', 'drip'], ['grab', 'lame']],\n",
3037     " 10: [['over', 'turn'], ['worn', 'anew'], ['stow', 'elks'], ['ergo', 'rich']],\n",
3038     " 11: [['bask', 'idea'], ['gabs', 'thud'], ['idea', 'clod'], ['mark', 'ibis']],\n",
3039     " 12: [['umps', 'torn'], ['futz', 'shun'], ['abut', 'face'], ['slug', 'open']],\n",
3040     " 13: [['umps', 'skin'], ['chum', 'rats'], ['fury', 'chum'], ['omen', 'zany']],\n",
3041     " 14: [['chug', 'gaff'], ['atom', 'fizz'], ['chug', 'jinn'], ['amen', 'flog'],\n",
3042     "     ['buzz', 'grog'], ['imps', 'pros']],\n",
3043     " 15: [['chug', 'oxen'], ['amen', 'doff']]}"
3044    ]
3045   },
3046   {
3047    "cell_type": "code",
3048    "execution_count": 66,
3049    "metadata": {},
3050    "outputs": [
3051     {
3052      "name": "stdout",
3053      "output_type": "stream",
3054      "text": [
3055       "1 loop, best of 3: 487 ms per loop\n"
3056      ]
3057     }
3058    ],
3059    "source": [
3060     "%%timeit\n",
3061     "astar_search_closed('blab', 'amen')"
3062    ]
3063   },
3064   {
3065    "cell_type": "code",
3066    "execution_count": 67,
3067    "metadata": {},
3068    "outputs": [
3069     {
3070      "name": "stdout",
3071      "output_type": "stream",
3072      "text": [
3073       "CPU times: user 768 ms, sys: 0 ns, total: 768 ms\n",
3074       "Wall time: 768 ms\n"
3075      ]
3076     },
3077     {
3078      "data": {
3079       "text/plain": [
3080        "14"
3081       ]
3082      },
3083      "execution_count": 67,
3084      "metadata": {},
3085      "output_type": "execute_result"
3086     }
3087    ],
3088    "source": [
3089     "%time len(astar_search_closed('blab', 'amen'))"
3090    ]
3091   },
3092   {
3093    "cell_type": "code",
3094    "execution_count": 68,
3095    "metadata": {},
3096    "outputs": [
3097     {
3098      "name": "stdout",
3099      "output_type": "stream",
3100      "text": [
3101       "CPU times: user 176 ms, sys: 0 ns, total: 176 ms\n",
3102       "Wall time: 176 ms\n"
3103      ]
3104     },
3105     {
3106      "data": {
3107       "text/plain": [
3108        "15"
3109       ]
3110      },
3111      "execution_count": 68,
3112      "metadata": {},
3113      "output_type": "execute_result"
3114     }
3115    ],
3116    "source": [
3117     "%time len(astar_search_closed('amen', 'doff'))"
3118    ]
3119   },
3120   {
3121    "cell_type": "code",
3122    "execution_count": 69,
3123    "metadata": {},
3124    "outputs": [
3125     {
3126      "name": "stdout",
3127      "output_type": "stream",
3128      "text": [
3129       "CPU times: user 72 ms, sys: 0 ns, total: 72 ms\n",
3130       "Wall time: 70.6 ms\n"
3131      ]
3132     },
3133     {
3134      "data": {
3135       "text/plain": [
3136        "14"
3137       ]
3138      },
3139      "execution_count": 69,
3140      "metadata": {},
3141      "output_type": "execute_result"
3142     }
3143    ],
3144    "source": [
3145     "%time len(astar_search_closed('chug', 'jinn'))"
3146    ]
3147   },
3148   {
3149    "cell_type": "code",
3150    "execution_count": 70,
3151    "metadata": {},
3152    "outputs": [
3153     {
3154      "name": "stdout",
3155      "output_type": "stream",
3156      "text": [
3157       "CPU times: user 32 ms, sys: 0 ns, total: 32 ms\n",
3158       "Wall time: 35.7 ms\n"
3159      ]
3160     },
3161     {
3162      "data": {
3163       "text/plain": [
3164        "14"
3165       ]
3166      },
3167      "execution_count": 70,
3168      "metadata": {},
3169      "output_type": "execute_result"
3170     }
3171    ],
3172    "source": [
3173     "%time len(astar_search_closed('amen', 'flog'))"
3174    ]
3175   },
3176   {
3177    "cell_type": "code",
3178    "execution_count": 71,
3179    "metadata": {},
3180    "outputs": [
3181     {
3182      "name": "stdout",
3183      "output_type": "stream",
3184      "text": [
3185       "CPU times: user 376 ms, sys: 4 ms, total: 380 ms\n",
3186       "Wall time: 382 ms\n"
3187      ]
3188     },
3189     {
3190      "data": {
3191       "text/plain": [
3192        "14"
3193       ]
3194      },
3195      "execution_count": 71,
3196      "metadata": {},
3197      "output_type": "execute_result"
3198     }
3199    ],
3200    "source": [
3201     "%time len(astar_search_closed('buzz', 'grog'))"
3202    ]
3203   },
3204   {
3205    "cell_type": "code",
3206    "execution_count": 72,
3207    "metadata": {},
3208    "outputs": [
3209     {
3210      "name": "stdout",
3211      "output_type": "stream",
3212      "text": [
3213       "CPU times: user 72 ms, sys: 4 ms, total: 76 ms\n",
3214       "Wall time: 76.9 ms\n"
3215      ]
3216     },
3217     {
3218      "data": {
3219       "text/plain": [
3220        "14"
3221       ]
3222      },
3223      "execution_count": 72,
3224      "metadata": {},
3225      "output_type": "execute_result"
3226     }
3227    ],
3228    "source": [
3229     "%time len(astar_search_closed('imps', 'pros'))"
3230    ]
3231   },
3232   {
3233    "cell_type": "code",
3234    "execution_count": null,
3235    "metadata": {
3236     "collapsed": true
3237    },
3238    "outputs": [],
3239    "source": []
3240   }
3241  ],
3242  "metadata": {
3243   "kernelspec": {
3244    "display_name": "Python 3",
3245    "language": "python",
3246    "name": "python3"
3247   },
3248   "language_info": {
3249    "codemirror_mode": {
3250     "name": "ipython",
3251     "version": 3
3252    },
3253    "file_extension": ".py",
3254    "mimetype": "text/x-python",
3255    "name": "python",
3256    "nbconvert_exporter": "python",
3257    "pygments_lexer": "ipython3",
3258    "version": "3.5.2+"
3259   }
3260  },
3261  "nbformat": 4,
3262  "nbformat_minor": 2
3263 }