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

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 30,
   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": 31,
  20    "metadata": {},
  21    "outputs": [
  22     {
  23      "data": {
  24       "text/plain": [
  25        "2336"
  26       ]
  27      },
  28      "execution_count": 31,
  29      "metadata": {},
  30      "output_type": "execute_result"
  31     }
  32    ],
  33    "source": [
  34     "words = frozenset(w.strip() for w in open('08-rooms.txt').readlines())\n",
  35     "len(words)"
  36    ]
  37   },
  38   {
  39    "cell_type": "code",
  40    "execution_count": 32,
  41    "metadata": {
  42     "collapsed": true
  43    },
  44    "outputs": [],
  45    "source": [
  46     "def adjacents_explicit(word):\n",
  47     "    neighbours = []\n",
  48     "    for i in range(len(word)):\n",
  49     "        for l in string.ascii_lowercase:\n",
  50     "            if l != word[i]:\n",
  51     "                neighbours.append(word[0:i] + l + word[i+1:])\n",
  52     "    return neighbours"
  53    ]
  54   },
  55   {
  56    "cell_type": "code",
  57    "execution_count": 33,
  58    "metadata": {
  59     "collapsed": true
  60    },
  61    "outputs": [],
  62    "source": [
  63     "def adjacents(word):\n",
  64     "    return frozenset(word[0:i] + l + word[i+1:]\n",
  65     "           for i in range(len(word))\n",
  66     "           for l in string.ascii_lowercase\n",
  67     "           if l != word[i])"
  68    ]
  69   },
  70   {
  71    "cell_type": "code",
  72    "execution_count": 34,
  73    "metadata": {},
  74    "outputs": [],
  75    "source": [
  76     "neighbours = {w: frozenset(n for n in adjacents(w) if n in words)\n",
  77     "             for w in words}"
  78    ]
  79   },
  80   {
  81    "cell_type": "code",
  82    "execution_count": 35,
  83    "metadata": {},
  84    "outputs": [
  85     {
  86      "data": {
  87       "text/plain": [
  88        "frozenset({'able'})"
  89       ]
  90      },
  91      "execution_count": 35,
  92      "metadata": {},
  93      "output_type": "execute_result"
  94     }
  95    ],
  96    "source": [
  97     "neighbours['abbe']"
  98    ]
  99   },
 100   {
 101    "cell_type": "code",
 102    "execution_count": 36,
 103    "metadata": {},
 104    "outputs": [
 105     {
 106      "data": {
 107       "text/plain": [
 108        "frozenset({'abbe', 'ably', 'axle'})"
 109       ]
 110      },
 111      "execution_count": 36,
 112      "metadata": {},
 113      "output_type": "execute_result"
 114     }
 115    ],
 116    "source": [
 117     "neighbours['able']"
 118    ]
 119   },
 120   {
 121    "cell_type": "code",
 122    "execution_count": 37,
 123    "metadata": {
 124     "collapsed": true
 125    },
 126    "outputs": [],
 127    "source": [
 128     "def distance(w1, w2):\n",
 129     "    return sum(1 for i in range(len(w1))\n",
 130     "               if w1[i] != w2[i])"
 131    ]
 132   },
 133   {
 134    "cell_type": "code",
 135    "execution_count": 38,
 136    "metadata": {},
 137    "outputs": [
 138     {
 139      "data": {
 140       "text/plain": [
 141        "0"
 142       ]
 143      },
 144      "execution_count": 38,
 145      "metadata": {},
 146      "output_type": "execute_result"
 147     }
 148    ],
 149    "source": [
 150     "distance('abbe', 'abbe')"
 151    ]
 152   },
 153   {
 154    "cell_type": "code",
 155    "execution_count": 39,
 156    "metadata": {
 157     "collapsed": true
 158    },
 159    "outputs": [],
 160    "source": [
 161     "def extend(chain, closed=None):\n",
 162     "    if closed:\n",
 163     "        nbrs = set(neighbours[chain[-1]]) - closed\n",
 164     "    else:\n",
 165     "        nbrs = neighbours[chain[-1]]\n",
 166     "    return [chain + [s] for s in nbrs\n",
 167     "           if s not in chain]"
 168    ]
 169   },
 170   {
 171    "cell_type": "code",
 172    "execution_count": 40,
 173    "metadata": {},
 174    "outputs": [
 175     {
 176      "data": {
 177       "text/plain": [
 178        "[['abbe', 'able']]"
 179       ]
 180      },
 181      "execution_count": 40,
 182      "metadata": {},
 183      "output_type": "execute_result"
 184     }
 185    ],
 186    "source": [
 187     "extend(['abbe'])"
 188    ]
 189   },
 190   {
 191    "cell_type": "code",
 192    "execution_count": 41,
 193    "metadata": {},
 194    "outputs": [
 195     {
 196      "data": {
 197       "text/plain": [
 198        "[['abbe', 'able', 'ably'], ['abbe', 'able', 'axle']]"
 199       ]
 200      },
 201      "execution_count": 41,
 202      "metadata": {},
 203      "output_type": "execute_result"
 204     }
 205    ],
 206    "source": [
 207     "extend(['abbe', 'able'])"
 208    ]
 209   },
 210   {
 211    "cell_type": "code",
 212    "execution_count": 42,
 213    "metadata": {},
 214    "outputs": [
 215     {
 216      "data": {
 217       "text/plain": [
 218        "[['abbe', 'able', 'ably', 'ally']]"
 219       ]
 220      },
 221      "execution_count": 42,
 222      "metadata": {},
 223      "output_type": "execute_result"
 224     }
 225    ],
 226    "source": [
 227     "extend(['abbe', 'able', 'ably'])"
 228    ]
 229   },
 230   {
 231    "cell_type": "code",
 232    "execution_count": 119,
 233    "metadata": {
 234     "collapsed": true
 235    },
 236    "outputs": [],
 237    "source": [
 238     "def bfs_search(start, goal, debug=False):\n",
 239     "    agenda = [[start]]\n",
 240     "    finished = False\n",
 241     "    while not finished and agenda:\n",
 242     "        current = agenda[0]\n",
 243     "        if debug:\n",
 244     "            print(current, agenda)\n",
 245     "        if current[-1] == goal:\n",
 246     "            finished = True\n",
 247     "        else:\n",
 248     "            successors = extend(current)\n",
 249     "            agenda = agenda[1:] + successors\n",
 250     "    if finished:\n",
 251     "        return current\n",
 252     "    else:\n",
 253     "        return None        "
 254    ]
 255   },
 256   {
 257    "cell_type": "code",
 258    "execution_count": 44,
 259    "metadata": {
 260     "collapsed": true
 261    },
 262    "outputs": [],
 263    "source": [
 264     "def bfs_search_closed(start, goal, debug=False):\n",
 265     "    agenda = [[start]]\n",
 266     "    closed = set()\n",
 267     "    finished = False\n",
 268     "    while not finished and agenda:\n",
 269     "        current = agenda[0]\n",
 270     "        if debug:\n",
 271     "            print(current)\n",
 272     "        if current[-1] == goal:\n",
 273     "            finished = True\n",
 274     "        else:\n",
 275     "            closed.add(current[-1])\n",
 276     "            successors = extend(current, closed)\n",
 277     "            agenda = agenda[1:] + successors\n",
 278     "    if finished:\n",
 279     "        return current\n",
 280     "    else:\n",
 281     "        return None        "
 282    ]
 283   },
 284   {
 285    "cell_type": "code",
 286    "execution_count": 45,
 287    "metadata": {},
 288    "outputs": [
 289     {
 290      "name": "stdout",
 291      "output_type": "stream",
 292      "text": [
 293       "['abbe']\n",
 294       "['abbe', 'able']\n",
 295       "['abbe', 'able', 'ably']\n",
 296       "['abbe', 'able', 'axle']\n",
 297       "['abbe', 'able', 'ably', 'ally']\n"
 298      ]
 299     },
 300     {
 301      "data": {
 302       "text/plain": [
 303        "['abbe', 'able', 'ably', 'ally']"
 304       ]
 305      },
 306      "execution_count": 45,
 307      "metadata": {},
 308      "output_type": "execute_result"
 309     }
 310    ],
 311    "source": [
 312     "bfs_search('abbe', 'ally', debug=True)"
 313    ]
 314   },
 315   {
 316    "cell_type": "code",
 317    "execution_count": 121,
 318    "metadata": {
 319     "collapsed": true
 320    },
 321    "outputs": [],
 322    "source": [
 323     "def dfs_search(start, goal, debug=False):\n",
 324     "    agenda = [[start]]\n",
 325     "    finished = False\n",
 326     "    while not finished and agenda:\n",
 327     "        current = agenda[0]\n",
 328     "        if debug:\n",
 329     "            print(agenda)\n",
 330     "        if current[-1] == goal:\n",
 331     "            finished = True\n",
 332     "        else:\n",
 333     "            successors = extend(current)\n",
 334     "            agenda = successors + agenda[1:]\n",
 335     "    if finished:\n",
 336     "        return current\n",
 337     "    else:\n",
 338     "        return None        "
 339    ]
 340   },
 341   {
 342    "cell_type": "code",
 343    "execution_count": 47,
 344    "metadata": {},
 345    "outputs": [
 346     {
 347      "name": "stdout",
 348      "output_type": "stream",
 349      "text": [
 350       "['abbe']\n",
 351       "['abbe', 'able']\n",
 352       "['abbe', 'able', 'ably']\n",
 353       "['abbe', 'able', 'ably', 'ally']\n"
 354      ]
 355     },
 356     {
 357      "data": {
 358       "text/plain": [
 359        "['abbe', 'able', 'ably', 'ally']"
 360       ]
 361      },
 362      "execution_count": 47,
 363      "metadata": {},
 364      "output_type": "execute_result"
 365     }
 366    ],
 367    "source": [
 368     "dfs_search('abbe', 'ally', debug=True)"
 369    ]
 370   },
 371   {
 372    "cell_type": "code",
 373    "execution_count": 48,
 374    "metadata": {},
 375    "outputs": [
 376     {
 377      "name": "stdout",
 378      "output_type": "stream",
 379      "text": [
 380       "['cart']\n",
 381       "['cart', 'cast']\n",
 382       "['cart', 'hart']\n",
 383       "['cart', 'cars']\n",
 384       "['cart', 'mart']\n",
 385       "['cart', 'wart']\n",
 386       "['cart', 'card']\n",
 387       "['cart', 'curt']\n",
 388       "['cart', 'tart']\n",
 389       "['cart', 'care']\n",
 390       "['cart', 'cant']\n",
 391       "['cart', 'dart']\n",
 392       "['cart', 'part']\n",
 393       "['cart', 'carp']\n",
 394       "['cart', 'cast', 'last']\n",
 395       "['cart', 'cast', 'bast']\n",
 396       "['cart', 'cast', 'cant']\n",
 397       "['cart', 'cast', 'past']\n",
 398       "['cart', 'cast', 'mast']\n",
 399       "['cart', 'cast', 'fast']\n",
 400       "['cart', 'cast', 'case']\n",
 401       "['cart', 'cast', 'east']\n",
 402       "['cart', 'cast', 'cyst']\n",
 403       "['cart', 'cast', 'cash']\n",
 404       "['cart', 'cast', 'cask']\n",
 405       "['cart', 'cast', 'vast']\n",
 406       "['cart', 'cast', 'cost']\n",
 407       "['cart', 'hart', 'hard']\n",
 408       "['cart', 'hart', 'harm']\n",
 409       "['cart', 'hart', 'hare']\n",
 410       "['cart', 'hart', 'hurt']\n",
 411       "['cart', 'hart', 'haft']\n",
 412       "['cart', 'hart', 'halt']\n",
 413       "['cart', 'hart', 'mart']\n",
 414       "['cart', 'hart', 'wart']\n",
 415       "['cart', 'hart', 'hark']\n",
 416       "['cart', 'hart', 'tart']\n",
 417       "['cart', 'hart', 'harp']\n",
 418       "['cart', 'hart', 'dart']\n",
 419       "['cart', 'hart', 'part']\n",
 420       "['cart', 'cars', 'bars']\n",
 421       "['cart', 'cars', 'ears']\n",
 422       "['cart', 'cars', 'caps']\n",
 423       "['cart', 'cars', 'wars']\n",
 424       "['cart', 'cars', 'cabs']\n",
 425       "['cart', 'cars', 'oars']\n",
 426       "['cart', 'cars', 'pars']\n",
 427       "['cart', 'cars', 'tars']\n",
 428       "['cart', 'cars', 'card']\n",
 429       "['cart', 'cars', 'cams']\n",
 430       "['cart', 'cars', 'caws']\n",
 431       "['cart', 'cars', 'cats']\n",
 432       "['cart', 'cars', 'cads']\n",
 433       "['cart', 'cars', 'care']\n",
 434       "['cart', 'cars', 'cans']\n",
 435       "['cart', 'cars', 'mars']\n",
 436       "['cart', 'cars', 'curs']\n",
 437       "['cart', 'cars', 'carp']\n",
 438       "['cart', 'cars', 'jars']\n",
 439       "['cart', 'mart', 'mare']\n",
 440       "['cart', 'mart', 'malt']\n",
 441       "['cart', 'mart', 'hart']\n",
 442       "['cart', 'mart', 'dart']\n",
 443       "['cart', 'mart', 'mast']\n",
 444       "['cart', 'mart', 'wart']\n",
 445       "['cart', 'mart', 'tart']\n",
 446       "['cart', 'mart', 'matt']\n",
 447       "['cart', 'mart', 'mars']\n",
 448       "['cart', 'mart', 'part']\n",
 449       "['cart', 'mart', 'mark']\n",
 450       "['cart', 'wart', 'wary']\n",
 451       "['cart', 'wart', 'hart']\n",
 452       "['cart', 'wart', 'warn']\n",
 453       "['cart', 'wart', 'warm']\n",
 454       "['cart', 'wart', 'warp']\n",
 455       "['cart', 'wart', 'wars']\n",
 456       "['cart', 'wart', 'mart']\n",
 457       "['cart', 'wart', 'watt']\n",
 458       "['cart', 'wart', 'want']\n",
 459       "['cart', 'wart', 'ware']\n",
 460       "['cart', 'wart', 'tart']\n",
 461       "['cart', 'wart', 'waft']\n",
 462       "['cart', 'wart', 'dart']\n",
 463       "['cart', 'wart', 'part']\n",
 464       "['cart', 'wart', 'wait']\n",
 465       "['cart', 'wart', 'ward']\n",
 466       "['cart', 'card', 'hard']\n",
 467       "['cart', 'card', 'bard']\n",
 468       "['cart', 'card', 'lard']\n",
 469       "['cart', 'card', 'cars']\n",
 470       "['cart', 'card', 'curd']\n",
 471       "['cart', 'card', 'carp']\n",
 472       "['cart', 'card', 'care']\n",
 473       "['cart', 'card', 'yard']\n",
 474       "['cart', 'card', 'ward']\n",
 475       "['cart', 'card', 'cord']\n",
 476       "['cart', 'curt', 'curb']\n",
 477       "['cart', 'curt', 'hurt']\n",
 478       "['cart', 'curt', 'curd']\n",
 479       "['cart', 'curt', 'curl']\n",
 480       "['cart', 'curt', 'cure']\n",
 481       "['cart', 'curt', 'cult']\n",
 482       "['cart', 'curt', 'curs']\n",
 483       "['cart', 'tart', 'hart']\n",
 484       "['cart', 'tart', 'tare']\n",
 485       "['cart', 'tart', 'mart']\n",
 486       "['cart', 'tart', 'wart']\n",
 487       "['cart', 'tart', 'tars']\n",
 488       "['cart', 'tart', 'taut']\n",
 489       "['cart', 'tart', 'tarp']\n",
 490       "['cart', 'tart', 'tact']\n",
 491       "['cart', 'tart', 'tort']\n",
 492       "['cart', 'tart', 'dart']\n",
 493       "['cart', 'tart', 'part']\n",
 494       "['cart', 'tart', 'taro']\n",
 495       "['cart', 'care', 'came']\n",
 496       "['cart', 'care', 'hare']\n",
 497       "['cart', 'care', 'cure']\n",
 498       "['cart', 'care', 'card']\n",
 499       "['cart', 'care', 'core']\n",
 500       "['cart', 'care', 'cafe']\n",
 501       "['cart', 'care', 'cars']\n",
 502       "['cart', 'care', 'fare']\n",
 503       "['cart', 'care', 'case']\n",
 504       "['cart', 'care', 'cane']\n",
 505       "['cart', 'care', 'bare']\n",
 506       "['cart', 'care', 'cage']\n",
 507       "['cart', 'care', 'carp']\n",
 508       "['cart', 'care', 'cave']\n",
 509       "['cart', 'care', 'cape']\n",
 510       "['cart', 'care', 'pare']\n",
 511       "['cart', 'care', 'ware']\n",
 512       "['cart', 'care', 'mare']\n",
 513       "['cart', 'care', 'cake']\n",
 514       "['cart', 'care', 'rare']\n",
 515       "['cart', 'care', 'tare']\n",
 516       "['cart', 'care', 'dare']\n",
 517       "['cart', 'cant', 'cast']\n",
 518       "['cart', 'cant', 'rant']\n",
 519       "['cart', 'cant', 'cent']\n",
 520       "['cart', 'cant', 'want']\n",
 521       "['cart', 'cant', 'cans']\n",
 522       "['cart', 'cant', 'cane']\n",
 523       "['cart', 'cant', 'pant']\n",
 524       "['cart', 'dart', 'dirt']\n",
 525       "['cart', 'dart', 'daft']\n",
 526       "['cart', 'dart', 'dark']\n",
 527       "['cart', 'dart', 'hart']\n",
 528       "['cart', 'dart', 'wart']\n",
 529       "['cart', 'dart', 'mart']\n",
 530       "['cart', 'dart', 'dare']\n",
 531       "['cart', 'dart', 'darn']\n",
 532       "['cart', 'dart', 'tart']\n",
 533       "['cart', 'dart', 'part']\n",
 534       "['cart', 'part', 'port']\n",
 535       "['cart', 'part', 'hart']\n",
 536       "['cart', 'part', 'pact']\n",
 537       "['cart', 'part', 'pert']\n",
 538       "['cart', 'part', 'pare']\n",
 539       "['cart', 'part', 'past']\n",
 540       "['cart', 'part', 'mart']\n",
 541       "['cart', 'part', 'wart']\n",
 542       "['cart', 'part', 'pars']\n",
 543       "['cart', 'part', 'dart']\n",
 544       "['cart', 'part', 'tart']\n",
 545       "['cart', 'part', 'park']\n",
 546       "['cart', 'part', 'pant']\n",
 547       "['cart', 'carp', 'cars']\n",
 548       "['cart', 'carp', 'warp']\n",
 549       "['cart', 'carp', 'card']\n",
 550       "['cart', 'carp', 'camp']\n",
 551       "['cart', 'carp', 'care']\n",
 552       "['cart', 'carp', 'tarp']\n",
 553       "['cart', 'carp', 'harp']\n",
 554       "['cart', 'cast', 'last', 'list']\n",
 555       "['cart', 'cast', 'last', 'lost']\n",
 556       "['cart', 'cast', 'last', 'bast']\n",
 557       "['cart', 'cast', 'last', 'lust']\n",
 558       "['cart', 'cast', 'last', 'lass']\n",
 559       "['cart', 'cast', 'last', 'past']\n",
 560       "['cart', 'cast', 'last', 'lash']\n",
 561       "['cart', 'cast', 'last', 'mast']\n",
 562       "['cart', 'cast', 'last', 'fast']\n",
 563       "['cart', 'cast', 'last', 'east']\n",
 564       "['cart', 'cast', 'last', 'lest']\n",
 565       "['cart', 'cast', 'last', 'vast']\n",
 566       "['cart', 'cast', 'bast', 'last']\n",
 567       "['cart', 'cast', 'bast', 'bust']\n",
 568       "['cart', 'cast', 'bast', 'bass']\n",
 569       "['cart', 'cast', 'bast', 'base']\n",
 570       "['cart', 'cast', 'bast', 'past']\n",
 571       "['cart', 'cast', 'bast', 'mast']\n",
 572       "['cart', 'cast', 'bast', 'bait']\n",
 573       "['cart', 'cast', 'bast', 'fast']\n",
 574       "['cart', 'cast', 'bast', 'best']\n",
 575       "['cart', 'cast', 'bast', 'bash']\n",
 576       "['cart', 'cast', 'bast', 'east']\n",
 577       "['cart', 'cast', 'bast', 'bask']\n",
 578       "['cart', 'cast', 'bast', 'vast']\n",
 579       "['cart', 'cast', 'cant', 'rant']\n",
 580       "['cart', 'cast', 'cant', 'cent']\n",
 581       "['cart', 'cast', 'cant', 'want']\n",
 582       "['cart', 'cast', 'cant', 'cans']\n",
 583       "['cart', 'cast', 'cant', 'cane']\n",
 584       "['cart', 'cast', 'cant', 'pant']\n",
 585       "['cart', 'cast', 'past', 'last']\n",
 586       "['cart', 'cast', 'past', 'bast']\n",
 587       "['cart', 'cast', 'past', 'psst']\n",
 588       "['cart', 'cast', 'past', 'pact']\n",
 589       "['cart', 'cast', 'past', 'pass']\n",
 590       "['cart', 'cast', 'past', 'pant']\n",
 591       "['cart', 'cast', 'past', 'mast']\n",
 592       "['cart', 'cast', 'past', 'post']\n",
 593       "['cart', 'cast', 'past', 'fast']\n",
 594       "['cart', 'cast', 'past', 'pest']\n",
 595       "['cart', 'cast', 'past', 'east']\n",
 596       "['cart', 'cast', 'past', 'part']\n",
 597       "['cart', 'cast', 'past', 'vast']\n",
 598       "['cart', 'cast', 'mast', 'mask']\n",
 599       "['cart', 'cast', 'mast', 'last']\n",
 600       "['cart', 'cast', 'mast', 'malt']\n",
 601       "['cart', 'cast', 'mast', 'bast']\n",
 602       "['cart', 'cast', 'mast', 'mist']\n",
 603       "['cart', 'cast', 'mast', 'must']\n",
 604       "['cart', 'cast', 'mast', 'past']\n",
 605       "['cart', 'cast', 'mast', 'mart']\n",
 606       "['cart', 'cast', 'mast', 'fast']\n",
 607       "['cart', 'cast', 'mast', 'most']\n",
 608       "['cart', 'cast', 'mast', 'mash']\n",
 609       "['cart', 'cast', 'mast', 'matt']\n",
 610       "['cart', 'cast', 'mast', 'east']\n",
 611       "['cart', 'cast', 'mast', 'vast']\n",
 612       "['cart', 'cast', 'mast', 'mass']\n",
 613       "['cart', 'cast', 'fast', 'last']\n",
 614       "['cart', 'cast', 'fast', 'fest']\n",
 615       "['cart', 'cast', 'fast', 'bast']\n",
 616       "['cart', 'cast', 'fast', 'fact']\n",
 617       "['cart', 'cast', 'fast', 'past']\n",
 618       "['cart', 'cast', 'fast', 'mast']\n",
 619       "['cart', 'cast', 'fast', 'fist']\n",
 620       "['cart', 'cast', 'fast', 'east']\n",
 621       "['cart', 'cast', 'fast', 'vast']\n",
 622       "['cart', 'cast', 'case', 'came']\n",
 623       "['cart', 'cast', 'case', 'cake']\n",
 624       "['cart', 'cast', 'case', 'cafe']\n",
 625       "['cart', 'cast', 'case', 'cape']\n",
 626       "['cart', 'cast', 'case', 'base']\n",
 627       "['cart', 'cast', 'case', 'vase']\n",
 628       "['cart', 'cast', 'case', 'care']\n",
 629       "['cart', 'cast', 'case', 'ease']\n",
 630       "['cart', 'cast', 'case', 'cane']\n",
 631       "['cart', 'cast', 'case', 'cash']\n",
 632       "['cart', 'cast', 'case', 'cask']\n",
 633       "['cart', 'cast', 'case', 'cage']\n",
 634       "['cart', 'cast', 'case', 'cave']\n",
 635       "['cart', 'cast', 'east', 'last']\n",
 636       "['cart', 'cast', 'east', 'bast']\n",
 637       "['cart', 'cast', 'east', 'easy']\n",
 638       "['cart', 'cast', 'east', 'past']\n",
 639       "['cart', 'cast', 'east', 'mast']\n",
 640       "['cart', 'cast', 'east', 'fast']\n",
 641       "['cart', 'cast', 'east', 'ease']\n",
 642       "['cart', 'cast', 'east', 'vast']\n",
 643       "['cart', 'cast', 'cyst', 'cost']\n",
 644       "['cart', 'cast', 'cash', 'sash']\n",
 645       "['cart', 'cast', 'cash', 'lash']\n",
 646       "['cart', 'cast', 'cash', 'dash']\n",
 647       "['cart', 'cast', 'cash', 'bash']\n",
 648       "['cart', 'cast', 'cash', 'wash']\n",
 649       "['cart', 'cast', 'cash', 'case']\n",
 650       "['cart', 'cast', 'cash', 'mash']\n",
 651       "['cart', 'cast', 'cash', 'cask']\n",
 652       "['cart', 'cast', 'cash', 'gash']\n",
 653       "['cart', 'cast', 'cash', 'hash']\n",
 654       "['cart', 'cast', 'cash', 'rash']\n",
 655       "['cart', 'cast', 'cask', 'mask']\n",
 656       "['cart', 'cast', 'cask', 'case']\n",
 657       "['cart', 'cast', 'cask', 'cash']\n",
 658       "['cart', 'cast', 'cask', 'bask']\n",
 659       "['cart', 'cast', 'cask', 'task']\n",
 660       "['cart', 'cast', 'vast', 'last']\n",
 661       "['cart', 'cast', 'vast', 'bast']\n",
 662       "['cart', 'cast', 'vast', 'vest']\n",
 663       "['cart', 'cast', 'vast', 'past']\n",
 664       "['cart', 'cast', 'vast', 'mast']\n",
 665       "['cart', 'cast', 'vast', 'vase']\n",
 666       "['cart', 'cast', 'vast', 'fast']\n",
 667       "['cart', 'cast', 'vast', 'east']\n",
 668       "['cart', 'cast', 'cost', 'colt']\n",
 669       "['cart', 'cast', 'cost', 'lost']\n",
 670       "['cart', 'cast', 'cost', 'tost']\n",
 671       "['cart', 'cast', 'cost', 'post']\n",
 672       "['cart', 'cast', 'cost', 'cosy']\n",
 673       "['cart', 'cast', 'cost', 'coat']\n",
 674       "['cart', 'cast', 'cost', 'coot']\n",
 675       "['cart', 'cast', 'cost', 'most']\n",
 676       "['cart', 'cast', 'cost', 'cyst']\n",
 677       "['cart', 'cast', 'cost', 'host']\n",
 678       "['cart', 'hart', 'hard', 'harm']\n",
 679       "['cart', 'hart', 'hard', 'bard']\n",
 680       "['cart', 'hart', 'hard', 'hare']\n",
 681       "['cart', 'hart', 'hard', 'lard']\n",
 682       "['cart', 'hart', 'hard', 'card']\n",
 683       "['cart', 'hart', 'hard', 'herd']\n",
 684       "['cart', 'hart', 'hard', 'hark']\n",
 685       "['cart', 'hart', 'hard', 'hand']\n",
 686       "['cart', 'hart', 'hard', 'harp']\n",
 687       "['cart', 'hart', 'hard', 'yard']\n",
 688       "['cart', 'hart', 'hard', 'ward']\n",
 689       "['cart', 'hart', 'harm', 'farm']\n",
 690       "['cart', 'hart', 'harm', 'hard']\n",
 691       "['cart', 'hart', 'harm', 'hare']\n",
 692       "['cart', 'hart', 'harm', 'warm']\n",
 693       "['cart', 'hart', 'harm', 'harp']\n",
 694       "['cart', 'hart', 'harm', 'hark']\n",
 695       "['cart', 'hart', 'hare', 'mare']\n",
 696       "['cart', 'hart', 'hare', 'hard']\n",
 697       "['cart', 'hart', 'hare', 'harm']\n",
 698       "['cart', 'hart', 'hare', 'rare']\n",
 699       "['cart', 'hart', 'hare', 'hake']\n",
 700       "['cart', 'hart', 'hare', 'fare']\n",
 701       "['cart', 'hart', 'hare', 'tare']\n",
 702       "['cart', 'hart', 'hare', 'pare']\n",
 703       "['cart', 'hart', 'hare', 'hate']\n",
 704       "['cart', 'hart', 'hare', 'here']\n",
 705       "['cart', 'hart', 'hare', 'dare']\n",
 706       "['cart', 'hart', 'hare', 'hale']\n",
 707       "['cart', 'hart', 'hare', 'care']\n",
 708       "['cart', 'hart', 'hare', 'have']\n",
 709       "['cart', 'hart', 'hare', 'harp']\n",
 710       "['cart', 'hart', 'hare', 'ware']\n",
 711       "['cart', 'hart', 'hare', 'bare']\n",
 712       "['cart', 'hart', 'hare', 'hark']\n",
 713       "['cart', 'hart', 'hare', 'hire']\n",
 714       "['cart', 'hart', 'hare', 'haze']\n",
 715       "['cart', 'hart', 'hurt', 'curt']\n",
 716       "['cart', 'hart', 'hurt', 'hurl']\n",
 717       "['cart', 'hart', 'hurt', 'hunt']\n",
 718       "['cart', 'hart', 'haft', 'daft']\n",
 719       "['cart', 'hart', 'haft', 'heft']\n",
 720       "['cart', 'hart', 'haft', 'halt']\n",
 721       "['cart', 'hart', 'haft', 'waft']\n",
 722       "['cart', 'hart', 'haft', 'raft']\n",
 723       "['cart', 'hart', 'halt', 'malt']\n",
 724       "['cart', 'hart', 'halt', 'halo']\n",
 725       "['cart', 'hart', 'halt', 'hall']\n",
 726       "['cart', 'hart', 'halt', 'salt']\n",
 727       "['cart', 'hart', 'halt', 'half']\n",
 728       "['cart', 'hart', 'halt', 'haft']\n",
 729       "['cart', 'hart', 'halt', 'hale']\n",
 730       "['cart', 'hart', 'halt', 'hilt']\n",
 731       "['cart', 'hart', 'mart', 'mare']\n",
 732       "['cart', 'hart', 'mart', 'malt']\n",
 733       "['cart', 'hart', 'mart', 'dart']\n",
 734       "['cart', 'hart', 'mart', 'mast']\n",
 735       "['cart', 'hart', 'mart', 'wart']\n",
 736       "['cart', 'hart', 'mart', 'tart']\n",
 737       "['cart', 'hart', 'mart', 'matt']\n",
 738       "['cart', 'hart', 'mart', 'mars']\n",
 739       "['cart', 'hart', 'mart', 'part']\n",
 740       "['cart', 'hart', 'mart', 'mark']\n",
 741       "['cart', 'hart', 'wart', 'wary']\n",
 742       "['cart', 'hart', 'wart', 'warn']\n",
 743       "['cart', 'hart', 'wart', 'warm']\n",
 744       "['cart', 'hart', 'wart', 'warp']\n",
 745       "['cart', 'hart', 'wart', 'wars']\n",
 746       "['cart', 'hart', 'wart', 'mart']\n",
 747       "['cart', 'hart', 'wart', 'watt']\n",
 748       "['cart', 'hart', 'wart', 'want']\n",
 749       "['cart', 'hart', 'wart', 'ware']\n",
 750       "['cart', 'hart', 'wart', 'tart']\n",
 751       "['cart', 'hart', 'wart', 'waft']\n",
 752       "['cart', 'hart', 'wart', 'dart']\n",
 753       "['cart', 'hart', 'wart', 'part']\n",
 754       "['cart', 'hart', 'wart', 'wait']\n",
 755       "['cart', 'hart', 'wart', 'ward']\n",
 756       "['cart', 'hart', 'hark', 'hard']\n",
 757       "['cart', 'hart', 'hark', 'harm']\n",
 758       "['cart', 'hart', 'hark', 'dark']\n",
 759       "['cart', 'hart', 'hark', 'hare']\n",
 760       "['cart', 'hart', 'hark', 'nark']\n",
 761       "['cart', 'hart', 'hark', 'bark']\n",
 762       "['cart', 'hart', 'hark', 'lark']\n",
 763       "['cart', 'hart', 'hark', 'hank']\n",
 764       "['cart', 'hart', 'hark', 'harp']\n",
 765       "['cart', 'hart', 'hark', 'park']\n",
 766       "['cart', 'hart', 'hark', 'hawk']\n",
 767       "['cart', 'hart', 'hark', 'hack']\n",
 768       "['cart', 'hart', 'hark', 'mark']\n",
 769       "['cart', 'hart', 'tart', 'tare']\n",
 770       "['cart', 'hart', 'tart', 'mart']\n",
 771       "['cart', 'hart', 'tart', 'wart']\n",
 772       "['cart', 'hart', 'tart', 'tars']\n",
 773       "['cart', 'hart', 'tart', 'taut']\n",
 774       "['cart', 'hart', 'tart', 'tarp']\n",
 775       "['cart', 'hart', 'tart', 'tact']\n",
 776       "['cart', 'hart', 'tart', 'tort']\n",
 777       "['cart', 'hart', 'tart', 'dart']\n",
 778       "['cart', 'hart', 'tart', 'part']\n",
 779       "['cart', 'hart', 'tart', 'taro']\n",
 780       "['cart', 'hart', 'harp', 'hard']\n",
 781       "['cart', 'hart', 'harp', 'harm']\n",
 782       "['cart', 'hart', 'harp', 'hare']\n",
 783       "['cart', 'hart', 'harp', 'warp']\n",
 784       "['cart', 'hart', 'harp', 'tarp']\n",
 785       "['cart', 'hart', 'harp', 'hark']\n",
 786       "['cart', 'hart', 'harp', 'hasp']\n",
 787       "['cart', 'hart', 'harp', 'carp']\n",
 788       "['cart', 'hart', 'dart', 'dirt']\n",
 789       "['cart', 'hart', 'dart', 'daft']\n",
 790       "['cart', 'hart', 'dart', 'dark']\n",
 791       "['cart', 'hart', 'dart', 'wart']\n",
 792       "['cart', 'hart', 'dart', 'mart']\n",
 793       "['cart', 'hart', 'dart', 'dare']\n",
 794       "['cart', 'hart', 'dart', 'darn']\n",
 795       "['cart', 'hart', 'dart', 'tart']\n",
 796       "['cart', 'hart', 'dart', 'part']\n",
 797       "['cart', 'hart', 'part', 'port']\n",
 798       "['cart', 'hart', 'part', 'pact']\n",
 799       "['cart', 'hart', 'part', 'pert']\n",
 800       "['cart', 'hart', 'part', 'pare']\n",
 801       "['cart', 'hart', 'part', 'past']\n",
 802       "['cart', 'hart', 'part', 'mart']\n",
 803       "['cart', 'hart', 'part', 'wart']\n",
 804       "['cart', 'hart', 'part', 'pars']\n",
 805       "['cart', 'hart', 'part', 'dart']\n",
 806       "['cart', 'hart', 'part', 'tart']\n",
 807       "['cart', 'hart', 'part', 'park']\n",
 808       "['cart', 'hart', 'part', 'pant']\n",
 809       "['cart', 'cars', 'bars', 'barb']\n",
 810       "['cart', 'cars', 'bars', 'bard']\n",
 811       "['cart', 'cars', 'bars', 'ears']\n",
 812       "['cart', 'cars', 'bars', 'bass']\n",
 813       "['cart', 'cars', 'bars', 'burs']\n",
 814       "['cart', 'cars', 'bars', 'mars']\n",
 815       "['cart', 'cars', 'bars', 'bays']\n",
 816       "['cart', 'cars', 'bars', 'baas']\n",
 817       "['cart', 'cars', 'bars', 'bark']\n",
 818       "['cart', 'cars', 'bars', 'bags']\n",
 819       "['cart', 'cars', 'bars', 'bans']\n",
 820       "['cart', 'cars', 'bars', 'oars']\n",
 821       "['cart', 'cars', 'bars', 'pars']\n",
 822       "['cart', 'cars', 'bars', 'tars']\n",
 823       "['cart', 'cars', 'bars', 'wars']\n",
 824       "['cart', 'cars', 'bars', 'barn']\n",
 825       "['cart', 'cars', 'bars', 'bats']\n",
 826       "['cart', 'cars', 'bars', 'bare']\n",
 827       "['cart', 'cars', 'bars', 'barf']\n",
 828       "['cart', 'cars', 'bars', 'jars']\n",
 829       "['cart', 'cars', 'ears', 'bars']\n",
 830       "['cart', 'cars', 'ears', 'eats']\n",
 831       "['cart', 'cars', 'ears', 'wars']\n",
 832       "['cart', 'cars', 'ears', 'earl']\n",
 833       "['cart', 'cars', 'ears', 'oars']\n",
 834       "['cart', 'cars', 'ears', 'pars']\n",
 835       "['cart', 'cars', 'ears', 'tars']\n",
 836       "['cart', 'cars', 'ears', 'errs']\n",
 837       "['cart', 'cars', 'ears', 'earn']\n",
 838       "['cart', 'cars', 'ears', 'mars']\n",
 839       "['cart', 'cars', 'ears', 'jars']\n",
 840       "['cart', 'cars', 'caps', 'maps']\n",
 841       "['cart', 'cars', 'caps', 'taps']\n",
 842       "['cart', 'cars', 'caps', 'laps']\n",
 843       "['cart', 'cars', 'caps', 'cape']\n",
 844       "['cart', 'cars', 'caps', 'saps']\n",
 845       "['cart', 'cars', 'caps', 'cops']\n",
 846       "['cart', 'cars', 'caps', 'cabs']\n",
 847       "['cart', 'cars', 'caps', 'cups']\n",
 848       "['cart', 'cars', 'caps', 'naps']\n",
 849       "['cart', 'cars', 'caps', 'raps']\n",
 850       "['cart', 'cars', 'caps', 'cams']\n",
 851       "['cart', 'cars', 'caps', 'cats']\n",
 852       "['cart', 'cars', 'caps', 'yaps']\n",
 853       "['cart', 'cars', 'caps', 'caws']\n",
 854       "['cart', 'cars', 'caps', 'cads']\n",
 855       "['cart', 'cars', 'caps', 'cans']\n",
 856       "['cart', 'cars', 'caps', 'zaps']\n",
 857       "['cart', 'cars', 'caps', 'paps']\n",
 858       "['cart', 'cars', 'caps', 'gaps']\n",
 859       "['cart', 'cars', 'wars', 'bars']\n",
 860       "['cart', 'cars', 'wars', 'wary']\n",
 861       "['cart', 'cars', 'wars', 'ears']\n",
 862       "['cart', 'cars', 'wars', 'warn']\n",
 863       "['cart', 'cars', 'wars', 'warm']\n",
 864       "['cart', 'cars', 'wars', 'warp']\n",
 865       "['cart', 'cars', 'wars', 'wart']\n",
 866       "['cart', 'cars', 'wars', 'oars']\n",
 867       "['cart', 'cars', 'wars', 'pars']\n",
 868       "['cart', 'cars', 'wars', 'tars']\n",
 869       "['cart', 'cars', 'wars', 'wags']\n",
 870       "['cart', 'cars', 'wars', 'ways']\n",
 871       "['cart', 'cars', 'wars', 'wads']\n",
 872       "['cart', 'cars', 'wars', 'ware']\n",
 873       "['cart', 'cars', 'wars', 'mars']\n",
 874       "['cart', 'cars', 'wars', 'ward']\n",
 875       "['cart', 'cars', 'wars', 'jars']\n",
 876       "['cart', 'cars', 'cabs', 'cubs']\n",
 877       "['cart', 'cars', 'cabs', 'labs']\n",
 878       "['cart', 'cars', 'cabs', 'caps']\n",
 879       "['cart', 'cars', 'cabs', 'cobs']\n",
 880       "['cart', 'cars', 'cabs', 'jabs']\n",
 881       "['cart', 'cars', 'cabs', 'cams']\n",
 882       "['cart', 'cars', 'cabs', 'cats']\n",
 883       "['cart', 'cars', 'cabs', 'caws']\n",
 884       "['cart', 'cars', 'cabs', 'tabs']\n",
 885       "['cart', 'cars', 'cabs', 'nabs']\n",
 886       "['cart', 'cars', 'cabs', 'dabs']\n",
 887       "['cart', 'cars', 'cabs', 'cads']\n",
 888       "['cart', 'cars', 'cabs', 'cans']\n",
 889       "['cart', 'cars', 'cabs', 'gabs']\n",
 890       "['cart', 'cars', 'oars', 'bars']\n",
 891       "['cart', 'cars', 'oars', 'ears']\n",
 892       "['cart', 'cars', 'oars', 'oaks']\n",
 893       "['cart', 'cars', 'oars', 'oafs']\n",
 894       "['cart', 'cars', 'oars', 'wars']\n",
 895       "['cart', 'cars', 'oars', 'oats']\n",
 896       "['cart', 'cars', 'oars', 'pars']\n",
 897       "['cart', 'cars', 'oars', 'tars']\n",
 898       "['cart', 'cars', 'oars', 'ours']\n",
 899       "['cart', 'cars', 'oars', 'mars']\n",
 900       "['cart', 'cars', 'oars', 'jars']\n",
 901       "['cart', 'cars', 'pars', 'pats']\n",
 902       "['cart', 'cars', 'pars', 'bars']\n",
 903       "['cart', 'cars', 'pars', 'ears']\n",
 904       "['cart', 'cars', 'pars', 'pals']\n",
 905       "['cart', 'cars', 'pars', 'pans']\n",
 906       "['cart', 'cars', 'pars', 'mars']\n",
 907       "['cart', 'cars', 'pars', 'pass']\n",
 908       "['cart', 'cars', 'pars', 'paws']\n",
 909       "['cart', 'cars', 'pars', 'pare']\n",
 910       "['cart', 'cars', 'pars', 'wars']\n",
 911       "['cart', 'cars', 'pars', 'oars']\n",
 912       "['cart', 'cars', 'pars', 'tars']\n",
 913       "['cart', 'cars', 'pars', 'paps']\n",
 914       "['cart', 'cars', 'pars', 'pays']\n",
 915       "['cart', 'cars', 'pars', 'park']\n",
 916       "['cart', 'cars', 'pars', 'part']\n",
 917       "['cart', 'cars', 'pars', 'jars']\n",
 918       "['cart', 'cars', 'pars', 'pads']\n",
 919       "['cart', 'cars', 'tars', 'tags']\n",
 920       "['cart', 'cars', 'tars', 'bars']\n",
 921       "['cart', 'cars', 'tars', 'tads']\n",
 922       "['cart', 'cars', 'tars', 'ears']\n",
 923       "['cart', 'cars', 'tars', 'taps']\n",
 924       "['cart', 'cars', 'tars', 'tare']\n",
 925       "['cart', 'cars', 'tars', 'tans']\n",
 926       "['cart', 'cars', 'tars', 'tors']\n",
 927       "['cart', 'cars', 'tars', 'oars']\n",
 928       "['cart', 'cars', 'tars', 'pars']\n",
 929       "['cart', 'cars', 'tars', 'tats']\n",
 930       "['cart', 'cars', 'tars', 'tams']\n",
 931       "['cart', 'cars', 'tars', 'tabs']\n",
 932       "['cart', 'cars', 'tars', 'tart']\n",
 933       "['cart', 'cars', 'tars', 'tarp']\n",
 934       "['cart', 'cars', 'tars', 'wars']\n",
 935       "['cart', 'cars', 'tars', 'mars']\n",
 936       "['cart', 'cars', 'tars', 'taro']\n",
 937       "['cart', 'cars', 'tars', 'jars']\n",
 938       "['cart', 'cars', 'card', 'hard']\n",
 939       "['cart', 'cars', 'card', 'bard']\n",
 940       "['cart', 'cars', 'card', 'lard']\n",
 941       "['cart', 'cars', 'card', 'curd']\n",
 942       "['cart', 'cars', 'card', 'carp']\n",
 943       "['cart', 'cars', 'card', 'care']\n",
 944       "['cart', 'cars', 'card', 'yard']\n",
 945       "['cart', 'cars', 'card', 'ward']\n",
 946       "['cart', 'cars', 'card', 'cord']\n",
 947       "['cart', 'cars', 'cams', 'came']\n",
 948       "['cart', 'cars', 'cams', 'rams']\n",
 949       "['cart', 'cars', 'cams', 'jams']\n",
 950       "['cart', 'cars', 'cams', 'caps']\n",
 951       "['cart', 'cars', 'cams', 'cums']\n",
 952       "['cart', 'cars', 'cams', 'lams']\n",
 953       "['cart', 'cars', 'cams', 'tams']\n",
 954       "['cart', 'cars', 'cams', 'camp']\n",
 955       "['cart', 'cars', 'cams', 'cabs']\n",
 956       "['cart', 'cars', 'cams', 'dams']\n",
 957       "['cart', 'cars', 'cams', 'cats']\n",
 958       "['cart', 'cars', 'cams', 'caws']\n",
 959       "['cart', 'cars', 'cams', 'cads']\n",
 960       "['cart', 'cars', 'cams', 'hams']\n",
 961       "['cart', 'cars', 'cams', 'cans']\n",
 962       "['cart', 'cars', 'cams', 'yams']\n",
 963       "['cart', 'cars', 'caws', 'saws']\n",
 964       "['cart', 'cars', 'caws', 'maws']\n",
 965       "['cart', 'cars', 'caws', 'haws']\n",
 966       "['cart', 'cars', 'caws', 'caps']\n",
 967       "['cart', 'cars', 'caws', 'paws']\n",
 968       "['cart', 'cars', 'caws', 'laws']\n",
 969       "['cart', 'cars', 'caws', 'cows']\n",
 970       "['cart', 'cars', 'caws', 'cabs']\n",
 971       "['cart', 'cars', 'caws', 'cams']\n",
 972       "['cart', 'cars', 'caws', 'cats']\n",
 973       "['cart', 'cars', 'caws', 'cads']\n",
 974       "['cart', 'cars', 'caws', 'cans']\n",
 975       "['cart', 'cars', 'caws', 'yaws']\n",
 976       "['cart', 'cars', 'caws', 'jaws']\n",
 977       "['cart', 'cars', 'cats', 'cots']\n",
 978       "['cart', 'cars', 'cats', 'eats']\n",
 979       "['cart', 'cars', 'cats', 'hats']\n",
 980       "['cart', 'cars', 'cats', 'caps']\n",
 981       "['cart', 'cars', 'cats', 'rats']\n",
 982       "['cart', 'cars', 'cats', 'cuts']\n",
 983       "['cart', 'cars', 'cats', 'fats']\n",
 984       "['cart', 'cars', 'cats', 'vats']\n",
 985       "['cart', 'cars', 'cats', 'cabs']\n",
 986       "['cart', 'cars', 'cats', 'oats']\n",
 987       "['cart', 'cars', 'cats', 'tats']\n",
 988       "['cart', 'cars', 'cats', 'cams']\n",
 989       "['cart', 'cars', 'cats', 'caws']\n",
 990       "['cart', 'cars', 'cats', 'cads']\n",
 991       "['cart', 'cars', 'cats', 'mats']\n",
 992       "['cart', 'cars', 'cats', 'bats']\n",
 993       "['cart', 'cars', 'cats', 'cans']\n",
 994       "['cart', 'cars', 'cats', 'lats']\n",
 995       "['cart', 'cars', 'cats', 'pats']\n",
 996       "['cart', 'cars', 'cads', 'tads']\n",
 997       "['cart', 'cars', 'cads', 'cods']\n",
 998       "['cart', 'cars', 'cads', 'caps']\n",
 999       "['cart', 'cars', 'cads', 'fads']\n",
1000       "['cart', 'cars', 'cads', 'dads']\n",
1001       "['cart', 'cars', 'cads', 'mads']\n",
1002       "['cart', 'cars', 'cads', 'lads']\n",
1003       "['cart', 'cars', 'cads', 'cuds']\n",
1004       "['cart', 'cars', 'cads', 'cabs']\n",
1005       "['cart', 'cars', 'cads', 'cams']\n",
1006       "['cart', 'cars', 'cads', 'wads']\n",
1007       "['cart', 'cars', 'cads', 'cats']\n",
1008       "['cart', 'cars', 'cads', 'caws']\n",
1009       "['cart', 'cars', 'cads', 'cans']\n",
1010       "['cart', 'cars', 'cads', 'gads']\n",
1011       "['cart', 'cars', 'cads', 'pads']\n",
1012       "['cart', 'cars', 'care', 'came']\n",
1013       "['cart', 'cars', 'care', 'hare']\n",
1014       "['cart', 'cars', 'care', 'cure']\n",
1015       "['cart', 'cars', 'care', 'card']\n",
1016       "['cart', 'cars', 'care', 'core']\n",
1017       "['cart', 'cars', 'care', 'cafe']\n",
1018       "['cart', 'cars', 'care', 'fare']\n",
1019       "['cart', 'cars', 'care', 'case']\n",
1020       "['cart', 'cars', 'care', 'cane']\n",
1021       "['cart', 'cars', 'care', 'bare']\n",
1022       "['cart', 'cars', 'care', 'cage']\n",
1023       "['cart', 'cars', 'care', 'carp']\n",
1024       "['cart', 'cars', 'care', 'cave']\n",
1025       "['cart', 'cars', 'care', 'cape']\n",
1026       "['cart', 'cars', 'care', 'pare']\n",
1027       "['cart', 'cars', 'care', 'ware']\n",
1028       "['cart', 'cars', 'care', 'mare']\n",
1029       "['cart', 'cars', 'care', 'cake']\n",
1030       "['cart', 'cars', 'care', 'rare']\n",
1031       "['cart', 'cars', 'care', 'tare']\n",
1032       "['cart', 'cars', 'care', 'dare']\n",
1033       "['cart', 'cars', 'cans', 'vans']\n"
1034      ]
1035     },
1036     {
1037      "data": {
1038       "text/plain": [
1039        "['cart', 'cars', 'cans', 'vans']"
1040       ]
1041      },
1042      "execution_count": 48,
1043      "metadata": {},
1044      "output_type": "execute_result"
1045     }
1046    ],
1047    "source": [
1048     "bfs_search('cart', 'vans', debug=True)"
1049    ]
1050   },
1051   {
1052    "cell_type": "code",
1053    "execution_count": 49,
1054    "metadata": {},
1055    "outputs": [
1056     {
1057      "data": {
1058       "text/plain": [
1059        "['cart', 'care', 'cane', 'vane']"
1060       ]
1061      },
1062      "execution_count": 49,
1063      "metadata": {},
1064      "output_type": "execute_result"
1065     }
1066    ],
1067    "source": [
1068     "bfs_search('cart', 'vane')"
1069    ]
1070   },
1071   {
1072    "cell_type": "code",
1073    "execution_count": 51,
1074    "metadata": {},
1075    "outputs": [
1076     {
1077      "data": {
1078       "text/plain": [
1079        "1494"
1080       ]
1081      },
1082      "execution_count": 51,
1083      "metadata": {},
1084      "output_type": "execute_result"
1085     }
1086    ],
1087    "source": [
1088     "len(dfs_search('cart', 'vane'))"
1089    ]
1090   },
1091   {
1092    "cell_type": "code",
1093    "execution_count": 52,
1094    "metadata": {
1095     "collapsed": true
1096    },
1097    "outputs": [],
1098    "source": [
1099     "def astar_search(start, goal, debug=False):\n",
1100     "    agenda = [(distance(start, goal), [start])]\n",
1101     "    heapq.heapify(agenda)\n",
1102     "    finished = False\n",
1103     "    while not finished and agenda:\n",
1104     "        _, current = heapq.heappop(agenda)\n",
1105     "        if debug:\n",
1106     "            print(current)\n",
1107     "        if current[-1] == goal:\n",
1108     "            finished = True\n",
1109     "        else:\n",
1110     "            successors = extend(current)\n",
1111     "            for s in successors:\n",
1112     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
1113     "    if finished:\n",
1114     "        return current\n",
1115     "    else:\n",
1116     "        return None        "
1117    ]
1118   },
1119   {
1120    "cell_type": "code",
1121    "execution_count": 53,
1122    "metadata": {},
1123    "outputs": [
1124     {
1125      "name": "stdout",
1126      "output_type": "stream",
1127      "text": [
1128       "['cart']\n",
1129       "['cart', 'cant']\n",
1130       "['cart', 'cant', 'cane']\n",
1131       "['cart', 'cant', 'cane', 'vane']\n"
1132      ]
1133     },
1134     {
1135      "data": {
1136       "text/plain": [
1137        "['cart', 'cant', 'cane', 'vane']"
1138       ]
1139      },
1140      "execution_count": 53,
1141      "metadata": {},
1142      "output_type": "execute_result"
1143     }
1144    ],
1145    "source": [
1146     "astar_search('cart', 'vane', debug=True)"
1147    ]
1148   },
1149   {
1150    "cell_type": "code",
1151    "execution_count": 54,
1152    "metadata": {
1153     "collapsed": true
1154    },
1155    "outputs": [],
1156    "source": [
1157     "def astar_search_closed(start, goal, debug=False):\n",
1158     "    agenda = [(distance(start, goal), [start])]\n",
1159     "    heapq.heapify(agenda)\n",
1160     "    closed = set()\n",
1161     "    finished = False\n",
1162     "    while not finished and agenda:\n",
1163     "        _, current = heapq.heappop(agenda)\n",
1164     "        if debug:\n",
1165     "            print(current)\n",
1166     "        if current[-1] == goal:\n",
1167     "            finished = True\n",
1168     "        else:\n",
1169     "            closed.add(current[-1])\n",
1170     "            successors = extend(current, closed)\n",
1171     "            for s in successors:\n",
1172     "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
1173     "    if finished:\n",
1174     "        return current\n",
1175     "    else:\n",
1176     "        return None        "
1177    ]
1178   },
1179   {
1180    "cell_type": "code",
1181    "execution_count": 55,
1182    "metadata": {},
1183    "outputs": [
1184     {
1185      "name": "stdout",
1186      "output_type": "stream",
1187      "text": [
1188       "['cart']\n",
1189       "['cart', 'cant']\n",
1190       "['cart', 'cant', 'cane']\n",
1191       "['cart', 'cant', 'cane', 'vane']\n"
1192      ]
1193     },
1194     {
1195      "data": {
1196       "text/plain": [
1197        "['cart', 'cant', 'cane', 'vane']"
1198       ]
1199      },
1200      "execution_count": 55,
1201      "metadata": {},
1202      "output_type": "execute_result"
1203     }
1204    ],
1205    "source": [
1206     "astar_search_closed('cart', 'vane', debug=True)"
1207    ]
1208   },
1209   {
1210    "cell_type": "markdown",
1211    "metadata": {},
1212    "source": [
1213     "# Mutually-reachable sets\n",
1214     "\n",
1215     "Find the transitive closure of the `neighbours` relation, so we can see which words can be transformed into which other words."
1216    ]
1217   },
1218   {
1219    "cell_type": "code",
1220    "execution_count": 69,
1221    "metadata": {
1222     "scrolled": true
1223    },
1224    "outputs": [
1225     {
1226      "name": "stdout",
1227      "output_type": "stream",
1228      "text": [
1229       "10 loops, best of 3: 23.9 ms per loop\n"
1230      ]
1231     }
1232    ],
1233    "source": [
1234     "%%timeit\n",
1235     "candidates = [set([k] + list(neighbours[k])) for k in neighbours]\n",
1236     "reachables = []\n",
1237     "while candidates:\n",
1238     "    current = set(candidates.pop())\n",
1239     "    altered = False\n",
1240     "    for other in candidates:\n",
1241     "        if current.intersection(other):\n",
1242     "            altered = True\n",
1243     "            current.update(other)\n",
1244     "            candidates.remove(other)\n",
1245     "    if altered:\n",
1246     "        candidates.append(current)\n",
1247     "    else:\n",
1248     "        reachables.append(current)\n",
1249     "\n",
1250     "len(reachables)"
1251    ]
1252   },
1253   {
1254    "cell_type": "code",
1255    "execution_count": 71,
1256    "metadata": {},
1257    "outputs": [
1258     {
1259      "name": "stdout",
1260      "output_type": "stream",
1261      "text": [
1262       "10 loops, best of 3: 25.9 ms per loop\n"
1263      ]
1264     }
1265    ],
1266    "source": [
1267     "%%timeit\n",
1268     "candidates = set(frozenset({k}.union(neighbours[k])) for k in neighbours)\n",
1269     "reachables = set()\n",
1270     "while candidates:\n",
1271     "    current = set(candidates.pop())\n",
1272     "    remove_because_merged = set()\n",
1273     "    for other in candidates:\n",
1274     "        if current.intersection(other):\n",
1275     "            current.update(other)\n",
1276     "            remove_because_merged.add(other)\n",
1277     "    if remove_because_merged:\n",
1278     "        for rbm in remove_because_merged:\n",
1279     "            candidates.remove(rbm)\n",
1280     "        candidates.add(frozenset(current))\n",
1281     "    else:\n",
1282     "        reachables.add(frozenset(current))\n",
1283     "\n",
1284     "len(reachables)"
1285    ]
1286   },
1287   {
1288    "cell_type": "code",
1289    "execution_count": 72,
1290    "metadata": {},
1291    "outputs": [
1292     {
1293      "data": {
1294       "text/plain": [
1295        "2204"
1296       ]
1297      },
1298      "execution_count": 72,
1299      "metadata": {},
1300      "output_type": "execute_result"
1301     }
1302    ],
1303    "source": [
1304     "len(max(reachables, key=len))"
1305    ]
1306   },
1307   {
1308    "cell_type": "code",
1309    "execution_count": 73,
1310    "metadata": {},
1311    "outputs": [
1312     {
1313      "data": {
1314       "text/plain": [
1315        "1"
1316       ]
1317      },
1318      "execution_count": 73,
1319      "metadata": {},
1320      "output_type": "execute_result"
1321     }
1322    ],
1323    "source": [
1324     "len(min(reachables, key=len))"
1325    ]
1326   },
1327   {
1328    "cell_type": "code",
1329    "execution_count": 74,
1330    "metadata": {
1331     "scrolled": true
1332    },
1333    "outputs": [
1334     {
1335      "data": {
1336       "text/plain": [
1337        "Counter({1: 75, 2: 6, 3: 7, 4: 2, 5: 2, 6: 1, 2204: 1})"
1338       ]
1339      },
1340      "execution_count": 74,
1341      "metadata": {},
1342      "output_type": "execute_result"
1343     }
1344    ],
1345    "source": [
1346     "collections.Counter(len(r) for r in reachables)"
1347    ]
1348   },
1349   {
1350    "cell_type": "code",
1351    "execution_count": 75,
1352    "metadata": {},
1353    "outputs": [
1354     {
1355      "data": {
1356       "text/plain": [
1357        "[5]"
1358       ]
1359      },
1360      "execution_count": 75,
1361      "metadata": {},
1362      "output_type": "execute_result"
1363     }
1364    ],
1365    "source": [
1366     "[len(r) for r in reachables if 'abbe' in r]"
1367    ]
1368   },
1369   {
1370    "cell_type": "code",
1371    "execution_count": 76,
1372    "metadata": {},
1373    "outputs": [
1374     {
1375      "data": {
1376       "text/plain": [
1377        "[frozenset({'abbe', 'able', 'ably', 'ally', 'axle'})]"
1378       ]
1379      },
1380      "execution_count": 76,
1381      "metadata": {},
1382      "output_type": "execute_result"
1383     }
1384    ],
1385    "source": [
1386     "[r for r in reachables if 'abbe' in r]"
1387    ]
1388   },
1389   {
1390    "cell_type": "code",
1391    "execution_count": 77,
1392    "metadata": {
1393     "scrolled": true
1394    },
1395    "outputs": [
1396     {
1397      "data": {
1398       "text/plain": [
1399        "[frozenset({'bevy', 'levy'}),\n",
1400        " frozenset({'ogle', 'ogre'}),\n",
1401        " frozenset({'demo', 'memo'}),\n",
1402        " frozenset({'crud', 'crux'}),\n",
1403        " frozenset({'thou', 'thru'}),\n",
1404        " frozenset({'idol', 'idyl'}),\n",
1405        " frozenset({'icon', 'ikon', 'iron'}),\n",
1406        " frozenset({'used', 'user', 'uses'}),\n",
1407        " frozenset({'opal', 'oral', 'oval'}),\n",
1408        " frozenset({'also', 'alto', 'auto'}),\n",
1409        " frozenset({'idle', 'idly', 'isle'}),\n",
1410        " frozenset({'afar', 'agar', 'ajar'}),\n",
1411        " frozenset({'eddy', 'edge', 'edgy'}),\n",
1412        " frozenset({'each', 'etch', 'inch', 'itch'}),\n",
1413        " frozenset({'high', 'nigh', 'sigh', 'sign'}),\n",
1414        " frozenset({'info', 'into', 'onto', 'undo', 'unto'}),\n",
1415        " frozenset({'abbe', 'able', 'ably', 'ally', 'axle'}),\n",
1416        " frozenset({'ache', 'achy', 'acme', 'acne', 'acre', 'ashy'})]"
1417       ]
1418      },
1419      "execution_count": 77,
1420      "metadata": {},
1421      "output_type": "execute_result"
1422     }
1423    ],
1424    "source": [
1425     "sorted((r for r in reachables if len(r) > 1 if len(r) < 10), key=len)"
1426    ]
1427   },
1428   {
1429    "cell_type": "code",
1430    "execution_count": 78,
1431    "metadata": {},
1432    "outputs": [
1433     {
1434      "data": {
1435       "text/plain": [
1436        "'adze; agog; ague; ahoy; alga; ammo; amok; anal; ankh; apse; aqua; aura; avow; awol; bozo; ebbs; echo; ecru; emus; ends; envy; epee; epic; espy; euro; evil; exam; expo; guru; hymn; ibex; iffy; imam; iota; isms; judo; kiwi; liar; luau; lynx; mayo; meow; myna; nova; obey; oboe; odor; ohms; okra; oleo; once; onyx; orgy; ovum; rely; rhea; semi; sexy; stye; sync; taxi; tofu; tuft; tutu; twos; ugly; ulna; upon; urge; uric; urns; void; wiki; yeti; zebu'"
1437       ]
1438      },
1439      "execution_count": 78,
1440      "metadata": {},
1441      "output_type": "execute_result"
1442     }
1443    ],
1444    "source": [
1445     "'; '.join(sorted(list(r)[0] for r in reachables if len(r) == 1))"
1446    ]
1447   },
1448   {
1449    "cell_type": "code",
1450    "execution_count": 120,
1451    "metadata": {},
1452    "outputs": [
1453     {
1454      "name": "stdout",
1455      "output_type": "stream",
1456      "text": [
1457       "['ache'] [['ache']]\n",
1458       "['ache', 'acne'] [['ache', 'acne'], ['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
1459       "['ache', 'acme'] [['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy'], ['ache', 'acne', 'acme'], ['ache', 'acne', 'acre']]\n",
1460       "['ache', 'acre'] [['ache', 'acre'], ['ache', 'achy'], ['ache', 'acne', 'acme'], ['ache', 'acne', 'acre'], ['ache', 'acme', 'acne'], ['ache', 'acme', 'acre']]\n",
1461       "['ache', 'achy'] [['ache', 'achy'], ['ache', 'acne', 'acme'], ['ache', 'acne', 'acre'], ['ache', 'acme', 'acne'], ['ache', 'acme', 'acre'], ['ache', 'acre', 'acne'], ['ache', 'acre', 'acme']]\n",
1462       "['ache', 'acne', 'acme'] [['ache', 'acne', 'acme'], ['ache', 'acne', 'acre'], ['ache', 'acme', 'acne'], ['ache', 'acme', 'acre'], ['ache', 'acre', 'acne'], ['ache', 'acre', 'acme'], ['ache', 'achy', 'ashy']]\n",
1463       "['ache', 'acne', 'acre'] [['ache', 'acne', 'acre'], ['ache', 'acme', 'acne'], ['ache', 'acme', 'acre'], ['ache', 'acre', 'acne'], ['ache', 'acre', 'acme'], ['ache', 'achy', 'ashy'], ['ache', 'acne', 'acme', 'acre']]\n",
1464       "['ache', 'acme', 'acne'] [['ache', 'acme', 'acne'], ['ache', 'acme', 'acre'], ['ache', 'acre', 'acne'], ['ache', 'acre', 'acme'], ['ache', 'achy', 'ashy'], ['ache', 'acne', 'acme', 'acre'], ['ache', 'acne', 'acre', 'acme']]\n",
1465       "['ache', 'acme', 'acre'] [['ache', 'acme', 'acre'], ['ache', 'acre', 'acne'], ['ache', 'acre', 'acme'], ['ache', 'achy', 'ashy'], ['ache', 'acne', 'acme', 'acre'], ['ache', 'acne', 'acre', 'acme'], ['ache', 'acme', 'acne', 'acre']]\n",
1466       "['ache', 'acre', 'acne'] [['ache', 'acre', 'acne'], ['ache', 'acre', 'acme'], ['ache', 'achy', 'ashy'], ['ache', 'acne', 'acme', 'acre'], ['ache', 'acne', 'acre', 'acme'], ['ache', 'acme', 'acne', 'acre'], ['ache', 'acme', 'acre', 'acne']]\n",
1467       "['ache', 'acre', 'acme'] [['ache', 'acre', 'acme'], ['ache', 'achy', 'ashy'], ['ache', 'acne', 'acme', 'acre'], ['ache', 'acne', 'acre', 'acme'], ['ache', 'acme', 'acne', 'acre'], ['ache', 'acme', 'acre', 'acne'], ['ache', 'acre', 'acne', 'acme']]\n",
1468       "['ache', 'achy', 'ashy'] [['ache', 'achy', 'ashy'], ['ache', 'acne', 'acme', 'acre'], ['ache', 'acne', 'acre', 'acme'], ['ache', 'acme', 'acne', 'acre'], ['ache', 'acme', 'acre', 'acne'], ['ache', 'acre', 'acne', 'acme'], ['ache', 'acre', 'acme', 'acne']]\n"
1469      ]
1470     },
1471     {
1472      "data": {
1473       "text/plain": [
1474        "['ache', 'achy', 'ashy']"
1475       ]
1476      },
1477      "execution_count": 120,
1478      "metadata": {},
1479      "output_type": "execute_result"
1480     }
1481    ],
1482    "source": [
1483     "bfs_search('ache', 'ashy', debug=True)"
1484    ]
1485   },
1486   {
1487    "cell_type": "code",
1488    "execution_count": 122,
1489    "metadata": {},
1490    "outputs": [
1491     {
1492      "name": "stdout",
1493      "output_type": "stream",
1494      "text": [
1495       "[['ache']]\n",
1496       "[['ache', 'acne'], ['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
1497       "[['ache', 'acne', 'acme'], ['ache', 'acne', 'acre'], ['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
1498       "[['ache', 'acne', 'acme', 'acre'], ['ache', 'acne', 'acre'], ['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
1499       "[['ache', 'acne', 'acre'], ['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
1500       "[['ache', 'acne', 'acre', 'acme'], ['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
1501       "[['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
1502       "[['ache', 'acme', 'acne'], ['ache', 'acme', 'acre'], ['ache', 'acre'], ['ache', 'achy']]\n",
1503       "[['ache', 'acme', 'acne', 'acre'], ['ache', 'acme', 'acre'], ['ache', 'acre'], ['ache', 'achy']]\n",
1504       "[['ache', 'acme', 'acre'], ['ache', 'acre'], ['ache', 'achy']]\n",
1505       "[['ache', 'acme', 'acre', 'acne'], ['ache', 'acre'], ['ache', 'achy']]\n",
1506       "[['ache', 'acre'], ['ache', 'achy']]\n",
1507       "[['ache', 'acre', 'acne'], ['ache', 'acre', 'acme'], ['ache', 'achy']]\n",
1508       "[['ache', 'acre', 'acne', 'acme'], ['ache', 'acre', 'acme'], ['ache', 'achy']]\n",
1509       "[['ache', 'acre', 'acme'], ['ache', 'achy']]\n",
1510       "[['ache', 'acre', 'acme', 'acne'], ['ache', 'achy']]\n",
1511       "[['ache', 'achy']]\n",
1512       "[['ache', 'achy', 'ashy']]\n"
1513      ]
1514     },
1515     {
1516      "data": {
1517       "text/plain": [
1518        "['ache', 'achy', 'ashy']"
1519       ]
1520      },
1521      "execution_count": 122,
1522      "metadata": {},
1523      "output_type": "execute_result"
1524     }
1525    ],
1526    "source": [
1527     "dfs_search('ache', 'ashy', debug=True)"
1528    ]
1529   },
1530   {
1531    "cell_type": "code",
1532    "execution_count": 79,
1533    "metadata": {},
1534    "outputs": [
1535     {
1536      "data": {
1537       "text/plain": [
1538        "['buns', 'bunk', 'punk']"
1539       ]
1540      },
1541      "execution_count": 79,
1542      "metadata": {},
1543      "output_type": "execute_result"
1544     }
1545    ],
1546    "source": [
1547     "astar_search('buns', 'punk')"
1548    ]
1549   },
1550   {
1551    "cell_type": "code",
1552    "execution_count": 80,
1553    "metadata": {
1554     "collapsed": true
1555    },
1556    "outputs": [],
1557    "source": [
1558     "for a in reachables:\n",
1559     "    for b in reachables:\n",
1560     "        if a != b:\n",
1561     "            if not a.isdisjoint(b):\n",
1562     "                print(a, b)"
1563    ]
1564   },
1565   {
1566    "cell_type": "code",
1567    "execution_count": 81,
1568    "metadata": {
1569     "collapsed": true
1570    },
1571    "outputs": [],
1572    "source": [
1573     "# longest_chain = []\n",
1574     "# with open('all-chains-4.txt', 'w', 1) as f:\n",
1575     "#     for ws in reachables:\n",
1576     "#         for s in ws:\n",
1577     "#             for t in ws:\n",
1578     "#                 if s < t:\n",
1579     "#                     chain = astar_search(s, t)\n",
1580     "#                     if chain:\n",
1581     "#                         f.write('{}\\n'.format(chain))\n",
1582     "#                         if len(chain) > len(longest_chain):\n",
1583     "#                             longest_chain = chain\n",
1584     "\n",
1585     "# longest_chain"
1586    ]
1587   },
1588   {
1589    "cell_type": "code",
1590    "execution_count": 82,
1591    "metadata": {
1592     "collapsed": true
1593    },
1594    "outputs": [],
1595    "source": [
1596     "bigset = max(reachables, key=len)"
1597    ]
1598   },
1599   {
1600    "cell_type": "code",
1601    "execution_count": 83,
1602    "metadata": {},
1603    "outputs": [
1604     {
1605      "name": "stdout",
1606      "output_type": "stream",
1607      "text": [
1608       "['foil', 'boil', 'bail', 'ball', 'balk', 'bank', 'hank']\n",
1609       "['pint', 'pent', 'peat', 'meat', 'meal', 'mewl']\n",
1610       "['fuse', 'fuss', 'furs', 'ours']\n",
1611       "['plop', 'flop', 'flow', 'flew']\n",
1612       "['lull', 'bull', 'bell', 'belt', 'welt', 'wept', 'kept']\n",
1613       "['coma', 'coda', 'cods', 'cons', 'sons']\n",
1614       "['pits', 'bits', 'bats', 'bass', 'bash', 'rash']\n",
1615       "['bean', 'been', 'bees', 'beds', 'buds', 'suds']\n",
1616       "['yips', 'nips', 'nits', 'nite', 'note', 'vote']\n",
1617       "['pent', 'pens', 'yens']\n",
1618       "['crop', 'coop', 'coos', 'cons', 'cans', 'fans']\n",
1619       "['flop', 'clop', 'coop', 'cool', 'cowl', 'bowl', 'bawl']\n",
1620       "['hill', 'hull', 'hulk', 'sulk', 'suck']\n",
1621       "['aced', 'acid', 'arid', 'grid', 'grin', 'gain', 'rain']\n",
1622       "['land', 'sand', 'sans', 'suns', 'subs', 'hubs']\n",
1623       "['cogs', 'coos', 'cool', 'coal', 'foal', 'foam']\n",
1624       "['loss', 'moss', 'mods', 'nods', 'nous', 'yous']\n",
1625       "['soap', 'soar', 'boar', 'boas', 'bogs', 'jogs']\n",
1626       "['musk', 'must', 'bust', 'best', 'beet', 'beef']\n",
1627       "['fine', 'wine', 'wane', 'want', 'waft']\n"
1628      ]
1629     }
1630    ],
1631    "source": [
1632     "for _ in range(20):\n",
1633     "    start, goal = random.sample(bigset, 2)\n",
1634     "    print(astar_search_closed(start, goal))"
1635    ]
1636   },
1637   {
1638    "cell_type": "code",
1639    "execution_count": 84,
1640    "metadata": {},
1641    "outputs": [
1642     {
1643      "data": {
1644       "text/plain": [
1645        "['cops', 'coos', 'coon', 'coin', 'chin', 'thin', 'this', 'thus', 'thug']"
1646       ]
1647      },
1648      "execution_count": 84,
1649      "metadata": {},
1650      "output_type": "execute_result"
1651     }
1652    ],
1653    "source": [
1654     "astar_search('cops', 'thug')"
1655    ]
1656   },
1657   {
1658    "cell_type": "code",
1659    "execution_count": 85,
1660    "metadata": {},
1661    "outputs": [
1662     {
1663      "data": {
1664       "text/plain": [
1665        "[2204]"
1666       ]
1667      },
1668      "execution_count": 85,
1669      "metadata": {},
1670      "output_type": "execute_result"
1671     }
1672    ],
1673    "source": [
1674     "[len(r) for r in reachables if 'love' in r if 'hate' in r]"
1675    ]
1676   },
1677   {
1678    "cell_type": "code",
1679    "execution_count": 86,
1680    "metadata": {},
1681    "outputs": [
1682     {
1683      "data": {
1684       "text/plain": [
1685        "[2204]"
1686       ]
1687      },
1688      "execution_count": 86,
1689      "metadata": {},
1690      "output_type": "execute_result"
1691     }
1692    ],
1693    "source": [
1694     "[len(r) for r in reachables if 'stay' in r ]"
1695    ]
1696   },
1697   {
1698    "cell_type": "code",
1699    "execution_count": 87,
1700    "metadata": {},
1701    "outputs": [
1702     {
1703      "data": {
1704       "text/plain": [
1705        "['hate', 'have', 'hove', 'love']"
1706       ]
1707      },
1708      "execution_count": 87,
1709      "metadata": {},
1710      "output_type": "execute_result"
1711     }
1712    ],
1713    "source": [
1714     "astar_search('hate', 'love')"
1715    ]
1716   },
1717   {
1718    "cell_type": "code",
1719    "execution_count": 88,
1720    "metadata": {},
1721    "outputs": [
1722     {
1723      "data": {
1724       "text/plain": [
1725        "['wars', 'ware', 'wave', 'wove', 'love']"
1726       ]
1727      },
1728      "execution_count": 88,
1729      "metadata": {},
1730      "output_type": "execute_result"
1731     }
1732    ],
1733    "source": [
1734     "astar_search('wars', 'love')"
1735    ]
1736   },
1737   {
1738    "cell_type": "code",
1739    "execution_count": 89,
1740    "metadata": {},
1741    "outputs": [
1742     {
1743      "name": "stdout",
1744      "output_type": "stream",
1745      "text": [
1746       "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
1747       "Wall time: 199 µs\n"
1748      ]
1749     },
1750     {
1751      "data": {
1752       "text/plain": [
1753        "5"
1754       ]
1755      },
1756      "execution_count": 89,
1757      "metadata": {},
1758      "output_type": "execute_result"
1759     }
1760    ],
1761    "source": [
1762     "%time len(astar_search('wars', 'love'))"
1763    ]
1764   },
1765   {
1766    "cell_type": "code",
1767    "execution_count": 90,
1768    "metadata": {},
1769    "outputs": [
1770     {
1771      "name": "stdout",
1772      "output_type": "stream",
1773      "text": [
1774       "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
1775       "Wall time: 210 µs\n"
1776      ]
1777     },
1778     {
1779      "data": {
1780       "text/plain": [
1781        "5"
1782       ]
1783      },
1784      "execution_count": 90,
1785      "metadata": {},
1786      "output_type": "execute_result"
1787     }
1788    ],
1789    "source": [
1790     "%time len(astar_search_closed('wars', 'love'))"
1791    ]
1792   },
1793   {
1794    "cell_type": "code",
1795    "execution_count": 91,
1796    "metadata": {},
1797    "outputs": [
1798     {
1799      "name": "stdout",
1800      "output_type": "stream",
1801      "text": [
1802       "CPU times: user 12 ms, sys: 0 ns, total: 12 ms\n",
1803       "Wall time: 13.5 ms\n"
1804      ]
1805     },
1806     {
1807      "data": {
1808       "text/plain": [
1809        "272"
1810       ]
1811      },
1812      "execution_count": 91,
1813      "metadata": {},
1814      "output_type": "execute_result"
1815     }
1816    ],
1817    "source": [
1818     "%time len(dfs_search('wars', 'love'))"
1819    ]
1820   },
1821   {
1822    "cell_type": "code",
1823    "execution_count": 92,
1824    "metadata": {
1825     "collapsed": true
1826    },
1827    "outputs": [],
1828    "source": [
1829     "# %time len(bfs_search('wars', 'love'))"
1830    ]
1831   },
1832   {
1833    "cell_type": "code",
1834    "execution_count": 93,
1835    "metadata": {},
1836    "outputs": [
1837     {
1838      "name": "stdout",
1839      "output_type": "stream",
1840      "text": [
1841       "CPU times: user 724 ms, sys: 0 ns, total: 724 ms\n",
1842       "Wall time: 723 ms\n"
1843      ]
1844     },
1845     {
1846      "data": {
1847       "text/plain": [
1848        "5"
1849       ]
1850      },
1851      "execution_count": 93,
1852      "metadata": {},
1853      "output_type": "execute_result"
1854     }
1855    ],
1856    "source": [
1857     "%time len(bfs_search_closed('wars', 'love'))"
1858    ]
1859   },
1860   {
1861    "cell_type": "code",
1862    "execution_count": 94,
1863    "metadata": {},
1864    "outputs": [
1865     {
1866      "data": {
1867       "text/plain": [
1868        "['fear', 'feat', 'fest', 'lest', 'lost', 'lose', 'love']"
1869       ]
1870      },
1871      "execution_count": 94,
1872      "metadata": {},
1873      "output_type": "execute_result"
1874     }
1875    ],
1876    "source": [
1877     "astar_search('fear', 'love')"
1878    ]
1879   },
1880   {
1881    "cell_type": "code",
1882    "execution_count": 95,
1883    "metadata": {},
1884    "outputs": [
1885     {
1886      "data": {
1887       "text/plain": [
1888        "['fail', 'fall', 'pall', 'pals', 'pass']"
1889       ]
1890      },
1891      "execution_count": 95,
1892      "metadata": {},
1893      "output_type": "execute_result"
1894     }
1895    ],
1896    "source": [
1897     "astar_search('fail', 'pass')"
1898    ]
1899   },
1900   {
1901    "cell_type": "code",
1902    "execution_count": 96,
1903    "metadata": {},
1904    "outputs": [
1905     {
1906      "data": {
1907       "text/plain": [
1908        "['star', 'soar', 'boar', 'boor', 'boon', 'born']"
1909       ]
1910      },
1911      "execution_count": 96,
1912      "metadata": {},
1913      "output_type": "execute_result"
1914     }
1915    ],
1916    "source": [
1917     "astar_search('star', 'born')"
1918    ]
1919   },
1920   {
1921    "cell_type": "code",
1922    "execution_count": 97,
1923    "metadata": {},
1924    "outputs": [
1925     {
1926      "data": {
1927       "text/plain": [
1928        "['open',\n",
1929        " 'oven',\n",
1930        " 'even',\n",
1931        " 'eves',\n",
1932        " 'eyes',\n",
1933        " 'byes',\n",
1934        " 'bees',\n",
1935        " 'begs',\n",
1936        " 'bags',\n",
1937        " 'bass',\n",
1938        " 'pass']"
1939       ]
1940      },
1941      "execution_count": 97,
1942      "metadata": {},
1943      "output_type": "execute_result"
1944     }
1945    ],
1946    "source": [
1947     "astar_search('open', 'pass')"
1948    ]
1949   },
1950   {
1951    "cell_type": "code",
1952    "execution_count": 98,
1953    "metadata": {},
1954    "outputs": [
1955     {
1956      "data": {
1957       "text/plain": [
1958        "frozenset({'bass',\n",
1959        "           'lass',\n",
1960        "           'mass',\n",
1961        "           'pads',\n",
1962        "           'pals',\n",
1963        "           'pans',\n",
1964        "           'paps',\n",
1965        "           'pars',\n",
1966        "           'past',\n",
1967        "           'pats',\n",
1968        "           'paws',\n",
1969        "           'pays',\n",
1970        "           'puss',\n",
1971        "           'sass'})"
1972       ]
1973      },
1974      "execution_count": 98,
1975      "metadata": {},
1976      "output_type": "execute_result"
1977     }
1978    ],
1979    "source": [
1980     "neighbours['pass']"
1981    ]
1982   },
1983   {
1984    "cell_type": "code",
1985    "execution_count": 99,
1986    "metadata": {},
1987    "outputs": [
1988     {
1989      "data": {
1990       "text/plain": [
1991        "[1]"
1992       ]
1993      },
1994      "execution_count": 99,
1995      "metadata": {},
1996      "output_type": "execute_result"
1997     }
1998    ],
1999    "source": [
2000     "[len(r) for r in reachables if 'exam' in r]"
2001    ]
2002   },
2003   {
2004    "cell_type": "code",
2005    "execution_count": 100,
2006    "metadata": {},
2007    "outputs": [
2008     {
2009      "data": {
2010       "text/plain": [
2011        "[2204]"
2012       ]
2013      },
2014      "execution_count": 100,
2015      "metadata": {},
2016      "output_type": "execute_result"
2017     }
2018    ],
2019    "source": [
2020     "[len(r) for r in reachables if 'star' in r if 'born' in r]"
2021    ]
2022   },
2023   {
2024    "cell_type": "code",
2025    "execution_count": 101,
2026    "metadata": {},
2027    "outputs": [
2028     {
2029      "name": "stdout",
2030      "output_type": "stream",
2031      "text": [
2032       "1 loop, best of 3: 9.05 s per loop\n"
2033      ]
2034     }
2035    ],
2036    "source": [
2037     "%%timeit\n",
2038     "astar_search('bats', 'exit')"
2039    ]
2040   },
2041   {
2042    "cell_type": "code",
2043    "execution_count": 102,
2044    "metadata": {},
2045    "outputs": [
2046     {
2047      "name": "stdout",
2048      "output_type": "stream",
2049      "text": [
2050       "10 loops, best of 3: 147 ms per loop\n"
2051      ]
2052     }
2053    ],
2054    "source": [
2055     "%%timeit\n",
2056     "astar_search_closed('bats', 'exit')"
2057    ]
2058   },
2059   {
2060    "cell_type": "code",
2061    "execution_count": 103,
2062    "metadata": {},
2063    "outputs": [
2064     {
2065      "data": {
2066       "text/plain": [
2067        "['bats',\n",
2068        " 'bans',\n",
2069        " 'band',\n",
2070        " 'sand',\n",
2071        " 'said',\n",
2072        " 'skid',\n",
2073        " 'skit',\n",
2074        " 'smit',\n",
2075        " 'emit',\n",
2076        " 'exit']"
2077       ]
2078      },
2079      "execution_count": 103,
2080      "metadata": {},
2081      "output_type": "execute_result"
2082     }
2083    ],
2084    "source": [
2085     "astar_search_closed('bats', 'exit')"
2086    ]
2087   },
2088   {
2089    "cell_type": "code",
2090    "execution_count": 104,
2091    "metadata": {
2092     "collapsed": true
2093    },
2094    "outputs": [],
2095    "source": [
2096     "# solutions = {}\n",
2097     "# for _ in range(10000):\n",
2098     "#     start, goal = random.sample(bigset, 2)\n",
2099     "#     solution = astar_search_closed(start, goal)\n",
2100     "#     sl = len(solution)\n",
2101     "#     if sl not in solutions:\n",
2102     "#         solutions[sl] = []\n",
2103     "#     if len(solutions[sl]) < 4:\n",
2104     "#         solutions[sl].append([start, goal])\n",
2105     "        \n",
2106     "# #     if len(solution) >= 10:\n",
2107     "# #         solutions += [solution]\n",
2108     "        \n",
2109     "# solutions"
2110    ]
2111   },
2112   {
2113    "cell_type": "code",
2114    "execution_count": 105,
2115    "metadata": {
2116     "collapsed": true
2117    },
2118    "outputs": [],
2119    "source": [
2120     "solutions = {2: [['heel', 'keel'], ['wane', 'wave'], ['cell', 'sell'], ['cons', 'cobs']],\n",
2121     " 3: [['hank', 'haws'], ['bars', 'bets'], ['rats', 'paws'], ['lock', 'hack']],\n",
2122     " 4: [['rule', 'sore'], ['wavy', 'rape'], ['peas', 'ping'], ['bond', 'toll']],\n",
2123     " 5: [['cope', 'yowl'], ['lose', 'loci'], ['rump', 'dash'], ['four', 'dyes']],\n",
2124     " 6: [['boon', 'sell'], ['lots', 'pomp'], ['cola', 'turn'], ['boos', 'laid']],\n",
2125     " 7: [['eave', 'inns'], ['meek', 'mere'], ['keys', 'wily'], ['slam', 'yore']],\n",
2126     " 8: [['hack', 'flip'], ['crag', 'huge'], ['flux', 'gill'], ['play', 'busy']],\n",
2127     " 9: [['lacy', 'whey'], ['wren', 'rook'], ['lire', 'drip'], ['grab', 'lame']],\n",
2128     " 10: [['over', 'turn'], ['worn', 'anew'], ['stow', 'elks'], ['ergo', 'rich']],\n",
2129     " 11: [['bask', 'idea'], ['gabs', 'thud'], ['idea', 'clod'], ['mark', 'ibis']],\n",
2130     " 12: [['umps', 'torn'], ['futz', 'shun'], ['abut', 'face'], ['slug', 'open']],\n",
2131     " 13: [['umps', 'skin'], ['chum', 'rats'], ['fury', 'chum'], ['omen', 'zany']],\n",
2132     " 14: [['chug', 'gaff'], ['atom', 'fizz'], ['chug', 'jinn'], ['amen', 'flog'],\n",
2133     "     ['buzz', 'grog'], ['imps', 'pros']],\n",
2134     " 15: [['chug', 'oxen'], ['amen', 'doff']]}"
2135    ]
2136   },
2137   {
2138    "cell_type": "code",
2139    "execution_count": 106,
2140    "metadata": {},
2141    "outputs": [
2142     {
2143      "name": "stdout",
2144      "output_type": "stream",
2145      "text": [
2146       "1 loop, best of 3: 358 ms per loop\n"
2147      ]
2148     }
2149    ],
2150    "source": [
2151     "%%timeit\n",
2152     "astar_search_closed('blab', 'amen')"
2153    ]
2154   },
2155   {
2156    "cell_type": "code",
2157    "execution_count": 107,
2158    "metadata": {},
2159    "outputs": [
2160     {
2161      "name": "stdout",
2162      "output_type": "stream",
2163      "text": [
2164       "CPU times: user 384 ms, sys: 0 ns, total: 384 ms\n",
2165       "Wall time: 382 ms\n"
2166      ]
2167     },
2168     {
2169      "data": {
2170       "text/plain": [
2171        "14"
2172       ]
2173      },
2174      "execution_count": 107,
2175      "metadata": {},
2176      "output_type": "execute_result"
2177     }
2178    ],
2179    "source": [
2180     "%time len(astar_search_closed('blab', 'amen'))"
2181    ]
2182   },
2183   {
2184    "cell_type": "code",
2185    "execution_count": 108,
2186    "metadata": {},
2187    "outputs": [
2188     {
2189      "name": "stdout",
2190      "output_type": "stream",
2191      "text": [
2192       "CPU times: user 112 ms, sys: 0 ns, total: 112 ms\n",
2193       "Wall time: 109 ms\n"
2194      ]
2195     },
2196     {
2197      "data": {
2198       "text/plain": [
2199        "15"
2200       ]
2201      },
2202      "execution_count": 108,
2203      "metadata": {},
2204      "output_type": "execute_result"
2205     }
2206    ],
2207    "source": [
2208     "%time len(astar_search_closed('amen', 'doff'))"
2209    ]
2210   },
2211   {
2212    "cell_type": "code",
2213    "execution_count": 109,
2214    "metadata": {},
2215    "outputs": [
2216     {
2217      "name": "stdout",
2218      "output_type": "stream",
2219      "text": [
2220       "CPU times: user 40 ms, sys: 0 ns, total: 40 ms\n",
2221       "Wall time: 36.5 ms\n"
2222      ]
2223     },
2224     {
2225      "data": {
2226       "text/plain": [
2227        "14"
2228       ]
2229      },
2230      "execution_count": 109,
2231      "metadata": {},
2232      "output_type": "execute_result"
2233     }
2234    ],
2235    "source": [
2236     "%time len(astar_search_closed('chug', 'jinn'))"
2237    ]
2238   },
2239   {
2240    "cell_type": "code",
2241    "execution_count": 110,
2242    "metadata": {},
2243    "outputs": [
2244     {
2245      "name": "stdout",
2246      "output_type": "stream",
2247      "text": [
2248       "CPU times: user 20 ms, sys: 0 ns, total: 20 ms\n",
2249       "Wall time: 18.1 ms\n"
2250      ]
2251     },
2252     {
2253      "data": {
2254       "text/plain": [
2255        "14"
2256       ]
2257      },
2258      "execution_count": 110,
2259      "metadata": {},
2260      "output_type": "execute_result"
2261     }
2262    ],
2263    "source": [
2264     "%time len(astar_search_closed('amen', 'flog'))"
2265    ]
2266   },
2267   {
2268    "cell_type": "code",
2269    "execution_count": 111,
2270    "metadata": {},
2271    "outputs": [
2272     {
2273      "name": "stdout",
2274      "output_type": "stream",
2275      "text": [
2276       "CPU times: user 272 ms, sys: 0 ns, total: 272 ms\n",
2277       "Wall time: 267 ms\n"
2278      ]
2279     },
2280     {
2281      "data": {
2282       "text/plain": [
2283        "14"
2284       ]
2285      },
2286      "execution_count": 111,
2287      "metadata": {},
2288      "output_type": "execute_result"
2289     }
2290    ],
2291    "source": [
2292     "%time len(astar_search_closed('buzz', 'grog'))"
2293    ]
2294   },
2295   {
2296    "cell_type": "code",
2297    "execution_count": 112,
2298    "metadata": {},
2299    "outputs": [
2300     {
2301      "name": "stdout",
2302      "output_type": "stream",
2303      "text": [
2304       "CPU times: user 40 ms, sys: 0 ns, total: 40 ms\n",
2305       "Wall time: 37.8 ms\n"
2306      ]
2307     },
2308     {
2309      "data": {
2310       "text/plain": [
2311        "14"
2312       ]
2313      },
2314      "execution_count": 112,
2315      "metadata": {},
2316      "output_type": "execute_result"
2317     }
2318    ],
2319    "source": [
2320     "%time len(astar_search_closed('imps', 'pros'))"
2321    ]
2322   },
2323   {
2324    "cell_type": "code",
2325    "execution_count": 113,
2326    "metadata": {},
2327    "outputs": [
2328     {
2329      "name": "stdout",
2330      "output_type": "stream",
2331      "text": [
2332       "rush bush True\n",
2333       "bash bush True\n"
2334      ]
2335     },
2336     {
2337      "data": {
2338       "text/plain": [
2339        "2"
2340       ]
2341      },
2342      "execution_count": 113,
2343      "metadata": {},
2344      "output_type": "execute_result"
2345     }
2346    ],
2347    "source": [
2348     "nb_count = collections.Counter()\n",
2349     "for w in neighbours['rash']:\n",
2350     "    for w2 in neighbours[w]:\n",
2351     "        if w2 == 'bush': print(w, w2, w2 not in neighbours['rash'])\n",
2352     "        if w2 != 'rash' and w2 not in neighbours['rash']:\n",
2353     "            nb_count.update([w2])\n",
2354     "nb_count.most_common(1)[0][1]"
2355    ]
2356   },
2357   {
2358    "cell_type": "code",
2359    "execution_count": 114,
2360    "metadata": {},
2361    "outputs": [
2362     {
2363      "data": {
2364       "text/plain": [
2365        "['gush', 'mush', 'bosh', 'tush', 'lush', 'push', 'hush']"
2366       ]
2367      },
2368      "execution_count": 114,
2369      "metadata": {},
2370      "output_type": "execute_result"
2371     }
2372    ],
2373    "source": [
2374     "[w for w in neighbours['bush'] if w in nb_count]"
2375    ]
2376   },
2377   {
2378    "cell_type": "code",
2379    "execution_count": 115,
2380    "metadata": {},
2381    "outputs": [
2382     {
2383      "data": {
2384       "text/plain": [
2385        "('came', 2)"
2386       ]
2387      },
2388      "execution_count": 115,
2389      "metadata": {},
2390      "output_type": "execute_result"
2391     }
2392    ],
2393    "source": [
2394     "best_start = ''\n",
2395     "best_overlap_count = 0\n",
2396     "for w0 in neighbours:    \n",
2397     "    nb_count = collections.Counter()\n",
2398     "    for w in neighbours[w0]:\n",
2399     "        for w2 in neighbours[w]:\n",
2400     "            if w2 != w0 and w2 not in neighbours[w0]:\n",
2401     "                nb_count.update([w2])\n",
2402     "    if len(nb_count) > 0:\n",
2403     "        if nb_count.most_common(1)[0][1] > best_overlap_count:\n",
2404     "            best_start = w0\n",
2405     "            best_overlap_count = nb_count.most_common(1)[0][1]\n",
2406     "        \n",
2407     "best_start, best_overlap_count"
2408    ]
2409   },
2410   {
2411    "cell_type": "code",
2412    "execution_count": 116,
2413    "metadata": {},
2414    "outputs": [
2415     {
2416      "data": {
2417       "text/plain": [
2418        "'hags'"
2419       ]
2420      },
2421      "execution_count": 116,
2422      "metadata": {},
2423      "output_type": "execute_result"
2424     }
2425    ],
2426    "source": [
2427     "w0"
2428    ]
2429   },
2430   {
2431    "cell_type": "code",
2432    "execution_count": 117,
2433    "metadata": {},
2434    "outputs": [
2435     {
2436      "data": {
2437       "text/plain": [
2438        "{'bash', 'rush'}"
2439       ]
2440      },
2441      "execution_count": 117,
2442      "metadata": {},
2443      "output_type": "execute_result"
2444     }
2445    ],
2446    "source": [
2447     "set(neighbours['rash']) & set(neighbours['bush'])"
2448    ]
2449   },
2450   {
2451    "cell_type": "code",
2452    "execution_count": null,
2453    "metadata": {
2454     "collapsed": true
2455    },
2456    "outputs": [],
2457    "source": []
2458   }
2459  ],
2460  "metadata": {
2461   "kernelspec": {
2462    "display_name": "Python 3",
2463    "language": "python",
2464    "name": "python3"
2465   },
2466   "language_info": {
2467    "codemirror_mode": {
2468     "name": "ipython",
2469     "version": 3
2470    },
2471    "file_extension": ".py",
2472    "mimetype": "text/x-python",
2473    "name": "python",
2474    "nbconvert_exporter": "python",
2475    "pygments_lexer": "ipython3",
2476    "version": "3.5.3"
2477   }
2478  },
2479  "nbformat": 4,
2480  "nbformat_minor": 2
2481 }