{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import string\n",
    "import heapq\n",
    "import collections\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2336"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = frozenset(w.strip() for w in open('08-rooms.txt').readlines())\n",
    "len(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "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": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def adjacents(word):\n",
    "    return frozenset(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": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "neighbours = {w: frozenset(n for n in adjacents(w) if n in words)\n",
    "             for w in words}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "frozenset({'able'})"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbours['abbe']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "frozenset({'abbe', 'ably', 'axle'})"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbours['able']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "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": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance('abbe', 'abbe')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "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": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['abbe', 'able']]"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "extend(['abbe'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['abbe', 'able', 'ably'], ['abbe', 'able', 'axle']]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "extend(['abbe', 'able'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['abbe', 'able', 'ably', 'ally']]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "extend(['abbe', 'able', 'ably'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "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, agenda)\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": 44,
   "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": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['abbe']\n",
      "['abbe', 'able']\n",
      "['abbe', 'able', 'ably']\n",
      "['abbe', 'able', 'axle']\n",
      "['abbe', 'able', 'ably', 'ally']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['abbe', 'able', 'ably', 'ally']"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bfs_search('abbe', 'ally', debug=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "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(agenda)\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": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['abbe']\n",
      "['abbe', 'able']\n",
      "['abbe', 'able', 'ably']\n",
      "['abbe', 'able', 'ably', 'ally']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['abbe', 'able', 'ably', 'ally']"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfs_search('abbe', 'ally', debug=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['cart']\n",
      "['cart', 'cast']\n",
      "['cart', 'hart']\n",
      "['cart', 'cars']\n",
      "['cart', 'mart']\n",
      "['cart', 'wart']\n",
      "['cart', 'card']\n",
      "['cart', 'curt']\n",
      "['cart', 'tart']\n",
      "['cart', 'care']\n",
      "['cart', 'cant']\n",
      "['cart', 'dart']\n",
      "['cart', 'part']\n",
      "['cart', 'carp']\n",
      "['cart', 'cast', 'last']\n",
      "['cart', 'cast', 'bast']\n",
      "['cart', 'cast', 'cant']\n",
      "['cart', 'cast', 'past']\n",
      "['cart', 'cast', 'mast']\n",
      "['cart', 'cast', 'fast']\n",
      "['cart', 'cast', 'case']\n",
      "['cart', 'cast', 'east']\n",
      "['cart', 'cast', 'cyst']\n",
      "['cart', 'cast', 'cash']\n",
      "['cart', 'cast', 'cask']\n",
      "['cart', 'cast', 'vast']\n",
      "['cart', 'cast', 'cost']\n",
      "['cart', 'hart', 'hard']\n",
      "['cart', 'hart', 'harm']\n",
      "['cart', 'hart', 'hare']\n",
      "['cart', 'hart', 'hurt']\n",
      "['cart', 'hart', 'haft']\n",
      "['cart', 'hart', 'halt']\n",
      "['cart', 'hart', 'mart']\n",
      "['cart', 'hart', 'wart']\n",
      "['cart', 'hart', 'hark']\n",
      "['cart', 'hart', 'tart']\n",
      "['cart', 'hart', 'harp']\n",
      "['cart', 'hart', 'dart']\n",
      "['cart', 'hart', 'part']\n",
      "['cart', 'cars', 'bars']\n",
      "['cart', 'cars', 'ears']\n",
      "['cart', 'cars', 'caps']\n",
      "['cart', 'cars', 'wars']\n",
      "['cart', 'cars', 'cabs']\n",
      "['cart', 'cars', 'oars']\n",
      "['cart', 'cars', 'pars']\n",
      "['cart', 'cars', 'tars']\n",
      "['cart', 'cars', 'card']\n",
      "['cart', 'cars', 'cams']\n",
      "['cart', 'cars', 'caws']\n",
      "['cart', 'cars', 'cats']\n",
      "['cart', 'cars', 'cads']\n",
      "['cart', 'cars', 'care']\n",
      "['cart', 'cars', 'cans']\n",
      "['cart', 'cars', 'mars']\n",
      "['cart', 'cars', 'curs']\n",
      "['cart', 'cars', 'carp']\n",
      "['cart', 'cars', 'jars']\n",
      "['cart', 'mart', 'mare']\n",
      "['cart', 'mart', 'malt']\n",
      "['cart', 'mart', 'hart']\n",
      "['cart', 'mart', 'dart']\n",
      "['cart', 'mart', 'mast']\n",
      "['cart', 'mart', 'wart']\n",
      "['cart', 'mart', 'tart']\n",
      "['cart', 'mart', 'matt']\n",
      "['cart', 'mart', 'mars']\n",
      "['cart', 'mart', 'part']\n",
      "['cart', 'mart', 'mark']\n",
      "['cart', 'wart', 'wary']\n",
      "['cart', 'wart', 'hart']\n",
      "['cart', 'wart', 'warn']\n",
      "['cart', 'wart', 'warm']\n",
      "['cart', 'wart', 'warp']\n",
      "['cart', 'wart', 'wars']\n",
      "['cart', 'wart', 'mart']\n",
      "['cart', 'wart', 'watt']\n",
      "['cart', 'wart', 'want']\n",
      "['cart', 'wart', 'ware']\n",
      "['cart', 'wart', 'tart']\n",
      "['cart', 'wart', 'waft']\n",
      "['cart', 'wart', 'dart']\n",
      "['cart', 'wart', 'part']\n",
      "['cart', 'wart', 'wait']\n",
      "['cart', 'wart', 'ward']\n",
      "['cart', 'card', 'hard']\n",
      "['cart', 'card', 'bard']\n",
      "['cart', 'card', 'lard']\n",
      "['cart', 'card', 'cars']\n",
      "['cart', 'card', 'curd']\n",
      "['cart', 'card', 'carp']\n",
      "['cart', 'card', 'care']\n",
      "['cart', 'card', 'yard']\n",
      "['cart', 'card', 'ward']\n",
      "['cart', 'card', 'cord']\n",
      "['cart', 'curt', 'curb']\n",
      "['cart', 'curt', 'hurt']\n",
      "['cart', 'curt', 'curd']\n",
      "['cart', 'curt', 'curl']\n",
      "['cart', 'curt', 'cure']\n",
      "['cart', 'curt', 'cult']\n",
      "['cart', 'curt', 'curs']\n",
      "['cart', 'tart', 'hart']\n",
      "['cart', 'tart', 'tare']\n",
      "['cart', 'tart', 'mart']\n",
      "['cart', 'tart', 'wart']\n",
      "['cart', 'tart', 'tars']\n",
      "['cart', 'tart', 'taut']\n",
      "['cart', 'tart', 'tarp']\n",
      "['cart', 'tart', 'tact']\n",
      "['cart', 'tart', 'tort']\n",
      "['cart', 'tart', 'dart']\n",
      "['cart', 'tart', 'part']\n",
      "['cart', 'tart', 'taro']\n",
      "['cart', 'care', 'came']\n",
      "['cart', 'care', 'hare']\n",
      "['cart', 'care', 'cure']\n",
      "['cart', 'care', 'card']\n",
      "['cart', 'care', 'core']\n",
      "['cart', 'care', 'cafe']\n",
      "['cart', 'care', 'cars']\n",
      "['cart', 'care', 'fare']\n",
      "['cart', 'care', 'case']\n",
      "['cart', 'care', 'cane']\n",
      "['cart', 'care', 'bare']\n",
      "['cart', 'care', 'cage']\n",
      "['cart', 'care', 'carp']\n",
      "['cart', 'care', 'cave']\n",
      "['cart', 'care', 'cape']\n",
      "['cart', 'care', 'pare']\n",
      "['cart', 'care', 'ware']\n",
      "['cart', 'care', 'mare']\n",
      "['cart', 'care', 'cake']\n",
      "['cart', 'care', 'rare']\n",
      "['cart', 'care', 'tare']\n",
      "['cart', 'care', 'dare']\n",
      "['cart', 'cant', 'cast']\n",
      "['cart', 'cant', 'rant']\n",
      "['cart', 'cant', 'cent']\n",
      "['cart', 'cant', 'want']\n",
      "['cart', 'cant', 'cans']\n",
      "['cart', 'cant', 'cane']\n",
      "['cart', 'cant', 'pant']\n",
      "['cart', 'dart', 'dirt']\n",
      "['cart', 'dart', 'daft']\n",
      "['cart', 'dart', 'dark']\n",
      "['cart', 'dart', 'hart']\n",
      "['cart', 'dart', 'wart']\n",
      "['cart', 'dart', 'mart']\n",
      "['cart', 'dart', 'dare']\n",
      "['cart', 'dart', 'darn']\n",
      "['cart', 'dart', 'tart']\n",
      "['cart', 'dart', 'part']\n",
      "['cart', 'part', 'port']\n",
      "['cart', 'part', 'hart']\n",
      "['cart', 'part', 'pact']\n",
      "['cart', 'part', 'pert']\n",
      "['cart', 'part', 'pare']\n",
      "['cart', 'part', 'past']\n",
      "['cart', 'part', 'mart']\n",
      "['cart', 'part', 'wart']\n",
      "['cart', 'part', 'pars']\n",
      "['cart', 'part', 'dart']\n",
      "['cart', 'part', 'tart']\n",
      "['cart', 'part', 'park']\n",
      "['cart', 'part', 'pant']\n",
      "['cart', 'carp', 'cars']\n",
      "['cart', 'carp', 'warp']\n",
      "['cart', 'carp', 'card']\n",
      "['cart', 'carp', 'camp']\n",
      "['cart', 'carp', 'care']\n",
      "['cart', 'carp', 'tarp']\n",
      "['cart', 'carp', 'harp']\n",
      "['cart', 'cast', 'last', 'list']\n",
      "['cart', 'cast', 'last', 'lost']\n",
      "['cart', 'cast', 'last', 'bast']\n",
      "['cart', 'cast', 'last', 'lust']\n",
      "['cart', 'cast', 'last', 'lass']\n",
      "['cart', 'cast', 'last', 'past']\n",
      "['cart', 'cast', 'last', 'lash']\n",
      "['cart', 'cast', 'last', 'mast']\n",
      "['cart', 'cast', 'last', 'fast']\n",
      "['cart', 'cast', 'last', 'east']\n",
      "['cart', 'cast', 'last', 'lest']\n",
      "['cart', 'cast', 'last', 'vast']\n",
      "['cart', 'cast', 'bast', 'last']\n",
      "['cart', 'cast', 'bast', 'bust']\n",
      "['cart', 'cast', 'bast', 'bass']\n",
      "['cart', 'cast', 'bast', 'base']\n",
      "['cart', 'cast', 'bast', 'past']\n",
      "['cart', 'cast', 'bast', 'mast']\n",
      "['cart', 'cast', 'bast', 'bait']\n",
      "['cart', 'cast', 'bast', 'fast']\n",
      "['cart', 'cast', 'bast', 'best']\n",
      "['cart', 'cast', 'bast', 'bash']\n",
      "['cart', 'cast', 'bast', 'east']\n",
      "['cart', 'cast', 'bast', 'bask']\n",
      "['cart', 'cast', 'bast', 'vast']\n",
      "['cart', 'cast', 'cant', 'rant']\n",
      "['cart', 'cast', 'cant', 'cent']\n",
      "['cart', 'cast', 'cant', 'want']\n",
      "['cart', 'cast', 'cant', 'cans']\n",
      "['cart', 'cast', 'cant', 'cane']\n",
      "['cart', 'cast', 'cant', 'pant']\n",
      "['cart', 'cast', 'past', 'last']\n",
      "['cart', 'cast', 'past', 'bast']\n",
      "['cart', 'cast', 'past', 'psst']\n",
      "['cart', 'cast', 'past', 'pact']\n",
      "['cart', 'cast', 'past', 'pass']\n",
      "['cart', 'cast', 'past', 'pant']\n",
      "['cart', 'cast', 'past', 'mast']\n",
      "['cart', 'cast', 'past', 'post']\n",
      "['cart', 'cast', 'past', 'fast']\n",
      "['cart', 'cast', 'past', 'pest']\n",
      "['cart', 'cast', 'past', 'east']\n",
      "['cart', 'cast', 'past', 'part']\n",
      "['cart', 'cast', 'past', 'vast']\n",
      "['cart', 'cast', 'mast', 'mask']\n",
      "['cart', 'cast', 'mast', 'last']\n",
      "['cart', 'cast', 'mast', 'malt']\n",
      "['cart', 'cast', 'mast', 'bast']\n",
      "['cart', 'cast', 'mast', 'mist']\n",
      "['cart', 'cast', 'mast', 'must']\n",
      "['cart', 'cast', 'mast', 'past']\n",
      "['cart', 'cast', 'mast', 'mart']\n",
      "['cart', 'cast', 'mast', 'fast']\n",
      "['cart', 'cast', 'mast', 'most']\n",
      "['cart', 'cast', 'mast', 'mash']\n",
      "['cart', 'cast', 'mast', 'matt']\n",
      "['cart', 'cast', 'mast', 'east']\n",
      "['cart', 'cast', 'mast', 'vast']\n",
      "['cart', 'cast', 'mast', 'mass']\n",
      "['cart', 'cast', 'fast', 'last']\n",
      "['cart', 'cast', 'fast', 'fest']\n",
      "['cart', 'cast', 'fast', 'bast']\n",
      "['cart', 'cast', 'fast', 'fact']\n",
      "['cart', 'cast', 'fast', 'past']\n",
      "['cart', 'cast', 'fast', 'mast']\n",
      "['cart', 'cast', 'fast', 'fist']\n",
      "['cart', 'cast', 'fast', 'east']\n",
      "['cart', 'cast', 'fast', 'vast']\n",
      "['cart', 'cast', 'case', 'came']\n",
      "['cart', 'cast', 'case', 'cake']\n",
      "['cart', 'cast', 'case', 'cafe']\n",
      "['cart', 'cast', 'case', 'cape']\n",
      "['cart', 'cast', 'case', 'base']\n",
      "['cart', 'cast', 'case', 'vase']\n",
      "['cart', 'cast', 'case', 'care']\n",
      "['cart', 'cast', 'case', 'ease']\n",
      "['cart', 'cast', 'case', 'cane']\n",
      "['cart', 'cast', 'case', 'cash']\n",
      "['cart', 'cast', 'case', 'cask']\n",
      "['cart', 'cast', 'case', 'cage']\n",
      "['cart', 'cast', 'case', 'cave']\n",
      "['cart', 'cast', 'east', 'last']\n",
      "['cart', 'cast', 'east', 'bast']\n",
      "['cart', 'cast', 'east', 'easy']\n",
      "['cart', 'cast', 'east', 'past']\n",
      "['cart', 'cast', 'east', 'mast']\n",
      "['cart', 'cast', 'east', 'fast']\n",
      "['cart', 'cast', 'east', 'ease']\n",
      "['cart', 'cast', 'east', 'vast']\n",
      "['cart', 'cast', 'cyst', 'cost']\n",
      "['cart', 'cast', 'cash', 'sash']\n",
      "['cart', 'cast', 'cash', 'lash']\n",
      "['cart', 'cast', 'cash', 'dash']\n",
      "['cart', 'cast', 'cash', 'bash']\n",
      "['cart', 'cast', 'cash', 'wash']\n",
      "['cart', 'cast', 'cash', 'case']\n",
      "['cart', 'cast', 'cash', 'mash']\n",
      "['cart', 'cast', 'cash', 'cask']\n",
      "['cart', 'cast', 'cash', 'gash']\n",
      "['cart', 'cast', 'cash', 'hash']\n",
      "['cart', 'cast', 'cash', 'rash']\n",
      "['cart', 'cast', 'cask', 'mask']\n",
      "['cart', 'cast', 'cask', 'case']\n",
      "['cart', 'cast', 'cask', 'cash']\n",
      "['cart', 'cast', 'cask', 'bask']\n",
      "['cart', 'cast', 'cask', 'task']\n",
      "['cart', 'cast', 'vast', 'last']\n",
      "['cart', 'cast', 'vast', 'bast']\n",
      "['cart', 'cast', 'vast', 'vest']\n",
      "['cart', 'cast', 'vast', 'past']\n",
      "['cart', 'cast', 'vast', 'mast']\n",
      "['cart', 'cast', 'vast', 'vase']\n",
      "['cart', 'cast', 'vast', 'fast']\n",
      "['cart', 'cast', 'vast', 'east']\n",
      "['cart', 'cast', 'cost', 'colt']\n",
      "['cart', 'cast', 'cost', 'lost']\n",
      "['cart', 'cast', 'cost', 'tost']\n",
      "['cart', 'cast', 'cost', 'post']\n",
      "['cart', 'cast', 'cost', 'cosy']\n",
      "['cart', 'cast', 'cost', 'coat']\n",
      "['cart', 'cast', 'cost', 'coot']\n",
      "['cart', 'cast', 'cost', 'most']\n",
      "['cart', 'cast', 'cost', 'cyst']\n",
      "['cart', 'cast', 'cost', 'host']\n",
      "['cart', 'hart', 'hard', 'harm']\n",
      "['cart', 'hart', 'hard', 'bard']\n",
      "['cart', 'hart', 'hard', 'hare']\n",
      "['cart', 'hart', 'hard', 'lard']\n",
      "['cart', 'hart', 'hard', 'card']\n",
      "['cart', 'hart', 'hard', 'herd']\n",
      "['cart', 'hart', 'hard', 'hark']\n",
      "['cart', 'hart', 'hard', 'hand']\n",
      "['cart', 'hart', 'hard', 'harp']\n",
      "['cart', 'hart', 'hard', 'yard']\n",
      "['cart', 'hart', 'hard', 'ward']\n",
      "['cart', 'hart', 'harm', 'farm']\n",
      "['cart', 'hart', 'harm', 'hard']\n",
      "['cart', 'hart', 'harm', 'hare']\n",
      "['cart', 'hart', 'harm', 'warm']\n",
      "['cart', 'hart', 'harm', 'harp']\n",
      "['cart', 'hart', 'harm', 'hark']\n",
      "['cart', 'hart', 'hare', 'mare']\n",
      "['cart', 'hart', 'hare', 'hard']\n",
      "['cart', 'hart', 'hare', 'harm']\n",
      "['cart', 'hart', 'hare', 'rare']\n",
      "['cart', 'hart', 'hare', 'hake']\n",
      "['cart', 'hart', 'hare', 'fare']\n",
      "['cart', 'hart', 'hare', 'tare']\n",
      "['cart', 'hart', 'hare', 'pare']\n",
      "['cart', 'hart', 'hare', 'hate']\n",
      "['cart', 'hart', 'hare', 'here']\n",
      "['cart', 'hart', 'hare', 'dare']\n",
      "['cart', 'hart', 'hare', 'hale']\n",
      "['cart', 'hart', 'hare', 'care']\n",
      "['cart', 'hart', 'hare', 'have']\n",
      "['cart', 'hart', 'hare', 'harp']\n",
      "['cart', 'hart', 'hare', 'ware']\n",
      "['cart', 'hart', 'hare', 'bare']\n",
      "['cart', 'hart', 'hare', 'hark']\n",
      "['cart', 'hart', 'hare', 'hire']\n",
      "['cart', 'hart', 'hare', 'haze']\n",
      "['cart', 'hart', 'hurt', 'curt']\n",
      "['cart', 'hart', 'hurt', 'hurl']\n",
      "['cart', 'hart', 'hurt', 'hunt']\n",
      "['cart', 'hart', 'haft', 'daft']\n",
      "['cart', 'hart', 'haft', 'heft']\n",
      "['cart', 'hart', 'haft', 'halt']\n",
      "['cart', 'hart', 'haft', 'waft']\n",
      "['cart', 'hart', 'haft', 'raft']\n",
      "['cart', 'hart', 'halt', 'malt']\n",
      "['cart', 'hart', 'halt', 'halo']\n",
      "['cart', 'hart', 'halt', 'hall']\n",
      "['cart', 'hart', 'halt', 'salt']\n",
      "['cart', 'hart', 'halt', 'half']\n",
      "['cart', 'hart', 'halt', 'haft']\n",
      "['cart', 'hart', 'halt', 'hale']\n",
      "['cart', 'hart', 'halt', 'hilt']\n",
      "['cart', 'hart', 'mart', 'mare']\n",
      "['cart', 'hart', 'mart', 'malt']\n",
      "['cart', 'hart', 'mart', 'dart']\n",
      "['cart', 'hart', 'mart', 'mast']\n",
      "['cart', 'hart', 'mart', 'wart']\n",
      "['cart', 'hart', 'mart', 'tart']\n",
      "['cart', 'hart', 'mart', 'matt']\n",
      "['cart', 'hart', 'mart', 'mars']\n",
      "['cart', 'hart', 'mart', 'part']\n",
      "['cart', 'hart', 'mart', 'mark']\n",
      "['cart', 'hart', 'wart', 'wary']\n",
      "['cart', 'hart', 'wart', 'warn']\n",
      "['cart', 'hart', 'wart', 'warm']\n",
      "['cart', 'hart', 'wart', 'warp']\n",
      "['cart', 'hart', 'wart', 'wars']\n",
      "['cart', 'hart', 'wart', 'mart']\n",
      "['cart', 'hart', 'wart', 'watt']\n",
      "['cart', 'hart', 'wart', 'want']\n",
      "['cart', 'hart', 'wart', 'ware']\n",
      "['cart', 'hart', 'wart', 'tart']\n",
      "['cart', 'hart', 'wart', 'waft']\n",
      "['cart', 'hart', 'wart', 'dart']\n",
      "['cart', 'hart', 'wart', 'part']\n",
      "['cart', 'hart', 'wart', 'wait']\n",
      "['cart', 'hart', 'wart', 'ward']\n",
      "['cart', 'hart', 'hark', 'hard']\n",
      "['cart', 'hart', 'hark', 'harm']\n",
      "['cart', 'hart', 'hark', 'dark']\n",
      "['cart', 'hart', 'hark', 'hare']\n",
      "['cart', 'hart', 'hark', 'nark']\n",
      "['cart', 'hart', 'hark', 'bark']\n",
      "['cart', 'hart', 'hark', 'lark']\n",
      "['cart', 'hart', 'hark', 'hank']\n",
      "['cart', 'hart', 'hark', 'harp']\n",
      "['cart', 'hart', 'hark', 'park']\n",
      "['cart', 'hart', 'hark', 'hawk']\n",
      "['cart', 'hart', 'hark', 'hack']\n",
      "['cart', 'hart', 'hark', 'mark']\n",
      "['cart', 'hart', 'tart', 'tare']\n",
      "['cart', 'hart', 'tart', 'mart']\n",
      "['cart', 'hart', 'tart', 'wart']\n",
      "['cart', 'hart', 'tart', 'tars']\n",
      "['cart', 'hart', 'tart', 'taut']\n",
      "['cart', 'hart', 'tart', 'tarp']\n",
      "['cart', 'hart', 'tart', 'tact']\n",
      "['cart', 'hart', 'tart', 'tort']\n",
      "['cart', 'hart', 'tart', 'dart']\n",
      "['cart', 'hart', 'tart', 'part']\n",
      "['cart', 'hart', 'tart', 'taro']\n",
      "['cart', 'hart', 'harp', 'hard']\n",
      "['cart', 'hart', 'harp', 'harm']\n",
      "['cart', 'hart', 'harp', 'hare']\n",
      "['cart', 'hart', 'harp', 'warp']\n",
      "['cart', 'hart', 'harp', 'tarp']\n",
      "['cart', 'hart', 'harp', 'hark']\n",
      "['cart', 'hart', 'harp', 'hasp']\n",
      "['cart', 'hart', 'harp', 'carp']\n",
      "['cart', 'hart', 'dart', 'dirt']\n",
      "['cart', 'hart', 'dart', 'daft']\n",
      "['cart', 'hart', 'dart', 'dark']\n",
      "['cart', 'hart', 'dart', 'wart']\n",
      "['cart', 'hart', 'dart', 'mart']\n",
      "['cart', 'hart', 'dart', 'dare']\n",
      "['cart', 'hart', 'dart', 'darn']\n",
      "['cart', 'hart', 'dart', 'tart']\n",
      "['cart', 'hart', 'dart', 'part']\n",
      "['cart', 'hart', 'part', 'port']\n",
      "['cart', 'hart', 'part', 'pact']\n",
      "['cart', 'hart', 'part', 'pert']\n",
      "['cart', 'hart', 'part', 'pare']\n",
      "['cart', 'hart', 'part', 'past']\n",
      "['cart', 'hart', 'part', 'mart']\n",
      "['cart', 'hart', 'part', 'wart']\n",
      "['cart', 'hart', 'part', 'pars']\n",
      "['cart', 'hart', 'part', 'dart']\n",
      "['cart', 'hart', 'part', 'tart']\n",
      "['cart', 'hart', 'part', 'park']\n",
      "['cart', 'hart', 'part', 'pant']\n",
      "['cart', 'cars', 'bars', 'barb']\n",
      "['cart', 'cars', 'bars', 'bard']\n",
      "['cart', 'cars', 'bars', 'ears']\n",
      "['cart', 'cars', 'bars', 'bass']\n",
      "['cart', 'cars', 'bars', 'burs']\n",
      "['cart', 'cars', 'bars', 'mars']\n",
      "['cart', 'cars', 'bars', 'bays']\n",
      "['cart', 'cars', 'bars', 'baas']\n",
      "['cart', 'cars', 'bars', 'bark']\n",
      "['cart', 'cars', 'bars', 'bags']\n",
      "['cart', 'cars', 'bars', 'bans']\n",
      "['cart', 'cars', 'bars', 'oars']\n",
      "['cart', 'cars', 'bars', 'pars']\n",
      "['cart', 'cars', 'bars', 'tars']\n",
      "['cart', 'cars', 'bars', 'wars']\n",
      "['cart', 'cars', 'bars', 'barn']\n",
      "['cart', 'cars', 'bars', 'bats']\n",
      "['cart', 'cars', 'bars', 'bare']\n",
      "['cart', 'cars', 'bars', 'barf']\n",
      "['cart', 'cars', 'bars', 'jars']\n",
      "['cart', 'cars', 'ears', 'bars']\n",
      "['cart', 'cars', 'ears', 'eats']\n",
      "['cart', 'cars', 'ears', 'wars']\n",
      "['cart', 'cars', 'ears', 'earl']\n",
      "['cart', 'cars', 'ears', 'oars']\n",
      "['cart', 'cars', 'ears', 'pars']\n",
      "['cart', 'cars', 'ears', 'tars']\n",
      "['cart', 'cars', 'ears', 'errs']\n",
      "['cart', 'cars', 'ears', 'earn']\n",
      "['cart', 'cars', 'ears', 'mars']\n",
      "['cart', 'cars', 'ears', 'jars']\n",
      "['cart', 'cars', 'caps', 'maps']\n",
      "['cart', 'cars', 'caps', 'taps']\n",
      "['cart', 'cars', 'caps', 'laps']\n",
      "['cart', 'cars', 'caps', 'cape']\n",
      "['cart', 'cars', 'caps', 'saps']\n",
      "['cart', 'cars', 'caps', 'cops']\n",
      "['cart', 'cars', 'caps', 'cabs']\n",
      "['cart', 'cars', 'caps', 'cups']\n",
      "['cart', 'cars', 'caps', 'naps']\n",
      "['cart', 'cars', 'caps', 'raps']\n",
      "['cart', 'cars', 'caps', 'cams']\n",
      "['cart', 'cars', 'caps', 'cats']\n",
      "['cart', 'cars', 'caps', 'yaps']\n",
      "['cart', 'cars', 'caps', 'caws']\n",
      "['cart', 'cars', 'caps', 'cads']\n",
      "['cart', 'cars', 'caps', 'cans']\n",
      "['cart', 'cars', 'caps', 'zaps']\n",
      "['cart', 'cars', 'caps', 'paps']\n",
      "['cart', 'cars', 'caps', 'gaps']\n",
      "['cart', 'cars', 'wars', 'bars']\n",
      "['cart', 'cars', 'wars', 'wary']\n",
      "['cart', 'cars', 'wars', 'ears']\n",
      "['cart', 'cars', 'wars', 'warn']\n",
      "['cart', 'cars', 'wars', 'warm']\n",
      "['cart', 'cars', 'wars', 'warp']\n",
      "['cart', 'cars', 'wars', 'wart']\n",
      "['cart', 'cars', 'wars', 'oars']\n",
      "['cart', 'cars', 'wars', 'pars']\n",
      "['cart', 'cars', 'wars', 'tars']\n",
      "['cart', 'cars', 'wars', 'wags']\n",
      "['cart', 'cars', 'wars', 'ways']\n",
      "['cart', 'cars', 'wars', 'wads']\n",
      "['cart', 'cars', 'wars', 'ware']\n",
      "['cart', 'cars', 'wars', 'mars']\n",
      "['cart', 'cars', 'wars', 'ward']\n",
      "['cart', 'cars', 'wars', 'jars']\n",
      "['cart', 'cars', 'cabs', 'cubs']\n",
      "['cart', 'cars', 'cabs', 'labs']\n",
      "['cart', 'cars', 'cabs', 'caps']\n",
      "['cart', 'cars', 'cabs', 'cobs']\n",
      "['cart', 'cars', 'cabs', 'jabs']\n",
      "['cart', 'cars', 'cabs', 'cams']\n",
      "['cart', 'cars', 'cabs', 'cats']\n",
      "['cart', 'cars', 'cabs', 'caws']\n",
      "['cart', 'cars', 'cabs', 'tabs']\n",
      "['cart', 'cars', 'cabs', 'nabs']\n",
      "['cart', 'cars', 'cabs', 'dabs']\n",
      "['cart', 'cars', 'cabs', 'cads']\n",
      "['cart', 'cars', 'cabs', 'cans']\n",
      "['cart', 'cars', 'cabs', 'gabs']\n",
      "['cart', 'cars', 'oars', 'bars']\n",
      "['cart', 'cars', 'oars', 'ears']\n",
      "['cart', 'cars', 'oars', 'oaks']\n",
      "['cart', 'cars', 'oars', 'oafs']\n",
      "['cart', 'cars', 'oars', 'wars']\n",
      "['cart', 'cars', 'oars', 'oats']\n",
      "['cart', 'cars', 'oars', 'pars']\n",
      "['cart', 'cars', 'oars', 'tars']\n",
      "['cart', 'cars', 'oars', 'ours']\n",
      "['cart', 'cars', 'oars', 'mars']\n",
      "['cart', 'cars', 'oars', 'jars']\n",
      "['cart', 'cars', 'pars', 'pats']\n",
      "['cart', 'cars', 'pars', 'bars']\n",
      "['cart', 'cars', 'pars', 'ears']\n",
      "['cart', 'cars', 'pars', 'pals']\n",
      "['cart', 'cars', 'pars', 'pans']\n",
      "['cart', 'cars', 'pars', 'mars']\n",
      "['cart', 'cars', 'pars', 'pass']\n",
      "['cart', 'cars', 'pars', 'paws']\n",
      "['cart', 'cars', 'pars', 'pare']\n",
      "['cart', 'cars', 'pars', 'wars']\n",
      "['cart', 'cars', 'pars', 'oars']\n",
      "['cart', 'cars', 'pars', 'tars']\n",
      "['cart', 'cars', 'pars', 'paps']\n",
      "['cart', 'cars', 'pars', 'pays']\n",
      "['cart', 'cars', 'pars', 'park']\n",
      "['cart', 'cars', 'pars', 'part']\n",
      "['cart', 'cars', 'pars', 'jars']\n",
      "['cart', 'cars', 'pars', 'pads']\n",
      "['cart', 'cars', 'tars', 'tags']\n",
      "['cart', 'cars', 'tars', 'bars']\n",
      "['cart', 'cars', 'tars', 'tads']\n",
      "['cart', 'cars', 'tars', 'ears']\n",
      "['cart', 'cars', 'tars', 'taps']\n",
      "['cart', 'cars', 'tars', 'tare']\n",
      "['cart', 'cars', 'tars', 'tans']\n",
      "['cart', 'cars', 'tars', 'tors']\n",
      "['cart', 'cars', 'tars', 'oars']\n",
      "['cart', 'cars', 'tars', 'pars']\n",
      "['cart', 'cars', 'tars', 'tats']\n",
      "['cart', 'cars', 'tars', 'tams']\n",
      "['cart', 'cars', 'tars', 'tabs']\n",
      "['cart', 'cars', 'tars', 'tart']\n",
      "['cart', 'cars', 'tars', 'tarp']\n",
      "['cart', 'cars', 'tars', 'wars']\n",
      "['cart', 'cars', 'tars', 'mars']\n",
      "['cart', 'cars', 'tars', 'taro']\n",
      "['cart', 'cars', 'tars', 'jars']\n",
      "['cart', 'cars', 'card', 'hard']\n",
      "['cart', 'cars', 'card', 'bard']\n",
      "['cart', 'cars', 'card', 'lard']\n",
      "['cart', 'cars', 'card', 'curd']\n",
      "['cart', 'cars', 'card', 'carp']\n",
      "['cart', 'cars', 'card', 'care']\n",
      "['cart', 'cars', 'card', 'yard']\n",
      "['cart', 'cars', 'card', 'ward']\n",
      "['cart', 'cars', 'card', 'cord']\n",
      "['cart', 'cars', 'cams', 'came']\n",
      "['cart', 'cars', 'cams', 'rams']\n",
      "['cart', 'cars', 'cams', 'jams']\n",
      "['cart', 'cars', 'cams', 'caps']\n",
      "['cart', 'cars', 'cams', 'cums']\n",
      "['cart', 'cars', 'cams', 'lams']\n",
      "['cart', 'cars', 'cams', 'tams']\n",
      "['cart', 'cars', 'cams', 'camp']\n",
      "['cart', 'cars', 'cams', 'cabs']\n",
      "['cart', 'cars', 'cams', 'dams']\n",
      "['cart', 'cars', 'cams', 'cats']\n",
      "['cart', 'cars', 'cams', 'caws']\n",
      "['cart', 'cars', 'cams', 'cads']\n",
      "['cart', 'cars', 'cams', 'hams']\n",
      "['cart', 'cars', 'cams', 'cans']\n",
      "['cart', 'cars', 'cams', 'yams']\n",
      "['cart', 'cars', 'caws', 'saws']\n",
      "['cart', 'cars', 'caws', 'maws']\n",
      "['cart', 'cars', 'caws', 'haws']\n",
      "['cart', 'cars', 'caws', 'caps']\n",
      "['cart', 'cars', 'caws', 'paws']\n",
      "['cart', 'cars', 'caws', 'laws']\n",
      "['cart', 'cars', 'caws', 'cows']\n",
      "['cart', 'cars', 'caws', 'cabs']\n",
      "['cart', 'cars', 'caws', 'cams']\n",
      "['cart', 'cars', 'caws', 'cats']\n",
      "['cart', 'cars', 'caws', 'cads']\n",
      "['cart', 'cars', 'caws', 'cans']\n",
      "['cart', 'cars', 'caws', 'yaws']\n",
      "['cart', 'cars', 'caws', 'jaws']\n",
      "['cart', 'cars', 'cats', 'cots']\n",
      "['cart', 'cars', 'cats', 'eats']\n",
      "['cart', 'cars', 'cats', 'hats']\n",
      "['cart', 'cars', 'cats', 'caps']\n",
      "['cart', 'cars', 'cats', 'rats']\n",
      "['cart', 'cars', 'cats', 'cuts']\n",
      "['cart', 'cars', 'cats', 'fats']\n",
      "['cart', 'cars', 'cats', 'vats']\n",
      "['cart', 'cars', 'cats', 'cabs']\n",
      "['cart', 'cars', 'cats', 'oats']\n",
      "['cart', 'cars', 'cats', 'tats']\n",
      "['cart', 'cars', 'cats', 'cams']\n",
      "['cart', 'cars', 'cats', 'caws']\n",
      "['cart', 'cars', 'cats', 'cads']\n",
      "['cart', 'cars', 'cats', 'mats']\n",
      "['cart', 'cars', 'cats', 'bats']\n",
      "['cart', 'cars', 'cats', 'cans']\n",
      "['cart', 'cars', 'cats', 'lats']\n",
      "['cart', 'cars', 'cats', 'pats']\n",
      "['cart', 'cars', 'cads', 'tads']\n",
      "['cart', 'cars', 'cads', 'cods']\n",
      "['cart', 'cars', 'cads', 'caps']\n",
      "['cart', 'cars', 'cads', 'fads']\n",
      "['cart', 'cars', 'cads', 'dads']\n",
      "['cart', 'cars', 'cads', 'mads']\n",
      "['cart', 'cars', 'cads', 'lads']\n",
      "['cart', 'cars', 'cads', 'cuds']\n",
      "['cart', 'cars', 'cads', 'cabs']\n",
      "['cart', 'cars', 'cads', 'cams']\n",
      "['cart', 'cars', 'cads', 'wads']\n",
      "['cart', 'cars', 'cads', 'cats']\n",
      "['cart', 'cars', 'cads', 'caws']\n",
      "['cart', 'cars', 'cads', 'cans']\n",
      "['cart', 'cars', 'cads', 'gads']\n",
      "['cart', 'cars', 'cads', 'pads']\n",
      "['cart', 'cars', 'care', 'came']\n",
      "['cart', 'cars', 'care', 'hare']\n",
      "['cart', 'cars', 'care', 'cure']\n",
      "['cart', 'cars', 'care', 'card']\n",
      "['cart', 'cars', 'care', 'core']\n",
      "['cart', 'cars', 'care', 'cafe']\n",
      "['cart', 'cars', 'care', 'fare']\n",
      "['cart', 'cars', 'care', 'case']\n",
      "['cart', 'cars', 'care', 'cane']\n",
      "['cart', 'cars', 'care', 'bare']\n",
      "['cart', 'cars', 'care', 'cage']\n",
      "['cart', 'cars', 'care', 'carp']\n",
      "['cart', 'cars', 'care', 'cave']\n",
      "['cart', 'cars', 'care', 'cape']\n",
      "['cart', 'cars', 'care', 'pare']\n",
      "['cart', 'cars', 'care', 'ware']\n",
      "['cart', 'cars', 'care', 'mare']\n",
      "['cart', 'cars', 'care', 'cake']\n",
      "['cart', 'cars', 'care', 'rare']\n",
      "['cart', 'cars', 'care', 'tare']\n",
      "['cart', 'cars', 'care', 'dare']\n",
      "['cart', 'cars', 'cans', 'vans']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['cart', 'cars', 'cans', 'vans']"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bfs_search('cart', 'vans', debug=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['cart', 'care', 'cane', 'vane']"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bfs_search('cart', 'vane')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1494"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(dfs_search('cart', 'vane'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "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": 53,
   "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": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('cart', 'vane', debug=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "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": 55,
   "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": 55,
     "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": 69,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 23.9 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "candidates = [set([k] + list(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": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 25.9 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "candidates = set(frozenset({k}.union(neighbours[k])) for k in neighbours)\n",
    "reachables = set()\n",
    "while candidates:\n",
    "    current = set(candidates.pop())\n",
    "    remove_because_merged = set()\n",
    "    for other in candidates:\n",
    "        if current.intersection(other):\n",
    "            current.update(other)\n",
    "            remove_because_merged.add(other)\n",
    "    if remove_because_merged:\n",
    "        for rbm in remove_because_merged:\n",
    "            candidates.remove(rbm)\n",
    "        candidates.add(frozenset(current))\n",
    "    else:\n",
    "        reachables.add(frozenset(current))\n",
    "\n",
    "len(reachables)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2204"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(max(reachables, key=len))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(min(reachables, key=len))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({1: 75, 2: 6, 3: 7, 4: 2, 5: 2, 6: 1, 2204: 1})"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "collections.Counter(len(r) for r in reachables)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5]"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[len(r) for r in reachables if 'abbe' in r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[frozenset({'abbe', 'able', 'ably', 'ally', 'axle'})]"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[r for r in reachables if 'abbe' in r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[frozenset({'bevy', 'levy'}),\n",
       " frozenset({'ogle', 'ogre'}),\n",
       " frozenset({'demo', 'memo'}),\n",
       " frozenset({'crud', 'crux'}),\n",
       " frozenset({'thou', 'thru'}),\n",
       " frozenset({'idol', 'idyl'}),\n",
       " frozenset({'icon', 'ikon', 'iron'}),\n",
       " frozenset({'used', 'user', 'uses'}),\n",
       " frozenset({'opal', 'oral', 'oval'}),\n",
       " frozenset({'also', 'alto', 'auto'}),\n",
       " frozenset({'idle', 'idly', 'isle'}),\n",
       " frozenset({'afar', 'agar', 'ajar'}),\n",
       " frozenset({'eddy', 'edge', 'edgy'}),\n",
       " frozenset({'each', 'etch', 'inch', 'itch'}),\n",
       " frozenset({'high', 'nigh', 'sigh', 'sign'}),\n",
       " frozenset({'info', 'into', 'onto', 'undo', 'unto'}),\n",
       " frozenset({'abbe', 'able', 'ably', 'ally', 'axle'}),\n",
       " frozenset({'ache', 'achy', 'acme', 'acne', 'acre', 'ashy'})]"
      ]
     },
     "execution_count": 77,
     "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": 78,
   "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": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'; '.join(sorted(list(r)[0] for r in reachables if len(r) == 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['ache'] [['ache']]\n",
      "['ache', 'acne'] [['ache', 'acne'], ['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
      "['ache', 'acme'] [['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy'], ['ache', 'acne', 'acme'], ['ache', 'acne', 'acre']]\n",
      "['ache', 'acre'] [['ache', 'acre'], ['ache', 'achy'], ['ache', 'acne', 'acme'], ['ache', 'acne', 'acre'], ['ache', 'acme', 'acne'], ['ache', 'acme', 'acre']]\n",
      "['ache', 'achy'] [['ache', 'achy'], ['ache', 'acne', 'acme'], ['ache', 'acne', 'acre'], ['ache', 'acme', 'acne'], ['ache', 'acme', 'acre'], ['ache', 'acre', 'acne'], ['ache', 'acre', 'acme']]\n",
      "['ache', 'acne', 'acme'] [['ache', 'acne', 'acme'], ['ache', 'acne', 'acre'], ['ache', 'acme', 'acne'], ['ache', 'acme', 'acre'], ['ache', 'acre', 'acne'], ['ache', 'acre', 'acme'], ['ache', 'achy', 'ashy']]\n",
      "['ache', 'acne', 'acre'] [['ache', 'acne', 'acre'], ['ache', 'acme', 'acne'], ['ache', 'acme', 'acre'], ['ache', 'acre', 'acne'], ['ache', 'acre', 'acme'], ['ache', 'achy', 'ashy'], ['ache', 'acne', 'acme', 'acre']]\n",
      "['ache', 'acme', 'acne'] [['ache', 'acme', 'acne'], ['ache', 'acme', 'acre'], ['ache', 'acre', 'acne'], ['ache', 'acre', 'acme'], ['ache', 'achy', 'ashy'], ['ache', 'acne', 'acme', 'acre'], ['ache', 'acne', 'acre', 'acme']]\n",
      "['ache', 'acme', 'acre'] [['ache', 'acme', 'acre'], ['ache', 'acre', 'acne'], ['ache', 'acre', 'acme'], ['ache', 'achy', 'ashy'], ['ache', 'acne', 'acme', 'acre'], ['ache', 'acne', 'acre', 'acme'], ['ache', 'acme', 'acne', 'acre']]\n",
      "['ache', 'acre', 'acne'] [['ache', 'acre', 'acne'], ['ache', 'acre', 'acme'], ['ache', 'achy', 'ashy'], ['ache', 'acne', 'acme', 'acre'], ['ache', 'acne', 'acre', 'acme'], ['ache', 'acme', 'acne', 'acre'], ['ache', 'acme', 'acre', 'acne']]\n",
      "['ache', 'acre', 'acme'] [['ache', 'acre', 'acme'], ['ache', 'achy', 'ashy'], ['ache', 'acne', 'acme', 'acre'], ['ache', 'acne', 'acre', 'acme'], ['ache', 'acme', 'acne', 'acre'], ['ache', 'acme', 'acre', 'acne'], ['ache', 'acre', 'acne', 'acme']]\n",
      "['ache', 'achy', 'ashy'] [['ache', 'achy', 'ashy'], ['ache', 'acne', 'acme', 'acre'], ['ache', 'acne', 'acre', 'acme'], ['ache', 'acme', 'acne', 'acre'], ['ache', 'acme', 'acre', 'acne'], ['ache', 'acre', 'acne', 'acme'], ['ache', 'acre', 'acme', 'acne']]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['ache', 'achy', 'ashy']"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bfs_search('ache', 'ashy', debug=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['ache']]\n",
      "[['ache', 'acne'], ['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
      "[['ache', 'acne', 'acme'], ['ache', 'acne', 'acre'], ['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
      "[['ache', 'acne', 'acme', 'acre'], ['ache', 'acne', 'acre'], ['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
      "[['ache', 'acne', 'acre'], ['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
      "[['ache', 'acne', 'acre', 'acme'], ['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
      "[['ache', 'acme'], ['ache', 'acre'], ['ache', 'achy']]\n",
      "[['ache', 'acme', 'acne'], ['ache', 'acme', 'acre'], ['ache', 'acre'], ['ache', 'achy']]\n",
      "[['ache', 'acme', 'acne', 'acre'], ['ache', 'acme', 'acre'], ['ache', 'acre'], ['ache', 'achy']]\n",
      "[['ache', 'acme', 'acre'], ['ache', 'acre'], ['ache', 'achy']]\n",
      "[['ache', 'acme', 'acre', 'acne'], ['ache', 'acre'], ['ache', 'achy']]\n",
      "[['ache', 'acre'], ['ache', 'achy']]\n",
      "[['ache', 'acre', 'acne'], ['ache', 'acre', 'acme'], ['ache', 'achy']]\n",
      "[['ache', 'acre', 'acne', 'acme'], ['ache', 'acre', 'acme'], ['ache', 'achy']]\n",
      "[['ache', 'acre', 'acme'], ['ache', 'achy']]\n",
      "[['ache', 'acre', 'acme', 'acne'], ['ache', 'achy']]\n",
      "[['ache', 'achy']]\n",
      "[['ache', 'achy', 'ashy']]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['ache', 'achy', 'ashy']"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfs_search('ache', 'ashy', debug=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['buns', 'bunk', 'punk']"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('buns', 'punk')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "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": 81,
   "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": 82,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "bigset = max(reachables, key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['foil', 'boil', 'bail', 'ball', 'balk', 'bank', 'hank']\n",
      "['pint', 'pent', 'peat', 'meat', 'meal', 'mewl']\n",
      "['fuse', 'fuss', 'furs', 'ours']\n",
      "['plop', 'flop', 'flow', 'flew']\n",
      "['lull', 'bull', 'bell', 'belt', 'welt', 'wept', 'kept']\n",
      "['coma', 'coda', 'cods', 'cons', 'sons']\n",
      "['pits', 'bits', 'bats', 'bass', 'bash', 'rash']\n",
      "['bean', 'been', 'bees', 'beds', 'buds', 'suds']\n",
      "['yips', 'nips', 'nits', 'nite', 'note', 'vote']\n",
      "['pent', 'pens', 'yens']\n",
      "['crop', 'coop', 'coos', 'cons', 'cans', 'fans']\n",
      "['flop', 'clop', 'coop', 'cool', 'cowl', 'bowl', 'bawl']\n",
      "['hill', 'hull', 'hulk', 'sulk', 'suck']\n",
      "['aced', 'acid', 'arid', 'grid', 'grin', 'gain', 'rain']\n",
      "['land', 'sand', 'sans', 'suns', 'subs', 'hubs']\n",
      "['cogs', 'coos', 'cool', 'coal', 'foal', 'foam']\n",
      "['loss', 'moss', 'mods', 'nods', 'nous', 'yous']\n",
      "['soap', 'soar', 'boar', 'boas', 'bogs', 'jogs']\n",
      "['musk', 'must', 'bust', 'best', 'beet', 'beef']\n",
      "['fine', 'wine', 'wane', 'want', 'waft']\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": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['cops', 'coos', 'coon', 'coin', 'chin', 'thin', 'this', 'thus', 'thug']"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('cops', 'thug')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2204]"
      ]
     },
     "execution_count": 85,
     "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": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2204]"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[len(r) for r in reachables if 'stay' in r ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['hate', 'have', 'hove', 'love']"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('hate', 'love')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['wars', 'ware', 'wave', 'wove', 'love']"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('wars', 'love')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
      "Wall time: 199 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time len(astar_search('wars', 'love'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
      "Wall time: 210 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time len(astar_search_closed('wars', 'love'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 12 ms, sys: 0 ns, total: 12 ms\n",
      "Wall time: 13.5 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "272"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time len(dfs_search('wars', 'love'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# %time len(bfs_search('wars', 'love'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 724 ms, sys: 0 ns, total: 724 ms\n",
      "Wall time: 723 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time len(bfs_search_closed('wars', 'love'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['fear', 'feat', 'fest', 'lest', 'lost', 'lose', 'love']"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('fear', 'love')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['fail', 'fall', 'pall', 'pals', 'pass']"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('fail', 'pass')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['star', 'soar', 'boar', 'boor', 'boon', 'born']"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('star', 'born')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "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": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search('open', 'pass')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "frozenset({'bass',\n",
       "           'lass',\n",
       "           'mass',\n",
       "           'pads',\n",
       "           'pals',\n",
       "           'pans',\n",
       "           'paps',\n",
       "           'pars',\n",
       "           'past',\n",
       "           'pats',\n",
       "           'paws',\n",
       "           'pays',\n",
       "           'puss',\n",
       "           'sass'})"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbours['pass']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[len(r) for r in reachables if 'exam' in r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2204]"
      ]
     },
     "execution_count": 100,
     "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": 101,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 9.05 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search('bats', 'exit')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 147 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search_closed('bats', 'exit')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "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": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "astar_search_closed('bats', 'exit')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "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": 105,
   "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": 106,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 358 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "astar_search_closed('blab', 'amen')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 384 ms, sys: 0 ns, total: 384 ms\n",
      "Wall time: 382 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time len(astar_search_closed('blab', 'amen'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 112 ms, sys: 0 ns, total: 112 ms\n",
      "Wall time: 109 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time len(astar_search_closed('amen', 'doff'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 40 ms, sys: 0 ns, total: 40 ms\n",
      "Wall time: 36.5 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time len(astar_search_closed('chug', 'jinn'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 20 ms, sys: 0 ns, total: 20 ms\n",
      "Wall time: 18.1 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time len(astar_search_closed('amen', 'flog'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 272 ms, sys: 0 ns, total: 272 ms\n",
      "Wall time: 267 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time len(astar_search_closed('buzz', 'grog'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 40 ms, sys: 0 ns, total: 40 ms\n",
      "Wall time: 37.8 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time len(astar_search_closed('imps', 'pros'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "rush bush True\n",
      "bash bush True\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 113,
     "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": 114,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['gush', 'mush', 'bosh', 'tush', 'lush', 'push', 'hush']"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[w for w in neighbours['bush'] if w in nb_count]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('came', 2)"
      ]
     },
     "execution_count": 115,
     "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": 116,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'hags'"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'bash', 'rush'}"
      ]
     },
     "execution_count": 117,
     "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}