{ "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('08-rooms.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 finished:\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 finished:\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 finished:\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", "['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" ] }, { "name": "stdout", "output_type": "stream", "text": [ "['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", "['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" ] }, { "name": "stdout", "output_type": "stream", "text": [ "['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 finished:\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": 81, "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 finished:\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": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "94" ] }, "execution_count": 27, "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": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2204" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(max(reachables, key=len))" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(min(reachables, key=len))" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "Counter({1: 75, 2: 6, 3: 7, 4: 2, 5: 2, 6: 1, 2204: 1})" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "collections.Counter(len(r) for r in reachables)" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[5]" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[len(r) for r in reachables if 'abbe' in r]" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[{'abbe', 'able', 'ably', 'ally', 'axle'}]" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[r for r in reachables if 'abbe' in r]" ] }, { "cell_type": "code", "execution_count": 76, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "[{'demo', 'memo'},\n", " {'thou', 'thru'},\n", " {'crud', 'crux'},\n", " {'bevy', 'levy'},\n", " {'ogle', 'ogre'},\n", " {'idol', 'idyl'},\n", " {'also', 'alto', 'auto'},\n", " {'used', 'user', 'uses'},\n", " {'idle', 'idly', 'isle'},\n", " {'eddy', 'edge', 'edgy'},\n", " {'opal', 'oral', 'oval'},\n", " {'icon', 'ikon', 'iron'},\n", " {'afar', 'agar', 'ajar'},\n", " {'each', 'etch', 'inch', 'itch'},\n", " {'high', 'nigh', 'sigh', 'sign'},\n", " {'abbe', 'able', 'ably', 'ally', 'axle'},\n", " {'info', 'into', 'onto', 'undo', 'unto'},\n", " {'ache', 'achy', 'acme', 'acne', 'acre', 'ashy'}]" ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sorted((r for r in reachables if len(r) > 1 if len(r) < 10), key=len)" ] }, { "cell_type": "code", "execution_count": 80, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'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'" ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" } ], "source": [ "'; '.join(sorted(list(r)[0] for r in reachables if len(r) == 1))" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['buns', 'bunk', 'punk']" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "astar_search('buns', 'punk')" ] }, { "cell_type": "code", "execution_count": 34, "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": 35, "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": 36, "metadata": { "collapsed": true }, "outputs": [], "source": [ "bigset = max(reachables, key=len)" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['army', 'arms', 'aims', 'aids', 'bids', 'bias', 'boas', 'boat', 'goat', 'gnat', 'gnaw']\n", "['hoes', 'toes', 'toms', 'tams', 'tame']\n", "['vane', 'vine', 'wine', 'wire', 'wiry', 'airy', 'awry', 'away']\n", "['mate', 'late', 'lane', 'land', 'laid', 'lain']\n", "['heal', 'head', 'bead', 'bend', 'bond', 'bone']\n", "['dune', 'dine', 'dins', 'dies', 'died', 'tied']\n", "['ions', 'dons', 'does', 'hoes', 'hoed', 'heed']\n", "['puck', 'pick', 'pink', 'mink', 'mine']\n", "['need', 'deed', 'died', 'dies', 'dims', 'dams', 'days', 'drys']\n", "['pore', 'core', 'code', 'cods', 'cuds']\n", "['mote', 'mite', 'mile', 'wile', 'wise']\n", "['wait', 'wail', 'mail', 'mall', 'male']\n", "['wail', 'bail', 'ball', 'boll', 'bolt', 'boot', 'boom', 'zoom']\n", "['beat', 'beet', 'bees', 'bets', 'bats', 'cats']\n", "['tore', 'tire', 'tile', 'vile', 'vise', 'visa']\n", "['went', 'pent', 'pant']\n", "['lick', 'sick', 'sics', 'sips', 'sops', 'oops']\n", "['womb', 'tomb', 'toms', 'toes', 'does', 'dyes', 'ayes', 'apes', 'aped']\n", "['cure', 'sure']\n", "['cute', 'cuts', 'guts', 'guys', 'gays']\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": [ "[2204]" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[len(r) for r in reachables if 'stay' in r ]" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['hate', 'have', 'hove', 'love']" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "astar_search('hate', 'love')" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['wars', 'ware', 'wave', 'wove', 'love']" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "astar_search('wars', 'love')" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n", "Wall time: 185 µs\n" ] }, { "data": { "text/plain": [ "5" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%time len(astar_search('wars', 'love'))" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n", "Wall time: 398 µs\n" ] }, { "data": { "text/plain": [ "5" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%time len(astar_search_closed('wars', 'love'))" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 32 ms, sys: 0 ns, total: 32 ms\n", "Wall time: 32.3 ms\n" ] }, { "data": { "text/plain": [ "404" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%time len(dfs_search('wars', 'love'))" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# %time len(bfs_search('wars', 'love'))" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 212 ms, sys: 0 ns, total: 212 ms\n", "Wall time: 213 ms\n" ] }, { "data": { "text/plain": [ "5" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%time len(bfs_search_closed('wars', 'love'))" ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['fear', 'feat', 'fest', 'lest', 'lost', 'lose', 'love']" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "astar_search('fear', 'love')" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['fail', 'fall', 'pall', 'pals', 'pass']" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "astar_search('fail', 'pass')" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['star', 'soar', 'boar', 'boor', 'boon', 'born']" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "astar_search('star', 'born')" ] }, { "cell_type": "code", "execution_count": 51, "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": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "astar_search('open', 'pass')" ] }, { "cell_type": "code", "execution_count": 52, "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": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "neighbours['pass']" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1]" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[len(r) for r in reachables if 'exam' in r]" ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[2204]" ] }, "execution_count": 54, "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": 55, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 loop, best of 3: 8.21 s per loop\n" ] } ], "source": [ "%%timeit\n", "astar_search('bats', 'exit')" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 loops, best of 3: 145 ms per loop\n" ] } ], "source": [ "%%timeit\n", "astar_search_closed('bats', 'exit')" ] }, { "cell_type": "code", "execution_count": 57, "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": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "astar_search_closed('bats', 'exit')" ] }, { "cell_type": "code", "execution_count": 58, "metadata": { "collapsed": true }, "outputs": [], "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": 59, "metadata": { "collapsed": true }, "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": 60, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 loop, best of 3: 334 ms per loop\n" ] } ], "source": [ "%%timeit\n", "astar_search_closed('blab', 'amen')" ] }, { "cell_type": "code", "execution_count": 61, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 344 ms, sys: 0 ns, total: 344 ms\n", "Wall time: 342 ms\n" ] }, { "data": { "text/plain": [ "14" ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%time len(astar_search_closed('blab', 'amen'))" ] }, { "cell_type": "code", "execution_count": 62, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 92 ms, sys: 0 ns, total: 92 ms\n", "Wall time: 93.7 ms\n" ] }, { "data": { "text/plain": [ "15" ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%time len(astar_search_closed('amen', 'doff'))" ] }, { "cell_type": "code", "execution_count": 63, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 32 ms, sys: 0 ns, total: 32 ms\n", "Wall time: 32.8 ms\n" ] }, { "data": { "text/plain": [ "14" ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%time len(astar_search_closed('chug', 'jinn'))" ] }, { "cell_type": "code", "execution_count": 64, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 16 ms, sys: 0 ns, total: 16 ms\n", "Wall time: 16.4 ms\n" ] }, { "data": { "text/plain": [ "14" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%time len(astar_search_closed('amen', 'flog'))" ] }, { "cell_type": "code", "execution_count": 65, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 256 ms, sys: 0 ns, total: 256 ms\n", "Wall time: 253 ms\n" ] }, { "data": { "text/plain": [ "14" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%time len(astar_search_closed('buzz', 'grog'))" ] }, { "cell_type": "code", "execution_count": 66, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 36 ms, sys: 0 ns, total: 36 ms\n", "Wall time: 34.2 ms\n" ] }, { "data": { "text/plain": [ "14" ] }, "execution_count": 66, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%time len(astar_search_closed('imps', 'pros'))" ] }, { "cell_type": "code", "execution_count": 67, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "bash bush True\n", "rush bush True\n" ] }, { "data": { "text/plain": [ "2" ] }, "execution_count": 67, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nb_count = collections.Counter()\n", "for w in neighbours['rash']:\n", " for w2 in neighbours[w]:\n", " if w2 == 'bush': print(w, w2, w2 not in neighbours['rash'])\n", " if w2 != 'rash' and w2 not in neighbours['rash']:\n", " nb_count.update([w2])\n", "nb_count.most_common(1)[0][1]" ] }, { "cell_type": "code", "execution_count": 68, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['gush', 'hush', 'lush', 'mush', 'push', 'tush', 'bosh']" ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[w for w in neighbours['bush'] if w in nb_count]" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "('nose', 2)" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "best_start = ''\n", "best_overlap_count = 0\n", "for w0 in neighbours: \n", " nb_count = collections.Counter()\n", " for w in neighbours[w0]:\n", " for w2 in neighbours[w]:\n", " if w2 != w0 and w2 not in neighbours[w0]:\n", " nb_count.update([w2])\n", " if len(nb_count) > 0:\n", " if nb_count.most_common(1)[0][1] > best_overlap_count:\n", " best_start = w0\n", " best_overlap_count = nb_count.most_common(1)[0][1]\n", " \n", "best_start, best_overlap_count" ] }, { "cell_type": "code", "execution_count": 70, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'grew'" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "w0" ] }, { "cell_type": "code", "execution_count": 71, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'bash', 'rush'}" ] }, "execution_count": 71, "metadata": {}, "output_type": "execute_result" } ], "source": [ "set(neighbours['rash']) & set(neighbours['bush'])" ] }, { "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 }