X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=09-word-chains%2Fexplore-word-chain-4.ipynb;fp=09-word-chains%2Fexplore-word-chain-4.ipynb;h=5f624fd65885f27cbae4e71c725cbe14d5821496;hb=9db793681c67b0ea1be1a404a5a7c1d5afc26610;hp=0000000000000000000000000000000000000000;hpb=76d7dcd5ad275f76e38a33a45e0fbdf2948c6b29;p=ou-summer-of-code-2017.git diff --git a/09-word-chains/explore-word-chain-4.ipynb b/09-word-chains/explore-word-chain-4.ipynb new file mode 100644 index 0000000..5f624fd --- /dev/null +++ b/09-word-chains/explore-word-chain-4.ipynb @@ -0,0 +1,3311 @@ +{ + "cells": [ + { + "cell_type": "code", + "execution_count": 1, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "import string\n", + "import heapq\n", + "import collections\n", + "import random" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "2336" + ] + }, + "execution_count": 2, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "words = [w.strip() for w in open('words4.txt').readlines()]\n", + "len(words)" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['abbe',\n", + " 'abed',\n", + " 'abet',\n", + " 'able',\n", + " 'ably',\n", + " 'abut',\n", + " 'aced',\n", + " 'aces',\n", + " 'ache',\n", + " 'achy']" + ] + }, + "execution_count": 3, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "words[:10]" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def adjacents_explicit(word):\n", + " neighbours = []\n", + " for i in range(len(word)):\n", + " for l in string.ascii_lowercase:\n", + " if l != word[i]:\n", + " neighbours.append(word[0:i] + l + word[i+1:])\n", + " return neighbours" + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def adjacents(word):\n", + " return [word[0:i] + l + word[i+1:]\n", + " for i in range(len(word))\n", + " for l in string.ascii_lowercase\n", + " if l != word[i]]" + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "neighbours = {w: [n for n in adjacents(w) if n in words]\n", + " for w in words}" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['able']" + ] + }, + "execution_count": 7, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "neighbours['abbe']" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['axle', 'abbe', 'ably']" + ] + }, + "execution_count": 8, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "neighbours['able']" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def distance(w1, w2):\n", + " return sum(1 for i in range(len(w1))\n", + " if w1[i] != w2[i])" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "0" + ] + }, + "execution_count": 10, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "distance('abbe', 'abbe')" + ] + }, + { + "cell_type": "code", + "execution_count": 11, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def extend(chain, closed=None):\n", + " if closed:\n", + " nbrs = set(neighbours[chain[-1]]) - closed\n", + " else:\n", + " nbrs = neighbours[chain[-1]]\n", + " return [chain + [s] for s in nbrs\n", + " if s not in chain]" + ] + }, + { + "cell_type": "code", + "execution_count": 12, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[['abbe', 'able']]" + ] + }, + "execution_count": 12, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "extend(['abbe'])" + ] + }, + { + "cell_type": "code", + "execution_count": 13, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[['abbe', 'able', 'axle'], ['abbe', 'able', 'ably']]" + ] + }, + "execution_count": 13, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "extend(['abbe', 'able'])" + ] + }, + { + "cell_type": "code", + "execution_count": 14, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[['abbe', 'able', 'ably', 'ally']]" + ] + }, + "execution_count": 14, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "extend(['abbe', 'able', 'ably'])" + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def bfs_search(start, goal, debug=False):\n", + " agenda = [[start]]\n", + " finished = False\n", + " while not finished and agenda:\n", + " current = agenda[0]\n", + " if debug:\n", + " print(current)\n", + " if current[-1] == goal:\n", + " finished = True\n", + " else:\n", + " successors = extend(current)\n", + " agenda = agenda[1:] + successors\n", + " if agenda:\n", + " return current\n", + " else:\n", + " return None " + ] + }, + { + "cell_type": "code", + "execution_count": 16, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def bfs_search_closed(start, goal, debug=False):\n", + " agenda = [[start]]\n", + " closed = set()\n", + " finished = False\n", + " while not finished and agenda:\n", + " current = agenda[0]\n", + " if debug:\n", + " print(current)\n", + " if current[-1] == goal:\n", + " finished = True\n", + " else:\n", + " closed.add(current[-1])\n", + " successors = extend(current, closed)\n", + " agenda = agenda[1:] + successors\n", + " if agenda:\n", + " return current\n", + " else:\n", + " return None " + ] + }, + { + "cell_type": "code", + "execution_count": 17, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "['abbe']\n", + "['abbe', 'able']\n", + "['abbe', 'able', 'axle']\n", + "['abbe', 'able', 'ably']\n", + "['abbe', 'able', 'ably', 'ally']\n" + ] + }, + { + "data": { + "text/plain": [ + "['abbe', 'able', 'ably', 'ally']" + ] + }, + "execution_count": 17, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "bfs_search('abbe', 'ally', debug=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def dfs_search(start, goal, debug=False):\n", + " agenda = [[start]]\n", + " finished = False\n", + " while not finished and agenda:\n", + " current = agenda[0]\n", + " if debug:\n", + " print(current)\n", + " if current[-1] == goal:\n", + " finished = True\n", + " else:\n", + " successors = extend(current)\n", + " agenda = successors + agenda[1:]\n", + " if agenda:\n", + " return current\n", + " else:\n", + " return None " + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "['abbe']\n", + "['abbe', 'able']\n", + "['abbe', 'able', 'axle']\n", + "['abbe', 'able', 'ably']\n", + "['abbe', 'able', 'ably', 'ally']\n" + ] + }, + { + "data": { + "text/plain": [ + "['abbe', 'able', 'ably', 'ally']" + ] + }, + "execution_count": 19, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "dfs_search('abbe', 'ally', debug=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 20, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "['cart']\n", + "['cart', 'dart']\n", + "['cart', 'hart']\n", + "['cart', 'mart']\n", + "['cart', 'part']\n", + "['cart', 'tart']\n", + "['cart', 'wart']\n", + "['cart', 'curt']\n", + "['cart', 'cant']\n", + "['cart', 'cast']\n", + "['cart', 'card']\n", + "['cart', 'care']\n", + "['cart', 'carp']\n", + "['cart', 'cars']\n", + "['cart', 'dart', 'hart']\n", + "['cart', 'dart', 'mart']\n", + "['cart', 'dart', 'part']\n", + "['cart', 'dart', 'tart']\n", + "['cart', 'dart', 'wart']\n", + "['cart', 'dart', 'dirt']\n", + "['cart', 'dart', 'daft']\n", + "['cart', 'dart', 'dare']\n", + "['cart', 'dart', 'dark']\n", + "['cart', 'dart', 'darn']\n", + "['cart', 'hart', 'dart']\n", + "['cart', 'hart', 'mart']\n", + "['cart', 'hart', 'part']\n", + "['cart', 'hart', 'tart']\n", + "['cart', 'hart', 'wart']\n", + "['cart', 'hart', 'hurt']\n", + "['cart', 'hart', 'haft']\n", + "['cart', 'hart', 'halt']\n", + "['cart', 'hart', 'hard']\n", + "['cart', 'hart', 'hare']\n", + "['cart', 'hart', 'hark']\n", + "['cart', 'hart', 'harm']\n", + "['cart', 'hart', 'harp']\n", + "['cart', 'mart', 'dart']\n", + "['cart', 'mart', 'hart']\n", + "['cart', 'mart', 'part']\n", + "['cart', 'mart', 'tart']\n", + "['cart', 'mart', 'wart']\n", + "['cart', 'mart', 'malt']\n", + "['cart', 'mart', 'mast']\n", + "['cart', 'mart', 'matt']\n", + "['cart', 'mart', 'mare']\n", + "['cart', 'mart', 'mark']\n", + "['cart', 'mart', 'mars']\n", + "['cart', 'part', 'dart']\n", + "['cart', 'part', 'hart']\n", + "['cart', 'part', 'mart']\n", + "['cart', 'part', 'tart']\n", + "['cart', 'part', 'wart']\n", + "['cart', 'part', 'pert']\n", + "['cart', 'part', 'port']\n", + "['cart', 'part', 'pact']\n", + "['cart', 'part', 'pant']\n", + "['cart', 'part', 'past']\n", + "['cart', 'part', 'pare']\n", + "['cart', 'part', 'park']\n", + "['cart', 'part', 'pars']\n", + "['cart', 'tart', 'dart']\n", + "['cart', 'tart', 'hart']\n", + "['cart', 'tart', 'mart']\n", + "['cart', 'tart', 'part']\n", + "['cart', 'tart', 'wart']\n", + "['cart', 'tart', 'tort']\n", + "['cart', 'tart', 'tact']\n", + "['cart', 'tart', 'taut']\n", + "['cart', 'tart', 'tare']\n", + "['cart', 'tart', 'taro']\n", + "['cart', 'tart', 'tarp']\n", + "['cart', 'tart', 'tars']\n", + "['cart', 'wart', 'dart']\n", + "['cart', 'wart', 'hart']\n", + "['cart', 'wart', 'mart']\n", + "['cart', 'wart', 'part']\n", + "['cart', 'wart', 'tart']\n", + "['cart', 'wart', 'waft']\n", + "['cart', 'wart', 'wait']\n", + "['cart', 'wart', 'want']\n", + "['cart', 'wart', 'watt']\n", + "['cart', 'wart', 'ward']\n", + "['cart', 'wart', 'ware']\n", + "['cart', 'wart', 'warm']\n", + "['cart', 'wart', 'warn']\n", + "['cart', 'wart', 'warp']\n", + "['cart', 'wart', 'wars']\n", + "['cart', 'wart', 'wary']\n", + "['cart', 'curt', 'hurt']\n", + "['cart', 'curt', 'cult']\n", + "['cart', 'curt', 'curb']\n", + "['cart', 'curt', 'curd']\n", + "['cart', 'curt', 'cure']\n", + "['cart', 'curt', 'curl']\n", + "['cart', 'curt', 'curs']\n", + "['cart', 'cant', 'pant']\n", + "['cart', 'cant', 'rant']\n", + "['cart', 'cant', 'want']\n", + "['cart', 'cant', 'cent']\n", + "['cart', 'cant', 'cast']\n", + "['cart', 'cant', 'cane']\n", + "['cart', 'cant', 'cans']\n", + "['cart', 'cast', 'bast']\n", + "['cart', 'cast', 'east']\n", + "['cart', 'cast', 'fast']\n", + "['cart', 'cast', 'last']\n", + "['cart', 'cast', 'mast']\n", + "['cart', 'cast', 'past']\n", + "['cart', 'cast', 'vast']\n", + "['cart', 'cast', 'cost']\n", + "['cart', 'cast', 'cyst']\n", + "['cart', 'cast', 'cant']\n", + "['cart', 'cast', 'case']\n", + "['cart', 'cast', 'cash']\n", + "['cart', 'cast', 'cask']\n", + "['cart', 'card', 'bard']\n", + "['cart', 'card', 'hard']\n", + "['cart', 'card', 'lard']\n", + "['cart', 'card', 'ward']\n", + "['cart', 'card', 'yard']\n", + "['cart', 'card', 'cord']\n", + "['cart', 'card', 'curd']\n", + "['cart', 'card', 'care']\n", + "['cart', 'card', 'carp']\n", + "['cart', 'card', 'cars']\n", + "['cart', 'care', 'bare']\n", + "['cart', 'care', 'dare']\n", + "['cart', 'care', 'fare']\n", + "['cart', 'care', 'hare']\n", + "['cart', 'care', 'mare']\n", + "['cart', 'care', 'pare']\n", + "['cart', 'care', 'rare']\n", + "['cart', 'care', 'tare']\n", + "['cart', 'care', 'ware']\n", + "['cart', 'care', 'core']\n", + "['cart', 'care', 'cure']\n", + "['cart', 'care', 'cafe']\n", + "['cart', 'care', 'cage']\n", + "['cart', 'care', 'cake']\n", + "['cart', 'care', 'came']\n", + "['cart', 'care', 'cane']\n", + "['cart', 'care', 'cape']\n", + "['cart', 'care', 'case']\n", + "['cart', 'care', 'cave']\n", + "['cart', 'care', 'card']\n", + "['cart', 'care', 'carp']\n", + "['cart', 'care', 'cars']\n", + "['cart', 'carp', 'harp']\n", + "['cart', 'carp', 'tarp']\n", + "['cart', 'carp', 'warp']\n", + "['cart', 'carp', 'camp']\n", + "['cart', 'carp', 'card']\n", + "['cart', 'carp', 'care']\n", + "['cart', 'carp', 'cars']\n", + "['cart', 'cars', 'bars']\n", + "['cart', 'cars', 'ears']\n", + "['cart', 'cars', 'jars']\n", + "['cart', 'cars', 'mars']\n", + "['cart', 'cars', 'oars']\n", + "['cart', 'cars', 'pars']\n", + "['cart', 'cars', 'tars']\n", + "['cart', 'cars', 'wars']\n", + "['cart', 'cars', 'curs']\n", + "['cart', 'cars', 'cabs']\n", + "['cart', 'cars', 'cads']\n", + "['cart', 'cars', 'cams']\n", + "['cart', 'cars', 'cans']\n", + "['cart', 'cars', 'caps']\n", + "['cart', 'cars', 'cats']\n", + "['cart', 'cars', 'caws']\n", + "['cart', 'cars', 'card']\n", + "['cart', 'cars', 'care']\n", + "['cart', 'cars', 'carp']\n", + "['cart', 'dart', 'hart', 'mart']\n", + "['cart', 'dart', 'hart', 'part']\n", + "['cart', 'dart', 'hart', 'tart']\n", + "['cart', 'dart', 'hart', 'wart']\n", + "['cart', 'dart', 'hart', 'hurt']\n", + "['cart', 'dart', 'hart', 'haft']\n", + "['cart', 'dart', 'hart', 'halt']\n", + "['cart', 'dart', 'hart', 'hard']\n", + "['cart', 'dart', 'hart', 'hare']\n", + "['cart', 'dart', 'hart', 'hark']\n", + "['cart', 'dart', 'hart', 'harm']\n", + "['cart', 'dart', 'hart', 'harp']\n", + "['cart', 'dart', 'mart', 'hart']\n", + "['cart', 'dart', 'mart', 'part']\n", + "['cart', 'dart', 'mart', 'tart']\n", + "['cart', 'dart', 'mart', 'wart']\n", + "['cart', 'dart', 'mart', 'malt']\n", + "['cart', 'dart', 'mart', 'mast']\n", + "['cart', 'dart', 'mart', 'matt']\n", + "['cart', 'dart', 'mart', 'mare']\n", + "['cart', 'dart', 'mart', 'mark']\n", + "['cart', 'dart', 'mart', 'mars']\n", + "['cart', 'dart', 'part', 'hart']\n", + "['cart', 'dart', 'part', 'mart']\n", + "['cart', 'dart', 'part', 'tart']\n", + "['cart', 'dart', 'part', 'wart']\n", + "['cart', 'dart', 'part', 'pert']\n", + "['cart', 'dart', 'part', 'port']\n", + "['cart', 'dart', 'part', 'pact']\n", + "['cart', 'dart', 'part', 'pant']\n", + "['cart', 'dart', 'part', 'past']\n", + "['cart', 'dart', 'part', 'pare']\n", + "['cart', 'dart', 'part', 'park']\n", + "['cart', 'dart', 'part', 'pars']\n", + "['cart', 'dart', 'tart', 'hart']\n", + "['cart', 'dart', 'tart', 'mart']\n", + "['cart', 'dart', 'tart', 'part']\n", + "['cart', 'dart', 'tart', 'wart']\n", + "['cart', 'dart', 'tart', 'tort']\n", + "['cart', 'dart', 'tart', 'tact']\n", + "['cart', 'dart', 'tart', 'taut']\n", + "['cart', 'dart', 'tart', 'tare']\n", + "['cart', 'dart', 'tart', 'taro']\n", + "['cart', 'dart', 'tart', 'tarp']\n", + "['cart', 'dart', 'tart', 'tars']\n", + "['cart', 'dart', 'wart', 'hart']\n", + "['cart', 'dart', 'wart', 'mart']\n", + "['cart', 'dart', 'wart', 'part']\n", + "['cart', 'dart', 'wart', 'tart']\n", + "['cart', 'dart', 'wart', 'waft']\n", + "['cart', 'dart', 'wart', 'wait']\n", + "['cart', 'dart', 'wart', 'want']\n", + "['cart', 'dart', 'wart', 'watt']\n", + "['cart', 'dart', 'wart', 'ward']\n", + "['cart', 'dart', 'wart', 'ware']\n", + "['cart', 'dart', 'wart', 'warm']\n", + "['cart', 'dart', 'wart', 'warn']\n", + "['cart', 'dart', 'wart', 'warp']\n", + "['cart', 'dart', 'wart', 'wars']\n", + "['cart', 'dart', 'wart', 'wary']\n", + "['cart', 'dart', 'dirt', 'girt']\n", + "['cart', 'dart', 'dirt', 'diet']\n", + "['cart', 'dart', 'dirt', 'dint']\n", + "['cart', 'dart', 'dirt', 'dire']\n", + "['cart', 'dart', 'dirt', 'dirk']\n", + "['cart', 'dart', 'daft', 'haft']\n", + "['cart', 'dart', 'daft', 'raft']\n", + "['cart', 'dart', 'daft', 'waft']\n", + "['cart', 'dart', 'daft', 'deft']\n", + "['cart', 'dart', 'dare', 'bare']\n", + "['cart', 'dart', 'dare', 'care']\n", + "['cart', 'dart', 'dare', 'fare']\n", + "['cart', 'dart', 'dare', 'hare']\n", + "['cart', 'dart', 'dare', 'mare']\n", + "['cart', 'dart', 'dare', 'pare']\n", + "['cart', 'dart', 'dare', 'rare']\n", + "['cart', 'dart', 'dare', 'tare']\n", + "['cart', 'dart', 'dare', 'ware']\n", + "['cart', 'dart', 'dare', 'dire']\n", + "['cart', 'dart', 'dare', 'dale']\n", + "['cart', 'dart', 'dare', 'dame']\n", + "['cart', 'dart', 'dare', 'date']\n", + "['cart', 'dart', 'dare', 'daze']\n", + "['cart', 'dart', 'dare', 'dark']\n", + "['cart', 'dart', 'dare', 'darn']\n", + "['cart', 'dart', 'dark', 'bark']\n", + "['cart', 'dart', 'dark', 'hark']\n", + "['cart', 'dart', 'dark', 'lark']\n", + "['cart', 'dart', 'dark', 'mark']\n", + "['cart', 'dart', 'dark', 'nark']\n", + "['cart', 'dart', 'dark', 'park']\n", + "['cart', 'dart', 'dark', 'dirk']\n", + "['cart', 'dart', 'dark', 'dork']\n", + "['cart', 'dart', 'dark', 'dank']\n", + "['cart', 'dart', 'dark', 'dare']\n", + "['cart', 'dart', 'dark', 'darn']\n", + "['cart', 'dart', 'darn', 'barn']\n", + "['cart', 'dart', 'darn', 'earn']\n", + "['cart', 'dart', 'darn', 'warn']\n", + "['cart', 'dart', 'darn', 'yarn']\n", + "['cart', 'dart', 'darn', 'damn']\n", + "['cart', 'dart', 'darn', 'dawn']\n", + "['cart', 'dart', 'darn', 'dare']\n", + "['cart', 'dart', 'darn', 'dark']\n", + "['cart', 'hart', 'dart', 'mart']\n", + "['cart', 'hart', 'dart', 'part']\n", + "['cart', 'hart', 'dart', 'tart']\n", + "['cart', 'hart', 'dart', 'wart']\n", + "['cart', 'hart', 'dart', 'dirt']\n", + "['cart', 'hart', 'dart', 'daft']\n", + "['cart', 'hart', 'dart', 'dare']\n", + "['cart', 'hart', 'dart', 'dark']\n", + "['cart', 'hart', 'dart', 'darn']\n", + "['cart', 'hart', 'mart', 'dart']\n", + "['cart', 'hart', 'mart', 'part']\n", + "['cart', 'hart', 'mart', 'tart']\n", + "['cart', 'hart', 'mart', 'wart']\n", + "['cart', 'hart', 'mart', 'malt']\n", + "['cart', 'hart', 'mart', 'mast']\n", + "['cart', 'hart', 'mart', 'matt']\n", + "['cart', 'hart', 'mart', 'mare']\n", + "['cart', 'hart', 'mart', 'mark']\n", + "['cart', 'hart', 'mart', 'mars']\n", + "['cart', 'hart', 'part', 'dart']\n", + "['cart', 'hart', 'part', 'mart']\n", + "['cart', 'hart', 'part', 'tart']\n", + "['cart', 'hart', 'part', 'wart']\n", + "['cart', 'hart', 'part', 'pert']\n", + "['cart', 'hart', 'part', 'port']\n", + "['cart', 'hart', 'part', 'pact']\n", + "['cart', 'hart', 'part', 'pant']\n", + "['cart', 'hart', 'part', 'past']\n", + "['cart', 'hart', 'part', 'pare']\n", + "['cart', 'hart', 'part', 'park']\n", + "['cart', 'hart', 'part', 'pars']\n", + "['cart', 'hart', 'tart', 'dart']\n", + "['cart', 'hart', 'tart', 'mart']\n", + "['cart', 'hart', 'tart', 'part']\n", + "['cart', 'hart', 'tart', 'wart']\n", + "['cart', 'hart', 'tart', 'tort']\n", + "['cart', 'hart', 'tart', 'tact']\n", + "['cart', 'hart', 'tart', 'taut']\n", + "['cart', 'hart', 'tart', 'tare']\n", + "['cart', 'hart', 'tart', 'taro']\n", + "['cart', 'hart', 'tart', 'tarp']\n", + "['cart', 'hart', 'tart', 'tars']\n", + "['cart', 'hart', 'wart', 'dart']\n", + "['cart', 'hart', 'wart', 'mart']\n", + "['cart', 'hart', 'wart', 'part']\n", + "['cart', 'hart', 'wart', 'tart']\n", + "['cart', 'hart', 'wart', 'waft']\n", + "['cart', 'hart', 'wart', 'wait']\n", + "['cart', 'hart', 'wart', 'want']\n", + "['cart', 'hart', 'wart', 'watt']\n", + "['cart', 'hart', 'wart', 'ward']\n", + "['cart', 'hart', 'wart', 'ware']\n", + "['cart', 'hart', 'wart', 'warm']\n", + "['cart', 'hart', 'wart', 'warn']\n", + "['cart', 'hart', 'wart', 'warp']\n", + "['cart', 'hart', 'wart', 'wars']\n", + "['cart', 'hart', 'wart', 'wary']\n", + "['cart', 'hart', 'hurt', 'curt']\n", + "['cart', 'hart', 'hurt', 'hunt']\n", + "['cart', 'hart', 'hurt', 'hurl']\n", + "['cart', 'hart', 'haft', 'daft']\n", + "['cart', 'hart', 'haft', 'raft']\n", + "['cart', 'hart', 'haft', 'waft']\n", + "['cart', 'hart', 'haft', 'heft']\n", + "['cart', 'hart', 'haft', 'halt']\n", + "['cart', 'hart', 'halt', 'malt']\n", + "['cart', 'hart', 'halt', 'salt']\n", + "['cart', 'hart', 'halt', 'hilt']\n", + "['cart', 'hart', 'halt', 'haft']\n", + "['cart', 'hart', 'halt', 'hale']\n", + "['cart', 'hart', 'halt', 'half']\n", + "['cart', 'hart', 'halt', 'hall']\n", + "['cart', 'hart', 'halt', 'halo']\n", + "['cart', 'hart', 'hard', 'bard']\n", + "['cart', 'hart', 'hard', 'card']\n", + "['cart', 'hart', 'hard', 'lard']\n", + "['cart', 'hart', 'hard', 'ward']\n", + "['cart', 'hart', 'hard', 'yard']\n", + "['cart', 'hart', 'hard', 'herd']\n", + "['cart', 'hart', 'hard', 'hand']\n", + "['cart', 'hart', 'hard', 'hare']\n", + "['cart', 'hart', 'hard', 'hark']\n", + "['cart', 'hart', 'hard', 'harm']\n", + "['cart', 'hart', 'hard', 'harp']\n", + "['cart', 'hart', 'hare', 'bare']\n", + "['cart', 'hart', 'hare', 'care']\n", + "['cart', 'hart', 'hare', 'dare']\n", + "['cart', 'hart', 'hare', 'fare']\n", + "['cart', 'hart', 'hare', 'mare']\n", + "['cart', 'hart', 'hare', 'pare']\n", + "['cart', 'hart', 'hare', 'rare']\n", + "['cart', 'hart', 'hare', 'tare']\n", + "['cart', 'hart', 'hare', 'ware']\n", + "['cart', 'hart', 'hare', 'here']\n", + "['cart', 'hart', 'hare', 'hire']\n", + "['cart', 'hart', 'hare', 'hake']\n", + "['cart', 'hart', 'hare', 'hale']\n", + "['cart', 'hart', 'hare', 'hate']\n", + "['cart', 'hart', 'hare', 'have']\n", + "['cart', 'hart', 'hare', 'haze']\n", + "['cart', 'hart', 'hare', 'hard']\n", + "['cart', 'hart', 'hare', 'hark']\n", + "['cart', 'hart', 'hare', 'harm']\n", + "['cart', 'hart', 'hare', 'harp']\n", + "['cart', 'hart', 'hark', 'bark']\n", + "['cart', 'hart', 'hark', 'dark']\n", + "['cart', 'hart', 'hark', 'lark']\n", + "['cart', 'hart', 'hark', 'mark']\n", + "['cart', 'hart', 'hark', 'nark']\n", + "['cart', 'hart', 'hark', 'park']\n", + "['cart', 'hart', 'hark', 'hack']\n", + "['cart', 'hart', 'hark', 'hank']\n", + "['cart', 'hart', 'hark', 'hawk']\n", + "['cart', 'hart', 'hark', 'hard']\n", + "['cart', 'hart', 'hark', 'hare']\n", + "['cart', 'hart', 'hark', 'harm']\n", + "['cart', 'hart', 'hark', 'harp']\n", + "['cart', 'hart', 'harm', 'farm']\n", + "['cart', 'hart', 'harm', 'warm']\n", + "['cart', 'hart', 'harm', 'hard']\n", + "['cart', 'hart', 'harm', 'hare']\n", + "['cart', 'hart', 'harm', 'hark']\n", + "['cart', 'hart', 'harm', 'harp']\n", + "['cart', 'hart', 'harp', 'carp']\n", + "['cart', 'hart', 'harp', 'tarp']\n", + "['cart', 'hart', 'harp', 'warp']\n", + "['cart', 'hart', 'harp', 'hasp']\n", + "['cart', 'hart', 'harp', 'hard']\n", + "['cart', 'hart', 'harp', 'hare']\n", + "['cart', 'hart', 'harp', 'hark']\n", + "['cart', 'hart', 'harp', 'harm']\n", + "['cart', 'mart', 'dart', 'hart']\n", + "['cart', 'mart', 'dart', 'part']\n", + "['cart', 'mart', 'dart', 'tart']\n", + "['cart', 'mart', 'dart', 'wart']\n", + "['cart', 'mart', 'dart', 'dirt']\n", + "['cart', 'mart', 'dart', 'daft']\n", + "['cart', 'mart', 'dart', 'dare']\n", + "['cart', 'mart', 'dart', 'dark']\n", + "['cart', 'mart', 'dart', 'darn']\n", + "['cart', 'mart', 'hart', 'dart']\n", + "['cart', 'mart', 'hart', 'part']\n", + "['cart', 'mart', 'hart', 'tart']\n", + "['cart', 'mart', 'hart', 'wart']\n", + "['cart', 'mart', 'hart', 'hurt']\n", + "['cart', 'mart', 'hart', 'haft']\n", + "['cart', 'mart', 'hart', 'halt']\n", + "['cart', 'mart', 'hart', 'hard']\n", + "['cart', 'mart', 'hart', 'hare']\n", + "['cart', 'mart', 'hart', 'hark']\n", + "['cart', 'mart', 'hart', 'harm']\n", + "['cart', 'mart', 'hart', 'harp']\n", + "['cart', 'mart', 'part', 'dart']\n", + "['cart', 'mart', 'part', 'hart']\n", + "['cart', 'mart', 'part', 'tart']\n", + "['cart', 'mart', 'part', 'wart']\n", + "['cart', 'mart', 'part', 'pert']\n", + "['cart', 'mart', 'part', 'port']\n", + "['cart', 'mart', 'part', 'pact']\n", + "['cart', 'mart', 'part', 'pant']\n", + "['cart', 'mart', 'part', 'past']\n", + "['cart', 'mart', 'part', 'pare']\n", + "['cart', 'mart', 'part', 'park']\n", + "['cart', 'mart', 'part', 'pars']\n", + "['cart', 'mart', 'tart', 'dart']\n", + "['cart', 'mart', 'tart', 'hart']\n", + "['cart', 'mart', 'tart', 'part']\n", + "['cart', 'mart', 'tart', 'wart']\n", + "['cart', 'mart', 'tart', 'tort']\n", + "['cart', 'mart', 'tart', 'tact']\n", + "['cart', 'mart', 'tart', 'taut']\n" + ] + }, + { + "name": "stdout", + "output_type": "stream", + "text": [ + "['cart', 'mart', 'tart', 'tare']\n", + "['cart', 'mart', 'tart', 'taro']\n", + "['cart', 'mart', 'tart', 'tarp']\n", + "['cart', 'mart', 'tart', 'tars']\n", + "['cart', 'mart', 'wart', 'dart']\n", + "['cart', 'mart', 'wart', 'hart']\n", + "['cart', 'mart', 'wart', 'part']\n", + "['cart', 'mart', 'wart', 'tart']\n", + "['cart', 'mart', 'wart', 'waft']\n", + "['cart', 'mart', 'wart', 'wait']\n", + "['cart', 'mart', 'wart', 'want']\n", + "['cart', 'mart', 'wart', 'watt']\n", + "['cart', 'mart', 'wart', 'ward']\n", + "['cart', 'mart', 'wart', 'ware']\n", + "['cart', 'mart', 'wart', 'warm']\n", + "['cart', 'mart', 'wart', 'warn']\n", + "['cart', 'mart', 'wart', 'warp']\n", + "['cart', 'mart', 'wart', 'wars']\n", + "['cart', 'mart', 'wart', 'wary']\n", + "['cart', 'mart', 'malt', 'halt']\n", + "['cart', 'mart', 'malt', 'salt']\n", + "['cart', 'mart', 'malt', 'melt']\n", + "['cart', 'mart', 'malt', 'mast']\n", + "['cart', 'mart', 'malt', 'matt']\n", + "['cart', 'mart', 'malt', 'male']\n", + "['cart', 'mart', 'malt', 'mall']\n", + "['cart', 'mart', 'mast', 'bast']\n", + "['cart', 'mart', 'mast', 'cast']\n", + "['cart', 'mart', 'mast', 'east']\n", + "['cart', 'mart', 'mast', 'fast']\n", + "['cart', 'mart', 'mast', 'last']\n", + "['cart', 'mart', 'mast', 'past']\n", + "['cart', 'mart', 'mast', 'vast']\n", + "['cart', 'mart', 'mast', 'mist']\n", + "['cart', 'mart', 'mast', 'most']\n", + "['cart', 'mart', 'mast', 'must']\n", + "['cart', 'mart', 'mast', 'malt']\n", + "['cart', 'mart', 'mast', 'matt']\n", + "['cart', 'mart', 'mast', 'mash']\n", + "['cart', 'mart', 'mast', 'mask']\n", + "['cart', 'mart', 'mast', 'mass']\n", + "['cart', 'mart', 'matt', 'watt']\n", + "['cart', 'mart', 'matt', 'mitt']\n", + "['cart', 'mart', 'matt', 'mutt']\n", + "['cart', 'mart', 'matt', 'malt']\n", + "['cart', 'mart', 'matt', 'mast']\n", + "['cart', 'mart', 'matt', 'mate']\n", + "['cart', 'mart', 'matt', 'math']\n", + "['cart', 'mart', 'matt', 'mats']\n", + "['cart', 'mart', 'mare', 'bare']\n", + "['cart', 'mart', 'mare', 'care']\n", + "['cart', 'mart', 'mare', 'dare']\n", + "['cart', 'mart', 'mare', 'fare']\n", + "['cart', 'mart', 'mare', 'hare']\n", + "['cart', 'mart', 'mare', 'pare']\n", + "['cart', 'mart', 'mare', 'rare']\n", + "['cart', 'mart', 'mare', 'tare']\n", + "['cart', 'mart', 'mare', 'ware']\n", + "['cart', 'mart', 'mare', 'mere']\n", + "['cart', 'mart', 'mare', 'mire']\n", + "['cart', 'mart', 'mare', 'more']\n", + "['cart', 'mart', 'mare', 'mace']\n", + "['cart', 'mart', 'mare', 'made']\n", + "['cart', 'mart', 'mare', 'make']\n", + "['cart', 'mart', 'mare', 'male']\n", + "['cart', 'mart', 'mare', 'mane']\n", + "['cart', 'mart', 'mare', 'mate']\n", + "['cart', 'mart', 'mare', 'maze']\n", + "['cart', 'mart', 'mare', 'mark']\n", + "['cart', 'mart', 'mare', 'mars']\n", + "['cart', 'mart', 'mark', 'bark']\n", + "['cart', 'mart', 'mark', 'dark']\n", + "['cart', 'mart', 'mark', 'hark']\n", + "['cart', 'mart', 'mark', 'lark']\n", + "['cart', 'mart', 'mark', 'nark']\n", + "['cart', 'mart', 'mark', 'park']\n", + "['cart', 'mart', 'mark', 'murk']\n", + "['cart', 'mart', 'mark', 'mask']\n", + "['cart', 'mart', 'mark', 'mare']\n", + "['cart', 'mart', 'mark', 'mars']\n", + "['cart', 'mart', 'mars', 'bars']\n", + "['cart', 'mart', 'mars', 'cars']\n", + "['cart', 'mart', 'mars', 'ears']\n", + "['cart', 'mart', 'mars', 'jars']\n", + "['cart', 'mart', 'mars', 'oars']\n", + "['cart', 'mart', 'mars', 'pars']\n", + "['cart', 'mart', 'mars', 'tars']\n", + "['cart', 'mart', 'mars', 'wars']\n", + "['cart', 'mart', 'mars', 'mads']\n", + "['cart', 'mart', 'mars', 'mans']\n", + "['cart', 'mart', 'mars', 'maps']\n", + "['cart', 'mart', 'mars', 'mass']\n", + "['cart', 'mart', 'mars', 'mats']\n", + "['cart', 'mart', 'mars', 'maws']\n", + "['cart', 'mart', 'mars', 'mare']\n", + "['cart', 'mart', 'mars', 'mark']\n", + "['cart', 'part', 'dart', 'hart']\n", + "['cart', 'part', 'dart', 'mart']\n", + "['cart', 'part', 'dart', 'tart']\n", + "['cart', 'part', 'dart', 'wart']\n", + "['cart', 'part', 'dart', 'dirt']\n", + "['cart', 'part', 'dart', 'daft']\n", + "['cart', 'part', 'dart', 'dare']\n", + "['cart', 'part', 'dart', 'dark']\n", + "['cart', 'part', 'dart', 'darn']\n", + "['cart', 'part', 'hart', 'dart']\n", + "['cart', 'part', 'hart', 'mart']\n", + "['cart', 'part', 'hart', 'tart']\n", + "['cart', 'part', 'hart', 'wart']\n", + "['cart', 'part', 'hart', 'hurt']\n", + "['cart', 'part', 'hart', 'haft']\n", + "['cart', 'part', 'hart', 'halt']\n", + "['cart', 'part', 'hart', 'hard']\n", + "['cart', 'part', 'hart', 'hare']\n", + "['cart', 'part', 'hart', 'hark']\n", + "['cart', 'part', 'hart', 'harm']\n", + "['cart', 'part', 'hart', 'harp']\n", + "['cart', 'part', 'mart', 'dart']\n", + "['cart', 'part', 'mart', 'hart']\n", + "['cart', 'part', 'mart', 'tart']\n", + "['cart', 'part', 'mart', 'wart']\n", + "['cart', 'part', 'mart', 'malt']\n", + "['cart', 'part', 'mart', 'mast']\n", + "['cart', 'part', 'mart', 'matt']\n", + "['cart', 'part', 'mart', 'mare']\n", + "['cart', 'part', 'mart', 'mark']\n", + "['cart', 'part', 'mart', 'mars']\n", + "['cart', 'part', 'tart', 'dart']\n", + "['cart', 'part', 'tart', 'hart']\n", + "['cart', 'part', 'tart', 'mart']\n", + "['cart', 'part', 'tart', 'wart']\n", + "['cart', 'part', 'tart', 'tort']\n", + "['cart', 'part', 'tart', 'tact']\n", + "['cart', 'part', 'tart', 'taut']\n", + "['cart', 'part', 'tart', 'tare']\n", + "['cart', 'part', 'tart', 'taro']\n", + "['cart', 'part', 'tart', 'tarp']\n", + "['cart', 'part', 'tart', 'tars']\n", + "['cart', 'part', 'wart', 'dart']\n", + "['cart', 'part', 'wart', 'hart']\n", + "['cart', 'part', 'wart', 'mart']\n", + "['cart', 'part', 'wart', 'tart']\n", + "['cart', 'part', 'wart', 'waft']\n", + "['cart', 'part', 'wart', 'wait']\n", + "['cart', 'part', 'wart', 'want']\n", + "['cart', 'part', 'wart', 'watt']\n", + "['cart', 'part', 'wart', 'ward']\n", + "['cart', 'part', 'wart', 'ware']\n", + "['cart', 'part', 'wart', 'warm']\n", + "['cart', 'part', 'wart', 'warn']\n", + "['cart', 'part', 'wart', 'warp']\n", + "['cart', 'part', 'wart', 'wars']\n", + "['cart', 'part', 'wart', 'wary']\n", + "['cart', 'part', 'pert', 'port']\n", + "['cart', 'part', 'pert', 'peat']\n", + "['cart', 'part', 'pert', 'pelt']\n", + "['cart', 'part', 'pert', 'pent']\n", + "['cart', 'part', 'pert', 'pest']\n", + "['cart', 'part', 'pert', 'perk']\n", + "['cart', 'part', 'pert', 'perm']\n", + "['cart', 'part', 'port', 'fort']\n", + "['cart', 'part', 'port', 'sort']\n", + "['cart', 'part', 'port', 'tort']\n", + "['cart', 'part', 'port', 'pert']\n", + "['cart', 'part', 'port', 'poet']\n", + "['cart', 'part', 'port', 'post']\n", + "['cart', 'part', 'port', 'pout']\n", + "['cart', 'part', 'port', 'pore']\n", + "['cart', 'part', 'port', 'pork']\n", + "['cart', 'part', 'port', 'porn']\n", + "['cart', 'part', 'pact', 'fact']\n", + "['cart', 'part', 'pact', 'tact']\n", + "['cart', 'part', 'pact', 'pant']\n", + "['cart', 'part', 'pact', 'past']\n", + "['cart', 'part', 'pact', 'pace']\n", + "['cart', 'part', 'pact', 'pack']\n", + "['cart', 'part', 'pant', 'cant']\n", + "['cart', 'part', 'pant', 'rant']\n", + "['cart', 'part', 'pant', 'want']\n", + "['cart', 'part', 'pant', 'pent']\n", + "['cart', 'part', 'pant', 'pint']\n", + "['cart', 'part', 'pant', 'punt']\n", + "['cart', 'part', 'pant', 'pact']\n", + "['cart', 'part', 'pant', 'past']\n", + "['cart', 'part', 'pant', 'pane']\n", + "['cart', 'part', 'pant', 'pang']\n", + "['cart', 'part', 'pant', 'pans']\n", + "['cart', 'part', 'past', 'bast']\n", + "['cart', 'part', 'past', 'cast']\n", + "['cart', 'part', 'past', 'east']\n", + "['cart', 'part', 'past', 'fast']\n", + "['cart', 'part', 'past', 'last']\n", + "['cart', 'part', 'past', 'mast']\n", + "['cart', 'part', 'past', 'vast']\n", + "['cart', 'part', 'past', 'pest']\n", + "['cart', 'part', 'past', 'post']\n", + "['cart', 'part', 'past', 'psst']\n", + "['cart', 'part', 'past', 'pact']\n", + "['cart', 'part', 'past', 'pant']\n", + "['cart', 'part', 'past', 'pass']\n", + "['cart', 'part', 'pare', 'bare']\n", + "['cart', 'part', 'pare', 'care']\n", + "['cart', 'part', 'pare', 'dare']\n", + "['cart', 'part', 'pare', 'fare']\n", + "['cart', 'part', 'pare', 'hare']\n", + "['cart', 'part', 'pare', 'mare']\n", + "['cart', 'part', 'pare', 'rare']\n", + "['cart', 'part', 'pare', 'tare']\n", + "['cart', 'part', 'pare', 'ware']\n", + "['cart', 'part', 'pare', 'pore']\n", + "['cart', 'part', 'pare', 'pure']\n", + "['cart', 'part', 'pare', 'pyre']\n", + "['cart', 'part', 'pare', 'pace']\n", + "['cart', 'part', 'pare', 'page']\n", + "['cart', 'part', 'pare', 'pale']\n", + "['cart', 'part', 'pare', 'pane']\n", + "['cart', 'part', 'pare', 'pate']\n", + "['cart', 'part', 'pare', 'pave']\n", + "['cart', 'part', 'pare', 'park']\n", + "['cart', 'part', 'pare', 'pars']\n", + "['cart', 'part', 'park', 'bark']\n", + "['cart', 'part', 'park', 'dark']\n", + "['cart', 'part', 'park', 'hark']\n", + "['cart', 'part', 'park', 'lark']\n", + "['cart', 'part', 'park', 'mark']\n", + "['cart', 'part', 'park', 'nark']\n", + "['cart', 'part', 'park', 'perk']\n", + "['cart', 'part', 'park', 'pork']\n", + "['cart', 'part', 'park', 'pack']\n", + "['cart', 'part', 'park', 'pare']\n", + "['cart', 'part', 'park', 'pars']\n", + "['cart', 'part', 'pars', 'bars']\n", + "['cart', 'part', 'pars', 'cars']\n", + "['cart', 'part', 'pars', 'ears']\n", + "['cart', 'part', 'pars', 'jars']\n", + "['cart', 'part', 'pars', 'mars']\n", + "['cart', 'part', 'pars', 'oars']\n", + "['cart', 'part', 'pars', 'tars']\n", + "['cart', 'part', 'pars', 'wars']\n", + "['cart', 'part', 'pars', 'pads']\n", + "['cart', 'part', 'pars', 'pals']\n", + "['cart', 'part', 'pars', 'pans']\n", + "['cart', 'part', 'pars', 'paps']\n", + "['cart', 'part', 'pars', 'pass']\n", + "['cart', 'part', 'pars', 'pats']\n", + "['cart', 'part', 'pars', 'paws']\n", + "['cart', 'part', 'pars', 'pays']\n", + "['cart', 'part', 'pars', 'pare']\n", + "['cart', 'part', 'pars', 'park']\n", + "['cart', 'tart', 'dart', 'hart']\n", + "['cart', 'tart', 'dart', 'mart']\n", + "['cart', 'tart', 'dart', 'part']\n", + "['cart', 'tart', 'dart', 'wart']\n", + "['cart', 'tart', 'dart', 'dirt']\n", + "['cart', 'tart', 'dart', 'daft']\n", + "['cart', 'tart', 'dart', 'dare']\n", + "['cart', 'tart', 'dart', 'dark']\n", + "['cart', 'tart', 'dart', 'darn']\n", + "['cart', 'tart', 'hart', 'dart']\n", + "['cart', 'tart', 'hart', 'mart']\n", + "['cart', 'tart', 'hart', 'part']\n", + "['cart', 'tart', 'hart', 'wart']\n", + "['cart', 'tart', 'hart', 'hurt']\n", + "['cart', 'tart', 'hart', 'haft']\n", + "['cart', 'tart', 'hart', 'halt']\n", + "['cart', 'tart', 'hart', 'hard']\n", + "['cart', 'tart', 'hart', 'hare']\n", + "['cart', 'tart', 'hart', 'hark']\n", + "['cart', 'tart', 'hart', 'harm']\n", + "['cart', 'tart', 'hart', 'harp']\n", + "['cart', 'tart', 'mart', 'dart']\n", + "['cart', 'tart', 'mart', 'hart']\n", + "['cart', 'tart', 'mart', 'part']\n", + "['cart', 'tart', 'mart', 'wart']\n", + "['cart', 'tart', 'mart', 'malt']\n", + "['cart', 'tart', 'mart', 'mast']\n", + "['cart', 'tart', 'mart', 'matt']\n", + "['cart', 'tart', 'mart', 'mare']\n", + "['cart', 'tart', 'mart', 'mark']\n", + "['cart', 'tart', 'mart', 'mars']\n", + "['cart', 'tart', 'part', 'dart']\n", + "['cart', 'tart', 'part', 'hart']\n", + "['cart', 'tart', 'part', 'mart']\n", + "['cart', 'tart', 'part', 'wart']\n", + "['cart', 'tart', 'part', 'pert']\n", + "['cart', 'tart', 'part', 'port']\n", + "['cart', 'tart', 'part', 'pact']\n", + "['cart', 'tart', 'part', 'pant']\n", + "['cart', 'tart', 'part', 'past']\n", + "['cart', 'tart', 'part', 'pare']\n", + "['cart', 'tart', 'part', 'park']\n", + "['cart', 'tart', 'part', 'pars']\n", + "['cart', 'tart', 'wart', 'dart']\n", + "['cart', 'tart', 'wart', 'hart']\n", + "['cart', 'tart', 'wart', 'mart']\n", + "['cart', 'tart', 'wart', 'part']\n", + "['cart', 'tart', 'wart', 'waft']\n", + "['cart', 'tart', 'wart', 'wait']\n", + "['cart', 'tart', 'wart', 'want']\n", + "['cart', 'tart', 'wart', 'watt']\n", + "['cart', 'tart', 'wart', 'ward']\n", + "['cart', 'tart', 'wart', 'ware']\n", + "['cart', 'tart', 'wart', 'warm']\n", + "['cart', 'tart', 'wart', 'warn']\n", + "['cart', 'tart', 'wart', 'warp']\n", + "['cart', 'tart', 'wart', 'wars']\n", + "['cart', 'tart', 'wart', 'wary']\n", + "['cart', 'tart', 'tort', 'fort']\n", + "['cart', 'tart', 'tort', 'port']\n", + "['cart', 'tart', 'tort', 'sort']\n", + "['cart', 'tart', 'tort', 'toot']\n", + "['cart', 'tart', 'tort', 'tost']\n", + "['cart', 'tart', 'tort', 'tout']\n", + "['cart', 'tart', 'tort', 'tore']\n", + "['cart', 'tart', 'tort', 'torn']\n", + "['cart', 'tart', 'tort', 'tors']\n", + "['cart', 'tart', 'tact', 'fact']\n", + "['cart', 'tart', 'tact', 'pact']\n", + "['cart', 'tart', 'tact', 'taut']\n", + "['cart', 'tart', 'tact', 'tack']\n", + "['cart', 'tart', 'tact', 'taco']\n", + "['cart', 'tart', 'taut', 'tout']\n", + "['cart', 'tart', 'taut', 'tact']\n", + "['cart', 'tart', 'tare', 'bare']\n", + "['cart', 'tart', 'tare', 'care']\n", + "['cart', 'tart', 'tare', 'dare']\n", + "['cart', 'tart', 'tare', 'fare']\n", + "['cart', 'tart', 'tare', 'hare']\n", + "['cart', 'tart', 'tare', 'mare']\n", + "['cart', 'tart', 'tare', 'pare']\n", + "['cart', 'tart', 'tare', 'rare']\n", + "['cart', 'tart', 'tare', 'ware']\n", + "['cart', 'tart', 'tare', 'tire']\n", + "['cart', 'tart', 'tare', 'tore']\n", + "['cart', 'tart', 'tare', 'tyre']\n", + "['cart', 'tart', 'tare', 'take']\n", + "['cart', 'tart', 'tare', 'tale']\n", + "['cart', 'tart', 'tare', 'tame']\n", + "['cart', 'tart', 'tare', 'tape']\n", + "['cart', 'tart', 'tare', 'taro']\n", + "['cart', 'tart', 'tare', 'tarp']\n", + "['cart', 'tart', 'tare', 'tars']\n", + "['cart', 'tart', 'taro', 'tiro']\n", + "['cart', 'tart', 'taro', 'tyro']\n", + "['cart', 'tart', 'taro', 'taco']\n", + "['cart', 'tart', 'taro', 'tare']\n", + "['cart', 'tart', 'taro', 'tarp']\n", + "['cart', 'tart', 'taro', 'tars']\n", + "['cart', 'tart', 'tarp', 'carp']\n", + "['cart', 'tart', 'tarp', 'harp']\n", + "['cart', 'tart', 'tarp', 'warp']\n", + "['cart', 'tart', 'tarp', 'tamp']\n", + "['cart', 'tart', 'tarp', 'tare']\n", + "['cart', 'tart', 'tarp', 'taro']\n", + "['cart', 'tart', 'tarp', 'tars']\n", + "['cart', 'tart', 'tars', 'bars']\n", + "['cart', 'tart', 'tars', 'cars']\n", + "['cart', 'tart', 'tars', 'ears']\n", + "['cart', 'tart', 'tars', 'jars']\n", + "['cart', 'tart', 'tars', 'mars']\n", + "['cart', 'tart', 'tars', 'oars']\n", + "['cart', 'tart', 'tars', 'pars']\n", + "['cart', 'tart', 'tars', 'wars']\n", + "['cart', 'tart', 'tars', 'tors']\n", + "['cart', 'tart', 'tars', 'tabs']\n", + "['cart', 'tart', 'tars', 'tads']\n", + "['cart', 'tart', 'tars', 'tags']\n", + "['cart', 'tart', 'tars', 'tams']\n", + "['cart', 'tart', 'tars', 'tans']\n", + "['cart', 'tart', 'tars', 'taps']\n", + "['cart', 'tart', 'tars', 'tats']\n", + "['cart', 'tart', 'tars', 'tare']\n", + "['cart', 'tart', 'tars', 'taro']\n", + "['cart', 'tart', 'tars', 'tarp']\n", + "['cart', 'wart', 'dart', 'hart']\n", + "['cart', 'wart', 'dart', 'mart']\n", + "['cart', 'wart', 'dart', 'part']\n", + "['cart', 'wart', 'dart', 'tart']\n", + "['cart', 'wart', 'dart', 'dirt']\n", + "['cart', 'wart', 'dart', 'daft']\n", + "['cart', 'wart', 'dart', 'dare']\n", + "['cart', 'wart', 'dart', 'dark']\n", + "['cart', 'wart', 'dart', 'darn']\n", + "['cart', 'wart', 'hart', 'dart']\n", + "['cart', 'wart', 'hart', 'mart']\n", + "['cart', 'wart', 'hart', 'part']\n", + "['cart', 'wart', 'hart', 'tart']\n", + "['cart', 'wart', 'hart', 'hurt']\n", + "['cart', 'wart', 'hart', 'haft']\n", + "['cart', 'wart', 'hart', 'halt']\n", + "['cart', 'wart', 'hart', 'hard']\n", + "['cart', 'wart', 'hart', 'hare']\n", + "['cart', 'wart', 'hart', 'hark']\n", + "['cart', 'wart', 'hart', 'harm']\n", + "['cart', 'wart', 'hart', 'harp']\n", + "['cart', 'wart', 'mart', 'dart']\n", + "['cart', 'wart', 'mart', 'hart']\n", + "['cart', 'wart', 'mart', 'part']\n", + "['cart', 'wart', 'mart', 'tart']\n", + "['cart', 'wart', 'mart', 'malt']\n", + "['cart', 'wart', 'mart', 'mast']\n", + "['cart', 'wart', 'mart', 'matt']\n", + "['cart', 'wart', 'mart', 'mare']\n", + "['cart', 'wart', 'mart', 'mark']\n", + "['cart', 'wart', 'mart', 'mars']\n", + "['cart', 'wart', 'part', 'dart']\n", + "['cart', 'wart', 'part', 'hart']\n", + "['cart', 'wart', 'part', 'mart']\n", + "['cart', 'wart', 'part', 'tart']\n", + "['cart', 'wart', 'part', 'pert']\n", + "['cart', 'wart', 'part', 'port']\n", + "['cart', 'wart', 'part', 'pact']\n", + "['cart', 'wart', 'part', 'pant']\n", + "['cart', 'wart', 'part', 'past']\n", + "['cart', 'wart', 'part', 'pare']\n", + "['cart', 'wart', 'part', 'park']\n", + "['cart', 'wart', 'part', 'pars']\n", + "['cart', 'wart', 'tart', 'dart']\n", + "['cart', 'wart', 'tart', 'hart']\n", + "['cart', 'wart', 'tart', 'mart']\n", + "['cart', 'wart', 'tart', 'part']\n", + "['cart', 'wart', 'tart', 'tort']\n", + "['cart', 'wart', 'tart', 'tact']\n", + "['cart', 'wart', 'tart', 'taut']\n", + "['cart', 'wart', 'tart', 'tare']\n", + "['cart', 'wart', 'tart', 'taro']\n", + "['cart', 'wart', 'tart', 'tarp']\n", + "['cart', 'wart', 'tart', 'tars']\n", + "['cart', 'wart', 'waft', 'daft']\n", + "['cart', 'wart', 'waft', 'haft']\n", + "['cart', 'wart', 'waft', 'raft']\n", + "['cart', 'wart', 'waft', 'weft']\n", + "['cart', 'wart', 'waft', 'wait']\n", + "['cart', 'wart', 'waft', 'want']\n", + "['cart', 'wart', 'waft', 'watt']\n", + "['cart', 'wart', 'wait', 'bait']\n", + "['cart', 'wart', 'wait', 'gait']\n", + "['cart', 'wart', 'wait', 'whit']\n", + "['cart', 'wart', 'wait', 'writ']\n", + "['cart', 'wart', 'wait', 'waft']\n", + "['cart', 'wart', 'wait', 'want']\n", + "['cart', 'wart', 'wait', 'watt']\n", + "['cart', 'wart', 'wait', 'waif']\n", + "['cart', 'wart', 'wait', 'wail']\n", + "['cart', 'wart', 'want', 'cant']\n", + "['cart', 'wart', 'want', 'pant']\n", + "['cart', 'wart', 'want', 'rant']\n", + "['cart', 'wart', 'want', 'went']\n", + "['cart', 'wart', 'want', 'wont']\n", + "['cart', 'wart', 'want', 'waft']\n", + "['cart', 'wart', 'want', 'wait']\n", + "['cart', 'wart', 'want', 'watt']\n", + "['cart', 'wart', 'want', 'wand']\n", + "['cart', 'wart', 'want', 'wane']\n", + "['cart', 'wart', 'watt', 'matt']\n", + "['cart', 'wart', 'watt', 'waft']\n", + "['cart', 'wart', 'watt', 'wait']\n", + "['cart', 'wart', 'watt', 'want']\n", + "['cart', 'wart', 'ward', 'bard']\n", + "['cart', 'wart', 'ward', 'card']\n", + "['cart', 'wart', 'ward', 'hard']\n", + "['cart', 'wart', 'ward', 'lard']\n", + "['cart', 'wart', 'ward', 'yard']\n", + "['cart', 'wart', 'ward', 'word']\n", + "['cart', 'wart', 'ward', 'wand']\n", + "['cart', 'wart', 'ward', 'ware']\n", + "['cart', 'wart', 'ward', 'warm']\n", + "['cart', 'wart', 'ward', 'warn']\n", + "['cart', 'wart', 'ward', 'warp']\n", + "['cart', 'wart', 'ward', 'wars']\n", + "['cart', 'wart', 'ward', 'wary']\n", + "['cart', 'wart', 'ware', 'bare']\n", + "['cart', 'wart', 'ware', 'care']\n", + "['cart', 'wart', 'ware', 'dare']\n", + "['cart', 'wart', 'ware', 'fare']\n", + "['cart', 'wart', 'ware', 'hare']\n", + "['cart', 'wart', 'ware', 'mare']\n", + "['cart', 'wart', 'ware', 'pare']\n", + "['cart', 'wart', 'ware', 'rare']\n", + "['cart', 'wart', 'ware', 'tare']\n", + "['cart', 'wart', 'ware', 'were']\n", + "['cart', 'wart', 'ware', 'wire']\n", + "['cart', 'wart', 'ware', 'wore']\n", + "['cart', 'wart', 'ware', 'wade']\n", + "['cart', 'wart', 'ware', 'wage']\n" + ] + }, + { + "name": "stdout", + "output_type": "stream", + "text": [ + "['cart', 'wart', 'ware', 'wake']\n", + "['cart', 'wart', 'ware', 'wale']\n", + "['cart', 'wart', 'ware', 'wane']\n", + "['cart', 'wart', 'ware', 'wave']\n", + "['cart', 'wart', 'ware', 'ward']\n", + "['cart', 'wart', 'ware', 'warm']\n", + "['cart', 'wart', 'ware', 'warn']\n", + "['cart', 'wart', 'ware', 'warp']\n", + "['cart', 'wart', 'ware', 'wars']\n", + "['cart', 'wart', 'ware', 'wary']\n", + "['cart', 'wart', 'warm', 'farm']\n", + "['cart', 'wart', 'warm', 'harm']\n", + "['cart', 'wart', 'warm', 'worm']\n", + "['cart', 'wart', 'warm', 'ward']\n", + "['cart', 'wart', 'warm', 'ware']\n", + "['cart', 'wart', 'warm', 'warn']\n", + "['cart', 'wart', 'warm', 'warp']\n", + "['cart', 'wart', 'warm', 'wars']\n", + "['cart', 'wart', 'warm', 'wary']\n", + "['cart', 'wart', 'warn', 'barn']\n", + "['cart', 'wart', 'warn', 'darn']\n", + "['cart', 'wart', 'warn', 'earn']\n", + "['cart', 'wart', 'warn', 'yarn']\n", + "['cart', 'wart', 'warn', 'worn']\n", + "['cart', 'wart', 'warn', 'ward']\n", + "['cart', 'wart', 'warn', 'ware']\n", + "['cart', 'wart', 'warn', 'warm']\n", + "['cart', 'wart', 'warn', 'warp']\n", + "['cart', 'wart', 'warn', 'wars']\n", + "['cart', 'wart', 'warn', 'wary']\n", + "['cart', 'wart', 'warp', 'carp']\n", + "['cart', 'wart', 'warp', 'harp']\n", + "['cart', 'wart', 'warp', 'tarp']\n", + "['cart', 'wart', 'warp', 'wasp']\n", + "['cart', 'wart', 'warp', 'ward']\n", + "['cart', 'wart', 'warp', 'ware']\n", + "['cart', 'wart', 'warp', 'warm']\n", + "['cart', 'wart', 'warp', 'warn']\n", + "['cart', 'wart', 'warp', 'wars']\n", + "['cart', 'wart', 'warp', 'wary']\n", + "['cart', 'wart', 'wars', 'bars']\n", + "['cart', 'wart', 'wars', 'cars']\n", + "['cart', 'wart', 'wars', 'ears']\n", + "['cart', 'wart', 'wars', 'jars']\n", + "['cart', 'wart', 'wars', 'mars']\n", + "['cart', 'wart', 'wars', 'oars']\n", + "['cart', 'wart', 'wars', 'pars']\n", + "['cart', 'wart', 'wars', 'tars']\n", + "['cart', 'wart', 'wars', 'wads']\n", + "['cart', 'wart', 'wars', 'wags']\n", + "['cart', 'wart', 'wars', 'ways']\n", + "['cart', 'wart', 'wars', 'ward']\n", + "['cart', 'wart', 'wars', 'ware']\n", + "['cart', 'wart', 'wars', 'warm']\n", + "['cart', 'wart', 'wars', 'warn']\n", + "['cart', 'wart', 'wars', 'warp']\n", + "['cart', 'wart', 'wars', 'wary']\n", + "['cart', 'wart', 'wary', 'nary']\n", + "['cart', 'wart', 'wary', 'vary']\n", + "['cart', 'wart', 'wary', 'wiry']\n", + "['cart', 'wart', 'wary', 'wavy']\n", + "['cart', 'wart', 'wary', 'waxy']\n", + "['cart', 'wart', 'wary', 'ward']\n", + "['cart', 'wart', 'wary', 'ware']\n", + "['cart', 'wart', 'wary', 'warm']\n", + "['cart', 'wart', 'wary', 'warn']\n", + "['cart', 'wart', 'wary', 'warp']\n", + "['cart', 'wart', 'wary', 'wars']\n", + "['cart', 'curt', 'hurt', 'hart']\n", + "['cart', 'curt', 'hurt', 'hunt']\n", + "['cart', 'curt', 'hurt', 'hurl']\n", + "['cart', 'curt', 'cult', 'colt']\n", + "['cart', 'curt', 'cult', 'cull']\n", + "['cart', 'curt', 'curb', 'curd']\n", + "['cart', 'curt', 'curb', 'cure']\n", + "['cart', 'curt', 'curb', 'curl']\n", + "['cart', 'curt', 'curb', 'curs']\n", + "['cart', 'curt', 'curd', 'turd']\n", + "['cart', 'curt', 'curd', 'card']\n", + "['cart', 'curt', 'curd', 'cord']\n", + "['cart', 'curt', 'curd', 'cued']\n", + "['cart', 'curt', 'curd', 'curb']\n", + "['cart', 'curt', 'curd', 'cure']\n", + "['cart', 'curt', 'curd', 'curl']\n", + "['cart', 'curt', 'curd', 'curs']\n", + "['cart', 'curt', 'cure', 'lure']\n", + "['cart', 'curt', 'cure', 'pure']\n", + "['cart', 'curt', 'cure', 'sure']\n", + "['cart', 'curt', 'cure', 'care']\n", + "['cart', 'curt', 'cure', 'core']\n", + "['cart', 'curt', 'cure', 'cube']\n", + "['cart', 'curt', 'cure', 'cute']\n", + "['cart', 'curt', 'cure', 'curb']\n", + "['cart', 'curt', 'cure', 'curd']\n", + "['cart', 'curt', 'cure', 'curl']\n", + "['cart', 'curt', 'cure', 'curs']\n", + "['cart', 'curt', 'curl', 'furl']\n", + "['cart', 'curt', 'curl', 'hurl']\n", + "['cart', 'curt', 'curl', 'purl']\n", + "['cart', 'curt', 'curl', 'cull']\n", + "['cart', 'curt', 'curl', 'curb']\n", + "['cart', 'curt', 'curl', 'curd']\n", + "['cart', 'curt', 'curl', 'cure']\n", + "['cart', 'curt', 'curl', 'curs']\n", + "['cart', 'curt', 'curs', 'burs']\n", + "['cart', 'curt', 'curs', 'furs']\n", + "['cart', 'curt', 'curs', 'ours']\n", + "['cart', 'curt', 'curs', 'cars']\n", + "['cart', 'curt', 'curs', 'cubs']\n", + "['cart', 'curt', 'curs', 'cuds']\n", + "['cart', 'curt', 'curs', 'cues']\n", + "['cart', 'curt', 'curs', 'cums']\n", + "['cart', 'curt', 'curs', 'cups']\n", + "['cart', 'curt', 'curs', 'cuss']\n", + "['cart', 'curt', 'curs', 'cuts']\n", + "['cart', 'curt', 'curs', 'curb']\n", + "['cart', 'curt', 'curs', 'curd']\n", + "['cart', 'curt', 'curs', 'cure']\n", + "['cart', 'curt', 'curs', 'curl']\n", + "['cart', 'cant', 'pant', 'rant']\n", + "['cart', 'cant', 'pant', 'want']\n", + "['cart', 'cant', 'pant', 'pent']\n", + "['cart', 'cant', 'pant', 'pint']\n", + "['cart', 'cant', 'pant', 'punt']\n", + "['cart', 'cant', 'pant', 'pact']\n", + "['cart', 'cant', 'pant', 'part']\n", + "['cart', 'cant', 'pant', 'past']\n", + "['cart', 'cant', 'pant', 'pane']\n", + "['cart', 'cant', 'pant', 'pang']\n", + "['cart', 'cant', 'pant', 'pans']\n", + "['cart', 'cant', 'rant', 'pant']\n", + "['cart', 'cant', 'rant', 'want']\n", + "['cart', 'cant', 'rant', 'rent']\n", + "['cart', 'cant', 'rant', 'runt']\n", + "['cart', 'cant', 'rant', 'raft']\n", + "['cart', 'cant', 'rant', 'rapt']\n", + "['cart', 'cant', 'rant', 'rang']\n", + "['cart', 'cant', 'rant', 'rank']\n", + "['cart', 'cant', 'want', 'pant']\n", + "['cart', 'cant', 'want', 'rant']\n", + "['cart', 'cant', 'want', 'went']\n", + "['cart', 'cant', 'want', 'wont']\n", + "['cart', 'cant', 'want', 'waft']\n", + "['cart', 'cant', 'want', 'wait']\n", + "['cart', 'cant', 'want', 'wart']\n", + "['cart', 'cant', 'want', 'watt']\n", + "['cart', 'cant', 'want', 'wand']\n", + "['cart', 'cant', 'want', 'wane']\n", + "['cart', 'cant', 'cent', 'bent']\n", + "['cart', 'cant', 'cent', 'dent']\n", + "['cart', 'cant', 'cent', 'gent']\n", + "['cart', 'cant', 'cent', 'lent']\n", + "['cart', 'cant', 'cent', 'pent']\n", + "['cart', 'cant', 'cent', 'rent']\n", + "['cart', 'cant', 'cent', 'sent']\n", + "['cart', 'cant', 'cent', 'tent']\n", + "['cart', 'cant', 'cent', 'vent']\n", + "['cart', 'cant', 'cent', 'went']\n", + "['cart', 'cant', 'cast', 'bast']\n", + "['cart', 'cant', 'cast', 'east']\n", + "['cart', 'cant', 'cast', 'fast']\n", + "['cart', 'cant', 'cast', 'last']\n", + "['cart', 'cant', 'cast', 'mast']\n", + "['cart', 'cant', 'cast', 'past']\n", + "['cart', 'cant', 'cast', 'vast']\n", + "['cart', 'cant', 'cast', 'cost']\n", + "['cart', 'cant', 'cast', 'cyst']\n", + "['cart', 'cant', 'cast', 'case']\n", + "['cart', 'cant', 'cast', 'cash']\n", + "['cart', 'cant', 'cast', 'cask']\n", + "['cart', 'cant', 'cane', 'bane']\n", + "['cart', 'cant', 'cane', 'lane']\n", + "['cart', 'cant', 'cane', 'mane']\n", + "['cart', 'cant', 'cane', 'pane']\n", + "['cart', 'cant', 'cane', 'sane']\n", + "['cart', 'cant', 'cane', 'vane']\n", + "['cart', 'cant', 'cane', 'wane']\n", + "['cart', 'cant', 'cane', 'cone']\n", + "['cart', 'cant', 'cane', 'cafe']\n", + "['cart', 'cant', 'cane', 'cage']\n", + "['cart', 'cant', 'cane', 'cake']\n", + "['cart', 'cant', 'cane', 'came']\n", + "['cart', 'cant', 'cane', 'cape']\n", + "['cart', 'cant', 'cane', 'care']\n", + "['cart', 'cant', 'cane', 'case']\n", + "['cart', 'cant', 'cane', 'cave']\n", + "['cart', 'cant', 'cane', 'cans']\n", + "['cart', 'cant', 'cans', 'bans']\n", + "['cart', 'cant', 'cans', 'fans']\n", + "['cart', 'cant', 'cans', 'mans']\n", + "['cart', 'cant', 'cans', 'pans']\n", + "['cart', 'cant', 'cans', 'sans']\n", + "['cart', 'cant', 'cans', 'tans']\n", + "['cart', 'cant', 'cans', 'vans']\n" + ] + }, + { + "data": { + "text/plain": [ + "['cart', 'cant', 'cans', 'vans']" + ] + }, + "execution_count": 20, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "bfs_search('cart', 'vans', debug=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 21, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['cart', 'cant', 'cane', 'vane']" + ] + }, + "execution_count": 21, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "bfs_search('cart', 'vane')" + ] + }, + { + "cell_type": "code", + "execution_count": 22, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['cart',\n", + " 'dart',\n", + " 'hart',\n", + " 'mart',\n", + " 'part',\n", + " 'tart',\n", + " 'wart',\n", + " 'waft',\n", + " 'daft',\n", + " 'haft',\n", + " 'raft',\n", + " 'rift',\n", + " 'gift',\n", + " 'lift',\n", + " 'sift',\n", + " 'soft',\n", + " 'loft',\n", + " 'left',\n", + " 'deft',\n", + " 'heft',\n", + " 'weft',\n", + " 'welt',\n", + " 'belt',\n", + " 'felt',\n", + " 'gelt',\n", + " 'melt',\n", + " 'pelt',\n", + " 'peat',\n", + " 'beat',\n", + " 'feat',\n", + " 'heat',\n", + " 'meat',\n", + " 'neat',\n", + " 'seat',\n", + " 'teat',\n", + " 'that',\n", + " 'chat',\n", + " 'shat',\n", + " 'what',\n", + " 'whet',\n", + " 'whit',\n", + " 'chit',\n", + " 'chic',\n", + " 'chid',\n", + " 'chin',\n", + " 'shin',\n", + " 'thin',\n", + " 'twin',\n", + " 'twig',\n", + " 'swig',\n", + " 'swag',\n", + " 'shag',\n", + " 'slag',\n", + " 'flag',\n", + " 'flog',\n", + " 'blog',\n", + " 'clog',\n", + " 'slog',\n", + " 'smog',\n", + " 'smug',\n", + " 'slug',\n", + " 'plug',\n", + " 'plum',\n", + " 'alum',\n", + " 'glum',\n", + " 'slum',\n", + " 'scum',\n", + " 'swum',\n", + " 'swam',\n", + " 'scam',\n", + " 'seam',\n", + " 'beam',\n", + " 'ream',\n", + " 'team',\n", + " 'tram',\n", + " 'cram',\n", + " 'dram',\n", + " 'gram',\n", + " 'pram',\n", + " 'prim',\n", + " 'brim',\n", + " 'grim',\n", + " 'trim',\n", + " 'trig',\n", + " 'brig',\n", + " 'brag',\n", + " 'crag',\n", + " 'drag',\n", + " 'drug',\n", + " 'drub',\n", + " 'grub',\n", + " 'grab',\n", + " 'crab',\n", + " 'drab',\n", + " 'draw',\n", + " 'craw',\n", + " 'claw',\n", + " 'flaw',\n", + " 'slaw',\n", + " 'slew',\n", + " 'blew',\n", + " 'clew',\n", + " 'flew',\n", + " 'flow',\n", + " 'blow',\n", + " 'glow',\n", + " 'slow',\n", + " 'scow',\n", + " 'show',\n", + " 'chow',\n", + " 'crow',\n", + " 'brow',\n", + " 'grow',\n", + " 'prow',\n", + " 'prod',\n", + " 'trod',\n", + " 'trot',\n", + " 'toot',\n", + " 'boot',\n", + " 'coot',\n", + " 'foot',\n", + " 'hoot',\n", + " 'loot',\n", + " 'moot',\n", + " 'root',\n", + " 'soot',\n", + " 'shot',\n", + " 'slot',\n", + " 'blot',\n", + " 'clot',\n", + " 'plot',\n", + " 'plod',\n", + " 'clod',\n", + " 'clad',\n", + " 'glad',\n", + " 'goad',\n", + " 'load',\n", + " 'road',\n", + " 'toad',\n", + " 'toed',\n", + " 'coed',\n", + " 'hoed',\n", + " 'heed',\n", + " 'deed',\n", + " 'feed',\n", + " 'geed',\n", + " 'need',\n", + " 'peed',\n", + " 'reed',\n", + " 'seed',\n", + " 'teed',\n", + " 'weed',\n", + " 'weld',\n", + " 'geld',\n", + " 'held',\n", + " 'meld',\n", + " 'veld',\n", + " 'vend',\n", + " 'bend',\n", + " 'fend',\n", + " 'lend',\n", + " 'mend',\n", + " 'rend',\n", + " 'send',\n", + " 'tend',\n", + " 'wend',\n", + " 'wand',\n", + " 'band',\n", + " 'hand',\n", + " 'land',\n", + " 'sand',\n", + " 'said',\n", + " 'laid',\n", + " 'maid',\n", + " 'paid',\n", + " 'raid',\n", + " 'rail',\n", + " 'bail',\n", + " 'fail',\n", + " 'hail',\n", + " 'jail',\n", + " 'mail',\n", + " 'nail',\n", + " 'pail',\n", + " 'sail',\n", + " 'tail',\n", + " 'wail',\n", + " 'wall',\n", + " 'ball',\n", + " 'call',\n", + " 'fall',\n", + " 'gall',\n", + " 'hall',\n", + " 'mall',\n", + " 'pall',\n", + " 'tall',\n", + " 'tell',\n", + " 'bell',\n", + " 'cell',\n", + " 'dell',\n", + " 'fell',\n", + " 'hell',\n", + " 'jell',\n", + " 'sell',\n", + " 'well',\n", + " 'yell',\n", + " 'yelp',\n", + " 'help',\n", + " 'kelp',\n", + " 'keep',\n", + " 'beep',\n", + " 'deep',\n", + " 'jeep',\n", + " 'peep',\n", + " 'seep',\n", + " 'veep',\n", + " 'weep',\n", + " 'week',\n", + " 'geek',\n", + " 'leek',\n", + " 'meek',\n", + " 'peek',\n", + " 'reek',\n", + " 'seek',\n", + " 'seem',\n", + " 'deem',\n", + " 'teem',\n", + " 'them',\n", + " 'thee',\n", + " 'tree',\n", + " 'free',\n", + " 'flee',\n", + " 'glee',\n", + " 'glue',\n", + " 'blue',\n", + " 'clue',\n", + " 'flue',\n", + " 'slue',\n", + " 'sloe',\n", + " 'aloe',\n", + " 'floe',\n", + " 'flop',\n", + " 'clop',\n", + " 'glop',\n", + " 'plop',\n", + " 'slop',\n", + " 'shop',\n", + " 'chop',\n", + " 'coop',\n", + " 'goop',\n", + " 'hoop',\n", + " 'loop',\n", + " 'poop',\n", + " 'prop',\n", + " 'crop',\n", + " 'drop',\n", + " 'drip',\n", + " 'grip',\n", + " 'trip',\n", + " 'trap',\n", + " 'tray',\n", + " 'bray',\n", + " 'dray',\n", + " 'fray',\n", + " 'gray',\n", + " 'pray',\n", + " 'play',\n", + " 'clay',\n", + " 'flay',\n", + " 'slay',\n", + " 'spay',\n", + " 'stay',\n", + " 'sway',\n", + " 'away',\n", + " 'awry',\n", + " 'aery',\n", + " 'eery',\n", + " 'very',\n", + " 'vary',\n", + " 'nary',\n", + " 'wary',\n", + " 'wiry',\n", + " 'airy',\n", + " 'airs',\n", + " 'firs',\n", + " 'sirs',\n", + " 'sics',\n", + " 'tics',\n", + " 'ties',\n", + " 'dies',\n", + " 'hies',\n", + " 'lies',\n", + " 'pies',\n", + " 'vies',\n", + " 'vied',\n", + " 'died',\n", + " 'hied',\n", + " 'lied',\n", + " 'pied',\n", + " 'tied',\n", + " 'tier',\n", + " 'bier',\n", + " 'pier',\n", + " 'peer',\n", + " 'beer',\n", + " 'deer',\n", + " 'jeer',\n", + " 'leer',\n", + " 'seer',\n", + " 'veer',\n", + " 'weer',\n", + " 'wear',\n", + " 'bear',\n", + " 'dear',\n", + " 'fear',\n", + " 'gear',\n", + " 'hear',\n", + " 'near',\n", + " 'pear',\n", + " 'rear',\n", + " 'sear',\n", + " 'tear',\n", + " 'year',\n", + " 'yeah',\n", + " 'yeas',\n", + " 'leas',\n", + " 'peas',\n", + " 'seas',\n", + " 'teas',\n", + " 'tees',\n", + " 'bees',\n", + " 'fees',\n", + " 'gees',\n", + " 'lees',\n", + " 'pees',\n", + " 'sees',\n", + " 'wees',\n", + " 'woes',\n", + " 'does',\n", + " 'foes',\n", + " 'goes',\n", + " 'hoes',\n", + " 'noes',\n", + " 'roes',\n", + " 'toes',\n", + " 'togs',\n", + " 'bogs',\n", + " 'cogs',\n", + " 'dogs',\n", + " 'fogs',\n", + " 'hogs',\n", + " 'jogs',\n", + " 'logs',\n", + " 'lags',\n", + " 'bags',\n", + " 'fags',\n", + " 'gags',\n", + " 'hags',\n", + " 'jags',\n", + " 'nags',\n", + " 'rags',\n", + " 'sags',\n", + " 'tags',\n", + " 'wags',\n", + " 'wigs',\n", + " 'digs',\n", + " 'figs',\n", + " 'gigs',\n", + " 'jigs',\n", + " 'pigs',\n", + " 'rigs',\n", + " 'rugs',\n", + " 'bugs',\n", + " 'hugs',\n", + " 'jugs',\n", + " 'lugs',\n", + " 'mugs',\n", + " 'pugs',\n", + " 'tugs',\n", + " 'tubs',\n", + " 'cubs',\n", + " 'dubs',\n", + " 'hubs',\n", + " 'nubs',\n", + " 'pubs',\n", + " 'rubs',\n", + " 'subs',\n", + " 'sobs',\n", + " 'bobs',\n", + " 'cobs',\n", + " 'fobs',\n", + " 'gobs',\n", + " 'hobs',\n", + " 'jobs',\n", + " 'lobs',\n", + " 'mobs',\n", + " 'robs',\n", + " 'ribs',\n", + " 'bibs',\n", + " 'fibs',\n", + " 'jibs',\n", + " 'nibs',\n", + " 'nabs',\n", + " 'cabs',\n", + " 'dabs',\n", + " 'gabs',\n", + " 'jabs',\n", + " 'labs',\n", + " 'tabs',\n", + " 'tads',\n", + " 'cads',\n", + " 'dads',\n", + " 'fads',\n", + " 'gads',\n", + " 'lads',\n", + " 'mads',\n", + " 'pads',\n", + " 'wads',\n", + " 'weds',\n", + " 'beds',\n", + " 'feds',\n", + " 'reds',\n", + " 'rids',\n", + " 'aids',\n", + " 'bids',\n", + " 'kids',\n", + " 'lids',\n", + " 'lips',\n", + " 'dips',\n", + " 'hips',\n", + " 'nips',\n", + " 'pips',\n", + " 'rips',\n", + " 'sips',\n", + " 'tips',\n", + " 'yips',\n", + " 'zips',\n", + " 'zaps',\n", + " 'caps',\n", + " 'gaps',\n", + " 'laps',\n", + " 'maps',\n", + " 'naps',\n", + " 'paps',\n", + " 'raps',\n", + " 'saps',\n", + " 'taps',\n", + " 'yaps',\n", + " 'yeps',\n", + " 'peps',\n", + " 'reps',\n", + " 'refs',\n", + " 'reis',\n", + " 'leis',\n", + " 'legs',\n", + " 'begs',\n", + " 'kegs',\n", + " 'megs',\n", + " 'pegs',\n", + " 'pens',\n", + " 'dens',\n", + " 'fens',\n", + " 'hens',\n", + " 'kens',\n", + " 'lens',\n", + " 'tens',\n", + " 'wens',\n", + " 'yens',\n", + " 'yews',\n", + " 'hews',\n", + " 'mews',\n", + " 'news',\n", + " 'pews',\n", + " 'sews',\n", + " 'saws',\n", + " 'caws',\n", + " 'haws',\n", + " 'jaws',\n", + " 'laws',\n", + " 'maws',\n", + " 'paws',\n", + " 'yaws',\n", + " 'yaks',\n", + " 'oaks',\n", + " 'oafs',\n", + " 'oars',\n", + " 'bars',\n", + " 'cars',\n", + " 'ears',\n", + " 'jars',\n", + " 'mars',\n", + " 'pars',\n", + " 'tars',\n", + " 'wars',\n", + " 'ways',\n", + " 'bays',\n", + " 'days',\n", + " 'gays',\n", + " 'hays',\n", + " 'jays',\n", + " 'lays',\n", + " 'nays',\n", + " 'pays',\n", + " 'rays',\n", + " 'says',\n", + " 'sacs',\n", + " 'secs',\n", + " 'sets',\n", + " 'bets',\n", + " 'gets',\n", + " 'jets',\n", + " 'lets',\n", + " 'nets',\n", + " 'pets',\n", + " 'vets',\n", + " 'wets',\n", + " 'wits',\n", + " 'bits',\n", + " 'fits',\n", + " 'hits',\n", + " 'kits',\n", + " 'nits',\n", + " 'pits',\n", + " 'sits',\n", + " 'tits',\n", + " 'tats',\n", + " 'bats',\n", + " 'cats',\n", + " 'eats',\n", + " 'fats',\n", + " 'hats',\n", + " 'lats',\n", + " 'mats',\n", + " 'oats',\n", + " 'pats',\n", + " 'rats',\n", + " 'vats',\n", + " 'vans',\n", + " 'bans',\n", + " 'cans',\n", + " 'fans',\n", + " 'mans',\n", + " 'pans',\n", + " 'sans',\n", + " 'tans',\n", + " 'tins',\n", + " 'bins',\n", + " 'dins',\n", + " 'fins',\n", + " 'gins',\n", + " 'pins',\n", + " 'sins',\n", + " 'wins',\n", + " 'wind',\n", + " 'bind',\n", + " 'find',\n", + " 'hind',\n", + " 'kind',\n", + " 'mind',\n", + " 'rind',\n", + " 'ring',\n", + " 'ding',\n", + " 'king',\n", + " 'ping',\n", + " 'sing',\n", + " 'ting',\n", + " 'wing',\n", + " 'wine',\n", + " 'dine',\n", + " 'fine',\n", + " 'line',\n", + " 'mine',\n", + " 'nine',\n", + " 'pine',\n", + " 'sine',\n", + " 'tine',\n", + " 'vine',\n", + " 'vane']" + ] + }, + "execution_count": 22, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "dfs_search('cart', 'vane')" + ] + }, + { + "cell_type": "code", + "execution_count": 23, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def astar_search(start, goal, debug=False):\n", + " agenda = [(distance(start, goal), [start])]\n", + " heapq.heapify(agenda)\n", + " finished = False\n", + " while not finished and agenda:\n", + " _, current = heapq.heappop(agenda)\n", + " if debug:\n", + " print(current)\n", + " if current[-1] == goal:\n", + " finished = True\n", + " else:\n", + " successors = extend(current)\n", + " for s in successors:\n", + " heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n", + " if agenda:\n", + " return current\n", + " else:\n", + " return None " + ] + }, + { + "cell_type": "code", + "execution_count": 24, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "['cart']\n", + "['cart', 'cant']\n", + "['cart', 'cant', 'cane']\n", + "['cart', 'cant', 'cane', 'vane']\n" + ] + }, + { + "data": { + "text/plain": [ + "['cart', 'cant', 'cane', 'vane']" + ] + }, + "execution_count": 24, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search('cart', 'vane', debug=True)" + ] + }, + { + "cell_type": "code", + "execution_count": 25, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "def astar_search_closed(start, goal, debug=False):\n", + " agenda = [(distance(start, goal), [start])]\n", + " heapq.heapify(agenda)\n", + " closed = set()\n", + " finished = False\n", + " while not finished and agenda:\n", + " _, current = heapq.heappop(agenda)\n", + " if debug:\n", + " print(current)\n", + " if current[-1] == goal:\n", + " finished = True\n", + " else:\n", + " closed.add(current[-1])\n", + " successors = extend(current, closed)\n", + " for s in successors:\n", + " heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n", + " if agenda:\n", + " return current\n", + " else:\n", + " return None " + ] + }, + { + "cell_type": "code", + "execution_count": 26, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "['cart']\n", + "['cart', 'cant']\n", + "['cart', 'cant', 'cane']\n", + "['cart', 'cant', 'cane', 'vane']\n" + ] + }, + { + "data": { + "text/plain": [ + "['cart', 'cant', 'cane', 'vane']" + ] + }, + "execution_count": 26, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search_closed('cart', 'vane', debug=True)" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Mutually-reachable sets\n", + "\n", + "Find the transitive closure of the `neighbours` relation, so we can see which words can be transformed into which other words." + ] + }, + { + "cell_type": "code", + "execution_count": 77, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "94" + ] + }, + "execution_count": 77, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "candidates = [set([k] + neighbours[k]) for k in neighbours]\n", + "reachables = []\n", + "while candidates:\n", + " current = set(candidates.pop())\n", + " altered = False\n", + " for other in candidates:\n", + " if current.intersection(other):\n", + " altered = True\n", + " current.update(other)\n", + " candidates.remove(other)\n", + " if altered:\n", + " candidates.append(current)\n", + " else:\n", + " reachables.append(current)\n", + "\n", + "len(reachables)" + ] + }, + { + "cell_type": "code", + "execution_count": 78, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "2204" + ] + }, + "execution_count": 78, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len(max(reachables, key=len))" + ] + }, + { + "cell_type": "code", + "execution_count": 79, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "1" + ] + }, + "execution_count": 79, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len(min(reachables, key=len))" + ] + }, + { + "cell_type": "code", + "execution_count": 80, + "metadata": { + "scrolled": true + }, + "outputs": [ + { + "data": { + "text/plain": [ + "Counter({1: 75, 2: 6, 3: 7, 4: 2, 5: 2, 6: 1, 2204: 1})" + ] + }, + "execution_count": 80, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "collections.Counter(len(r) for r in reachables)" + ] + }, + { + "cell_type": "code", + "execution_count": 81, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[5]" + ] + }, + "execution_count": 81, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[len(r) for r in reachables if 'abbe' in r]" + ] + }, + { + "cell_type": "code", + "execution_count": 82, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[{'abbe', 'able', 'ably', 'ally', 'axle'}]" + ] + }, + "execution_count": 82, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[r for r in reachables if 'abbe' in r]" + ] + }, + { + "cell_type": "code", + "execution_count": 83, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['buns', 'bunk', 'punk']" + ] + }, + "execution_count": 83, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search('buns', 'punk')" + ] + }, + { + "cell_type": "code", + "execution_count": 84, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "for a in reachables:\n", + " for b in reachables:\n", + " if a != b:\n", + " if not a.isdisjoint(b):\n", + " print(a, b)" + ] + }, + { + "cell_type": "code", + "execution_count": 85, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "# longest_chain = []\n", + "# with open('all-chains-4.txt', 'w', 1) as f:\n", + "# for ws in reachables:\n", + "# for s in ws:\n", + "# for t in ws:\n", + "# if s < t:\n", + "# chain = astar_search(s, t)\n", + "# if chain:\n", + "# f.write('{}\\n'.format(chain))\n", + "# if len(chain) > len(longest_chain):\n", + "# longest_chain = chain\n", + "\n", + "# longest_chain" + ] + }, + { + "cell_type": "code", + "execution_count": 86, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [ + "bigset = max(reachables, key=len)" + ] + }, + { + "cell_type": "code", + "execution_count": 87, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "['late', 'lats', 'lets', 'leas', 'seas', 'seam', 'swam', 'sway']\n", + "['leap', 'heap', 'hear', 'dear', 'deer']\n", + "['peel', 'peek', 'perk', 'park', 'nark']\n", + "['sing', 'sang', 'sand', 'said', 'sail', 'hail', 'haul']\n", + "['vats', 'bats', 'bets', 'bees', 'been', 'teen', 'then', 'thin', 'this', 'thus', 'thud']\n", + "['sues', 'sees', 'seen', 'sewn', 'hewn']\n", + "['rash', 'bash', 'bast', 'bait', 'bail', 'hail', 'hair', 'heir']\n", + "['apex', 'aped', 'sped', 'seed', 'deed', 'dead', 'deal', 'veal']\n", + "['gulf', 'golf', 'gold', 'bold', 'bond', 'bony', 'tony']\n", + "['snag', 'shag', 'shat', 'seat', 'peat', 'pent', 'pint', 'mint']\n", + "['rife', 'rime', 'rims', 'rums', 'cums', 'cuss']\n", + "['diss', 'kiss', 'kits']\n", + "['gyps', 'gaps', 'gads', 'wads', 'wade', 'wide', 'tide']\n", + "['bilk', 'bill', 'bell', 'tell', 'teal', 'tear', 'tzar']\n", + "['logo', 'loge', 'lode', 'lade', 'jade', 'jape']\n", + "['hunt', 'bunt', 'buns', 'nuns', 'nubs']\n", + "['glow', 'glop', 'plop', 'prop', 'prep', 'peep', 'keep']\n", + "['iamb', 'lamb', 'lams', 'laps', 'lips', 'pips']\n", + "['pain', 'lain', 'laid', 'land', 'lend', 'vend', 'veld']\n", + "['fake', 'bake', 'bare', 'bars', 'ears', 'errs', 'ergs', 'eggs', 'egos']\n" + ] + } + ], + "source": [ + "for _ in range(20):\n", + " start, goal = random.sample(bigset, 2)\n", + " print(astar_search_closed(start, goal))" + ] + }, + { + "cell_type": "code", + "execution_count": 38, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['cops', 'coos', 'coon', 'coin', 'chin', 'thin', 'this', 'thus', 'thug']" + ] + }, + "execution_count": 38, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search('cops', 'thug')" + ] + }, + { + "cell_type": "code", + "execution_count": 39, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[2204]" + ] + }, + "execution_count": 39, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[len(r) for r in reachables if 'love' in r if 'hate' in r]" + ] + }, + { + "cell_type": "code", + "execution_count": 40, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['hate', 'have', 'hove', 'love']" + ] + }, + "execution_count": 40, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search('hate', 'love')" + ] + }, + { + "cell_type": "code", + "execution_count": 41, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['wars', 'ware', 'wave', 'wove', 'love']" + ] + }, + "execution_count": 41, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search('wars', 'love')" + ] + }, + { + "cell_type": "code", + "execution_count": 61, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n", + "Wall time: 210 µs\n" + ] + }, + { + "data": { + "text/plain": [ + "5" + ] + }, + "execution_count": 61, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%time len(astar_search('wars', 'love'))" + ] + }, + { + "cell_type": "code", + "execution_count": 62, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n", + "Wall time: 252 µs\n" + ] + }, + { + "data": { + "text/plain": [ + "5" + ] + }, + "execution_count": 62, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%time len(astar_search_closed('wars', 'love'))" + ] + }, + { + "cell_type": "code", + "execution_count": 63, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "CPU times: user 24 ms, sys: 0 ns, total: 24 ms\n", + "Wall time: 24.2 ms\n" + ] + }, + { + "data": { + "text/plain": [ + "404" + ] + }, + "execution_count": 63, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%time len(dfs_search('wars', 'love'))" + ] + }, + { + "cell_type": "code", + "execution_count": 64, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "CPU times: user 5min 20s, sys: 76 ms, total: 5min 20s\n", + "Wall time: 5min 20s\n" + ] + }, + { + "data": { + "text/plain": [ + "5" + ] + }, + "execution_count": 64, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%time len(bfs_search('wars', 'love'))" + ] + }, + { + "cell_type": "code", + "execution_count": 65, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "CPU times: user 1.44 s, sys: 0 ns, total: 1.44 s\n", + "Wall time: 1.43 s\n" + ] + }, + { + "data": { + "text/plain": [ + "5" + ] + }, + "execution_count": 65, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%time len(bfs_search_closed('wars', 'love'))" + ] + }, + { + "cell_type": "code", + "execution_count": 42, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['fear', 'feat', 'fest', 'lest', 'lost', 'lose', 'love']" + ] + }, + "execution_count": 42, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search('fear', 'love')" + ] + }, + { + "cell_type": "code", + "execution_count": 43, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['fail', 'fall', 'pall', 'pals', 'pass']" + ] + }, + "execution_count": 43, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search('fail', 'pass')" + ] + }, + { + "cell_type": "code", + "execution_count": 44, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['star', 'soar', 'boar', 'boor', 'boon', 'born']" + ] + }, + "execution_count": 44, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search('star', 'born')" + ] + }, + { + "cell_type": "code", + "execution_count": 45, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['open',\n", + " 'oven',\n", + " 'even',\n", + " 'eves',\n", + " 'eyes',\n", + " 'byes',\n", + " 'bees',\n", + " 'begs',\n", + " 'bags',\n", + " 'bass',\n", + " 'pass']" + ] + }, + "execution_count": 45, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search('open', 'pass')" + ] + }, + { + "cell_type": "code", + "execution_count": 46, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['bass',\n", + " 'lass',\n", + " 'mass',\n", + " 'sass',\n", + " 'puss',\n", + " 'pads',\n", + " 'pals',\n", + " 'pans',\n", + " 'paps',\n", + " 'pars',\n", + " 'pats',\n", + " 'paws',\n", + " 'pays',\n", + " 'past']" + ] + }, + "execution_count": 46, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "neighbours['pass']" + ] + }, + { + "cell_type": "code", + "execution_count": 47, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[1]" + ] + }, + "execution_count": 47, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[len(r) for r in reachables if 'exam' in r]" + ] + }, + { + "cell_type": "code", + "execution_count": 48, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[2204]" + ] + }, + "execution_count": 48, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[len(r) for r in reachables if 'star' in r if 'born' in r]" + ] + }, + { + "cell_type": "code", + "execution_count": 49, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "1 loop, best of 3: 7.9 s per loop\n" + ] + } + ], + "source": [ + "%%timeit\n", + "astar_search('bats', 'exit')" + ] + }, + { + "cell_type": "code", + "execution_count": 50, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "10 loops, best of 3: 141 ms per loop\n" + ] + } + ], + "source": [ + "%%timeit\n", + "astar_search_closed('bats', 'exit')" + ] + }, + { + "cell_type": "code", + "execution_count": 51, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "['bats',\n", + " 'bans',\n", + " 'band',\n", + " 'sand',\n", + " 'said',\n", + " 'skid',\n", + " 'skit',\n", + " 'smit',\n", + " 'emit',\n", + " 'exit']" + ] + }, + "execution_count": 51, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search_closed('bats', 'exit')" + ] + }, + { + "cell_type": "code", + "execution_count": 88, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "{2: [['heel', 'keel'], ['wane', 'wave'], ['cell', 'sell'], ['cons', 'cobs']],\n", + " 3: [['hank', 'haws'], ['bars', 'bets'], ['rats', 'paws'], ['lock', 'hack']],\n", + " 4: [['rule', 'sore'], ['wavy', 'rape'], ['peas', 'ping'], ['bond', 'toll']],\n", + " 5: [['cope', 'yowl'], ['lose', 'loci'], ['rump', 'dash'], ['four', 'dyes']],\n", + " 6: [['boon', 'sell'], ['lots', 'pomp'], ['cola', 'turn'], ['boos', 'laid']],\n", + " 7: [['eave', 'inns'], ['meek', 'mere'], ['keys', 'wily'], ['slam', 'yore']],\n", + " 8: [['hack', 'flip'], ['crag', 'huge'], ['flux', 'gill'], ['play', 'busy']],\n", + " 9: [['lacy', 'whey'], ['wren', 'rook'], ['lire', 'drip'], ['grab', 'lame']],\n", + " 10: [['over', 'turn'], ['worn', 'anew'], ['stow', 'elks'], ['ergo', 'rich']],\n", + " 11: [['bask', 'idea'], ['gabs', 'thud'], ['idea', 'clod'], ['mark', 'ibis']],\n", + " 12: [['umps', 'torn'], ['futz', 'shun'], ['abut', 'face'], ['slug', 'open']],\n", + " 13: [['umps', 'skin'], ['chum', 'rats'], ['fury', 'chum'], ['omen', 'zany']],\n", + " 14: [['chug', 'gaff'], ['atom', 'fizz']],\n", + " 15: [['chug', 'oxen']]}" + ] + }, + "execution_count": 88, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "solutions = {}\n", + "for _ in range(10000):\n", + " start, goal = random.sample(bigset, 2)\n", + " solution = astar_search_closed(start, goal)\n", + " sl = len(solution)\n", + " if sl not in solutions:\n", + " solutions[sl] = []\n", + " if len(solutions[sl]) < 4:\n", + " solutions[sl].append([start, goal])\n", + " \n", + "# if len(solution) >= 10:\n", + "# solutions += [solution]\n", + " \n", + "solutions" + ] + }, + { + "cell_type": "code", + "execution_count": 91, + "metadata": {}, + "outputs": [], + "source": [ + "solutions = {2: [['heel', 'keel'], ['wane', 'wave'], ['cell', 'sell'], ['cons', 'cobs']],\n", + " 3: [['hank', 'haws'], ['bars', 'bets'], ['rats', 'paws'], ['lock', 'hack']],\n", + " 4: [['rule', 'sore'], ['wavy', 'rape'], ['peas', 'ping'], ['bond', 'toll']],\n", + " 5: [['cope', 'yowl'], ['lose', 'loci'], ['rump', 'dash'], ['four', 'dyes']],\n", + " 6: [['boon', 'sell'], ['lots', 'pomp'], ['cola', 'turn'], ['boos', 'laid']],\n", + " 7: [['eave', 'inns'], ['meek', 'mere'], ['keys', 'wily'], ['slam', 'yore']],\n", + " 8: [['hack', 'flip'], ['crag', 'huge'], ['flux', 'gill'], ['play', 'busy']],\n", + " 9: [['lacy', 'whey'], ['wren', 'rook'], ['lire', 'drip'], ['grab', 'lame']],\n", + " 10: [['over', 'turn'], ['worn', 'anew'], ['stow', 'elks'], ['ergo', 'rich']],\n", + " 11: [['bask', 'idea'], ['gabs', 'thud'], ['idea', 'clod'], ['mark', 'ibis']],\n", + " 12: [['umps', 'torn'], ['futz', 'shun'], ['abut', 'face'], ['slug', 'open']],\n", + " 13: [['umps', 'skin'], ['chum', 'rats'], ['fury', 'chum'], ['omen', 'zany']],\n", + " 14: [['chug', 'gaff'], ['atom', 'fizz'], ['chug', 'jinn'], ['amen', 'flog'],\n", + " ['buzz', 'grog'], ['imps', 'pros']],\n", + " 15: [['chug', 'oxen'], ['amen', 'doff']]}" + ] + }, + { + "cell_type": "code", + "execution_count": 54, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "[('amen', 'doff', 15), ('chug', 'jinn', 14), ('amen', 'flog', 14)]" + ] + }, + "execution_count": 54, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "[(s[0], s[-1], len(s)) for s in solutions if len(s) >= 14]" + ] + }, + { + "cell_type": "code", + "execution_count": 55, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "1 loop, best of 3: 360 ms per loop\n" + ] + } + ], + "source": [ + "%%timeit\n", + "astar_search_closed('blab', 'amen')" + ] + }, + { + "cell_type": "code", + "execution_count": 56, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "CPU times: user 384 ms, sys: 0 ns, total: 384 ms\n", + "Wall time: 385 ms\n" + ] + }, + { + "data": { + "text/plain": [ + "14" + ] + }, + "execution_count": 56, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%time len(astar_search_closed('blab', 'amen'))" + ] + }, + { + "cell_type": "code", + "execution_count": 57, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "CPU times: user 124 ms, sys: 0 ns, total: 124 ms\n", + "Wall time: 121 ms\n" + ] + }, + { + "data": { + "text/plain": [ + "15" + ] + }, + "execution_count": 57, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%time len(astar_search_closed('amen', 'doff'))" + ] + }, + { + "cell_type": "code", + "execution_count": 58, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "CPU times: user 32 ms, sys: 0 ns, total: 32 ms\n", + "Wall time: 32.4 ms\n" + ] + }, + { + "data": { + "text/plain": [ + "14" + ] + }, + "execution_count": 58, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%time len(astar_search_closed('chug', 'jinn'))" + ] + }, + { + "cell_type": "code", + "execution_count": 59, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "CPU times: user 16 ms, sys: 0 ns, total: 16 ms\n", + "Wall time: 17.1 ms\n" + ] + }, + { + "data": { + "text/plain": [ + "14" + ] + }, + "execution_count": 59, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%time len(astar_search_closed('amen', 'flog'))" + ] + }, + { + "cell_type": "code", + "execution_count": 73, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "CPU times: user 268 ms, sys: 4 ms, total: 272 ms\n", + "Wall time: 272 ms\n" + ] + }, + { + "data": { + "text/plain": [ + "14" + ] + }, + "execution_count": 73, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%time len(astar_search_closed('buzz', 'grog'))" + ] + }, + { + "cell_type": "code", + "execution_count": 74, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "CPU times: user 64 ms, sys: 0 ns, total: 64 ms\n", + "Wall time: 64.1 ms\n" + ] + }, + { + "data": { + "text/plain": [ + "14" + ] + }, + "execution_count": 74, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%time len(astar_search_closed('imps', 'pros'))" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], + "source": [] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Python 3", + "language": "python", + "name": "python3" + }, + "language_info": { + "codemirror_mode": { + "name": "ipython", + "version": 3 + }, + "file_extension": ".py", + "mimetype": "text/x-python", + "name": "python", + "nbconvert_exporter": "python", + "pygments_lexer": "ipython3", + "version": "3.5.2+" + } + }, + "nbformat": 4, + "nbformat_minor": 2 +}