--- /dev/null
+{
+ "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": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2336"
+ ]
+ },
+ "execution_count": 2,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "words = [w.strip() for w in open('08-words.txt').readlines()]\n",
+ "len(words)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['able']"
+ ]
+ },
+ "execution_count": 7,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "neighbours['abbe']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "metadata": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[['abbe', 'able']]"
+ ]
+ },
+ "execution_count": 12,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "extend(['abbe'])"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "metadata": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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",
+ "['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",
+ "['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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false,
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "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": 54,
+ "metadata": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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": {
+ "collapsed": false
+ },
+ "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
+}
projects / ou-summer-of-code-2017.git / blobdiff