+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Visa woes\n",
+ "\n",
+ "It seems there's been a problem with your visa, and the authorities have only just noticed, even though you're coming to the end of your holiday. There's no option but to navigate the bowels of the Foreign Ministry, to find the right series of offices to visit.\n",
+ "\n",
+ "For some reason known only to themselves, all the offices have a four-letter code that just happens to be an English word. (All the ministry office codes are given in the file [08-rooms.txt](08-rooms.txt).) An office will give you the authorisation to move to a different office if the codes differ by just one letter. For instance, the authorisation from office `rash` will allow you to move to the office `bash` and you can move from `able` to `axle`.\n",
+ "\n",
+ "You can move from office `rash` to `jags` by visiting five offices in total:\n",
+ "\n",
+ "```\n",
+ "rash\n",
+ "Bash\n",
+ "basS\n",
+ "baGs\n",
+ "Jags\n",
+ "```\n",
+ "\n",
+ "where the capital letters indicate the changed letters in each step. There are other ways of getting from `rash` to `jags`, but there is no shorter route.\n",
+ "\n",
+ "# Part 1\n",
+ "\n",
+ "Including the offices at both ends, what is the smallest number of offices do you have to visit to get from `coax` to `stay`?"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "You may have found a route to your goal, but what if `stay` wasn't the right office? How many offices could you get in a few steps from a starting point?\n",
+ "\n",
+ "For example, there are 11 offices you can reach in one step from `rash`:\n",
+ "\n",
+ "`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`\n",
+ "\n",
+ "There are 47 distinct offices you could reach in up to two steps:\n",
+ "\n",
+ "`base`, `bash`, `bask`, `bass`, `bast`, `bath`, `bosh`, `bush`, `case`, `cash`, `cask`, `cast`, `dash`, `dish`, `gash`, `gasp`, `gosh`, `gush`, `hash`, `hasp`, `hath`, `hush`, `lash`, `lass`, `last`, `lath`, `lush`, `mash`, `mask`, `mass`, `mast`, `math`, `mesh`, `mush`, `push`, `ramp`, `rasp`, `ruse`, `rush`, `rusk`, `rust`, `sash`, `sass`, `tush`, `wash`, `wasp`, `wish`\n",
+ "\n",
+ "The there are 180 distinct offices reachable in up to three steps from `rash`.\n",
+ "\n",
+ "The ministry office codes are still given in the file [08-rooms.txt](08-rooms.txt).\n",
+ "\n",
+ "# Part 2\n",
+ "\n",
+ "How many different offices could you visit in no more than 10 steps from `coax`?"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "import string\n",
+ "import heapq"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2336"
+ ]
+ },
+ "execution_count": 3,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "words = [w.strip() for w in open('08-rooms.txt').readlines()]\n",
+ "len(words)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "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": 5,
+ "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": 6,
+ "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": 7,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# def extend(chain):\n",
+ "# return [chain + [s] for s in neighbours[chain[-1]]\n",
+ "# if s not in chain]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "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": 9,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def extend_raw(chain):\n",
+ " nbrs = [w for w in adjacents(chain[-1]) if w in words]\n",
+ " return [chain + [s] for s in nbrs\n",
+ " if s not in chain]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def bfs_search(start, goal, debug=False):\n",
+ " agenda = [[start]]\n",
+ " finished = False\n",
+ " while not finished and agenda:\n",
+ " current = agenda[0]\n",
+ " if debug:\n",
+ " print(current)\n",
+ " if current[-1] == goal:\n",
+ " finished = True\n",
+ " else:\n",
+ " successors = extend(current)\n",
+ " agenda = agenda[1:] + successors\n",
+ " if finished:\n",
+ " return current\n",
+ " else:\n",
+ " return None "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "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": 12,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def dfs_search(start, goal, debug=False):\n",
+ " agenda = [[start]]\n",
+ " finished = False\n",
+ " while not finished and agenda:\n",
+ " current = agenda[0]\n",
+ " if debug:\n",
+ " print(current)\n",
+ " if current[-1] == goal:\n",
+ " finished = True\n",
+ " else:\n",
+ " successors = extend(current)\n",
+ " agenda = successors + agenda[1:]\n",
+ " if finished:\n",
+ " return current\n",
+ " else:\n",
+ " return None "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "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": 14,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# Uses direct lookup of successors, rather than using cached neighbours in the dict\n",
+ "def astar_search_raw(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_raw(current) # Difference here\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": 15,
+ "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": 16,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
+ ]
+ },
+ "execution_count": 16,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "astar_search('vice', 'wars')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
+ ]
+ },
+ "execution_count": 17,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "astar_search_raw('vice', 'wars')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 18,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['boon', 'boot', 'bolt', 'belt', 'bell', 'sell']"
+ ]
+ },
+ "execution_count": 18,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "astar_search_raw('boon', 'sell')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "6"
+ ]
+ },
+ "execution_count": 19,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(astar_search('vice', 'wars'))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 20,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# len(bfs_search('vice', 'wars'))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 21,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "6"
+ ]
+ },
+ "execution_count": 21,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(bfs_search_closed('vice', 'wars'))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 22,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "793"
+ ]
+ },
+ "execution_count": 22,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(dfs_search('vice', 'wars'))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 23,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "10000 loops, best of 3: 157 µs per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "astar_search('vice', 'wars')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 24,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "100 loops, best of 3: 15.5 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "astar_search_raw('vice', 'wars')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 25,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "10000 loops, best of 3: 166 µs per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "astar_search_closed('vice', 'wars')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 26,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# %%timeit\n",
+ "# bfs_search('vice', 'wars')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 27,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 554 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "bfs_search_closed('vice', 'wars')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 28,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "10 loops, best of 3: 90.6 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "dfs_search('vice', 'wars')"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Part 2\n",
+ "\n",
+ "The example shows that `jags` is reachable in four steps from `rash`. There are 11 words one step away from `rash`: \n",
+ "`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, and `wash`. \n",
+ "\n",
+ "There are 47 words reachable in one or two steps from `rash`. They are `base`, `bash`, `bask`, `bass`, `bast`, `bath`, `bosh`, `bush`, `case`, `cash`, `cask`, `cast`, `dash`, `dish`, `gash`, `gasp`, `gosh`, `gush`, `hash`, `hasp`, `hath`, `hush`, `lash`, `lass`, `last`, `lath`, `lush`, `mash`, `mask`, `mass`, `mast`, `math`, `mesh`, `mush`, `push`, `ramp`, `rasp`, `ruse`, `rush`, `rusk`, `rust`, `sash`, `sass`, `tush`, `wash`, `wasp`, and `wish`.\n",
+ "\n",
+ "There are 180 words reachable in up to three steps from `rash`.\n",
+ "\n",
+ "How many words are reachable in up to ten steps from `vice`?"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 29,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def reachable_in(word, n, trim_extras=False):\n",
+ " reachable = set()\n",
+ " boundary = set([word])\n",
+ " for i in range(n):\n",
+ " extras = set()\n",
+ " for w in boundary:\n",
+ " extras.update(neighbours[w])\n",
+ " if trim_extras:\n",
+ " extras.difference_update(reachable)\n",
+ " reachable.update(boundary)\n",
+ " boundary = extras.copy()\n",
+ " return reachable.union(extras).difference(set([word]))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 30,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['bash',\n",
+ " 'cash',\n",
+ " 'dash',\n",
+ " 'gash',\n",
+ " 'hash',\n",
+ " 'lash',\n",
+ " 'mash',\n",
+ " 'sash',\n",
+ " 'wash',\n",
+ " 'rush',\n",
+ " 'rasp']"
+ ]
+ },
+ "execution_count": 30,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "neighbours['rash']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 31,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(11,\n",
+ " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
+ ]
+ },
+ "execution_count": 31,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('rash', 1)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 1)))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 32,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(11,\n",
+ " '<code>bash</code>, <code>cash</code>, <code>dash</code>, <code>gash</code>, <code>hash</code>, <code>lash</code>, <code>mash</code>, <code>rasp</code>, <code>rush</code>, <code>sash</code>, <code>wash</code>')"
+ ]
+ },
+ "execution_count": 32,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('rash', 1)), ', '.join(sorted('<code>{}</code>'.format(r) for r in reachable_in('rash', 1)))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 33,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(47,\n",
+ " '`base`, `bash`, `bask`, `bass`, `bast`, `bath`, `bosh`, `bush`, `case`, `cash`, `cask`, `cast`, `dash`, `dish`, `gash`, `gasp`, `gosh`, `gush`, `hash`, `hasp`, `hath`, `hush`, `lash`, `lass`, `last`, `lath`, `lush`, `mash`, `mask`, `mass`, `mast`, `math`, `mesh`, `mush`, `push`, `ramp`, `rasp`, `ruse`, `rush`, `rusk`, `rust`, `sash`, `sass`, `tush`, `wash`, `wasp`, `wish`')"
+ ]
+ },
+ "execution_count": 33,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('rash', 2)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 2)))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 34,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(47,\n",
+ " '<code>base</code>, <code>bash</code>, <code>bask</code>, <code>bass</code>, <code>bast</code>, <code>bath</code>, <code>bosh</code>, <code>bush</code>, <code>case</code>, <code>cash</code>, <code>cask</code>, <code>cast</code>, <code>dash</code>, <code>dish</code>, <code>gash</code>, <code>gasp</code>, <code>gosh</code>, <code>gush</code>, <code>hash</code>, <code>hasp</code>, <code>hath</code>, <code>hush</code>, <code>lash</code>, <code>lass</code>, <code>last</code>, <code>lath</code>, <code>lush</code>, <code>mash</code>, <code>mask</code>, <code>mass</code>, <code>mast</code>, <code>math</code>, <code>mesh</code>, <code>mush</code>, <code>push</code>, <code>ramp</code>, <code>rasp</code>, <code>ruse</code>, <code>rush</code>, <code>rusk</code>, <code>rust</code>, <code>sash</code>, <code>sass</code>, <code>tush</code>, <code>wash</code>, <code>wasp</code>, <code>wish</code>')"
+ ]
+ },
+ "execution_count": 34,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('rash', 2)), ', '.join(sorted('<code>{}</code>'.format(r) for r in reachable_in('rash', 2)))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 35,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "180"
+ ]
+ },
+ "execution_count": 35,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('rash', 3))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 36,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2195"
+ ]
+ },
+ "execution_count": 36,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('rash', 10))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 37,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2192"
+ ]
+ },
+ "execution_count": 37,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('vice', 10))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 38,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "100 loops, best of 3: 5.81 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "len(reachable_in('rash', 10))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 39,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "100 loops, best of 3: 2.71 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "len(reachable_in('rash', 10, trim_extras=True))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 40,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2188"
+ ]
+ },
+ "execution_count": 40,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('stay', 10))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 41,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2193"
+ ]
+ },
+ "execution_count": 41,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(reachable_in('coax', 10))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 42,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "280"
+ ]
+ },
+ "execution_count": 42,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "stay5 = reachable_in('stay', 4)\n",
+ "len(stay5)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 43,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "296"
+ ]
+ },
+ "execution_count": 43,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "extras = set()\n",
+ "for w in stay5:\n",
+ " extras.update(neighbours[w])\n",
+ "extras.difference_update(stay5)\n",
+ "len(extras)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 44,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'know step yeps test pout book beck poor boos veep teed gent saws dyer hemp soon deem legs bets twit whim belt rock well bled whet prop spec weep peed loan week clef feed lock yens vent doer less teem toot yews blur clue pert pegs brew flea trig vets sued felt perk bobs brat tens beef leap bloc shoo moan boob jeez suet sits rood drag goat stay chip fled fist than loot pets suck peek pled heel hair sill prep char knot lens meek trap jeep beet crew draw tell nets peep meet sows glue bees bent pelt whit need foot bran chop gram chew teen veil lent gees fret soft leis pent gets weed keen reek news prim drab wets sics deed bows pier akin pock geed grey bogs goad skis peck prod loam keep pens hoot best reed yous sewn been tram pest whom bout unit deep boot dual lees omit peel sues berm dock yock shes lets mock grow jell whip lean thin sots geek stem floe tees sort fees gout mead dram said twin prom bras bier heft foul root fell melt bops coup coot atop brad chin moot shoe sacs chit hell door lead feet boon bolt leaf bell bias eery goop reel text boom herd rent leek rend club self send sick term airs frog yell next czar plus mean brow foam crow troy nest heed dell load glib peps cent chow pees bend jock held tent soil poop moor sped emit boss fest crop mews knit tout crag knob grab thaw vial sack help jets very boys flue whir newt wiry beep room pews crab baas cock coop hock blue flee moat skid quit dial brag cell aloe grad hews went leak toad wees mewl coat dent'"
+ ]
+ },
+ "execution_count": 44,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "' '.join(extras)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 45,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']"
+ ]
+ },
+ "execution_count": 45,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "astar_search('coax', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 46,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "CPU times: user 620 ms, sys: 4 ms, total: 624 ms\n",
+ "Wall time: 624 ms\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "['coax', 'coat', 'chat', 'shat', 'spat', 'spay', 'stay']"
+ ]
+ },
+ "execution_count": 46,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "%time bfs_search_closed('coax', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 47,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# %time bfs_search('coax', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 48,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['czar', 'tzar', 'tear', 'sear', 'star', 'stay']"
+ ]
+ },
+ "execution_count": 48,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "astar_search('czar', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 49,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# %time bfs_search('czar', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 50,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "# %time bfs_search('coax', 'stay')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 79,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "185"
+ ]
+ },
+ "execution_count": 79,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "rushn = reachable_in('rush', 3)\n",
+ "rushn.add('rush')\n",
+ "len(rushn)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 80,
+ "metadata": {
+ "collapsed": true,
+ "scrolled": true
+ },
+ "outputs": [],
+ "source": [
+ "links = set()\n",
+ "for w in rushn:\n",
+ " for n in neighbours[w]:\n",
+ " if n in rushn:\n",
+ " links.add(frozenset((n, w)))\n",
+ "\n",
+ "with open('rush3.dot', 'w') as f:\n",
+ " f.write('graph g {\\n')\n",
+ " for l in links:\n",
+ " lt = tuple(l)\n",
+ " f.write('\"{}\" -- \"{}\";\\n'.format(lt[0], lt[1]))\n",
+ " f.write('}\\n')"
+ ]
+ },
+ {
+ "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 / commitdiff
