projects / ou-summer-of-code-2017.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Merge branch 'master' of git.njae.me.uk:ou-programming-quiz
[ou-summer-of-code-2017.git] / 08-word-chains / explore-word-chain-4.ipynb
1 {
2 "cells": [
3 {
4 "cell_type": "code",
5 "execution_count": 1,
6 "metadata": {
7 "collapsed": true
8 },
9 "outputs": [],
10 "source": [
11 "import string\n",
12 "import heapq\n",
13 "import collections\n",
14 "import random"
15 ]
16 },
17 {
18 "cell_type": "code",
19 "execution_count": 2,
20 "metadata": {
21 "collapsed": false
22 },
23 "outputs": [
24 {
25 "data": {
26 "text/plain": [
27 "2336"
28 ]
29 },
30 "execution_count": 2,
31 "metadata": {},
32 "output_type": "execute_result"
33 }
34 ],
35 "source": [
36 "words = [w.strip() for w in open('08-words.txt').readlines()]\n",
37 "len(words)"
38 ]
39 },
40 {
41 "cell_type": "code",
42 "execution_count": 3,
43 "metadata": {
44 "collapsed": false
45 },
46 "outputs": [
47 {
48 "data": {
49 "text/plain": [
50 "['abbe',\n",
51 " 'abed',\n",
52 " 'abet',\n",
53 " 'able',\n",
54 " 'ably',\n",
55 " 'abut',\n",
56 " 'aced',\n",
57 " 'aces',\n",
58 " 'ache',\n",
59 " 'achy']"
60 ]
61 },
62 "execution_count": 3,
63 "metadata": {},
64 "output_type": "execute_result"
65 }
66 ],
67 "source": [
68 "words[:10]"
69 ]
70 },
71 {
72 "cell_type": "code",
73 "execution_count": 4,
74 "metadata": {
75 "collapsed": true
76 },
77 "outputs": [],
78 "source": [
79 "def adjacents_explicit(word):\n",
80 " neighbours = []\n",
81 " for i in range(len(word)):\n",
82 " for l in string.ascii_lowercase:\n",
83 " if l != word[i]:\n",
84 " neighbours.append(word[0:i] + l + word[i+1:])\n",
85 " return neighbours"
86 ]
87 },
88 {
89 "cell_type": "code",
90 "execution_count": 5,
91 "metadata": {
92 "collapsed": true
93 },
94 "outputs": [],
95 "source": [
96 "def adjacents(word):\n",
97 " return [word[0:i] + l + word[i+1:]\n",
98 " for i in range(len(word))\n",
99 " for l in string.ascii_lowercase\n",
100 " if l != word[i]]"
101 ]
102 },
103 {
104 "cell_type": "code",
105 "execution_count": 6,
106 "metadata": {
107 "collapsed": true
108 },
109 "outputs": [],
110 "source": [
111 "neighbours = {w: [n for n in adjacents(w) if n in words]\n",
112 " for w in words}"
113 ]
114 },
115 {
116 "cell_type": "code",
117 "execution_count": 7,
118 "metadata": {
119 "collapsed": false
120 },
121 "outputs": [
122 {
123 "data": {
124 "text/plain": [
125 "['able']"
126 ]
127 },
128 "execution_count": 7,
129 "metadata": {},
130 "output_type": "execute_result"
131 }
132 ],
133 "source": [
134 "neighbours['abbe']"
135 ]
136 },
137 {
138 "cell_type": "code",
139 "execution_count": 8,
140 "metadata": {
141 "collapsed": false
142 },
143 "outputs": [
144 {
145 "data": {
146 "text/plain": [
147 "['axle', 'abbe', 'ably']"
148 ]
149 },
150 "execution_count": 8,
151 "metadata": {},
152 "output_type": "execute_result"
153 }
154 ],
155 "source": [
156 "neighbours['able']"
157 ]
158 },
159 {
160 "cell_type": "code",
161 "execution_count": 9,
162 "metadata": {
163 "collapsed": true
164 },
165 "outputs": [],
166 "source": [
167 "def distance(w1, w2):\n",
168 " return sum(1 for i in range(len(w1))\n",
169 " if w1[i] != w2[i])"
170 ]
171 },
172 {
173 "cell_type": "code",
174 "execution_count": 10,
175 "metadata": {
176 "collapsed": false
177 },
178 "outputs": [
179 {
180 "data": {
181 "text/plain": [
182 "0"
183 ]
184 },
185 "execution_count": 10,
186 "metadata": {},
187 "output_type": "execute_result"
188 }
189 ],
190 "source": [
191 "distance('abbe', 'abbe')"
192 ]
193 },
194 {
195 "cell_type": "code",
196 "execution_count": 11,
197 "metadata": {
198 "collapsed": true
199 },
200 "outputs": [],
201 "source": [
202 "def extend(chain, closed=None):\n",
203 " if closed:\n",
204 " nbrs = set(neighbours[chain[-1]]) - closed\n",
205 " else:\n",
206 " nbrs = neighbours[chain[-1]]\n",
207 " return [chain + [s] for s in nbrs\n",
208 " if s not in chain]"
209 ]
210 },
211 {
212 "cell_type": "code",
213 "execution_count": 12,
214 "metadata": {
215 "collapsed": false
216 },
217 "outputs": [
218 {
219 "data": {
220 "text/plain": [
221 "[['abbe', 'able']]"
222 ]
223 },
224 "execution_count": 12,
225 "metadata": {},
226 "output_type": "execute_result"
227 }
228 ],
229 "source": [
230 "extend(['abbe'])"
231 ]
232 },
233 {
234 "cell_type": "code",
235 "execution_count": 13,
236 "metadata": {
237 "collapsed": false
238 },
239 "outputs": [
240 {
241 "data": {
242 "text/plain": [
243 "[['abbe', 'able', 'axle'], ['abbe', 'able', 'ably']]"
244 ]
245 },
246 "execution_count": 13,
247 "metadata": {},
248 "output_type": "execute_result"
249 }
250 ],
251 "source": [
252 "extend(['abbe', 'able'])"
253 ]
254 },
255 {
256 "cell_type": "code",
257 "execution_count": 14,
258 "metadata": {
259 "collapsed": false
260 },
261 "outputs": [
262 {
263 "data": {
264 "text/plain": [
265 "[['abbe', 'able', 'ably', 'ally']]"
266 ]
267 },
268 "execution_count": 14,
269 "metadata": {},
270 "output_type": "execute_result"
271 }
272 ],
273 "source": [
274 "extend(['abbe', 'able', 'ably'])"
275 ]
276 },
277 {
278 "cell_type": "code",
279 "execution_count": 15,
280 "metadata": {
281 "collapsed": true
282 },
283 "outputs": [],
284 "source": [
285 "def bfs_search(start, goal, debug=False):\n",
286 " agenda = [[start]]\n",
287 " finished = False\n",
288 " while not finished and agenda:\n",
289 " current = agenda[0]\n",
290 " if debug:\n",
291 " print(current)\n",
292 " if current[-1] == goal:\n",
293 " finished = True\n",
294 " else:\n",
295 " successors = extend(current)\n",
296 " agenda = agenda[1:] + successors\n",
297 " if agenda:\n",
298 " return current\n",
299 " else:\n",
300 " return None "
301 ]
302 },
303 {
304 "cell_type": "code",
305 "execution_count": 16,
306 "metadata": {
307 "collapsed": true
308 },
309 "outputs": [],
310 "source": [
311 "def bfs_search_closed(start, goal, debug=False):\n",
312 " agenda = [[start]]\n",
313 " closed = set()\n",
314 " finished = False\n",
315 " while not finished and agenda:\n",
316 " current = agenda[0]\n",
317 " if debug:\n",
318 " print(current)\n",
319 " if current[-1] == goal:\n",
320 " finished = True\n",
321 " else:\n",
322 " closed.add(current[-1])\n",
323 " successors = extend(current, closed)\n",
324 " agenda = agenda[1:] + successors\n",
325 " if agenda:\n",
326 " return current\n",
327 " else:\n",
328 " return None "
329 ]
330 },
331 {
332 "cell_type": "code",
333 "execution_count": 17,
334 "metadata": {
335 "collapsed": false
336 },
337 "outputs": [
338 {
339 "name": "stdout",
340 "output_type": "stream",
341 "text": [
342 "['abbe']\n",
343 "['abbe', 'able']\n",
344 "['abbe', 'able', 'axle']\n",
345 "['abbe', 'able', 'ably']\n",
346 "['abbe', 'able', 'ably', 'ally']\n"
347 ]
348 },
349 {
350 "data": {
351 "text/plain": [
352 "['abbe', 'able', 'ably', 'ally']"
353 ]
354 },
355 "execution_count": 17,
356 "metadata": {},
357 "output_type": "execute_result"
358 }
359 ],
360 "source": [
361 "bfs_search('abbe', 'ally', debug=True)"
362 ]
363 },
364 {
365 "cell_type": "code",
366 "execution_count": 18,
367 "metadata": {
368 "collapsed": true
369 },
370 "outputs": [],
371 "source": [
372 "def dfs_search(start, goal, debug=False):\n",
373 " agenda = [[start]]\n",
374 " finished = False\n",
375 " while not finished and agenda:\n",
376 " current = agenda[0]\n",
377 " if debug:\n",
378 " print(current)\n",
379 " if current[-1] == goal:\n",
380 " finished = True\n",
381 " else:\n",
382 " successors = extend(current)\n",
383 " agenda = successors + agenda[1:]\n",
384 " if agenda:\n",
385 " return current\n",
386 " else:\n",
387 " return None "
388 ]
389 },
390 {
391 "cell_type": "code",
392 "execution_count": 19,
393 "metadata": {
394 "collapsed": false
395 },
396 "outputs": [
397 {
398 "name": "stdout",
399 "output_type": "stream",
400 "text": [
401 "['abbe']\n",
402 "['abbe', 'able']\n",
403 "['abbe', 'able', 'axle']\n",
404 "['abbe', 'able', 'ably']\n",
405 "['abbe', 'able', 'ably', 'ally']\n"
406 ]
407 },
408 {
409 "data": {
410 "text/plain": [
411 "['abbe', 'able', 'ably', 'ally']"
412 ]
413 },
414 "execution_count": 19,
415 "metadata": {},
416 "output_type": "execute_result"
417 }
418 ],
419 "source": [
420 "dfs_search('abbe', 'ally', debug=True)"
421 ]
422 },
423 {
424 "cell_type": "code",
425 "execution_count": 20,
426 "metadata": {
427 "collapsed": false
428 },
429 "outputs": [
430 {
431 "name": "stdout",
432 "output_type": "stream",
433 "text": [
434 "['cart']\n",
435 "['cart', 'dart']\n",
436 "['cart', 'hart']\n",
437 "['cart', 'mart']\n",
438 "['cart', 'part']\n",
439 "['cart', 'tart']\n",
440 "['cart', 'wart']\n",
441 "['cart', 'curt']\n",
442 "['cart', 'cant']\n",
443 "['cart', 'cast']\n",
444 "['cart', 'card']\n",
445 "['cart', 'care']\n",
446 "['cart', 'carp']\n",
447 "['cart', 'cars']\n",
448 "['cart', 'dart', 'hart']\n",
449 "['cart', 'dart', 'mart']\n",
450 "['cart', 'dart', 'part']\n",
451 "['cart', 'dart', 'tart']\n",
452 "['cart', 'dart', 'wart']\n",
453 "['cart', 'dart', 'dirt']\n",
454 "['cart', 'dart', 'daft']\n",
455 "['cart', 'dart', 'dare']\n",
456 "['cart', 'dart', 'dark']\n",
457 "['cart', 'dart', 'darn']\n",
458 "['cart', 'hart', 'dart']\n",
459 "['cart', 'hart', 'mart']\n",
460 "['cart', 'hart', 'part']\n",
461 "['cart', 'hart', 'tart']\n",
462 "['cart', 'hart', 'wart']\n",
463 "['cart', 'hart', 'hurt']\n",
464 "['cart', 'hart', 'haft']\n",
465 "['cart', 'hart', 'halt']\n",
466 "['cart', 'hart', 'hard']\n",
467 "['cart', 'hart', 'hare']\n",
468 "['cart', 'hart', 'hark']\n",
469 "['cart', 'hart', 'harm']\n",
470 "['cart', 'hart', 'harp']\n",
471 "['cart', 'mart', 'dart']\n",
472 "['cart', 'mart', 'hart']\n",
473 "['cart', 'mart', 'part']\n",
474 "['cart', 'mart', 'tart']\n",
475 "['cart', 'mart', 'wart']\n",
476 "['cart', 'mart', 'malt']\n",
477 "['cart', 'mart', 'mast']\n",
478 "['cart', 'mart', 'matt']\n",
479 "['cart', 'mart', 'mare']\n",
480 "['cart', 'mart', 'mark']\n",
481 "['cart', 'mart', 'mars']\n",
482 "['cart', 'part', 'dart']\n",
483 "['cart', 'part', 'hart']\n",
484 "['cart', 'part', 'mart']\n",
485 "['cart', 'part', 'tart']\n",
486 "['cart', 'part', 'wart']\n",
487 "['cart', 'part', 'pert']\n",
488 "['cart', 'part', 'port']\n",
489 "['cart', 'part', 'pact']\n",
490 "['cart', 'part', 'pant']\n",
491 "['cart', 'part', 'past']\n",
492 "['cart', 'part', 'pare']\n",
493 "['cart', 'part', 'park']\n",
494 "['cart', 'part', 'pars']\n",
495 "['cart', 'tart', 'dart']\n",
496 "['cart', 'tart', 'hart']\n",
497 "['cart', 'tart', 'mart']\n",
498 "['cart', 'tart', 'part']\n",
499 "['cart', 'tart', 'wart']\n",
500 "['cart', 'tart', 'tort']\n",
501 "['cart', 'tart', 'tact']\n",
502 "['cart', 'tart', 'taut']\n",
503 "['cart', 'tart', 'tare']\n",
504 "['cart', 'tart', 'taro']\n",
505 "['cart', 'tart', 'tarp']\n",
506 "['cart', 'tart', 'tars']\n",
507 "['cart', 'wart', 'dart']\n",
508 "['cart', 'wart', 'hart']\n",
509 "['cart', 'wart', 'mart']\n",
510 "['cart', 'wart', 'part']\n",
511 "['cart', 'wart', 'tart']\n",
512 "['cart', 'wart', 'waft']\n",
513 "['cart', 'wart', 'wait']\n",
514 "['cart', 'wart', 'want']\n",
515 "['cart', 'wart', 'watt']\n",
516 "['cart', 'wart', 'ward']\n",
517 "['cart', 'wart', 'ware']\n",
518 "['cart', 'wart', 'warm']\n",
519 "['cart', 'wart', 'warn']\n",
520 "['cart', 'wart', 'warp']\n",
521 "['cart', 'wart', 'wars']\n",
522 "['cart', 'wart', 'wary']\n",
523 "['cart', 'curt', 'hurt']\n",
524 "['cart', 'curt', 'cult']\n",
525 "['cart', 'curt', 'curb']\n",
526 "['cart', 'curt', 'curd']\n",
527 "['cart', 'curt', 'cure']\n",
528 "['cart', 'curt', 'curl']\n",
529 "['cart', 'curt', 'curs']\n",
530 "['cart', 'cant', 'pant']\n",
531 "['cart', 'cant', 'rant']\n",
532 "['cart', 'cant', 'want']\n",
533 "['cart', 'cant', 'cent']\n",
534 "['cart', 'cant', 'cast']\n",
535 "['cart', 'cant', 'cane']\n",
536 "['cart', 'cant', 'cans']\n",
537 "['cart', 'cast', 'bast']\n",
538 "['cart', 'cast', 'east']\n",
539 "['cart', 'cast', 'fast']\n",
540 "['cart', 'cast', 'last']\n",
541 "['cart', 'cast', 'mast']\n",
542 "['cart', 'cast', 'past']\n",
543 "['cart', 'cast', 'vast']\n",
544 "['cart', 'cast', 'cost']\n",
545 "['cart', 'cast', 'cyst']\n",
546 "['cart', 'cast', 'cant']\n",
547 "['cart', 'cast', 'case']\n",
548 "['cart', 'cast', 'cash']\n",
549 "['cart', 'cast', 'cask']\n",
550 "['cart', 'card', 'bard']\n",
551 "['cart', 'card', 'hard']\n",
552 "['cart', 'card', 'lard']\n",
553 "['cart', 'card', 'ward']\n",
554 "['cart', 'card', 'yard']\n",
555 "['cart', 'card', 'cord']\n",
556 "['cart', 'card', 'curd']\n",
557 "['cart', 'card', 'care']\n",
558 "['cart', 'card', 'carp']\n",
559 "['cart', 'card', 'cars']\n",
560 "['cart', 'care', 'bare']\n",
561 "['cart', 'care', 'dare']\n",
562 "['cart', 'care', 'fare']\n",
563 "['cart', 'care', 'hare']\n",
564 "['cart', 'care', 'mare']\n",
565 "['cart', 'care', 'pare']\n",
566 "['cart', 'care', 'rare']\n",
567 "['cart', 'care', 'tare']\n",
568 "['cart', 'care', 'ware']\n",
569 "['cart', 'care', 'core']\n",
570 "['cart', 'care', 'cure']\n",
571 "['cart', 'care', 'cafe']\n",
572 "['cart', 'care', 'cage']\n",
573 "['cart', 'care', 'cake']\n",
574 "['cart', 'care', 'came']\n",
575 "['cart', 'care', 'cane']\n",
576 "['cart', 'care', 'cape']\n",
577 "['cart', 'care', 'case']\n",
578 "['cart', 'care', 'cave']\n",
579 "['cart', 'care', 'card']\n",
580 "['cart', 'care', 'carp']\n",
581 "['cart', 'care', 'cars']\n",
582 "['cart', 'carp', 'harp']\n",
583 "['cart', 'carp', 'tarp']\n",
584 "['cart', 'carp', 'warp']\n",
585 "['cart', 'carp', 'camp']\n",
586 "['cart', 'carp', 'card']\n",
587 "['cart', 'carp', 'care']\n",
588 "['cart', 'carp', 'cars']\n",
589 "['cart', 'cars', 'bars']\n",
590 "['cart', 'cars', 'ears']\n",
591 "['cart', 'cars', 'jars']\n",
592 "['cart', 'cars', 'mars']\n",
593 "['cart', 'cars', 'oars']\n",
594 "['cart', 'cars', 'pars']\n",
595 "['cart', 'cars', 'tars']\n",
596 "['cart', 'cars', 'wars']\n",
597 "['cart', 'cars', 'curs']\n",
598 "['cart', 'cars', 'cabs']\n",
599 "['cart', 'cars', 'cads']\n",
600 "['cart', 'cars', 'cams']\n",
601 "['cart', 'cars', 'cans']\n",
602 "['cart', 'cars', 'caps']\n",
603 "['cart', 'cars', 'cats']\n",
604 "['cart', 'cars', 'caws']\n",
605 "['cart', 'cars', 'card']\n",
606 "['cart', 'cars', 'care']\n",
607 "['cart', 'cars', 'carp']\n",
608 "['cart', 'dart', 'hart', 'mart']\n",
609 "['cart', 'dart', 'hart', 'part']\n",
610 "['cart', 'dart', 'hart', 'tart']\n",
611 "['cart', 'dart', 'hart', 'wart']\n",
612 "['cart', 'dart', 'hart', 'hurt']\n",
613 "['cart', 'dart', 'hart', 'haft']\n",
614 "['cart', 'dart', 'hart', 'halt']\n",
615 "['cart', 'dart', 'hart', 'hard']\n",
616 "['cart', 'dart', 'hart', 'hare']\n",
617 "['cart', 'dart', 'hart', 'hark']\n",
618 "['cart', 'dart', 'hart', 'harm']\n",
619 "['cart', 'dart', 'hart', 'harp']\n",
620 "['cart', 'dart', 'mart', 'hart']\n",
621 "['cart', 'dart', 'mart', 'part']\n",
622 "['cart', 'dart', 'mart', 'tart']\n",
623 "['cart', 'dart', 'mart', 'wart']\n",
624 "['cart', 'dart', 'mart', 'malt']\n",
625 "['cart', 'dart', 'mart', 'mast']\n",
626 "['cart', 'dart', 'mart', 'matt']\n",
627 "['cart', 'dart', 'mart', 'mare']\n",
628 "['cart', 'dart', 'mart', 'mark']\n",
629 "['cart', 'dart', 'mart', 'mars']\n",
630 "['cart', 'dart', 'part', 'hart']\n",
631 "['cart', 'dart', 'part', 'mart']\n",
632 "['cart', 'dart', 'part', 'tart']\n",
633 "['cart', 'dart', 'part', 'wart']\n",
634 "['cart', 'dart', 'part', 'pert']\n",
635 "['cart', 'dart', 'part', 'port']\n",
636 "['cart', 'dart', 'part', 'pact']\n",
637 "['cart', 'dart', 'part', 'pant']\n",
638 "['cart', 'dart', 'part', 'past']\n",
639 "['cart', 'dart', 'part', 'pare']\n",
640 "['cart', 'dart', 'part', 'park']\n",
641 "['cart', 'dart', 'part', 'pars']\n",
642 "['cart', 'dart', 'tart', 'hart']\n",
643 "['cart', 'dart', 'tart', 'mart']\n",
644 "['cart', 'dart', 'tart', 'part']\n",
645 "['cart', 'dart', 'tart', 'wart']\n",
646 "['cart', 'dart', 'tart', 'tort']\n",
647 "['cart', 'dart', 'tart', 'tact']\n",
648 "['cart', 'dart', 'tart', 'taut']\n",
649 "['cart', 'dart', 'tart', 'tare']\n",
650 "['cart', 'dart', 'tart', 'taro']\n",
651 "['cart', 'dart', 'tart', 'tarp']\n",
652 "['cart', 'dart', 'tart', 'tars']\n",
653 "['cart', 'dart', 'wart', 'hart']\n",
654 "['cart', 'dart', 'wart', 'mart']\n",
655 "['cart', 'dart', 'wart', 'part']\n",
656 "['cart', 'dart', 'wart', 'tart']\n",
657 "['cart', 'dart', 'wart', 'waft']\n",
658 "['cart', 'dart', 'wart', 'wait']\n",
659 "['cart', 'dart', 'wart', 'want']\n",
660 "['cart', 'dart', 'wart', 'watt']\n",
661 "['cart', 'dart', 'wart', 'ward']\n",
662 "['cart', 'dart', 'wart', 'ware']\n",
663 "['cart', 'dart', 'wart', 'warm']\n",
664 "['cart', 'dart', 'wart', 'warn']\n",
665 "['cart', 'dart', 'wart', 'warp']\n",
666 "['cart', 'dart', 'wart', 'wars']\n",
667 "['cart', 'dart', 'wart', 'wary']\n",
668 "['cart', 'dart', 'dirt', 'girt']\n",
669 "['cart', 'dart', 'dirt', 'diet']\n",
670 "['cart', 'dart', 'dirt', 'dint']\n",
671 "['cart', 'dart', 'dirt', 'dire']\n",
672 "['cart', 'dart', 'dirt', 'dirk']\n",
673 "['cart', 'dart', 'daft', 'haft']\n",
674 "['cart', 'dart', 'daft', 'raft']\n",
675 "['cart', 'dart', 'daft', 'waft']\n",
676 "['cart', 'dart', 'daft', 'deft']\n",
677 "['cart', 'dart', 'dare', 'bare']\n",
678 "['cart', 'dart', 'dare', 'care']\n",
679 "['cart', 'dart', 'dare', 'fare']\n",
680 "['cart', 'dart', 'dare', 'hare']\n",
681 "['cart', 'dart', 'dare', 'mare']\n",
682 "['cart', 'dart', 'dare', 'pare']\n",
683 "['cart', 'dart', 'dare', 'rare']\n",
684 "['cart', 'dart', 'dare', 'tare']\n",
685 "['cart', 'dart', 'dare', 'ware']\n",
686 "['cart', 'dart', 'dare', 'dire']\n",
687 "['cart', 'dart', 'dare', 'dale']\n",
688 "['cart', 'dart', 'dare', 'dame']\n",
689 "['cart', 'dart', 'dare', 'date']\n",
690 "['cart', 'dart', 'dare', 'daze']\n",
691 "['cart', 'dart', 'dare', 'dark']\n",
692 "['cart', 'dart', 'dare', 'darn']\n",
693 "['cart', 'dart', 'dark', 'bark']\n",
694 "['cart', 'dart', 'dark', 'hark']\n",
695 "['cart', 'dart', 'dark', 'lark']\n",
696 "['cart', 'dart', 'dark', 'mark']\n",
697 "['cart', 'dart', 'dark', 'nark']\n",
698 "['cart', 'dart', 'dark', 'park']\n",
699 "['cart', 'dart', 'dark', 'dirk']\n",
700 "['cart', 'dart', 'dark', 'dork']\n",
701 "['cart', 'dart', 'dark', 'dank']\n",
702 "['cart', 'dart', 'dark', 'dare']\n",
703 "['cart', 'dart', 'dark', 'darn']\n",
704 "['cart', 'dart', 'darn', 'barn']\n",
705 "['cart', 'dart', 'darn', 'earn']\n",
706 "['cart', 'dart', 'darn', 'warn']\n",
707 "['cart', 'dart', 'darn', 'yarn']\n",
708 "['cart', 'dart', 'darn', 'damn']\n",
709 "['cart', 'dart', 'darn', 'dawn']\n",
710 "['cart', 'dart', 'darn', 'dare']\n",
711 "['cart', 'dart', 'darn', 'dark']\n",
712 "['cart', 'hart', 'dart', 'mart']\n",
713 "['cart', 'hart', 'dart', 'part']\n",
714 "['cart', 'hart', 'dart', 'tart']\n",
715 "['cart', 'hart', 'dart', 'wart']\n",
716 "['cart', 'hart', 'dart', 'dirt']\n",
717 "['cart', 'hart', 'dart', 'daft']\n",
718 "['cart', 'hart', 'dart', 'dare']\n",
719 "['cart', 'hart', 'dart', 'dark']\n",
720 "['cart', 'hart', 'dart', 'darn']\n",
721 "['cart', 'hart', 'mart', 'dart']\n",
722 "['cart', 'hart', 'mart', 'part']\n",
723 "['cart', 'hart', 'mart', 'tart']\n",
724 "['cart', 'hart', 'mart', 'wart']\n",
725 "['cart', 'hart', 'mart', 'malt']\n",
726 "['cart', 'hart', 'mart', 'mast']\n",
727 "['cart', 'hart', 'mart', 'matt']\n",
728 "['cart', 'hart', 'mart', 'mare']\n",
729 "['cart', 'hart', 'mart', 'mark']\n",
730 "['cart', 'hart', 'mart', 'mars']\n",
731 "['cart', 'hart', 'part', 'dart']\n",
732 "['cart', 'hart', 'part', 'mart']\n",
733 "['cart', 'hart', 'part', 'tart']\n",
734 "['cart', 'hart', 'part', 'wart']\n",
735 "['cart', 'hart', 'part', 'pert']\n",
736 "['cart', 'hart', 'part', 'port']\n",
737 "['cart', 'hart', 'part', 'pact']\n",
738 "['cart', 'hart', 'part', 'pant']\n",
739 "['cart', 'hart', 'part', 'past']\n",
740 "['cart', 'hart', 'part', 'pare']\n",
741 "['cart', 'hart', 'part', 'park']\n",
742 "['cart', 'hart', 'part', 'pars']\n",
743 "['cart', 'hart', 'tart', 'dart']\n",
744 "['cart', 'hart', 'tart', 'mart']\n",
745 "['cart', 'hart', 'tart', 'part']\n",
746 "['cart', 'hart', 'tart', 'wart']\n",
747 "['cart', 'hart', 'tart', 'tort']\n",
748 "['cart', 'hart', 'tart', 'tact']\n",
749 "['cart', 'hart', 'tart', 'taut']\n",
750 "['cart', 'hart', 'tart', 'tare']\n",
751 "['cart', 'hart', 'tart', 'taro']\n",
752 "['cart', 'hart', 'tart', 'tarp']\n",
753 "['cart', 'hart', 'tart', 'tars']\n",
754 "['cart', 'hart', 'wart', 'dart']\n",
755 "['cart', 'hart', 'wart', 'mart']\n",
756 "['cart', 'hart', 'wart', 'part']\n",
757 "['cart', 'hart', 'wart', 'tart']\n",
758 "['cart', 'hart', 'wart', 'waft']\n",
759 "['cart', 'hart', 'wart', 'wait']\n",
760 "['cart', 'hart', 'wart', 'want']\n",
761 "['cart', 'hart', 'wart', 'watt']\n",
762 "['cart', 'hart', 'wart', 'ward']\n",
763 "['cart', 'hart', 'wart', 'ware']\n",
764 "['cart', 'hart', 'wart', 'warm']\n",
765 "['cart', 'hart', 'wart', 'warn']\n",
766 "['cart', 'hart', 'wart', 'warp']\n",
767 "['cart', 'hart', 'wart', 'wars']\n",
768 "['cart', 'hart', 'wart', 'wary']\n",
769 "['cart', 'hart', 'hurt', 'curt']\n",
770 "['cart', 'hart', 'hurt', 'hunt']\n",
771 "['cart', 'hart', 'hurt', 'hurl']\n",
772 "['cart', 'hart', 'haft', 'daft']\n",
773 "['cart', 'hart', 'haft', 'raft']\n",
774 "['cart', 'hart', 'haft', 'waft']\n",
775 "['cart', 'hart', 'haft', 'heft']\n",
776 "['cart', 'hart', 'haft', 'halt']\n",
777 "['cart', 'hart', 'halt', 'malt']\n",
778 "['cart', 'hart', 'halt', 'salt']\n",
779 "['cart', 'hart', 'halt', 'hilt']\n",
780 "['cart', 'hart', 'halt', 'haft']\n",
781 "['cart', 'hart', 'halt', 'hale']\n",
782 "['cart', 'hart', 'halt', 'half']\n",
783 "['cart', 'hart', 'halt', 'hall']\n",
784 "['cart', 'hart', 'halt', 'halo']\n",
785 "['cart', 'hart', 'hard', 'bard']\n",
786 "['cart', 'hart', 'hard', 'card']\n",
787 "['cart', 'hart', 'hard', 'lard']\n",
788 "['cart', 'hart', 'hard', 'ward']\n",
789 "['cart', 'hart', 'hard', 'yard']\n",
790 "['cart', 'hart', 'hard', 'herd']\n",
791 "['cart', 'hart', 'hard', 'hand']\n",
792 "['cart', 'hart', 'hard', 'hare']\n",
793 "['cart', 'hart', 'hard', 'hark']\n",
794 "['cart', 'hart', 'hard', 'harm']\n",
795 "['cart', 'hart', 'hard', 'harp']\n",
796 "['cart', 'hart', 'hare', 'bare']\n",
797 "['cart', 'hart', 'hare', 'care']\n",
798 "['cart', 'hart', 'hare', 'dare']\n",
799 "['cart', 'hart', 'hare', 'fare']\n",
800 "['cart', 'hart', 'hare', 'mare']\n",
801 "['cart', 'hart', 'hare', 'pare']\n",
802 "['cart', 'hart', 'hare', 'rare']\n",
803 "['cart', 'hart', 'hare', 'tare']\n",
804 "['cart', 'hart', 'hare', 'ware']\n",
805 "['cart', 'hart', 'hare', 'here']\n",
806 "['cart', 'hart', 'hare', 'hire']\n",
807 "['cart', 'hart', 'hare', 'hake']\n",
808 "['cart', 'hart', 'hare', 'hale']\n",
809 "['cart', 'hart', 'hare', 'hate']\n",
810 "['cart', 'hart', 'hare', 'have']\n",
811 "['cart', 'hart', 'hare', 'haze']\n",
812 "['cart', 'hart', 'hare', 'hard']\n",
813 "['cart', 'hart', 'hare', 'hark']\n",
814 "['cart', 'hart', 'hare', 'harm']\n",
815 "['cart', 'hart', 'hare', 'harp']\n",
816 "['cart', 'hart', 'hark', 'bark']\n",
817 "['cart', 'hart', 'hark', 'dark']\n",
818 "['cart', 'hart', 'hark', 'lark']\n",
819 "['cart', 'hart', 'hark', 'mark']\n",
820 "['cart', 'hart', 'hark', 'nark']\n",
821 "['cart', 'hart', 'hark', 'park']\n",
822 "['cart', 'hart', 'hark', 'hack']\n",
823 "['cart', 'hart', 'hark', 'hank']\n",
824 "['cart', 'hart', 'hark', 'hawk']\n",
825 "['cart', 'hart', 'hark', 'hard']\n",
826 "['cart', 'hart', 'hark', 'hare']\n",
827 "['cart', 'hart', 'hark', 'harm']\n",
828 "['cart', 'hart', 'hark', 'harp']\n",
829 "['cart', 'hart', 'harm', 'farm']\n",
830 "['cart', 'hart', 'harm', 'warm']\n",
831 "['cart', 'hart', 'harm', 'hard']\n",
832 "['cart', 'hart', 'harm', 'hare']\n",
833 "['cart', 'hart', 'harm', 'hark']\n",
834 "['cart', 'hart', 'harm', 'harp']\n",
835 "['cart', 'hart', 'harp', 'carp']\n",
836 "['cart', 'hart', 'harp', 'tarp']\n",
837 "['cart', 'hart', 'harp', 'warp']\n",
838 "['cart', 'hart', 'harp', 'hasp']\n",
839 "['cart', 'hart', 'harp', 'hard']\n",
840 "['cart', 'hart', 'harp', 'hare']\n",
841 "['cart', 'hart', 'harp', 'hark']\n",
842 "['cart', 'hart', 'harp', 'harm']\n",
843 "['cart', 'mart', 'dart', 'hart']\n",
844 "['cart', 'mart', 'dart', 'part']\n",
845 "['cart', 'mart', 'dart', 'tart']\n",
846 "['cart', 'mart', 'dart', 'wart']\n",
847 "['cart', 'mart', 'dart', 'dirt']\n",
848 "['cart', 'mart', 'dart', 'daft']\n",
849 "['cart', 'mart', 'dart', 'dare']\n",
850 "['cart', 'mart', 'dart', 'dark']\n",
851 "['cart', 'mart', 'dart', 'darn']\n",
852 "['cart', 'mart', 'hart', 'dart']\n",
853 "['cart', 'mart', 'hart', 'part']\n",
854 "['cart', 'mart', 'hart', 'tart']\n",
855 "['cart', 'mart', 'hart', 'wart']\n",
856 "['cart', 'mart', 'hart', 'hurt']\n",
857 "['cart', 'mart', 'hart', 'haft']\n",
858 "['cart', 'mart', 'hart', 'halt']\n",
859 "['cart', 'mart', 'hart', 'hard']\n",
860 "['cart', 'mart', 'hart', 'hare']\n",
861 "['cart', 'mart', 'hart', 'hark']\n",
862 "['cart', 'mart', 'hart', 'harm']\n",
863 "['cart', 'mart', 'hart', 'harp']\n",
864 "['cart', 'mart', 'part', 'dart']\n",
865 "['cart', 'mart', 'part', 'hart']\n",
866 "['cart', 'mart', 'part', 'tart']\n",
867 "['cart', 'mart', 'part', 'wart']\n",
868 "['cart', 'mart', 'part', 'pert']\n",
869 "['cart', 'mart', 'part', 'port']\n",
870 "['cart', 'mart', 'part', 'pact']\n",
871 "['cart', 'mart', 'part', 'pant']\n",
872 "['cart', 'mart', 'part', 'past']\n",
873 "['cart', 'mart', 'part', 'pare']\n",
874 "['cart', 'mart', 'part', 'park']\n",
875 "['cart', 'mart', 'part', 'pars']\n",
876 "['cart', 'mart', 'tart', 'dart']\n",
877 "['cart', 'mart', 'tart', 'hart']\n",
878 "['cart', 'mart', 'tart', 'part']\n",
879 "['cart', 'mart', 'tart', 'wart']\n",
880 "['cart', 'mart', 'tart', 'tort']\n",
881 "['cart', 'mart', 'tart', 'tact']\n",
882 "['cart', 'mart', 'tart', 'taut']\n",
883 "['cart', 'mart', 'tart', 'tare']\n",
884 "['cart', 'mart', 'tart', 'taro']\n",
885 "['cart', 'mart', 'tart', 'tarp']\n",
886 "['cart', 'mart', 'tart', 'tars']\n",
887 "['cart', 'mart', 'wart', 'dart']\n",
888 "['cart', 'mart', 'wart', 'hart']\n",
889 "['cart', 'mart', 'wart', 'part']\n",
890 "['cart', 'mart', 'wart', 'tart']\n",
891 "['cart', 'mart', 'wart', 'waft']\n",
892 "['cart', 'mart', 'wart', 'wait']\n",
893 "['cart', 'mart', 'wart', 'want']\n",
894 "['cart', 'mart', 'wart', 'watt']\n",
895 "['cart', 'mart', 'wart', 'ward']\n",
896 "['cart', 'mart', 'wart', 'ware']\n",
897 "['cart', 'mart', 'wart', 'warm']\n",
898 "['cart', 'mart', 'wart', 'warn']\n",
899 "['cart', 'mart', 'wart', 'warp']\n",
900 "['cart', 'mart', 'wart', 'wars']\n",
901 "['cart', 'mart', 'wart', 'wary']\n",
902 "['cart', 'mart', 'malt', 'halt']\n",
903 "['cart', 'mart', 'malt', 'salt']\n",
904 "['cart', 'mart', 'malt', 'melt']\n",
905 "['cart', 'mart', 'malt', 'mast']\n",
906 "['cart', 'mart', 'malt', 'matt']\n",
907 "['cart', 'mart', 'malt', 'male']\n",
908 "['cart', 'mart', 'malt', 'mall']\n",
909 "['cart', 'mart', 'mast', 'bast']\n",
910 "['cart', 'mart', 'mast', 'cast']\n",
911 "['cart', 'mart', 'mast', 'east']\n",
912 "['cart', 'mart', 'mast', 'fast']\n",
913 "['cart', 'mart', 'mast', 'last']\n",
914 "['cart', 'mart', 'mast', 'past']\n",
915 "['cart', 'mart', 'mast', 'vast']\n",
916 "['cart', 'mart', 'mast', 'mist']\n",
917 "['cart', 'mart', 'mast', 'most']\n",
918 "['cart', 'mart', 'mast', 'must']\n",
919 "['cart', 'mart', 'mast', 'malt']\n",
920 "['cart', 'mart', 'mast', 'matt']\n",
921 "['cart', 'mart', 'mast', 'mash']\n",
922 "['cart', 'mart', 'mast', 'mask']\n",
923 "['cart', 'mart', 'mast', 'mass']\n",
924 "['cart', 'mart', 'matt', 'watt']\n",
925 "['cart', 'mart', 'matt', 'mitt']\n",
926 "['cart', 'mart', 'matt', 'mutt']\n",
927 "['cart', 'mart', 'matt', 'malt']\n",
928 "['cart', 'mart', 'matt', 'mast']\n",
929 "['cart', 'mart', 'matt', 'mate']\n",
930 "['cart', 'mart', 'matt', 'math']\n",
931 "['cart', 'mart', 'matt', 'mats']\n",
932 "['cart', 'mart', 'mare', 'bare']\n",
933 "['cart', 'mart', 'mare', 'care']\n",
934 "['cart', 'mart', 'mare', 'dare']\n",
935 "['cart', 'mart', 'mare', 'fare']\n",
936 "['cart', 'mart', 'mare', 'hare']\n",
937 "['cart', 'mart', 'mare', 'pare']\n",
938 "['cart', 'mart', 'mare', 'rare']\n",
939 "['cart', 'mart', 'mare', 'tare']\n",
940 "['cart', 'mart', 'mare', 'ware']\n",
941 "['cart', 'mart', 'mare', 'mere']\n",
942 "['cart', 'mart', 'mare', 'mire']\n",
943 "['cart', 'mart', 'mare', 'more']\n",
944 "['cart', 'mart', 'mare', 'mace']\n",
945 "['cart', 'mart', 'mare', 'made']\n",
946 "['cart', 'mart', 'mare', 'make']\n",
947 "['cart', 'mart', 'mare', 'male']\n",
948 "['cart', 'mart', 'mare', 'mane']\n",
949 "['cart', 'mart', 'mare', 'mate']\n",
950 "['cart', 'mart', 'mare', 'maze']\n",
951 "['cart', 'mart', 'mare', 'mark']\n",
952 "['cart', 'mart', 'mare', 'mars']\n",
953 "['cart', 'mart', 'mark', 'bark']\n",
954 "['cart', 'mart', 'mark', 'dark']\n",
955 "['cart', 'mart', 'mark', 'hark']\n",
956 "['cart', 'mart', 'mark', 'lark']\n",
957 "['cart', 'mart', 'mark', 'nark']\n",
958 "['cart', 'mart', 'mark', 'park']\n",
959 "['cart', 'mart', 'mark', 'murk']\n",
960 "['cart', 'mart', 'mark', 'mask']\n",
961 "['cart', 'mart', 'mark', 'mare']\n",
962 "['cart', 'mart', 'mark', 'mars']\n",
963 "['cart', 'mart', 'mars', 'bars']\n",
964 "['cart', 'mart', 'mars', 'cars']\n",
965 "['cart', 'mart', 'mars', 'ears']\n",
966 "['cart', 'mart', 'mars', 'jars']\n",
967 "['cart', 'mart', 'mars', 'oars']\n",
968 "['cart', 'mart', 'mars', 'pars']\n",
969 "['cart', 'mart', 'mars', 'tars']\n",
970 "['cart', 'mart', 'mars', 'wars']\n",
971 "['cart', 'mart', 'mars', 'mads']\n",
972 "['cart', 'mart', 'mars', 'mans']\n",
973 "['cart', 'mart', 'mars', 'maps']\n",
974 "['cart', 'mart', 'mars', 'mass']\n",
975 "['cart', 'mart', 'mars', 'mats']\n",
976 "['cart', 'mart', 'mars', 'maws']\n",
977 "['cart', 'mart', 'mars', 'mare']\n",
978 "['cart', 'mart', 'mars', 'mark']\n",
979 "['cart', 'part', 'dart', 'hart']\n",
980 "['cart', 'part', 'dart', 'mart']\n",
981 "['cart', 'part', 'dart', 'tart']\n",
982 "['cart', 'part', 'dart', 'wart']\n",
983 "['cart', 'part', 'dart', 'dirt']\n",
984 "['cart', 'part', 'dart', 'daft']\n",
985 "['cart', 'part', 'dart', 'dare']\n",
986 "['cart', 'part', 'dart', 'dark']\n",
987 "['cart', 'part', 'dart', 'darn']\n",
988 "['cart', 'part', 'hart', 'dart']\n",
989 "['cart', 'part', 'hart', 'mart']\n",
990 "['cart', 'part', 'hart', 'tart']\n",
991 "['cart', 'part', 'hart', 'wart']\n",
992 "['cart', 'part', 'hart', 'hurt']\n",
993 "['cart', 'part', 'hart', 'haft']\n",
994 "['cart', 'part', 'hart', 'halt']\n",
995 "['cart', 'part', 'hart', 'hard']\n",
996 "['cart', 'part', 'hart', 'hare']\n",
997 "['cart', 'part', 'hart', 'hark']\n",
998 "['cart', 'part', 'hart', 'harm']\n",
999 "['cart', 'part', 'hart', 'harp']\n",
1000 "['cart', 'part', 'mart', 'dart']\n",
1001 "['cart', 'part', 'mart', 'hart']\n",
1002 "['cart', 'part', 'mart', 'tart']\n",
1003 "['cart', 'part', 'mart', 'wart']\n",
1004 "['cart', 'part', 'mart', 'malt']\n",
1005 "['cart', 'part', 'mart', 'mast']\n",
1006 "['cart', 'part', 'mart', 'matt']\n",
1007 "['cart', 'part', 'mart', 'mare']\n",
1008 "['cart', 'part', 'mart', 'mark']\n",
1009 "['cart', 'part', 'mart', 'mars']\n",
1010 "['cart', 'part', 'tart', 'dart']\n",
1011 "['cart', 'part', 'tart', 'hart']\n",
1012 "['cart', 'part', 'tart', 'mart']\n",
1013 "['cart', 'part', 'tart', 'wart']\n",
1014 "['cart', 'part', 'tart', 'tort']\n",
1015 "['cart', 'part', 'tart', 'tact']\n",
1016 "['cart', 'part', 'tart', 'taut']\n",
1017 "['cart', 'part', 'tart', 'tare']\n",
1018 "['cart', 'part', 'tart', 'taro']\n",
1019 "['cart', 'part', 'tart', 'tarp']\n",
1020 "['cart', 'part', 'tart', 'tars']\n",
1021 "['cart', 'part', 'wart', 'dart']\n",
1022 "['cart', 'part', 'wart', 'hart']\n",
1023 "['cart', 'part', 'wart', 'mart']\n",
1024 "['cart', 'part', 'wart', 'tart']\n",
1025 "['cart', 'part', 'wart', 'waft']\n",
1026 "['cart', 'part', 'wart', 'wait']\n",
1027 "['cart', 'part', 'wart', 'want']\n",
1028 "['cart', 'part', 'wart', 'watt']\n",
1029 "['cart', 'part', 'wart', 'ward']\n",
1030 "['cart', 'part', 'wart', 'ware']\n",
1031 "['cart', 'part', 'wart', 'warm']\n",
1032 "['cart', 'part', 'wart', 'warn']\n",
1033 "['cart', 'part', 'wart', 'warp']\n",
1034 "['cart', 'part', 'wart', 'wars']\n",
1035 "['cart', 'part', 'wart', 'wary']\n",
1036 "['cart', 'part', 'pert', 'port']\n",
1037 "['cart', 'part', 'pert', 'peat']\n",
1038 "['cart', 'part', 'pert', 'pelt']\n",
1039 "['cart', 'part', 'pert', 'pent']\n",
1040 "['cart', 'part', 'pert', 'pest']\n",
1041 "['cart', 'part', 'pert', 'perk']\n",
1042 "['cart', 'part', 'pert', 'perm']\n",
1043 "['cart', 'part', 'port', 'fort']\n",
1044 "['cart', 'part', 'port', 'sort']\n",
1045 "['cart', 'part', 'port', 'tort']\n",
1046 "['cart', 'part', 'port', 'pert']\n",
1047 "['cart', 'part', 'port', 'poet']\n",
1048 "['cart', 'part', 'port', 'post']\n",
1049 "['cart', 'part', 'port', 'pout']\n",
1050 "['cart', 'part', 'port', 'pore']\n",
1051 "['cart', 'part', 'port', 'pork']\n",
1052 "['cart', 'part', 'port', 'porn']\n",
1053 "['cart', 'part', 'pact', 'fact']\n",
1054 "['cart', 'part', 'pact', 'tact']\n",
1055 "['cart', 'part', 'pact', 'pant']\n",
1056 "['cart', 'part', 'pact', 'past']\n",
1057 "['cart', 'part', 'pact', 'pace']\n",
1058 "['cart', 'part', 'pact', 'pack']\n",
1059 "['cart', 'part', 'pant', 'cant']\n",
1060 "['cart', 'part', 'pant', 'rant']\n",
1061 "['cart', 'part', 'pant', 'want']\n",
1062 "['cart', 'part', 'pant', 'pent']\n",
1063 "['cart', 'part', 'pant', 'pint']\n",
1064 "['cart', 'part', 'pant', 'punt']\n",
1065 "['cart', 'part', 'pant', 'pact']\n",
1066 "['cart', 'part', 'pant', 'past']\n",
1067 "['cart', 'part', 'pant', 'pane']\n",
1068 "['cart', 'part', 'pant', 'pang']\n",
1069 "['cart', 'part', 'pant', 'pans']\n",
1070 "['cart', 'part', 'past', 'bast']\n",
1071 "['cart', 'part', 'past', 'cast']\n",
1072 "['cart', 'part', 'past', 'east']\n",
1073 "['cart', 'part', 'past', 'fast']\n",
1074 "['cart', 'part', 'past', 'last']\n",
1075 "['cart', 'part', 'past', 'mast']\n",
1076 "['cart', 'part', 'past', 'vast']\n",
1077 "['cart', 'part', 'past', 'pest']\n",
1078 "['cart', 'part', 'past', 'post']\n",
1079 "['cart', 'part', 'past', 'psst']\n",
1080 "['cart', 'part', 'past', 'pact']\n",
1081 "['cart', 'part', 'past', 'pant']\n",
1082 "['cart', 'part', 'past', 'pass']\n",
1083 "['cart', 'part', 'pare', 'bare']\n",
1084 "['cart', 'part', 'pare', 'care']\n",
1085 "['cart', 'part', 'pare', 'dare']\n",
1086 "['cart', 'part', 'pare', 'fare']\n",
1087 "['cart', 'part', 'pare', 'hare']\n",
1088 "['cart', 'part', 'pare', 'mare']\n",
1089 "['cart', 'part', 'pare', 'rare']\n",
1090 "['cart', 'part', 'pare', 'tare']\n",
1091 "['cart', 'part', 'pare', 'ware']\n",
1092 "['cart', 'part', 'pare', 'pore']\n",
1093 "['cart', 'part', 'pare', 'pure']\n",
1094 "['cart', 'part', 'pare', 'pyre']\n",
1095 "['cart', 'part', 'pare', 'pace']\n",
1096 "['cart', 'part', 'pare', 'page']\n",
1097 "['cart', 'part', 'pare', 'pale']\n",
1098 "['cart', 'part', 'pare', 'pane']\n",
1099 "['cart', 'part', 'pare', 'pate']\n",
1100 "['cart', 'part', 'pare', 'pave']\n",
1101 "['cart', 'part', 'pare', 'park']\n",
1102 "['cart', 'part', 'pare', 'pars']\n",
1103 "['cart', 'part', 'park', 'bark']\n",
1104 "['cart', 'part', 'park', 'dark']\n",
1105 "['cart', 'part', 'park', 'hark']\n",
1106 "['cart', 'part', 'park', 'lark']\n",
1107 "['cart', 'part', 'park', 'mark']\n",
1108 "['cart', 'part', 'park', 'nark']\n",
1109 "['cart', 'part', 'park', 'perk']\n",
1110 "['cart', 'part', 'park', 'pork']\n",
1111 "['cart', 'part', 'park', 'pack']\n",
1112 "['cart', 'part', 'park', 'pare']\n",
1113 "['cart', 'part', 'park', 'pars']\n",
1114 "['cart', 'part', 'pars', 'bars']\n",
1115 "['cart', 'part', 'pars', 'cars']\n",
1116 "['cart', 'part', 'pars', 'ears']\n",
1117 "['cart', 'part', 'pars', 'jars']\n",
1118 "['cart', 'part', 'pars', 'mars']\n",
1119 "['cart', 'part', 'pars', 'oars']\n",
1120 "['cart', 'part', 'pars', 'tars']\n",
1121 "['cart', 'part', 'pars', 'wars']\n",
1122 "['cart', 'part', 'pars', 'pads']\n",
1123 "['cart', 'part', 'pars', 'pals']\n",
1124 "['cart', 'part', 'pars', 'pans']\n",
1125 "['cart', 'part', 'pars', 'paps']\n",
1126 "['cart', 'part', 'pars', 'pass']\n",
1127 "['cart', 'part', 'pars', 'pats']\n",
1128 "['cart', 'part', 'pars', 'paws']\n",
1129 "['cart', 'part', 'pars', 'pays']\n",
1130 "['cart', 'part', 'pars', 'pare']\n",
1131 "['cart', 'part', 'pars', 'park']\n",
1132 "['cart', 'tart', 'dart', 'hart']\n",
1133 "['cart', 'tart', 'dart', 'mart']\n",
1134 "['cart', 'tart', 'dart', 'part']\n",
1135 "['cart', 'tart', 'dart', 'wart']\n",
1136 "['cart', 'tart', 'dart', 'dirt']\n",
1137 "['cart', 'tart', 'dart', 'daft']\n",
1138 "['cart', 'tart', 'dart', 'dare']\n",
1139 "['cart', 'tart', 'dart', 'dark']\n",
1140 "['cart', 'tart', 'dart', 'darn']\n",
1141 "['cart', 'tart', 'hart', 'dart']\n",
1142 "['cart', 'tart', 'hart', 'mart']\n",
1143 "['cart', 'tart', 'hart', 'part']\n",
1144 "['cart', 'tart', 'hart', 'wart']\n",
1145 "['cart', 'tart', 'hart', 'hurt']\n",
1146 "['cart', 'tart', 'hart', 'haft']\n",
1147 "['cart', 'tart', 'hart', 'halt']\n",
1148 "['cart', 'tart', 'hart', 'hard']\n",
1149 "['cart', 'tart', 'hart', 'hare']\n",
1150 "['cart', 'tart', 'hart', 'hark']\n",
1151 "['cart', 'tart', 'hart', 'harm']\n",
1152 "['cart', 'tart', 'hart', 'harp']\n",
1153 "['cart', 'tart', 'mart', 'dart']\n",
1154 "['cart', 'tart', 'mart', 'hart']\n",
1155 "['cart', 'tart', 'mart', 'part']\n",
1156 "['cart', 'tart', 'mart', 'wart']\n",
1157 "['cart', 'tart', 'mart', 'malt']\n",
1158 "['cart', 'tart', 'mart', 'mast']\n",
1159 "['cart', 'tart', 'mart', 'matt']\n",
1160 "['cart', 'tart', 'mart', 'mare']\n",
1161 "['cart', 'tart', 'mart', 'mark']\n",
1162 "['cart', 'tart', 'mart', 'mars']\n",
1163 "['cart', 'tart', 'part', 'dart']\n",
1164 "['cart', 'tart', 'part', 'hart']\n",
1165 "['cart', 'tart', 'part', 'mart']\n",
1166 "['cart', 'tart', 'part', 'wart']\n",
1167 "['cart', 'tart', 'part', 'pert']\n",
1168 "['cart', 'tart', 'part', 'port']\n",
1169 "['cart', 'tart', 'part', 'pact']\n",
1170 "['cart', 'tart', 'part', 'pant']\n",
1171 "['cart', 'tart', 'part', 'past']\n",
1172 "['cart', 'tart', 'part', 'pare']\n",
1173 "['cart', 'tart', 'part', 'park']\n",
1174 "['cart', 'tart', 'part', 'pars']\n",
1175 "['cart', 'tart', 'wart', 'dart']\n",
1176 "['cart', 'tart', 'wart', 'hart']\n",
1177 "['cart', 'tart', 'wart', 'mart']\n",
1178 "['cart', 'tart', 'wart', 'part']\n",
1179 "['cart', 'tart', 'wart', 'waft']\n",
1180 "['cart', 'tart', 'wart', 'wait']\n",
1181 "['cart', 'tart', 'wart', 'want']\n",
1182 "['cart', 'tart', 'wart', 'watt']\n",
1183 "['cart', 'tart', 'wart', 'ward']\n",
1184 "['cart', 'tart', 'wart', 'ware']\n",
1185 "['cart', 'tart', 'wart', 'warm']\n",
1186 "['cart', 'tart', 'wart', 'warn']\n",
1187 "['cart', 'tart', 'wart', 'warp']\n",
1188 "['cart', 'tart', 'wart', 'wars']\n",
1189 "['cart', 'tart', 'wart', 'wary']\n",
1190 "['cart', 'tart', 'tort', 'fort']\n",
1191 "['cart', 'tart', 'tort', 'port']\n",
1192 "['cart', 'tart', 'tort', 'sort']\n",
1193 "['cart', 'tart', 'tort', 'toot']\n",
1194 "['cart', 'tart', 'tort', 'tost']\n",
1195 "['cart', 'tart', 'tort', 'tout']\n",
1196 "['cart', 'tart', 'tort', 'tore']\n",
1197 "['cart', 'tart', 'tort', 'torn']\n",
1198 "['cart', 'tart', 'tort', 'tors']\n",
1199 "['cart', 'tart', 'tact', 'fact']\n",
1200 "['cart', 'tart', 'tact', 'pact']\n",
1201 "['cart', 'tart', 'tact', 'taut']\n",
1202 "['cart', 'tart', 'tact', 'tack']\n",
1203 "['cart', 'tart', 'tact', 'taco']\n",
1204 "['cart', 'tart', 'taut', 'tout']\n",
1205 "['cart', 'tart', 'taut', 'tact']\n",
1206 "['cart', 'tart', 'tare', 'bare']\n",
1207 "['cart', 'tart', 'tare', 'care']\n",
1208 "['cart', 'tart', 'tare', 'dare']\n",
1209 "['cart', 'tart', 'tare', 'fare']\n",
1210 "['cart', 'tart', 'tare', 'hare']\n",
1211 "['cart', 'tart', 'tare', 'mare']\n",
1212 "['cart', 'tart', 'tare', 'pare']\n",
1213 "['cart', 'tart', 'tare', 'rare']\n",
1214 "['cart', 'tart', 'tare', 'ware']\n",
1215 "['cart', 'tart', 'tare', 'tire']\n",
1216 "['cart', 'tart', 'tare', 'tore']\n",
1217 "['cart', 'tart', 'tare', 'tyre']\n",
1218 "['cart', 'tart', 'tare', 'take']\n",
1219 "['cart', 'tart', 'tare', 'tale']\n",
1220 "['cart', 'tart', 'tare', 'tame']\n",
1221 "['cart', 'tart', 'tare', 'tape']\n",
1222 "['cart', 'tart', 'tare', 'taro']\n",
1223 "['cart', 'tart', 'tare', 'tarp']\n",
1224 "['cart', 'tart', 'tare', 'tars']\n",
1225 "['cart', 'tart', 'taro', 'tiro']\n",
1226 "['cart', 'tart', 'taro', 'tyro']\n",
1227 "['cart', 'tart', 'taro', 'taco']\n",
1228 "['cart', 'tart', 'taro', 'tare']\n",
1229 "['cart', 'tart', 'taro', 'tarp']\n",
1230 "['cart', 'tart', 'taro', 'tars']\n",
1231 "['cart', 'tart', 'tarp', 'carp']\n",
1232 "['cart', 'tart', 'tarp', 'harp']\n",
1233 "['cart', 'tart', 'tarp', 'warp']\n",
1234 "['cart', 'tart', 'tarp', 'tamp']\n",
1235 "['cart', 'tart', 'tarp', 'tare']\n",
1236 "['cart', 'tart', 'tarp', 'taro']\n",
1237 "['cart', 'tart', 'tarp', 'tars']\n",
1238 "['cart', 'tart', 'tars', 'bars']\n",
1239 "['cart', 'tart', 'tars', 'cars']\n",
1240 "['cart', 'tart', 'tars', 'ears']\n",
1241 "['cart', 'tart', 'tars', 'jars']\n",
1242 "['cart', 'tart', 'tars', 'mars']\n",
1243 "['cart', 'tart', 'tars', 'oars']\n",
1244 "['cart', 'tart', 'tars', 'pars']\n",
1245 "['cart', 'tart', 'tars', 'wars']\n",
1246 "['cart', 'tart', 'tars', 'tors']\n",
1247 "['cart', 'tart', 'tars', 'tabs']\n",
1248 "['cart', 'tart', 'tars', 'tads']\n",
1249 "['cart', 'tart', 'tars', 'tags']\n",
1250 "['cart', 'tart', 'tars', 'tams']\n",
1251 "['cart', 'tart', 'tars', 'tans']\n",
1252 "['cart', 'tart', 'tars', 'taps']\n",
1253 "['cart', 'tart', 'tars', 'tats']\n",
1254 "['cart', 'tart', 'tars', 'tare']\n",
1255 "['cart', 'tart', 'tars', 'taro']\n",
1256 "['cart', 'tart', 'tars', 'tarp']\n",
1257 "['cart', 'wart', 'dart', 'hart']\n",
1258 "['cart', 'wart', 'dart', 'mart']\n",
1259 "['cart', 'wart', 'dart', 'part']\n",
1260 "['cart', 'wart', 'dart', 'tart']\n",
1261 "['cart', 'wart', 'dart', 'dirt']\n",
1262 "['cart', 'wart', 'dart', 'daft']\n",
1263 "['cart', 'wart', 'dart', 'dare']\n",
1264 "['cart', 'wart', 'dart', 'dark']\n",
1265 "['cart', 'wart', 'dart', 'darn']\n",
1266 "['cart', 'wart', 'hart', 'dart']\n",
1267 "['cart', 'wart', 'hart', 'mart']\n",
1268 "['cart', 'wart', 'hart', 'part']\n",
1269 "['cart', 'wart', 'hart', 'tart']\n",
1270 "['cart', 'wart', 'hart', 'hurt']\n",
1271 "['cart', 'wart', 'hart', 'haft']\n",
1272 "['cart', 'wart', 'hart', 'halt']\n",
1273 "['cart', 'wart', 'hart', 'hard']\n",
1274 "['cart', 'wart', 'hart', 'hare']\n",
1275 "['cart', 'wart', 'hart', 'hark']\n",
1276 "['cart', 'wart', 'hart', 'harm']\n",
1277 "['cart', 'wart', 'hart', 'harp']\n",
1278 "['cart', 'wart', 'mart', 'dart']\n",
1279 "['cart', 'wart', 'mart', 'hart']\n",
1280 "['cart', 'wart', 'mart', 'part']\n",
1281 "['cart', 'wart', 'mart', 'tart']\n",
1282 "['cart', 'wart', 'mart', 'malt']\n",
1283 "['cart', 'wart', 'mart', 'mast']\n",
1284 "['cart', 'wart', 'mart', 'matt']\n",
1285 "['cart', 'wart', 'mart', 'mare']\n",
1286 "['cart', 'wart', 'mart', 'mark']\n",
1287 "['cart', 'wart', 'mart', 'mars']\n",
1288 "['cart', 'wart', 'part', 'dart']\n",
1289 "['cart', 'wart', 'part', 'hart']\n",
1290 "['cart', 'wart', 'part', 'mart']\n",
1291 "['cart', 'wart', 'part', 'tart']\n",
1292 "['cart', 'wart', 'part', 'pert']\n",
1293 "['cart', 'wart', 'part', 'port']\n",
1294 "['cart', 'wart', 'part', 'pact']\n",
1295 "['cart', 'wart', 'part', 'pant']\n",
1296 "['cart', 'wart', 'part', 'past']\n",
1297 "['cart', 'wart', 'part', 'pare']\n",
1298 "['cart', 'wart', 'part', 'park']\n",
1299 "['cart', 'wart', 'part', 'pars']\n",
1300 "['cart', 'wart', 'tart', 'dart']\n",
1301 "['cart', 'wart', 'tart', 'hart']\n",
1302 "['cart', 'wart', 'tart', 'mart']\n",
1303 "['cart', 'wart', 'tart', 'part']\n",
1304 "['cart', 'wart', 'tart', 'tort']\n",
1305 "['cart', 'wart', 'tart', 'tact']\n",
1306 "['cart', 'wart', 'tart', 'taut']\n",
1307 "['cart', 'wart', 'tart', 'tare']\n",
1308 "['cart', 'wart', 'tart', 'taro']\n",
1309 "['cart', 'wart', 'tart', 'tarp']\n",
1310 "['cart', 'wart', 'tart', 'tars']\n",
1311 "['cart', 'wart', 'waft', 'daft']\n",
1312 "['cart', 'wart', 'waft', 'haft']\n",
1313 "['cart', 'wart', 'waft', 'raft']\n",
1314 "['cart', 'wart', 'waft', 'weft']\n",
1315 "['cart', 'wart', 'waft', 'wait']\n",
1316 "['cart', 'wart', 'waft', 'want']\n",
1317 "['cart', 'wart', 'waft', 'watt']\n",
1318 "['cart', 'wart', 'wait', 'bait']\n",
1319 "['cart', 'wart', 'wait', 'gait']\n",
1320 "['cart', 'wart', 'wait', 'whit']\n",
1321 "['cart', 'wart', 'wait', 'writ']\n",
1322 "['cart', 'wart', 'wait', 'waft']\n",
1323 "['cart', 'wart', 'wait', 'want']\n",
1324 "['cart', 'wart', 'wait', 'watt']\n",
1325 "['cart', 'wart', 'wait', 'waif']\n",
1326 "['cart', 'wart', 'wait', 'wail']\n",
1327 "['cart', 'wart', 'want', 'cant']\n",
1328 "['cart', 'wart', 'want', 'pant']\n",
1329 "['cart', 'wart', 'want', 'rant']\n",
1330 "['cart', 'wart', 'want', 'went']\n",
1331 "['cart', 'wart', 'want', 'wont']\n",
1332 "['cart', 'wart', 'want', 'waft']\n",
1333 "['cart', 'wart', 'want', 'wait']\n",
1334 "['cart', 'wart', 'want', 'watt']\n",
1335 "['cart', 'wart', 'want', 'wand']\n",
1336 "['cart', 'wart', 'want', 'wane']\n",
1337 "['cart', 'wart', 'watt', 'matt']\n",
1338 "['cart', 'wart', 'watt', 'waft']\n",
1339 "['cart', 'wart', 'watt', 'wait']\n",
1340 "['cart', 'wart', 'watt', 'want']\n",
1341 "['cart', 'wart', 'ward', 'bard']\n",
1342 "['cart', 'wart', 'ward', 'card']\n",
1343 "['cart', 'wart', 'ward', 'hard']\n",
1344 "['cart', 'wart', 'ward', 'lard']\n",
1345 "['cart', 'wart', 'ward', 'yard']\n",
1346 "['cart', 'wart', 'ward', 'word']\n",
1347 "['cart', 'wart', 'ward', 'wand']\n",
1348 "['cart', 'wart', 'ward', 'ware']\n",
1349 "['cart', 'wart', 'ward', 'warm']\n",
1350 "['cart', 'wart', 'ward', 'warn']\n",
1351 "['cart', 'wart', 'ward', 'warp']\n",
1352 "['cart', 'wart', 'ward', 'wars']\n",
1353 "['cart', 'wart', 'ward', 'wary']\n",
1354 "['cart', 'wart', 'ware', 'bare']\n",
1355 "['cart', 'wart', 'ware', 'care']\n",
1356 "['cart', 'wart', 'ware', 'dare']\n",
1357 "['cart', 'wart', 'ware', 'fare']\n",
1358 "['cart', 'wart', 'ware', 'hare']\n",
1359 "['cart', 'wart', 'ware', 'mare']\n",
1360 "['cart', 'wart', 'ware', 'pare']\n",
1361 "['cart', 'wart', 'ware', 'rare']\n",
1362 "['cart', 'wart', 'ware', 'tare']\n",
1363 "['cart', 'wart', 'ware', 'were']\n",
1364 "['cart', 'wart', 'ware', 'wire']\n",
1365 "['cart', 'wart', 'ware', 'wore']\n",
1366 "['cart', 'wart', 'ware', 'wade']\n",
1367 "['cart', 'wart', 'ware', 'wage']\n",
1368 "['cart', 'wart', 'ware', 'wake']\n",
1369 "['cart', 'wart', 'ware', 'wale']\n",
1370 "['cart', 'wart', 'ware', 'wane']\n",
1371 "['cart', 'wart', 'ware', 'wave']\n",
1372 "['cart', 'wart', 'ware', 'ward']\n",
1373 "['cart', 'wart', 'ware', 'warm']\n",
1374 "['cart', 'wart', 'ware', 'warn']\n",
1375 "['cart', 'wart', 'ware', 'warp']\n",
1376 "['cart', 'wart', 'ware', 'wars']\n",
1377 "['cart', 'wart', 'ware', 'wary']\n",
1378 "['cart', 'wart', 'warm', 'farm']\n",
1379 "['cart', 'wart', 'warm', 'harm']\n",
1380 "['cart', 'wart', 'warm', 'worm']\n",
1381 "['cart', 'wart', 'warm', 'ward']\n",
1382 "['cart', 'wart', 'warm', 'ware']\n",
1383 "['cart', 'wart', 'warm', 'warn']\n",
1384 "['cart', 'wart', 'warm', 'warp']\n",
1385 "['cart', 'wart', 'warm', 'wars']\n",
1386 "['cart', 'wart', 'warm', 'wary']\n",
1387 "['cart', 'wart', 'warn', 'barn']\n",
1388 "['cart', 'wart', 'warn', 'darn']\n",
1389 "['cart', 'wart', 'warn', 'earn']\n",
1390 "['cart', 'wart', 'warn', 'yarn']\n",
1391 "['cart', 'wart', 'warn', 'worn']\n",
1392 "['cart', 'wart', 'warn', 'ward']\n",
1393 "['cart', 'wart', 'warn', 'ware']\n",
1394 "['cart', 'wart', 'warn', 'warm']\n",
1395 "['cart', 'wart', 'warn', 'warp']\n",
1396 "['cart', 'wart', 'warn', 'wars']\n",
1397 "['cart', 'wart', 'warn', 'wary']\n",
1398 "['cart', 'wart', 'warp', 'carp']\n",
1399 "['cart', 'wart', 'warp', 'harp']\n",
1400 "['cart', 'wart', 'warp', 'tarp']\n",
1401 "['cart', 'wart', 'warp', 'wasp']\n",
1402 "['cart', 'wart', 'warp', 'ward']\n",
1403 "['cart', 'wart', 'warp', 'ware']\n",
1404 "['cart', 'wart', 'warp', 'warm']\n",
1405 "['cart', 'wart', 'warp', 'warn']\n",
1406 "['cart', 'wart', 'warp', 'wars']\n",
1407 "['cart', 'wart', 'warp', 'wary']\n",
1408 "['cart', 'wart', 'wars', 'bars']\n",
1409 "['cart', 'wart', 'wars', 'cars']\n",
1410 "['cart', 'wart', 'wars', 'ears']\n",
1411 "['cart', 'wart', 'wars', 'jars']\n",
1412 "['cart', 'wart', 'wars', 'mars']\n",
1413 "['cart', 'wart', 'wars', 'oars']\n",
1414 "['cart', 'wart', 'wars', 'pars']\n",
1415 "['cart', 'wart', 'wars', 'tars']\n",
1416 "['cart', 'wart', 'wars', 'wads']\n",
1417 "['cart', 'wart', 'wars', 'wags']\n",
1418 "['cart', 'wart', 'wars', 'ways']\n",
1419 "['cart', 'wart', 'wars', 'ward']\n",
1420 "['cart', 'wart', 'wars', 'ware']\n",
1421 "['cart', 'wart', 'wars', 'warm']\n",
1422 "['cart', 'wart', 'wars', 'warn']\n",
1423 "['cart', 'wart', 'wars', 'warp']\n",
1424 "['cart', 'wart', 'wars', 'wary']\n",
1425 "['cart', 'wart', 'wary', 'nary']\n",
1426 "['cart', 'wart', 'wary', 'vary']\n",
1427 "['cart', 'wart', 'wary', 'wiry']\n",
1428 "['cart', 'wart', 'wary', 'wavy']\n",
1429 "['cart', 'wart', 'wary', 'waxy']\n",
1430 "['cart', 'wart', 'wary', 'ward']\n",
1431 "['cart', 'wart', 'wary', 'ware']\n",
1432 "['cart', 'wart', 'wary', 'warm']\n",
1433 "['cart', 'wart', 'wary', 'warn']\n",
1434 "['cart', 'wart', 'wary', 'warp']\n",
1435 "['cart', 'wart', 'wary', 'wars']\n",
1436 "['cart', 'curt', 'hurt', 'hart']\n",
1437 "['cart', 'curt', 'hurt', 'hunt']\n",
1438 "['cart', 'curt', 'hurt', 'hurl']\n",
1439 "['cart', 'curt', 'cult', 'colt']\n",
1440 "['cart', 'curt', 'cult', 'cull']\n",
1441 "['cart', 'curt', 'curb', 'curd']\n",
1442 "['cart', 'curt', 'curb', 'cure']\n",
1443 "['cart', 'curt', 'curb', 'curl']\n",
1444 "['cart', 'curt', 'curb', 'curs']\n",
1445 "['cart', 'curt', 'curd', 'turd']\n",
1446 "['cart', 'curt', 'curd', 'card']\n",
1447 "['cart', 'curt', 'curd', 'cord']\n",
1448 "['cart', 'curt', 'curd', 'cued']\n",
1449 "['cart', 'curt', 'curd', 'curb']\n",
1450 "['cart', 'curt', 'curd', 'cure']\n",
1451 "['cart', 'curt', 'curd', 'curl']\n",
1452 "['cart', 'curt', 'curd', 'curs']\n",
1453 "['cart', 'curt', 'cure', 'lure']\n",
1454 "['cart', 'curt', 'cure', 'pure']\n",
1455 "['cart', 'curt', 'cure', 'sure']\n",
1456 "['cart', 'curt', 'cure', 'care']\n",
1457 "['cart', 'curt', 'cure', 'core']\n",
1458 "['cart', 'curt', 'cure', 'cube']\n",
1459 "['cart', 'curt', 'cure', 'cute']\n",
1460 "['cart', 'curt', 'cure', 'curb']\n",
1461 "['cart', 'curt', 'cure', 'curd']\n",
1462 "['cart', 'curt', 'cure', 'curl']\n",
1463 "['cart', 'curt', 'cure', 'curs']\n",
1464 "['cart', 'curt', 'curl', 'furl']\n",
1465 "['cart', 'curt', 'curl', 'hurl']\n",
1466 "['cart', 'curt', 'curl', 'purl']\n",
1467 "['cart', 'curt', 'curl', 'cull']\n",
1468 "['cart', 'curt', 'curl', 'curb']\n",
1469 "['cart', 'curt', 'curl', 'curd']\n",
1470 "['cart', 'curt', 'curl', 'cure']\n",
1471 "['cart', 'curt', 'curl', 'curs']\n",
1472 "['cart', 'curt', 'curs', 'burs']\n",
1473 "['cart', 'curt', 'curs', 'furs']\n",
1474 "['cart', 'curt', 'curs', 'ours']\n",
1475 "['cart', 'curt', 'curs', 'cars']\n",
1476 "['cart', 'curt', 'curs', 'cubs']\n",
1477 "['cart', 'curt', 'curs', 'cuds']\n",
1478 "['cart', 'curt', 'curs', 'cues']\n",
1479 "['cart', 'curt', 'curs', 'cums']\n",
1480 "['cart', 'curt', 'curs', 'cups']\n",
1481 "['cart', 'curt', 'curs', 'cuss']\n",
1482 "['cart', 'curt', 'curs', 'cuts']\n",
1483 "['cart', 'curt', 'curs', 'curb']\n",
1484 "['cart', 'curt', 'curs', 'curd']\n",
1485 "['cart', 'curt', 'curs', 'cure']\n",
1486 "['cart', 'curt', 'curs', 'curl']\n",
1487 "['cart', 'cant', 'pant', 'rant']\n",
1488 "['cart', 'cant', 'pant', 'want']\n",
1489 "['cart', 'cant', 'pant', 'pent']\n",
1490 "['cart', 'cant', 'pant', 'pint']\n",
1491 "['cart', 'cant', 'pant', 'punt']\n",
1492 "['cart', 'cant', 'pant', 'pact']\n",
1493 "['cart', 'cant', 'pant', 'part']\n",
1494 "['cart', 'cant', 'pant', 'past']\n",
1495 "['cart', 'cant', 'pant', 'pane']\n",
1496 "['cart', 'cant', 'pant', 'pang']\n",
1497 "['cart', 'cant', 'pant', 'pans']\n",
1498 "['cart', 'cant', 'rant', 'pant']\n",
1499 "['cart', 'cant', 'rant', 'want']\n",
1500 "['cart', 'cant', 'rant', 'rent']\n",
1501 "['cart', 'cant', 'rant', 'runt']\n",
1502 "['cart', 'cant', 'rant', 'raft']\n",
1503 "['cart', 'cant', 'rant', 'rapt']\n",
1504 "['cart', 'cant', 'rant', 'rang']\n",
1505 "['cart', 'cant', 'rant', 'rank']\n",
1506 "['cart', 'cant', 'want', 'pant']\n",
1507 "['cart', 'cant', 'want', 'rant']\n",
1508 "['cart', 'cant', 'want', 'went']\n",
1509 "['cart', 'cant', 'want', 'wont']\n",
1510 "['cart', 'cant', 'want', 'waft']\n",
1511 "['cart', 'cant', 'want', 'wait']\n",
1512 "['cart', 'cant', 'want', 'wart']\n",
1513 "['cart', 'cant', 'want', 'watt']\n",
1514 "['cart', 'cant', 'want', 'wand']\n",
1515 "['cart', 'cant', 'want', 'wane']\n",
1516 "['cart', 'cant', 'cent', 'bent']\n",
1517 "['cart', 'cant', 'cent', 'dent']\n",
1518 "['cart', 'cant', 'cent', 'gent']\n",
1519 "['cart', 'cant', 'cent', 'lent']\n",
1520 "['cart', 'cant', 'cent', 'pent']\n",
1521 "['cart', 'cant', 'cent', 'rent']\n",
1522 "['cart', 'cant', 'cent', 'sent']\n",
1523 "['cart', 'cant', 'cent', 'tent']\n",
1524 "['cart', 'cant', 'cent', 'vent']\n",
1525 "['cart', 'cant', 'cent', 'went']\n",
1526 "['cart', 'cant', 'cast', 'bast']\n",
1527 "['cart', 'cant', 'cast', 'east']\n",
1528 "['cart', 'cant', 'cast', 'fast']\n",
1529 "['cart', 'cant', 'cast', 'last']\n",
1530 "['cart', 'cant', 'cast', 'mast']\n",
1531 "['cart', 'cant', 'cast', 'past']\n",
1532 "['cart', 'cant', 'cast', 'vast']\n",
1533 "['cart', 'cant', 'cast', 'cost']\n",
1534 "['cart', 'cant', 'cast', 'cyst']\n",
1535 "['cart', 'cant', 'cast', 'case']\n",
1536 "['cart', 'cant', 'cast', 'cash']\n",
1537 "['cart', 'cant', 'cast', 'cask']\n",
1538 "['cart', 'cant', 'cane', 'bane']\n",
1539 "['cart', 'cant', 'cane', 'lane']\n",
1540 "['cart', 'cant', 'cane', 'mane']\n",
1541 "['cart', 'cant', 'cane', 'pane']\n",
1542 "['cart', 'cant', 'cane', 'sane']\n",
1543 "['cart', 'cant', 'cane', 'vane']\n",
1544 "['cart', 'cant', 'cane', 'wane']\n",
1545 "['cart', 'cant', 'cane', 'cone']\n",
1546 "['cart', 'cant', 'cane', 'cafe']\n",
1547 "['cart', 'cant', 'cane', 'cage']\n",
1548 "['cart', 'cant', 'cane', 'cake']\n",
1549 "['cart', 'cant', 'cane', 'came']\n",
1550 "['cart', 'cant', 'cane', 'cape']\n",
1551 "['cart', 'cant', 'cane', 'care']\n",
1552 "['cart', 'cant', 'cane', 'case']\n",
1553 "['cart', 'cant', 'cane', 'cave']\n",
1554 "['cart', 'cant', 'cane', 'cans']\n",
1555 "['cart', 'cant', 'cans', 'bans']\n",
1556 "['cart', 'cant', 'cans', 'fans']\n",
1557 "['cart', 'cant', 'cans', 'mans']\n",
1558 "['cart', 'cant', 'cans', 'pans']\n",
1559 "['cart', 'cant', 'cans', 'sans']\n",
1560 "['cart', 'cant', 'cans', 'tans']\n",
1561 "['cart', 'cant', 'cans', 'vans']\n"
1562 ]
1563 },
1564 {
1565 "data": {
1566 "text/plain": [
1567 "['cart', 'cant', 'cans', 'vans']"
1568 ]
1569 },
1570 "execution_count": 20,
1571 "metadata": {},
1572 "output_type": "execute_result"
1573 }
1574 ],
1575 "source": [
1576 "bfs_search('cart', 'vans', debug=True)"
1577 ]
1578 },
1579 {
1580 "cell_type": "code",
1581 "execution_count": 21,
1582 "metadata": {
1583 "collapsed": false
1584 },
1585 "outputs": [
1586 {
1587 "data": {
1588 "text/plain": [
1589 "['cart', 'cant', 'cane', 'vane']"
1590 ]
1591 },
1592 "execution_count": 21,
1593 "metadata": {},
1594 "output_type": "execute_result"
1595 }
1596 ],
1597 "source": [
1598 "bfs_search('cart', 'vane')"
1599 ]
1600 },
1601 {
1602 "cell_type": "code",
1603 "execution_count": 22,
1604 "metadata": {
1605 "collapsed": false
1606 },
1607 "outputs": [
1608 {
1609 "data": {
1610 "text/plain": [
1611 "['cart',\n",
1612 " 'dart',\n",
1613 " 'hart',\n",
1614 " 'mart',\n",
1615 " 'part',\n",
1616 " 'tart',\n",
1617 " 'wart',\n",
1618 " 'waft',\n",
1619 " 'daft',\n",
1620 " 'haft',\n",
1621 " 'raft',\n",
1622 " 'rift',\n",
1623 " 'gift',\n",
1624 " 'lift',\n",
1625 " 'sift',\n",
1626 " 'soft',\n",
1627 " 'loft',\n",
1628 " 'left',\n",
1629 " 'deft',\n",
1630 " 'heft',\n",
1631 " 'weft',\n",
1632 " 'welt',\n",
1633 " 'belt',\n",
1634 " 'felt',\n",
1635 " 'gelt',\n",
1636 " 'melt',\n",
1637 " 'pelt',\n",
1638 " 'peat',\n",
1639 " 'beat',\n",
1640 " 'feat',\n",
1641 " 'heat',\n",
1642 " 'meat',\n",
1643 " 'neat',\n",
1644 " 'seat',\n",
1645 " 'teat',\n",
1646 " 'that',\n",
1647 " 'chat',\n",
1648 " 'shat',\n",
1649 " 'what',\n",
1650 " 'whet',\n",
1651 " 'whit',\n",
1652 " 'chit',\n",
1653 " 'chic',\n",
1654 " 'chid',\n",
1655 " 'chin',\n",
1656 " 'shin',\n",
1657 " 'thin',\n",
1658 " 'twin',\n",
1659 " 'twig',\n",
1660 " 'swig',\n",
1661 " 'swag',\n",
1662 " 'shag',\n",
1663 " 'slag',\n",
1664 " 'flag',\n",
1665 " 'flog',\n",
1666 " 'blog',\n",
1667 " 'clog',\n",
1668 " 'slog',\n",
1669 " 'smog',\n",
1670 " 'smug',\n",
1671 " 'slug',\n",
1672 " 'plug',\n",
1673 " 'plum',\n",
1674 " 'alum',\n",
1675 " 'glum',\n",
1676 " 'slum',\n",
1677 " 'scum',\n",
1678 " 'swum',\n",
1679 " 'swam',\n",
1680 " 'scam',\n",
1681 " 'seam',\n",
1682 " 'beam',\n",
1683 " 'ream',\n",
1684 " 'team',\n",
1685 " 'tram',\n",
1686 " 'cram',\n",
1687 " 'dram',\n",
1688 " 'gram',\n",
1689 " 'pram',\n",
1690 " 'prim',\n",
1691 " 'brim',\n",
1692 " 'grim',\n",
1693 " 'trim',\n",
1694 " 'trig',\n",
1695 " 'brig',\n",
1696 " 'brag',\n",
1697 " 'crag',\n",
1698 " 'drag',\n",
1699 " 'drug',\n",
1700 " 'drub',\n",
1701 " 'grub',\n",
1702 " 'grab',\n",
1703 " 'crab',\n",
1704 " 'drab',\n",
1705 " 'draw',\n",
1706 " 'craw',\n",
1707 " 'claw',\n",
1708 " 'flaw',\n",
1709 " 'slaw',\n",
1710 " 'slew',\n",
1711 " 'blew',\n",
1712 " 'clew',\n",
1713 " 'flew',\n",
1714 " 'flow',\n",
1715 " 'blow',\n",
1716 " 'glow',\n",
1717 " 'slow',\n",
1718 " 'scow',\n",
1719 " 'show',\n",
1720 " 'chow',\n",
1721 " 'crow',\n",
1722 " 'brow',\n",
1723 " 'grow',\n",
1724 " 'prow',\n",
1725 " 'prod',\n",
1726 " 'trod',\n",
1727 " 'trot',\n",
1728 " 'toot',\n",
1729 " 'boot',\n",
1730 " 'coot',\n",
1731 " 'foot',\n",
1732 " 'hoot',\n",
1733 " 'loot',\n",
1734 " 'moot',\n",
1735 " 'root',\n",
1736 " 'soot',\n",
1737 " 'shot',\n",
1738 " 'slot',\n",
1739 " 'blot',\n",
1740 " 'clot',\n",
1741 " 'plot',\n",
1742 " 'plod',\n",
1743 " 'clod',\n",
1744 " 'clad',\n",
1745 " 'glad',\n",
1746 " 'goad',\n",
1747 " 'load',\n",
1748 " 'road',\n",
1749 " 'toad',\n",
1750 " 'toed',\n",
1751 " 'coed',\n",
1752 " 'hoed',\n",
1753 " 'heed',\n",
1754 " 'deed',\n",
1755 " 'feed',\n",
1756 " 'geed',\n",
1757 " 'need',\n",
1758 " 'peed',\n",
1759 " 'reed',\n",
1760 " 'seed',\n",
1761 " 'teed',\n",
1762 " 'weed',\n",
1763 " 'weld',\n",
1764 " 'geld',\n",
1765 " 'held',\n",
1766 " 'meld',\n",
1767 " 'veld',\n",
1768 " 'vend',\n",
1769 " 'bend',\n",
1770 " 'fend',\n",
1771 " 'lend',\n",
1772 " 'mend',\n",
1773 " 'rend',\n",
1774 " 'send',\n",
1775 " 'tend',\n",
1776 " 'wend',\n",
1777 " 'wand',\n",
1778 " 'band',\n",
1779 " 'hand',\n",
1780 " 'land',\n",
1781 " 'sand',\n",
1782 " 'said',\n",
1783 " 'laid',\n",
1784 " 'maid',\n",
1785 " 'paid',\n",
1786 " 'raid',\n",
1787 " 'rail',\n",
1788 " 'bail',\n",
1789 " 'fail',\n",
1790 " 'hail',\n",
1791 " 'jail',\n",
1792 " 'mail',\n",
1793 " 'nail',\n",
1794 " 'pail',\n",
1795 " 'sail',\n",
1796 " 'tail',\n",
1797 " 'wail',\n",
1798 " 'wall',\n",
1799 " 'ball',\n",
1800 " 'call',\n",
1801 " 'fall',\n",
1802 " 'gall',\n",
1803 " 'hall',\n",
1804 " 'mall',\n",
1805 " 'pall',\n",
1806 " 'tall',\n",
1807 " 'tell',\n",
1808 " 'bell',\n",
1809 " 'cell',\n",
1810 " 'dell',\n",
1811 " 'fell',\n",
1812 " 'hell',\n",
1813 " 'jell',\n",
1814 " 'sell',\n",
1815 " 'well',\n",
1816 " 'yell',\n",
1817 " 'yelp',\n",
1818 " 'help',\n",
1819 " 'kelp',\n",
1820 " 'keep',\n",
1821 " 'beep',\n",
1822 " 'deep',\n",
1823 " 'jeep',\n",
1824 " 'peep',\n",
1825 " 'seep',\n",
1826 " 'veep',\n",
1827 " 'weep',\n",
1828 " 'week',\n",
1829 " 'geek',\n",
1830 " 'leek',\n",
1831 " 'meek',\n",
1832 " 'peek',\n",
1833 " 'reek',\n",
1834 " 'seek',\n",
1835 " 'seem',\n",
1836 " 'deem',\n",
1837 " 'teem',\n",
1838 " 'them',\n",
1839 " 'thee',\n",
1840 " 'tree',\n",
1841 " 'free',\n",
1842 " 'flee',\n",
1843 " 'glee',\n",
1844 " 'glue',\n",
1845 " 'blue',\n",
1846 " 'clue',\n",
1847 " 'flue',\n",
1848 " 'slue',\n",
1849 " 'sloe',\n",
1850 " 'aloe',\n",
1851 " 'floe',\n",
1852 " 'flop',\n",
1853 " 'clop',\n",
1854 " 'glop',\n",
1855 " 'plop',\n",
1856 " 'slop',\n",
1857 " 'shop',\n",
1858 " 'chop',\n",
1859 " 'coop',\n",
1860 " 'goop',\n",
1861 " 'hoop',\n",
1862 " 'loop',\n",
1863 " 'poop',\n",
1864 " 'prop',\n",
1865 " 'crop',\n",
1866 " 'drop',\n",
1867 " 'drip',\n",
1868 " 'grip',\n",
1869 " 'trip',\n",
1870 " 'trap',\n",
1871 " 'tray',\n",
1872 " 'bray',\n",
1873 " 'dray',\n",
1874 " 'fray',\n",
1875 " 'gray',\n",
1876 " 'pray',\n",
1877 " 'play',\n",
1878 " 'clay',\n",
1879 " 'flay',\n",
1880 " 'slay',\n",
1881 " 'spay',\n",
1882 " 'stay',\n",
1883 " 'sway',\n",
1884 " 'away',\n",
1885 " 'awry',\n",
1886 " 'aery',\n",
1887 " 'eery',\n",
1888 " 'very',\n",
1889 " 'vary',\n",
1890 " 'nary',\n",
1891 " 'wary',\n",
1892 " 'wiry',\n",
1893 " 'airy',\n",
1894 " 'airs',\n",
1895 " 'firs',\n",
1896 " 'sirs',\n",
1897 " 'sics',\n",
1898 " 'tics',\n",
1899 " 'ties',\n",
1900 " 'dies',\n",
1901 " 'hies',\n",
1902 " 'lies',\n",
1903 " 'pies',\n",
1904 " 'vies',\n",
1905 " 'vied',\n",
1906 " 'died',\n",
1907 " 'hied',\n",
1908 " 'lied',\n",
1909 " 'pied',\n",
1910 " 'tied',\n",
1911 " 'tier',\n",
1912 " 'bier',\n",
1913 " 'pier',\n",
1914 " 'peer',\n",
1915 " 'beer',\n",
1916 " 'deer',\n",
1917 " 'jeer',\n",
1918 " 'leer',\n",
1919 " 'seer',\n",
1920 " 'veer',\n",
1921 " 'weer',\n",
1922 " 'wear',\n",
1923 " 'bear',\n",
1924 " 'dear',\n",
1925 " 'fear',\n",
1926 " 'gear',\n",
1927 " 'hear',\n",
1928 " 'near',\n",
1929 " 'pear',\n",
1930 " 'rear',\n",
1931 " 'sear',\n",
1932 " 'tear',\n",
1933 " 'year',\n",
1934 " 'yeah',\n",
1935 " 'yeas',\n",
1936 " 'leas',\n",
1937 " 'peas',\n",
1938 " 'seas',\n",
1939 " 'teas',\n",
1940 " 'tees',\n",
1941 " 'bees',\n",
1942 " 'fees',\n",
1943 " 'gees',\n",
1944 " 'lees',\n",
1945 " 'pees',\n",
1946 " 'sees',\n",
1947 " 'wees',\n",
1948 " 'woes',\n",
1949 " 'does',\n",
1950 " 'foes',\n",
1951 " 'goes',\n",
1952 " 'hoes',\n",
1953 " 'noes',\n",
1954 " 'roes',\n",
1955 " 'toes',\n",
1956 " 'togs',\n",
1957 " 'bogs',\n",
1958 " 'cogs',\n",
1959 " 'dogs',\n",
1960 " 'fogs',\n",
1961 " 'hogs',\n",
1962 " 'jogs',\n",
1963 " 'logs',\n",
1964 " 'lags',\n",
1965 " 'bags',\n",
1966 " 'fags',\n",
1967 " 'gags',\n",
1968 " 'hags',\n",
1969 " 'jags',\n",
1970 " 'nags',\n",
1971 " 'rags',\n",
1972 " 'sags',\n",
1973 " 'tags',\n",
1974 " 'wags',\n",
1975 " 'wigs',\n",
1976 " 'digs',\n",
1977 " 'figs',\n",
1978 " 'gigs',\n",
1979 " 'jigs',\n",
1980 " 'pigs',\n",
1981 " 'rigs',\n",
1982 " 'rugs',\n",
1983 " 'bugs',\n",
1984 " 'hugs',\n",
1985 " 'jugs',\n",
1986 " 'lugs',\n",
1987 " 'mugs',\n",
1988 " 'pugs',\n",
1989 " 'tugs',\n",
1990 " 'tubs',\n",
1991 " 'cubs',\n",
1992 " 'dubs',\n",
1993 " 'hubs',\n",
1994 " 'nubs',\n",
1995 " 'pubs',\n",
1996 " 'rubs',\n",
1997 " 'subs',\n",
1998 " 'sobs',\n",
1999 " 'bobs',\n",
2000 " 'cobs',\n",
2001 " 'fobs',\n",
2002 " 'gobs',\n",
2003 " 'hobs',\n",
2004 " 'jobs',\n",
2005 " 'lobs',\n",
2006 " 'mobs',\n",
2007 " 'robs',\n",
2008 " 'ribs',\n",
2009 " 'bibs',\n",
2010 " 'fibs',\n",
2011 " 'jibs',\n",
2012 " 'nibs',\n",
2013 " 'nabs',\n",
2014 " 'cabs',\n",
2015 " 'dabs',\n",
2016 " 'gabs',\n",
2017 " 'jabs',\n",
2018 " 'labs',\n",
2019 " 'tabs',\n",
2020 " 'tads',\n",
2021 " 'cads',\n",
2022 " 'dads',\n",
2023 " 'fads',\n",
2024 " 'gads',\n",
2025 " 'lads',\n",
2026 " 'mads',\n",
2027 " 'pads',\n",
2028 " 'wads',\n",
2029 " 'weds',\n",
2030 " 'beds',\n",
2031 " 'feds',\n",
2032 " 'reds',\n",
2033 " 'rids',\n",
2034 " 'aids',\n",
2035 " 'bids',\n",
2036 " 'kids',\n",
2037 " 'lids',\n",
2038 " 'lips',\n",
2039 " 'dips',\n",
2040 " 'hips',\n",
2041 " 'nips',\n",
2042 " 'pips',\n",
2043 " 'rips',\n",
2044 " 'sips',\n",
2045 " 'tips',\n",
2046 " 'yips',\n",
2047 " 'zips',\n",
2048 " 'zaps',\n",
2049 " 'caps',\n",
2050 " 'gaps',\n",
2051 " 'laps',\n",
2052 " 'maps',\n",
2053 " 'naps',\n",
2054 " 'paps',\n",
2055 " 'raps',\n",
2056 " 'saps',\n",
2057 " 'taps',\n",
2058 " 'yaps',\n",
2059 " 'yeps',\n",
2060 " 'peps',\n",
2061 " 'reps',\n",
2062 " 'refs',\n",
2063 " 'reis',\n",
2064 " 'leis',\n",
2065 " 'legs',\n",
2066 " 'begs',\n",
2067 " 'kegs',\n",
2068 " 'megs',\n",
2069 " 'pegs',\n",
2070 " 'pens',\n",
2071 " 'dens',\n",
2072 " 'fens',\n",
2073 " 'hens',\n",
2074 " 'kens',\n",
2075 " 'lens',\n",
2076 " 'tens',\n",
2077 " 'wens',\n",
2078 " 'yens',\n",
2079 " 'yews',\n",
2080 " 'hews',\n",
2081 " 'mews',\n",
2082 " 'news',\n",
2083 " 'pews',\n",
2084 " 'sews',\n",
2085 " 'saws',\n",
2086 " 'caws',\n",
2087 " 'haws',\n",
2088 " 'jaws',\n",
2089 " 'laws',\n",
2090 " 'maws',\n",
2091 " 'paws',\n",
2092 " 'yaws',\n",
2093 " 'yaks',\n",
2094 " 'oaks',\n",
2095 " 'oafs',\n",
2096 " 'oars',\n",
2097 " 'bars',\n",
2098 " 'cars',\n",
2099 " 'ears',\n",
2100 " 'jars',\n",
2101 " 'mars',\n",
2102 " 'pars',\n",
2103 " 'tars',\n",
2104 " 'wars',\n",
2105 " 'ways',\n",
2106 " 'bays',\n",
2107 " 'days',\n",
2108 " 'gays',\n",
2109 " 'hays',\n",
2110 " 'jays',\n",
2111 " 'lays',\n",
2112 " 'nays',\n",
2113 " 'pays',\n",
2114 " 'rays',\n",
2115 " 'says',\n",
2116 " 'sacs',\n",
2117 " 'secs',\n",
2118 " 'sets',\n",
2119 " 'bets',\n",
2120 " 'gets',\n",
2121 " 'jets',\n",
2122 " 'lets',\n",
2123 " 'nets',\n",
2124 " 'pets',\n",
2125 " 'vets',\n",
2126 " 'wets',\n",
2127 " 'wits',\n",
2128 " 'bits',\n",
2129 " 'fits',\n",
2130 " 'hits',\n",
2131 " 'kits',\n",
2132 " 'nits',\n",
2133 " 'pits',\n",
2134 " 'sits',\n",
2135 " 'tits',\n",
2136 " 'tats',\n",
2137 " 'bats',\n",
2138 " 'cats',\n",
2139 " 'eats',\n",
2140 " 'fats',\n",
2141 " 'hats',\n",
2142 " 'lats',\n",
2143 " 'mats',\n",
2144 " 'oats',\n",
2145 " 'pats',\n",
2146 " 'rats',\n",
2147 " 'vats',\n",
2148 " 'vans',\n",
2149 " 'bans',\n",
2150 " 'cans',\n",
2151 " 'fans',\n",
2152 " 'mans',\n",
2153 " 'pans',\n",
2154 " 'sans',\n",
2155 " 'tans',\n",
2156 " 'tins',\n",
2157 " 'bins',\n",
2158 " 'dins',\n",
2159 " 'fins',\n",
2160 " 'gins',\n",
2161 " 'pins',\n",
2162 " 'sins',\n",
2163 " 'wins',\n",
2164 " 'wind',\n",
2165 " 'bind',\n",
2166 " 'find',\n",
2167 " 'hind',\n",
2168 " 'kind',\n",
2169 " 'mind',\n",
2170 " 'rind',\n",
2171 " 'ring',\n",
2172 " 'ding',\n",
2173 " 'king',\n",
2174 " 'ping',\n",
2175 " 'sing',\n",
2176 " 'ting',\n",
2177 " 'wing',\n",
2178 " 'wine',\n",
2179 " 'dine',\n",
2180 " 'fine',\n",
2181 " 'line',\n",
2182 " 'mine',\n",
2183 " 'nine',\n",
2184 " 'pine',\n",
2185 " 'sine',\n",
2186 " 'tine',\n",
2187 " 'vine',\n",
2188 " 'vane']"
2189 ]
2190 },
2191 "execution_count": 22,
2192 "metadata": {},
2193 "output_type": "execute_result"
2194 }
2195 ],
2196 "source": [
2197 "dfs_search('cart', 'vane')"
2198 ]
2199 },
2200 {
2201 "cell_type": "code",
2202 "execution_count": 23,
2203 "metadata": {
2204 "collapsed": true
2205 },
2206 "outputs": [],
2207 "source": [
2208 "def astar_search(start, goal, debug=False):\n",
2209 " agenda = [(distance(start, goal), [start])]\n",
2210 " heapq.heapify(agenda)\n",
2211 " finished = False\n",
2212 " while not finished and agenda:\n",
2213 " _, current = heapq.heappop(agenda)\n",
2214 " if debug:\n",
2215 " print(current)\n",
2216 " if current[-1] == goal:\n",
2217 " finished = True\n",
2218 " else:\n",
2219 " successors = extend(current)\n",
2220 " for s in successors:\n",
2221 " heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
2222 " if agenda:\n",
2223 " return current\n",
2224 " else:\n",
2225 " return None "
2226 ]
2227 },
2228 {
2229 "cell_type": "code",
2230 "execution_count": 24,
2231 "metadata": {
2232 "collapsed": false
2233 },
2234 "outputs": [
2235 {
2236 "name": "stdout",
2237 "output_type": "stream",
2238 "text": [
2239 "['cart']\n",
2240 "['cart', 'cant']\n",
2241 "['cart', 'cant', 'cane']\n",
2242 "['cart', 'cant', 'cane', 'vane']\n"
2243 ]
2244 },
2245 {
2246 "data": {
2247 "text/plain": [
2248 "['cart', 'cant', 'cane', 'vane']"
2249 ]
2250 },
2251 "execution_count": 24,
2252 "metadata": {},
2253 "output_type": "execute_result"
2254 }
2255 ],
2256 "source": [
2257 "astar_search('cart', 'vane', debug=True)"
2258 ]
2259 },
2260 {
2261 "cell_type": "code",
2262 "execution_count": 25,
2263 "metadata": {
2264 "collapsed": true
2265 },
2266 "outputs": [],
2267 "source": [
2268 "def astar_search_closed(start, goal, debug=False):\n",
2269 " agenda = [(distance(start, goal), [start])]\n",
2270 " heapq.heapify(agenda)\n",
2271 " closed = set()\n",
2272 " finished = False\n",
2273 " while not finished and agenda:\n",
2274 " _, current = heapq.heappop(agenda)\n",
2275 " if debug:\n",
2276 " print(current)\n",
2277 " if current[-1] == goal:\n",
2278 " finished = True\n",
2279 " else:\n",
2280 " closed.add(current[-1])\n",
2281 " successors = extend(current, closed)\n",
2282 " for s in successors:\n",
2283 " heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
2284 " if agenda:\n",
2285 " return current\n",
2286 " else:\n",
2287 " return None "
2288 ]
2289 },
2290 {
2291 "cell_type": "code",
2292 "execution_count": 26,
2293 "metadata": {
2294 "collapsed": false
2295 },
2296 "outputs": [
2297 {
2298 "name": "stdout",
2299 "output_type": "stream",
2300 "text": [
2301 "['cart']\n",
2302 "['cart', 'cant']\n",
2303 "['cart', 'cant', 'cane']\n",
2304 "['cart', 'cant', 'cane', 'vane']\n"
2305 ]
2306 },
2307 {
2308 "data": {
2309 "text/plain": [
2310 "['cart', 'cant', 'cane', 'vane']"
2311 ]
2312 },
2313 "execution_count": 26,
2314 "metadata": {},
2315 "output_type": "execute_result"
2316 }
2317 ],
2318 "source": [
2319 "astar_search_closed('cart', 'vane', debug=True)"
2320 ]
2321 },
2322 {
2323 "cell_type": "markdown",
2324 "metadata": {},
2325 "source": [
2326 "# Mutually-reachable sets\n",
2327 "\n",
2328 "Find the transitive closure of the `neighbours` relation, so we can see which words can be transformed into which other words."
2329 ]
2330 },
2331 {
2332 "cell_type": "code",
2333 "execution_count": 77,
2334 "metadata": {
2335 "collapsed": false
2336 },
2337 "outputs": [
2338 {
2339 "data": {
2340 "text/plain": [
2341 "94"
2342 ]
2343 },
2344 "execution_count": 77,
2345 "metadata": {},
2346 "output_type": "execute_result"
2347 }
2348 ],
2349 "source": [
2350 "candidates = [set([k] + neighbours[k]) for k in neighbours]\n",
2351 "reachables = []\n",
2352 "while candidates:\n",
2353 " current = set(candidates.pop())\n",
2354 " altered = False\n",
2355 " for other in candidates:\n",
2356 " if current.intersection(other):\n",
2357 " altered = True\n",
2358 " current.update(other)\n",
2359 " candidates.remove(other)\n",
2360 " if altered:\n",
2361 " candidates.append(current)\n",
2362 " else:\n",
2363 " reachables.append(current)\n",
2364 "\n",
2365 "len(reachables)"
2366 ]
2367 },
2368 {
2369 "cell_type": "code",
2370 "execution_count": 78,
2371 "metadata": {
2372 "collapsed": false
2373 },
2374 "outputs": [
2375 {
2376 "data": {
2377 "text/plain": [
2378 "2204"
2379 ]
2380 },
2381 "execution_count": 78,
2382 "metadata": {},
2383 "output_type": "execute_result"
2384 }
2385 ],
2386 "source": [
2387 "len(max(reachables, key=len))"
2388 ]
2389 },
2390 {
2391 "cell_type": "code",
2392 "execution_count": 79,
2393 "metadata": {
2394 "collapsed": false
2395 },
2396 "outputs": [
2397 {
2398 "data": {
2399 "text/plain": [
2400 "1"
2401 ]
2402 },
2403 "execution_count": 79,
2404 "metadata": {},
2405 "output_type": "execute_result"
2406 }
2407 ],
2408 "source": [
2409 "len(min(reachables, key=len))"
2410 ]
2411 },
2412 {
2413 "cell_type": "code",
2414 "execution_count": 80,
2415 "metadata": {
2416 "collapsed": false,
2417 "scrolled": true
2418 },
2419 "outputs": [
2420 {
2421 "data": {
2422 "text/plain": [
2423 "Counter({1: 75, 2: 6, 3: 7, 4: 2, 5: 2, 6: 1, 2204: 1})"
2424 ]
2425 },
2426 "execution_count": 80,
2427 "metadata": {},
2428 "output_type": "execute_result"
2429 }
2430 ],
2431 "source": [
2432 "collections.Counter(len(r) for r in reachables)"
2433 ]
2434 },
2435 {
2436 "cell_type": "code",
2437 "execution_count": 81,
2438 "metadata": {
2439 "collapsed": false
2440 },
2441 "outputs": [
2442 {
2443 "data": {
2444 "text/plain": [
2445 "[5]"
2446 ]
2447 },
2448 "execution_count": 81,
2449 "metadata": {},
2450 "output_type": "execute_result"
2451 }
2452 ],
2453 "source": [
2454 "[len(r) for r in reachables if 'abbe' in r]"
2455 ]
2456 },
2457 {
2458 "cell_type": "code",
2459 "execution_count": 82,
2460 "metadata": {
2461 "collapsed": false
2462 },
2463 "outputs": [
2464 {
2465 "data": {
2466 "text/plain": [
2467 "[{'abbe', 'able', 'ably', 'ally', 'axle'}]"
2468 ]
2469 },
2470 "execution_count": 82,
2471 "metadata": {},
2472 "output_type": "execute_result"
2473 }
2474 ],
2475 "source": [
2476 "[r for r in reachables if 'abbe' in r]"
2477 ]
2478 },
2479 {
2480 "cell_type": "code",
2481 "execution_count": 83,
2482 "metadata": {
2483 "collapsed": false
2484 },
2485 "outputs": [
2486 {
2487 "data": {
2488 "text/plain": [
2489 "['buns', 'bunk', 'punk']"
2490 ]
2491 },
2492 "execution_count": 83,
2493 "metadata": {},
2494 "output_type": "execute_result"
2495 }
2496 ],
2497 "source": [
2498 "astar_search('buns', 'punk')"
2499 ]
2500 },
2501 {
2502 "cell_type": "code",
2503 "execution_count": 84,
2504 "metadata": {
2505 "collapsed": true
2506 },
2507 "outputs": [],
2508 "source": [
2509 "for a in reachables:\n",
2510 " for b in reachables:\n",
2511 " if a != b:\n",
2512 " if not a.isdisjoint(b):\n",
2513 " print(a, b)"
2514 ]
2515 },
2516 {
2517 "cell_type": "code",
2518 "execution_count": 85,
2519 "metadata": {
2520 "collapsed": true
2521 },
2522 "outputs": [],
2523 "source": [
2524 "# longest_chain = []\n",
2525 "# with open('all-chains-4.txt', 'w', 1) as f:\n",
2526 "# for ws in reachables:\n",
2527 "# for s in ws:\n",
2528 "# for t in ws:\n",
2529 "# if s < t:\n",
2530 "# chain = astar_search(s, t)\n",
2531 "# if chain:\n",
2532 "# f.write('{}\\n'.format(chain))\n",
2533 "# if len(chain) > len(longest_chain):\n",
2534 "# longest_chain = chain\n",
2535 "\n",
2536 "# longest_chain"
2537 ]
2538 },
2539 {
2540 "cell_type": "code",
2541 "execution_count": 86,
2542 "metadata": {
2543 "collapsed": true
2544 },
2545 "outputs": [],
2546 "source": [
2547 "bigset = max(reachables, key=len)"
2548 ]
2549 },
2550 {
2551 "cell_type": "code",
2552 "execution_count": 87,
2553 "metadata": {
2554 "collapsed": false
2555 },
2556 "outputs": [
2557 {
2558 "name": "stdout",
2559 "output_type": "stream",
2560 "text": [
2561 "['late', 'lats', 'lets', 'leas', 'seas', 'seam', 'swam', 'sway']\n",
2562 "['leap', 'heap', 'hear', 'dear', 'deer']\n",
2563 "['peel', 'peek', 'perk', 'park', 'nark']\n",
2564 "['sing', 'sang', 'sand', 'said', 'sail', 'hail', 'haul']\n",
2565 "['vats', 'bats', 'bets', 'bees', 'been', 'teen', 'then', 'thin', 'this', 'thus', 'thud']\n",
2566 "['sues', 'sees', 'seen', 'sewn', 'hewn']\n",
2567 "['rash', 'bash', 'bast', 'bait', 'bail', 'hail', 'hair', 'heir']\n",
2568 "['apex', 'aped', 'sped', 'seed', 'deed', 'dead', 'deal', 'veal']\n",
2569 "['gulf', 'golf', 'gold', 'bold', 'bond', 'bony', 'tony']\n",
2570 "['snag', 'shag', 'shat', 'seat', 'peat', 'pent', 'pint', 'mint']\n",
2571 "['rife', 'rime', 'rims', 'rums', 'cums', 'cuss']\n",
2572 "['diss', 'kiss', 'kits']\n",
2573 "['gyps', 'gaps', 'gads', 'wads', 'wade', 'wide', 'tide']\n",
2574 "['bilk', 'bill', 'bell', 'tell', 'teal', 'tear', 'tzar']\n",
2575 "['logo', 'loge', 'lode', 'lade', 'jade', 'jape']\n",
2576 "['hunt', 'bunt', 'buns', 'nuns', 'nubs']\n",
2577 "['glow', 'glop', 'plop', 'prop', 'prep', 'peep', 'keep']\n",
2578 "['iamb', 'lamb', 'lams', 'laps', 'lips', 'pips']\n",
2579 "['pain', 'lain', 'laid', 'land', 'lend', 'vend', 'veld']\n",
2580 "['fake', 'bake', 'bare', 'bars', 'ears', 'errs', 'ergs', 'eggs', 'egos']\n"
2581 ]
2582 }
2583 ],
2584 "source": [
2585 "for _ in range(20):\n",
2586 " start, goal = random.sample(bigset, 2)\n",
2587 " print(astar_search_closed(start, goal))"
2588 ]
2589 },
2590 {
2591 "cell_type": "code",
2592 "execution_count": 38,
2593 "metadata": {
2594 "collapsed": false
2595 },
2596 "outputs": [
2597 {
2598 "data": {
2599 "text/plain": [
2600 "['cops', 'coos', 'coon', 'coin', 'chin', 'thin', 'this', 'thus', 'thug']"
2601 ]
2602 },
2603 "execution_count": 38,
2604 "metadata": {},
2605 "output_type": "execute_result"
2606 }
2607 ],
2608 "source": [
2609 "astar_search('cops', 'thug')"
2610 ]
2611 },
2612 {
2613 "cell_type": "code",
2614 "execution_count": 39,
2615 "metadata": {
2616 "collapsed": false
2617 },
2618 "outputs": [
2619 {
2620 "data": {
2621 "text/plain": [
2622 "[2204]"
2623 ]
2624 },
2625 "execution_count": 39,
2626 "metadata": {},
2627 "output_type": "execute_result"
2628 }
2629 ],
2630 "source": [
2631 "[len(r) for r in reachables if 'love' in r if 'hate' in r]"
2632 ]
2633 },
2634 {
2635 "cell_type": "code",
2636 "execution_count": 40,
2637 "metadata": {
2638 "collapsed": false
2639 },
2640 "outputs": [
2641 {
2642 "data": {
2643 "text/plain": [
2644 "['hate', 'have', 'hove', 'love']"
2645 ]
2646 },
2647 "execution_count": 40,
2648 "metadata": {},
2649 "output_type": "execute_result"
2650 }
2651 ],
2652 "source": [
2653 "astar_search('hate', 'love')"
2654 ]
2655 },
2656 {
2657 "cell_type": "code",
2658 "execution_count": 41,
2659 "metadata": {
2660 "collapsed": false
2661 },
2662 "outputs": [
2663 {
2664 "data": {
2665 "text/plain": [
2666 "['wars', 'ware', 'wave', 'wove', 'love']"
2667 ]
2668 },
2669 "execution_count": 41,
2670 "metadata": {},
2671 "output_type": "execute_result"
2672 }
2673 ],
2674 "source": [
2675 "astar_search('wars', 'love')"
2676 ]
2677 },
2678 {
2679 "cell_type": "code",
2680 "execution_count": 61,
2681 "metadata": {
2682 "collapsed": false
2683 },
2684 "outputs": [
2685 {
2686 "name": "stdout",
2687 "output_type": "stream",
2688 "text": [
2689 "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
2690 "Wall time: 210 µs\n"
2691 ]
2692 },
2693 {
2694 "data": {
2695 "text/plain": [
2696 "5"
2697 ]
2698 },
2699 "execution_count": 61,
2700 "metadata": {},
2701 "output_type": "execute_result"
2702 }
2703 ],
2704 "source": [
2705 "%time len(astar_search('wars', 'love'))"
2706 ]
2707 },
2708 {
2709 "cell_type": "code",
2710 "execution_count": 62,
2711 "metadata": {
2712 "collapsed": false
2713 },
2714 "outputs": [
2715 {
2716 "name": "stdout",
2717 "output_type": "stream",
2718 "text": [
2719 "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
2720 "Wall time: 252 µs\n"
2721 ]
2722 },
2723 {
2724 "data": {
2725 "text/plain": [
2726 "5"
2727 ]
2728 },
2729 "execution_count": 62,
2730 "metadata": {},
2731 "output_type": "execute_result"
2732 }
2733 ],
2734 "source": [
2735 "%time len(astar_search_closed('wars', 'love'))"
2736 ]
2737 },
2738 {
2739 "cell_type": "code",
2740 "execution_count": 63,
2741 "metadata": {
2742 "collapsed": false
2743 },
2744 "outputs": [
2745 {
2746 "name": "stdout",
2747 "output_type": "stream",
2748 "text": [
2749 "CPU times: user 24 ms, sys: 0 ns, total: 24 ms\n",
2750 "Wall time: 24.2 ms\n"
2751 ]
2752 },
2753 {
2754 "data": {
2755 "text/plain": [
2756 "404"
2757 ]
2758 },
2759 "execution_count": 63,
2760 "metadata": {},
2761 "output_type": "execute_result"
2762 }
2763 ],
2764 "source": [
2765 "%time len(dfs_search('wars', 'love'))"
2766 ]
2767 },
2768 {
2769 "cell_type": "code",
2770 "execution_count": 64,
2771 "metadata": {
2772 "collapsed": false
2773 },
2774 "outputs": [
2775 {
2776 "name": "stdout",
2777 "output_type": "stream",
2778 "text": [
2779 "CPU times: user 5min 20s, sys: 76 ms, total: 5min 20s\n",
2780 "Wall time: 5min 20s\n"
2781 ]
2782 },
2783 {
2784 "data": {
2785 "text/plain": [
2786 "5"
2787 ]
2788 },
2789 "execution_count": 64,
2790 "metadata": {},
2791 "output_type": "execute_result"
2792 }
2793 ],
2794 "source": [
2795 "%time len(bfs_search('wars', 'love'))"
2796 ]
2797 },
2798 {
2799 "cell_type": "code",
2800 "execution_count": 65,
2801 "metadata": {
2802 "collapsed": false
2803 },
2804 "outputs": [
2805 {
2806 "name": "stdout",
2807 "output_type": "stream",
2808 "text": [
2809 "CPU times: user 1.44 s, sys: 0 ns, total: 1.44 s\n",
2810 "Wall time: 1.43 s\n"
2811 ]
2812 },
2813 {
2814 "data": {
2815 "text/plain": [
2816 "5"
2817 ]
2818 },
2819 "execution_count": 65,
2820 "metadata": {},
2821 "output_type": "execute_result"
2822 }
2823 ],
2824 "source": [
2825 "%time len(bfs_search_closed('wars', 'love'))"
2826 ]
2827 },
2828 {
2829 "cell_type": "code",
2830 "execution_count": 42,
2831 "metadata": {
2832 "collapsed": false
2833 },
2834 "outputs": [
2835 {
2836 "data": {
2837 "text/plain": [
2838 "['fear', 'feat', 'fest', 'lest', 'lost', 'lose', 'love']"
2839 ]
2840 },
2841 "execution_count": 42,
2842 "metadata": {},
2843 "output_type": "execute_result"
2844 }
2845 ],
2846 "source": [
2847 "astar_search('fear', 'love')"
2848 ]
2849 },
2850 {
2851 "cell_type": "code",
2852 "execution_count": 43,
2853 "metadata": {
2854 "collapsed": false
2855 },
2856 "outputs": [
2857 {
2858 "data": {
2859 "text/plain": [
2860 "['fail', 'fall', 'pall', 'pals', 'pass']"
2861 ]
2862 },
2863 "execution_count": 43,
2864 "metadata": {},
2865 "output_type": "execute_result"
2866 }
2867 ],
2868 "source": [
2869 "astar_search('fail', 'pass')"
2870 ]
2871 },
2872 {
2873 "cell_type": "code",
2874 "execution_count": 44,
2875 "metadata": {
2876 "collapsed": false
2877 },
2878 "outputs": [
2879 {
2880 "data": {
2881 "text/plain": [
2882 "['star', 'soar', 'boar', 'boor', 'boon', 'born']"
2883 ]
2884 },
2885 "execution_count": 44,
2886 "metadata": {},
2887 "output_type": "execute_result"
2888 }
2889 ],
2890 "source": [
2891 "astar_search('star', 'born')"
2892 ]
2893 },
2894 {
2895 "cell_type": "code",
2896 "execution_count": 45,
2897 "metadata": {
2898 "collapsed": false
2899 },
2900 "outputs": [
2901 {
2902 "data": {
2903 "text/plain": [
2904 "['open',\n",
2905 " 'oven',\n",
2906 " 'even',\n",
2907 " 'eves',\n",
2908 " 'eyes',\n",
2909 " 'byes',\n",
2910 " 'bees',\n",
2911 " 'begs',\n",
2912 " 'bags',\n",
2913 " 'bass',\n",
2914 " 'pass']"
2915 ]
2916 },
2917 "execution_count": 45,
2918 "metadata": {},
2919 "output_type": "execute_result"
2920 }
2921 ],
2922 "source": [
2923 "astar_search('open', 'pass')"
2924 ]
2925 },
2926 {
2927 "cell_type": "code",
2928 "execution_count": 46,
2929 "metadata": {
2930 "collapsed": false
2931 },
2932 "outputs": [
2933 {
2934 "data": {
2935 "text/plain": [
2936 "['bass',\n",
2937 " 'lass',\n",
2938 " 'mass',\n",
2939 " 'sass',\n",
2940 " 'puss',\n",
2941 " 'pads',\n",
2942 " 'pals',\n",
2943 " 'pans',\n",
2944 " 'paps',\n",
2945 " 'pars',\n",
2946 " 'pats',\n",
2947 " 'paws',\n",
2948 " 'pays',\n",
2949 " 'past']"
2950 ]
2951 },
2952 "execution_count": 46,
2953 "metadata": {},
2954 "output_type": "execute_result"
2955 }
2956 ],
2957 "source": [
2958 "neighbours['pass']"
2959 ]
2960 },
2961 {
2962 "cell_type": "code",
2963 "execution_count": 47,
2964 "metadata": {
2965 "collapsed": false
2966 },
2967 "outputs": [
2968 {
2969 "data": {
2970 "text/plain": [
2971 "[1]"
2972 ]
2973 },
2974 "execution_count": 47,
2975 "metadata": {},
2976 "output_type": "execute_result"
2977 }
2978 ],
2979 "source": [
2980 "[len(r) for r in reachables if 'exam' in r]"
2981 ]
2982 },
2983 {
2984 "cell_type": "code",
2985 "execution_count": 48,
2986 "metadata": {
2987 "collapsed": false
2988 },
2989 "outputs": [
2990 {
2991 "data": {
2992 "text/plain": [
2993 "[2204]"
2994 ]
2995 },
2996 "execution_count": 48,
2997 "metadata": {},
2998 "output_type": "execute_result"
2999 }
3000 ],
3001 "source": [
3002 "[len(r) for r in reachables if 'star' in r if 'born' in r]"
3003 ]
3004 },
3005 {
3006 "cell_type": "code",
3007 "execution_count": 49,
3008 "metadata": {
3009 "collapsed": false
3010 },
3011 "outputs": [
3012 {
3013 "name": "stdout",
3014 "output_type": "stream",
3015 "text": [
3016 "1 loop, best of 3: 7.9 s per loop\n"
3017 ]
3018 }
3019 ],
3020 "source": [
3021 "%%timeit\n",
3022 "astar_search('bats', 'exit')"
3023 ]
3024 },
3025 {
3026 "cell_type": "code",
3027 "execution_count": 50,
3028 "metadata": {
3029 "collapsed": false
3030 },
3031 "outputs": [
3032 {
3033 "name": "stdout",
3034 "output_type": "stream",
3035 "text": [
3036 "10 loops, best of 3: 141 ms per loop\n"
3037 ]
3038 }
3039 ],
3040 "source": [
3041 "%%timeit\n",
3042 "astar_search_closed('bats', 'exit')"
3043 ]
3044 },
3045 {
3046 "cell_type": "code",
3047 "execution_count": 51,
3048 "metadata": {
3049 "collapsed": false
3050 },
3051 "outputs": [
3052 {
3053 "data": {
3054 "text/plain": [
3055 "['bats',\n",
3056 " 'bans',\n",
3057 " 'band',\n",
3058 " 'sand',\n",
3059 " 'said',\n",
3060 " 'skid',\n",
3061 " 'skit',\n",
3062 " 'smit',\n",
3063 " 'emit',\n",
3064 " 'exit']"
3065 ]
3066 },
3067 "execution_count": 51,
3068 "metadata": {},
3069 "output_type": "execute_result"
3070 }
3071 ],
3072 "source": [
3073 "astar_search_closed('bats', 'exit')"
3074 ]
3075 },
3076 {
3077 "cell_type": "code",
3078 "execution_count": 88,
3079 "metadata": {
3080 "collapsed": false
3081 },
3082 "outputs": [
3083 {
3084 "data": {
3085 "text/plain": [
3086 "{2: [['heel', 'keel'], ['wane', 'wave'], ['cell', 'sell'], ['cons', 'cobs']],\n",
3087 " 3: [['hank', 'haws'], ['bars', 'bets'], ['rats', 'paws'], ['lock', 'hack']],\n",
3088 " 4: [['rule', 'sore'], ['wavy', 'rape'], ['peas', 'ping'], ['bond', 'toll']],\n",
3089 " 5: [['cope', 'yowl'], ['lose', 'loci'], ['rump', 'dash'], ['four', 'dyes']],\n",
3090 " 6: [['boon', 'sell'], ['lots', 'pomp'], ['cola', 'turn'], ['boos', 'laid']],\n",
3091 " 7: [['eave', 'inns'], ['meek', 'mere'], ['keys', 'wily'], ['slam', 'yore']],\n",
3092 " 8: [['hack', 'flip'], ['crag', 'huge'], ['flux', 'gill'], ['play', 'busy']],\n",
3093 " 9: [['lacy', 'whey'], ['wren', 'rook'], ['lire', 'drip'], ['grab', 'lame']],\n",
3094 " 10: [['over', 'turn'], ['worn', 'anew'], ['stow', 'elks'], ['ergo', 'rich']],\n",
3095 " 11: [['bask', 'idea'], ['gabs', 'thud'], ['idea', 'clod'], ['mark', 'ibis']],\n",
3096 " 12: [['umps', 'torn'], ['futz', 'shun'], ['abut', 'face'], ['slug', 'open']],\n",
3097 " 13: [['umps', 'skin'], ['chum', 'rats'], ['fury', 'chum'], ['omen', 'zany']],\n",
3098 " 14: [['chug', 'gaff'], ['atom', 'fizz']],\n",
3099 " 15: [['chug', 'oxen']]}"
3100 ]
3101 },
3102 "execution_count": 88,
3103 "metadata": {},
3104 "output_type": "execute_result"
3105 }
3106 ],
3107 "source": [
3108 "solutions = {}\n",
3109 "for _ in range(10000):\n",
3110 " start, goal = random.sample(bigset, 2)\n",
3111 " solution = astar_search_closed(start, goal)\n",
3112 " sl = len(solution)\n",
3113 " if sl not in solutions:\n",
3114 " solutions[sl] = []\n",
3115 " if len(solutions[sl]) < 4:\n",
3116 " solutions[sl].append([start, goal])\n",
3117 " \n",
3118 "# if len(solution) >= 10:\n",
3119 "# solutions += [solution]\n",
3120 " \n",
3121 "solutions"
3122 ]
3123 },
3124 {
3125 "cell_type": "code",
3126 "execution_count": 91,
3127 "metadata": {
3128 "collapsed": true
3129 },
3130 "outputs": [],
3131 "source": [
3132 "solutions = {2: [['heel', 'keel'], ['wane', 'wave'], ['cell', 'sell'], ['cons', 'cobs']],\n",
3133 " 3: [['hank', 'haws'], ['bars', 'bets'], ['rats', 'paws'], ['lock', 'hack']],\n",
3134 " 4: [['rule', 'sore'], ['wavy', 'rape'], ['peas', 'ping'], ['bond', 'toll']],\n",
3135 " 5: [['cope', 'yowl'], ['lose', 'loci'], ['rump', 'dash'], ['four', 'dyes']],\n",
3136 " 6: [['boon', 'sell'], ['lots', 'pomp'], ['cola', 'turn'], ['boos', 'laid']],\n",
3137 " 7: [['eave', 'inns'], ['meek', 'mere'], ['keys', 'wily'], ['slam', 'yore']],\n",
3138 " 8: [['hack', 'flip'], ['crag', 'huge'], ['flux', 'gill'], ['play', 'busy']],\n",
3139 " 9: [['lacy', 'whey'], ['wren', 'rook'], ['lire', 'drip'], ['grab', 'lame']],\n",
3140 " 10: [['over', 'turn'], ['worn', 'anew'], ['stow', 'elks'], ['ergo', 'rich']],\n",
3141 " 11: [['bask', 'idea'], ['gabs', 'thud'], ['idea', 'clod'], ['mark', 'ibis']],\n",
3142 " 12: [['umps', 'torn'], ['futz', 'shun'], ['abut', 'face'], ['slug', 'open']],\n",
3143 " 13: [['umps', 'skin'], ['chum', 'rats'], ['fury', 'chum'], ['omen', 'zany']],\n",
3144 " 14: [['chug', 'gaff'], ['atom', 'fizz'], ['chug', 'jinn'], ['amen', 'flog'],\n",
3145 " ['buzz', 'grog'], ['imps', 'pros']],\n",
3146 " 15: [['chug', 'oxen'], ['amen', 'doff']]}"
3147 ]
3148 },
3149 {
3150 "cell_type": "code",
3151 "execution_count": 54,
3152 "metadata": {
3153 "collapsed": false
3154 },
3155 "outputs": [
3156 {
3157 "data": {
3158 "text/plain": [
3159 "[('amen', 'doff', 15), ('chug', 'jinn', 14), ('amen', 'flog', 14)]"
3160 ]
3161 },
3162 "execution_count": 54,
3163 "metadata": {},
3164 "output_type": "execute_result"
3165 }
3166 ],
3167 "source": [
3168 "[(s[0], s[-1], len(s)) for s in solutions if len(s) >= 14]"
3169 ]
3170 },
3171 {
3172 "cell_type": "code",
3173 "execution_count": 55,
3174 "metadata": {
3175 "collapsed": false
3176 },
3177 "outputs": [
3178 {
3179 "name": "stdout",
3180 "output_type": "stream",
3181 "text": [
3182 "1 loop, best of 3: 360 ms per loop\n"
3183 ]
3184 }
3185 ],
3186 "source": [
3187 "%%timeit\n",
3188 "astar_search_closed('blab', 'amen')"
3189 ]
3190 },
3191 {
3192 "cell_type": "code",
3193 "execution_count": 56,
3194 "metadata": {
3195 "collapsed": false
3196 },
3197 "outputs": [
3198 {
3199 "name": "stdout",
3200 "output_type": "stream",
3201 "text": [
3202 "CPU times: user 384 ms, sys: 0 ns, total: 384 ms\n",
3203 "Wall time: 385 ms\n"
3204 ]
3205 },
3206 {
3207 "data": {
3208 "text/plain": [
3209 "14"
3210 ]
3211 },
3212 "execution_count": 56,
3213 "metadata": {},
3214 "output_type": "execute_result"
3215 }
3216 ],
3217 "source": [
3218 "%time len(astar_search_closed('blab', 'amen'))"
3219 ]
3220 },
3221 {
3222 "cell_type": "code",
3223 "execution_count": 57,
3224 "metadata": {
3225 "collapsed": false
3226 },
3227 "outputs": [
3228 {
3229 "name": "stdout",
3230 "output_type": "stream",
3231 "text": [
3232 "CPU times: user 124 ms, sys: 0 ns, total: 124 ms\n",
3233 "Wall time: 121 ms\n"
3234 ]
3235 },
3236 {
3237 "data": {
3238 "text/plain": [
3239 "15"
3240 ]
3241 },
3242 "execution_count": 57,
3243 "metadata": {},
3244 "output_type": "execute_result"
3245 }
3246 ],
3247 "source": [
3248 "%time len(astar_search_closed('amen', 'doff'))"
3249 ]
3250 },
3251 {
3252 "cell_type": "code",
3253 "execution_count": 58,
3254 "metadata": {
3255 "collapsed": false
3256 },
3257 "outputs": [
3258 {
3259 "name": "stdout",
3260 "output_type": "stream",
3261 "text": [
3262 "CPU times: user 32 ms, sys: 0 ns, total: 32 ms\n",
3263 "Wall time: 32.4 ms\n"
3264 ]
3265 },
3266 {
3267 "data": {
3268 "text/plain": [
3269 "14"
3270 ]
3271 },
3272 "execution_count": 58,
3273 "metadata": {},
3274 "output_type": "execute_result"
3275 }
3276 ],
3277 "source": [
3278 "%time len(astar_search_closed('chug', 'jinn'))"
3279 ]
3280 },
3281 {
3282 "cell_type": "code",
3283 "execution_count": 59,
3284 "metadata": {
3285 "collapsed": false
3286 },
3287 "outputs": [
3288 {
3289 "name": "stdout",
3290 "output_type": "stream",
3291 "text": [
3292 "CPU times: user 16 ms, sys: 0 ns, total: 16 ms\n",
3293 "Wall time: 17.1 ms\n"
3294 ]
3295 },
3296 {
3297 "data": {
3298 "text/plain": [
3299 "14"
3300 ]
3301 },
3302 "execution_count": 59,
3303 "metadata": {},
3304 "output_type": "execute_result"
3305 }
3306 ],
3307 "source": [
3308 "%time len(astar_search_closed('amen', 'flog'))"
3309 ]
3310 },
3311 {
3312 "cell_type": "code",
3313 "execution_count": 73,
3314 "metadata": {
3315 "collapsed": false
3316 },
3317 "outputs": [
3318 {
3319 "name": "stdout",
3320 "output_type": "stream",
3321 "text": [
3322 "CPU times: user 268 ms, sys: 4 ms, total: 272 ms\n",
3323 "Wall time: 272 ms\n"
3324 ]
3325 },
3326 {
3327 "data": {
3328 "text/plain": [
3329 "14"
3330 ]
3331 },
3332 "execution_count": 73,
3333 "metadata": {},
3334 "output_type": "execute_result"
3335 }
3336 ],
3337 "source": [
3338 "%time len(astar_search_closed('buzz', 'grog'))"
3339 ]
3340 },
3341 {
3342 "cell_type": "code",
3343 "execution_count": 74,
3344 "metadata": {
3345 "collapsed": false
3346 },
3347 "outputs": [
3348 {
3349 "name": "stdout",
3350 "output_type": "stream",
3351 "text": [
3352 "CPU times: user 64 ms, sys: 0 ns, total: 64 ms\n",
3353 "Wall time: 64.1 ms\n"
3354 ]
3355 },
3356 {
3357 "data": {
3358 "text/plain": [
3359 "14"
3360 ]
3361 },
3362 "execution_count": 74,
3363 "metadata": {},
3364 "output_type": "execute_result"
3365 }
3366 ],
3367 "source": [
3368 "%time len(astar_search_closed('imps', 'pros'))"
3369 ]
3370 },
3371 {
3372 "cell_type": "code",
3373 "execution_count": null,
3374 "metadata": {
3375 "collapsed": true
3376 },
3377 "outputs": [],
3378 "source": []
3379 }
3380 ],
3381 "metadata": {
3382 "kernelspec": {
3383 "display_name": "Python 3",
3384 "language": "python",
3385 "name": "python3"
3386 },
3387 "language_info": {
3388 "codemirror_mode": {
3389 "name": "ipython",
3390 "version": 3
3391 },
3392 "file_extension": ".py",
3393 "mimetype": "text/x-python",
3394 "name": "python",
3395 "nbconvert_exporter": "python",
3396 "pygments_lexer": "ipython3",
3397 "version": "3.5.2"
3398 }
3399 },
3400 "nbformat": 4,
3401 "nbformat_minor": 2
3402 }
OU Summer of Code challenge, 2017