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('words4.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": 6,
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": 7,
122 "def extend_raw(chain):\n",
123 " nbrs = [w for w in adjacents(chain[-1]) if w in words]\n",
124 " return [chain + [s] for s in nbrs\n",
125 " if s not in chain]"
130 "execution_count": 8,
136 "def bfs_search(start, target, debug=False):\n",
137 " return bfs([[start]], target, debug=debug)"
142 "execution_count": 9,
148 "def bfs(agenda, goal, debug=False):\n",
149 " finished = False\n",
150 " while not finished and agenda:\n",
151 " current = agenda[0]\n",
154 " if current[-1] == goal:\n",
155 " finished = True\n",
157 " successors = extend(current)\n",
158 " agenda = agenda[1:] + successors\n",
167 "execution_count": 10,
173 "def dfs_search(start, target, debug=False):\n",
174 " return dfs([[start]], target, debug=debug)"
179 "execution_count": 11,
185 "def dfs(agenda, goal, debug=False):\n",
186 " finished = False\n",
187 " while not finished and agenda:\n",
188 " current = agenda[0]\n",
191 " if current[-1] == goal:\n",
192 " finished = True\n",
194 " successors = extend(current)\n",
195 " agenda = successors + agenda[1:]\n",
204 "execution_count": 12,
210 "def astar_search(start, target, debug=False):\n",
211 " agenda = [(distance(start, target), [start])]\n",
212 " heapq.heapify(agenda)\n",
213 " return astar(agenda, target, debug=debug)"
218 "execution_count": 13,
224 "def astar(agenda, goal, debug=False):\n",
225 " finished = False\n",
226 " while not finished and agenda:\n",
227 " _, current = heapq.heappop(agenda)\n",
230 " if current[-1] == goal:\n",
231 " finished = True\n",
233 " successors = extend(current)\n",
234 " for s in successors:\n",
235 " heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
244 "execution_count": 14,
250 "def astar_search_raw(start, target, debug=False):\n",
251 " agenda = [(distance(start, target), [start])]\n",
252 " heapq.heapify(agenda)\n",
253 " return astar_raw(agenda, target, debug=debug)"
258 "execution_count": 15,
264 "def astar_raw(agenda, goal, debug=False):\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)\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 "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
293 "execution_count": 16,
295 "output_type": "execute_result"
299 "astar_search('vice', 'wars')"
304 "execution_count": 17,
310 "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
313 "execution_count": 17,
315 "output_type": "execute_result"
319 "astar_search_raw('vice', 'wars')"
324 "execution_count": 18,
333 "execution_count": 18,
335 "output_type": "execute_result"
339 "len(astar_search('vice', 'wars'))"
344 "execution_count": 19,
353 "execution_count": 19,
355 "output_type": "execute_result"
359 "len(bfs_search('vice', 'wars'))"
364 "execution_count": 20,
373 "execution_count": 20,
375 "output_type": "execute_result"
379 "len(dfs_search('vice', 'wars'))"
384 "execution_count": 21,
389 "output_type": "stream",
391 "10000 loops, best of 3: 153 µs per loop\n"
397 "astar_search('vice', 'wars')"
402 "execution_count": 22,
407 "output_type": "stream",
409 "100 loops, best of 3: 15.8 ms per loop\n"
415 "astar_search_raw('vice', 'wars')"
420 "execution_count": 23,
425 "output_type": "stream",
427 "1 loop, best of 3: 1min 42s per loop\n"
433 "bfs_search('vice', 'wars')"
438 "execution_count": 24,
443 "output_type": "stream",
445 "10 loops, best of 3: 88 ms per loop\n"
451 "dfs_search('vice', 'wars')"
455 "cell_type": "markdown",
460 "The example shows that `jags` is reachable in four steps from `rash`. There are 11 words one step away from `rash`: \n",
461 "`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, and `wash`. \n",
463 "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",
465 "There are 180 words reachable in up to three steps from `rash`.\n",
467 "How many words are reachable in up to ten steps from `vice`?"
472 "execution_count": 25,
478 "def reachable_in(word, n, trim_extras=False):\n",
479 " reachable = set()\n",
480 " boundary = set([word])\n",
481 " for i in range(n):\n",
483 " for w in boundary:\n",
484 " extras.update(neighbours[w])\n",
485 " if trim_extras:\n",
486 " extras.difference_update(reachable)\n",
487 " reachable.update(boundary)\n",
488 " boundary = extras.copy()\n",
489 " return reachable.union(extras).difference(set([word]))"
494 "execution_count": 26,
503 " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
506 "execution_count": 26,
508 "output_type": "execute_result"
512 "len(reachable_in('rash', 1)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 1)))"
517 "execution_count": 27,
526 " '`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`')"
529 "execution_count": 27,
531 "output_type": "execute_result"
535 "len(reachable_in('rash', 2)), ', '.join(sorted('`{}`'.format(r) for r in reachable_in('rash', 2)))"
540 "execution_count": 28,
551 "execution_count": 28,
553 "output_type": "execute_result"
557 "len(reachable_in('rash', 3))"
562 "execution_count": 29,
573 "execution_count": 29,
575 "output_type": "execute_result"
579 "len(reachable_in('rash', 10))"
584 "execution_count": 30,
595 "execution_count": 30,
597 "output_type": "execute_result"
601 "len(reachable_in('vice', 10))"
606 "execution_count": 31,
613 "output_type": "stream",
615 "100 loops, best of 3: 5.96 ms per loop\n"
621 "len(reachable_in('rash', 10))"
626 "execution_count": 32,
633 "output_type": "stream",
635 "100 loops, best of 3: 2.75 ms per loop\n"
641 "len(reachable_in('rash', 10, trim_extras=True))"
646 "execution_count": null,
656 "display_name": "Python 3",
657 "language": "python",
665 "file_extension": ".py",
666 "mimetype": "text/x-python",
668 "nbconvert_exporter": "python",
669 "pygments_lexer": "ipython3",