4 "cell_type": "markdown",
9 "\"Word chain\" puzzles are where you transform one word into another, by changing one letter at a time, with all the intermediate steps being valid words. \n",
11 "For instance, you can transform 'rash' to 'jags' like this:\n",
21 "(the capital letter is the one changed in each step).\n",
25 "Given this [list of words](words4.txt), what is the minimum number of steps to go from `vice` to `wars`?"
53 "output_type": "execute_result"
57 "words = [w.strip() for w in open('09-words.txt').readlines()]\n",
69 "def adjacents(word):\n",
70 " return [word[0:i] + l + word[i+1:]\n",
71 " for i in range(len(word))\n",
72 " for l in string.ascii_lowercase\n",
84 "neighbours = {w: [n for n in adjacents(w) if n in words]\n",
96 "def distance(w1, w2):\n",
97 " return sum(1 for i in range(len(w1))\n",
103 "execution_count": 8,
109 "# def extend(chain):\n",
110 "# return [chain + [s] for s in neighbours[chain[-1]]\n",
111 "# if s not in chain]"
116 "execution_count": 9,
122 "def extend(chain, closed=None):\n",
124 " nbrs = set(neighbours[chain[-1]]) - closed\n",
126 " nbrs = neighbours[chain[-1]]\n",
127 " return [chain + [s] for s in nbrs\n",
128 " if s not in chain]"
133 "execution_count": 10,
139 "def extend_raw(chain):\n",
140 " nbrs = [w for w in adjacents(chain[-1]) if w in words]\n",
141 " return [chain + [s] for s in nbrs\n",
142 " if s not in chain]"
147 "execution_count": 11,
153 "def bfs_search(start, goal, debug=False):\n",
154 " agenda = [[start]]\n",
155 " finished = False\n",
156 " while not finished and agenda:\n",
157 " current = agenda[0]\n",
160 " if current[-1] == goal:\n",
161 " finished = True\n",
163 " successors = extend(current)\n",
164 " agenda = agenda[1:] + successors\n",
173 "execution_count": 12,
179 "def bfs_search_closed(start, goal, debug=False):\n",
180 " agenda = [[start]]\n",
182 " finished = False\n",
183 " while not finished and agenda:\n",
184 " current = agenda[0]\n",
187 " if current[-1] == goal:\n",
188 " finished = True\n",
190 " closed.add(current[-1])\n",
191 " successors = extend(current, closed)\n",
192 " agenda = agenda[1:] + successors\n",
201 "execution_count": 13,
207 "def dfs_search(start, goal, debug=False):\n",
208 " agenda = [[start]]\n",
209 " finished = False\n",
210 " while not finished and agenda:\n",
211 " current = agenda[0]\n",
214 " if current[-1] == goal:\n",
215 " finished = True\n",
217 " successors = extend(current)\n",
218 " agenda = successors + agenda[1:]\n",
227 "execution_count": 14,
233 "def astar_search(start, goal, debug=False):\n",
234 " agenda = [(distance(start, goal), [start])]\n",
235 " heapq.heapify(agenda)\n",
236 " finished = False\n",
237 " while not finished and agenda:\n",
238 " _, current = heapq.heappop(agenda)\n",
241 " if current[-1] == goal:\n",
242 " finished = True\n",
244 " successors = extend(current)\n",
245 " for s in successors:\n",
246 " heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
255 "execution_count": 15,
261 "# Uses direct lookup of successors, rather than using cached neighbours in the dict\n",
262 "def astar_search_raw(start, goal, debug=False):\n",
263 " agenda = [(distance(start, goal), [start])]\n",
264 " heapq.heapify(agenda)\n",
265 " finished = False\n",
266 " while not finished and agenda:\n",
267 " _, current = heapq.heappop(agenda)\n",
270 " if current[-1] == goal:\n",
271 " finished = True\n",
273 " successors = extend_raw(current) # Difference here\n",
274 " for s in successors:\n",
275 " heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
284 "execution_count": 16,
290 "def astar_search_closed(start, goal, debug=False):\n",
291 " agenda = [(distance(start, goal), [start])]\n",
292 " heapq.heapify(agenda)\n",
294 " finished = False\n",
295 " while not finished and agenda:\n",
296 " _, current = heapq.heappop(agenda)\n",
299 " if current[-1] == goal:\n",
300 " finished = True\n",
302 " closed.add(current[-1])\n",
303 " successors = extend(current, closed)\n",
304 " for s in successors:\n",
305 " heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
314 "execution_count": 17,
320 "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
323 "execution_count": 17,
325 "output_type": "execute_result"
329 "astar_search('vice', 'wars')"
334 "execution_count": 18,
340 "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
343 "execution_count": 18,
345 "output_type": "execute_result"
349 "astar_search_raw('vice', 'wars')"
354 "execution_count": 19,
363 "execution_count": 19,
365 "output_type": "execute_result"
369 "len(astar_search('vice', 'wars'))"
374 "execution_count": 20,
383 "execution_count": 20,
385 "output_type": "execute_result"
389 "len(bfs_search('vice', 'wars'))"
394 "execution_count": 21,
403 "execution_count": 21,
405 "output_type": "execute_result"
409 "len(bfs_search_closed('vice', 'wars'))"
414 "execution_count": 22,
423 "execution_count": 22,
425 "output_type": "execute_result"
429 "len(dfs_search('vice', 'wars'))"
434 "execution_count": 23,
439 "output_type": "stream",
441 "10000 loops, best of 3: 157 µs per loop\n"
447 "astar_search('vice', 'wars')"
452 "execution_count": 24,
457 "output_type": "stream",
459 "100 loops, best of 3: 15.8 ms per loop\n"
465 "astar_search_raw('vice', 'wars')"
470 "execution_count": 25,
475 "output_type": "stream",
477 "10000 loops, best of 3: 170 µs per loop\n"
483 "astar_search_closed('vice', 'wars')"
488 "execution_count": 26,
493 "output_type": "stream",
495 "1 loop, best of 3: 1min 42s per loop\n"
501 "bfs_search('vice', 'wars')"
506 "execution_count": 27,
511 "output_type": "stream",
513 "1 loop, best of 3: 557 ms per loop\n"
519 "bfs_search_closed('vice', 'wars')"
524 "execution_count": 28,
529 "output_type": "stream",
531 "10 loops, best of 3: 87.9 ms per loop\n"
537 "dfs_search('vice', 'wars')"
541 "cell_type": "markdown",
546 "The example shows that `jags` is reachable in four steps from `rash`. There are 11 words one step away from `rash`: \n",
547 "`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, and `wash`. \n",
549 "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",
551 "There are 180 words reachable in up to three steps from `rash`.\n",
553 "How many words are reachable in up to ten steps from `vice`?"
558 "execution_count": 29,
564 "def reachable_in(word, n, trim_extras=False):\n",
565 " reachable = set()\n",
566 " boundary = set([word])\n",
567 " for i in range(n):\n",
569 " for w in boundary:\n",
570 " extras.update(neighbours[w])\n",
571 " if trim_extras:\n",
572 " extras.difference_update(reachable)\n",
573 " reachable.update(boundary)\n",
574 " boundary = extras.copy()\n",
575 " return reachable.union(extras).difference(set([word]))"
580 "execution_count": 30,
589 " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
592 "execution_count": 30,
594 "output_type": "execute_result"
598 "len(reachable_in('rash', 1)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 1)))"
603 "execution_count": 31,
612 " '`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`')"
615 "execution_count": 31,
617 "output_type": "execute_result"
621 "len(reachable_in('rash', 2)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 2)))"
626 "execution_count": 32,
637 "execution_count": 32,
639 "output_type": "execute_result"
643 "len(reachable_in('rash', 3))"
648 "execution_count": 33,
659 "execution_count": 33,
661 "output_type": "execute_result"
665 "len(reachable_in('rash', 10))"
670 "execution_count": 34,
681 "execution_count": 34,
683 "output_type": "execute_result"
687 "len(reachable_in('vice', 10))"
692 "execution_count": 35,
699 "output_type": "stream",
701 "100 loops, best of 3: 6.01 ms per loop\n"
707 "len(reachable_in('rash', 10))"
712 "execution_count": 36,
719 "output_type": "stream",
721 "100 loops, best of 3: 2.92 ms per loop\n"
727 "len(reachable_in('rash', 10, trim_extras=True))"
732 "execution_count": null,
742 "display_name": "Python 3",
743 "language": "python",
751 "file_extension": ".py",
752 "mimetype": "text/x-python",
754 "nbconvert_exporter": "python",
755 "pygments_lexer": "ipython3",