From f8a31f9a1391dbafc69ea6042dd213a3baa7a64c Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Mon, 10 Jul 2017 18:45:30 +0300 Subject: [PATCH] Some changes to day 8 --- .../{08-words.txt => 08-offices.txt} | 0 08-word-chains/explore-word-chain-4.ipynb | 414 ++++++++--------- 08-word-chains/word-chain-solution.ipynb | 422 +++++++++++++++--- 3 files changed, 545 insertions(+), 291 deletions(-) rename 08-word-chains/{08-words.txt => 08-offices.txt} (100%) diff --git a/08-word-chains/08-words.txt b/08-word-chains/08-offices.txt similarity index 100% rename from 08-word-chains/08-words.txt rename to 08-word-chains/08-offices.txt diff --git a/08-word-chains/explore-word-chain-4.ipynb b/08-word-chains/explore-word-chain-4.ipynb index c2bca54..da9196a 100644 --- a/08-word-chains/explore-word-chain-4.ipynb +++ b/08-word-chains/explore-word-chain-4.ipynb @@ -2,7 +2,7 @@ "cells": [ { "cell_type": "code", - "execution_count": 1, + "execution_count": 4, "metadata": { "collapsed": true }, @@ -16,7 +16,7 @@ }, { "cell_type": "code", - "execution_count": 2, + "execution_count": 5, "metadata": { "collapsed": false }, @@ -27,19 +27,19 @@ "2336" ] }, - "execution_count": 2, + "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ - "words = [w.strip() for w in open('08-words.txt').readlines()]\n", + "words = [w.strip() for w in open('08-offices.txt').readlines()]\n", "len(words)" ] }, { "cell_type": "code", - "execution_count": 3, + "execution_count": 6, "metadata": { "collapsed": false }, @@ -59,7 +59,7 @@ " 'achy']" ] }, - "execution_count": 3, + "execution_count": 6, "metadata": {}, "output_type": "execute_result" } @@ -70,7 +70,7 @@ }, { "cell_type": "code", - "execution_count": 4, + "execution_count": 7, "metadata": { "collapsed": true }, @@ -87,7 +87,7 @@ }, { "cell_type": "code", - "execution_count": 5, + "execution_count": 8, "metadata": { "collapsed": true }, @@ -102,7 +102,7 @@ }, { "cell_type": "code", - "execution_count": 6, + "execution_count": 9, "metadata": { "collapsed": true }, @@ -114,7 +114,7 @@ }, { "cell_type": "code", - "execution_count": 7, + "execution_count": 10, "metadata": { "collapsed": false }, @@ -125,7 +125,7 @@ "['able']" ] }, - "execution_count": 7, + "execution_count": 10, "metadata": {}, "output_type": "execute_result" } @@ -136,7 +136,7 @@ }, { "cell_type": "code", - "execution_count": 8, + "execution_count": 11, "metadata": { "collapsed": false }, @@ -147,7 +147,7 @@ "['axle', 'abbe', 'ably']" ] }, - "execution_count": 8, + "execution_count": 11, "metadata": {}, "output_type": "execute_result" } @@ -158,7 +158,7 @@ }, { "cell_type": "code", - "execution_count": 9, + "execution_count": 12, "metadata": { "collapsed": true }, @@ -171,7 +171,7 @@ }, { "cell_type": "code", - "execution_count": 10, + "execution_count": 13, "metadata": { "collapsed": false }, @@ -182,7 +182,7 @@ "0" ] }, - "execution_count": 10, + "execution_count": 13, "metadata": {}, "output_type": "execute_result" } @@ -193,7 +193,7 @@ }, { "cell_type": "code", - "execution_count": 11, + "execution_count": 14, "metadata": { "collapsed": true }, @@ -210,7 +210,7 @@ }, { "cell_type": "code", - "execution_count": 12, + "execution_count": 15, "metadata": { "collapsed": false }, @@ -221,7 +221,7 @@ "[['abbe', 'able']]" ] }, - "execution_count": 12, + "execution_count": 15, "metadata": {}, "output_type": "execute_result" } @@ -232,7 +232,7 @@ }, { "cell_type": "code", - "execution_count": 13, + "execution_count": 16, "metadata": { "collapsed": false }, @@ -243,7 +243,7 @@ "[['abbe', 'able', 'axle'], ['abbe', 'able', 'ably']]" ] }, - "execution_count": 13, + "execution_count": 16, "metadata": {}, "output_type": "execute_result" } @@ -254,7 +254,7 @@ }, { "cell_type": "code", - "execution_count": 14, + "execution_count": 17, "metadata": { "collapsed": false }, @@ -265,7 +265,7 @@ "[['abbe', 'able', 'ably', 'ally']]" ] }, - "execution_count": 14, + "execution_count": 17, "metadata": {}, "output_type": "execute_result" } @@ -276,7 +276,7 @@ }, { "cell_type": "code", - "execution_count": 15, + "execution_count": 18, "metadata": { "collapsed": true }, @@ -302,7 +302,7 @@ }, { "cell_type": "code", - "execution_count": 16, + "execution_count": 19, "metadata": { "collapsed": true }, @@ -330,7 +330,7 @@ }, { "cell_type": "code", - "execution_count": 17, + "execution_count": 20, "metadata": { "collapsed": false }, @@ -352,7 +352,7 @@ "['abbe', 'able', 'ably', 'ally']" ] }, - "execution_count": 17, + "execution_count": 20, "metadata": {}, "output_type": "execute_result" } @@ -363,7 +363,7 @@ }, { "cell_type": "code", - "execution_count": 18, + "execution_count": 21, "metadata": { "collapsed": true }, @@ -389,7 +389,7 @@ }, { "cell_type": "code", - "execution_count": 19, + "execution_count": 22, "metadata": { "collapsed": false }, @@ -411,7 +411,7 @@ "['abbe', 'able', 'ably', 'ally']" ] }, - "execution_count": 19, + "execution_count": 22, "metadata": {}, "output_type": "execute_result" } @@ -422,7 +422,7 @@ }, { "cell_type": "code", - "execution_count": 20, + "execution_count": 23, "metadata": { "collapsed": false }, @@ -1567,7 +1567,7 @@ "['cart', 'cant', 'cans', 'vans']" ] }, - "execution_count": 20, + "execution_count": 23, "metadata": {}, "output_type": "execute_result" } @@ -1578,7 +1578,7 @@ }, { "cell_type": "code", - "execution_count": 21, + "execution_count": 24, "metadata": { "collapsed": false }, @@ -1589,7 +1589,7 @@ "['cart', 'cant', 'cane', 'vane']" ] }, - "execution_count": 21, + "execution_count": 24, "metadata": {}, "output_type": "execute_result" } @@ -1600,7 +1600,7 @@ }, { "cell_type": "code", - "execution_count": 22, + "execution_count": 25, "metadata": { "collapsed": false }, @@ -2188,7 +2188,7 @@ " 'vane']" ] }, - "execution_count": 22, + "execution_count": 25, "metadata": {}, "output_type": "execute_result" } @@ -2199,7 +2199,7 @@ }, { "cell_type": "code", - "execution_count": 23, + "execution_count": 26, "metadata": { "collapsed": true }, @@ -2227,7 +2227,7 @@ }, { "cell_type": "code", - "execution_count": 24, + "execution_count": 27, "metadata": { "collapsed": false }, @@ -2248,7 +2248,7 @@ "['cart', 'cant', 'cane', 'vane']" ] }, - "execution_count": 24, + "execution_count": 27, "metadata": {}, "output_type": "execute_result" } @@ -2259,7 +2259,7 @@ }, { "cell_type": "code", - "execution_count": 25, + "execution_count": 28, "metadata": { "collapsed": true }, @@ -2289,7 +2289,7 @@ }, { "cell_type": "code", - "execution_count": 26, + "execution_count": 29, "metadata": { "collapsed": false }, @@ -2310,7 +2310,7 @@ "['cart', 'cant', 'cane', 'vane']" ] }, - "execution_count": 26, + "execution_count": 29, "metadata": {}, "output_type": "execute_result" } @@ -2330,7 +2330,7 @@ }, { "cell_type": "code", - "execution_count": 77, + "execution_count": 30, "metadata": { "collapsed": false }, @@ -2341,7 +2341,7 @@ "94" ] }, - "execution_count": 77, + "execution_count": 30, "metadata": {}, "output_type": "execute_result" } @@ -2367,7 +2367,7 @@ }, { "cell_type": "code", - "execution_count": 78, + "execution_count": 31, "metadata": { "collapsed": false }, @@ -2378,7 +2378,7 @@ "2204" ] }, - "execution_count": 78, + "execution_count": 31, "metadata": {}, "output_type": "execute_result" } @@ -2389,7 +2389,7 @@ }, { "cell_type": "code", - "execution_count": 79, + "execution_count": 32, "metadata": { "collapsed": false }, @@ -2400,7 +2400,7 @@ "1" ] }, - "execution_count": 79, + "execution_count": 32, "metadata": {}, "output_type": "execute_result" } @@ -2411,7 +2411,7 @@ }, { "cell_type": "code", - "execution_count": 80, + "execution_count": 33, "metadata": { "collapsed": false, "scrolled": true @@ -2423,7 +2423,7 @@ "Counter({1: 75, 2: 6, 3: 7, 4: 2, 5: 2, 6: 1, 2204: 1})" ] }, - "execution_count": 80, + "execution_count": 33, "metadata": {}, "output_type": "execute_result" } @@ -2434,7 +2434,7 @@ }, { "cell_type": "code", - "execution_count": 81, + "execution_count": 34, "metadata": { "collapsed": false }, @@ -2445,7 +2445,7 @@ "[5]" ] }, - "execution_count": 81, + "execution_count": 34, "metadata": {}, "output_type": "execute_result" } @@ -2456,7 +2456,7 @@ }, { "cell_type": "code", - "execution_count": 82, + "execution_count": 35, "metadata": { "collapsed": false }, @@ -2467,7 +2467,7 @@ "[{'abbe', 'able', 'ably', 'ally', 'axle'}]" ] }, - "execution_count": 82, + "execution_count": 35, "metadata": {}, "output_type": "execute_result" } @@ -2478,7 +2478,7 @@ }, { "cell_type": "code", - "execution_count": 83, + "execution_count": 36, "metadata": { "collapsed": false }, @@ -2489,7 +2489,7 @@ "['buns', 'bunk', 'punk']" ] }, - "execution_count": 83, + "execution_count": 36, "metadata": {}, "output_type": "execute_result" } @@ -2500,7 +2500,7 @@ }, { "cell_type": "code", - "execution_count": 84, + "execution_count": 37, "metadata": { "collapsed": true }, @@ -2515,7 +2515,7 @@ }, { "cell_type": "code", - "execution_count": 85, + "execution_count": 38, "metadata": { "collapsed": true }, @@ -2538,7 +2538,7 @@ }, { "cell_type": "code", - "execution_count": 86, + "execution_count": 39, "metadata": { "collapsed": true }, @@ -2549,7 +2549,7 @@ }, { "cell_type": "code", - "execution_count": 87, + "execution_count": 40, "metadata": { "collapsed": false }, @@ -2558,26 +2558,26 @@ "name": "stdout", "output_type": "stream", "text": [ - "['late', 'lats', 'lets', 'leas', 'seas', 'seam', 'swam', 'sway']\n", - "['leap', 'heap', 'hear', 'dear', 'deer']\n", - "['peel', 'peek', 'perk', 'park', 'nark']\n", - "['sing', 'sang', 'sand', 'said', 'sail', 'hail', 'haul']\n", - "['vats', 'bats', 'bets', 'bees', 'been', 'teen', 'then', 'thin', 'this', 'thus', 'thud']\n", - "['sues', 'sees', 'seen', 'sewn', 'hewn']\n", - "['rash', 'bash', 'bast', 'bait', 'bail', 'hail', 'hair', 'heir']\n", - "['apex', 'aped', 'sped', 'seed', 'deed', 'dead', 'deal', 'veal']\n", - "['gulf', 'golf', 'gold', 'bold', 'bond', 'bony', 'tony']\n", - "['snag', 'shag', 'shat', 'seat', 'peat', 'pent', 'pint', 'mint']\n", - "['rife', 'rime', 'rims', 'rums', 'cums', 'cuss']\n", - "['diss', 'kiss', 'kits']\n", - "['gyps', 'gaps', 'gads', 'wads', 'wade', 'wide', 'tide']\n", - "['bilk', 'bill', 'bell', 'tell', 'teal', 'tear', 'tzar']\n", - "['logo', 'loge', 'lode', 'lade', 'jade', 'jape']\n", - "['hunt', 'bunt', 'buns', 'nuns', 'nubs']\n", - "['glow', 'glop', 'plop', 'prop', 'prep', 'peep', 'keep']\n", - "['iamb', 'lamb', 'lams', 'laps', 'lips', 'pips']\n", - "['pain', 'lain', 'laid', 'land', 'lend', 'vend', 'veld']\n", - "['fake', 'bake', 'bare', 'bars', 'ears', 'errs', 'ergs', 'eggs', 'egos']\n" + "['bops', 'bogs', 'begs', 'bees', 'byes', 'eyes', 'eyed']\n", + "['foal', 'foil', 'fail']\n", + "['bush', 'bash', 'base', 'bale', 'ball', 'boll']\n", + "['rift', 'lift', 'life', 'live', 'give', 'gave']\n", + "['club', 'clue', 'flue', 'flee', 'fled', 'pled', 'pied', 'lied', 'lien', 'mien']\n", + "['rung', 'dung', 'ding', 'dins', 'dies', 'lies', 'lien']\n", + "['baas', 'bags', 'bugs', 'bums', 'sums', 'sumo']\n", + "['fits', 'bits', 'bins', 'bind']\n", + "['lids', 'bids', 'bias', 'boas', 'boat', 'boot', 'soot', 'snot', 'snob']\n", + "['cake', 'came', 'cams', 'caws', 'cows', 'tows']\n", + "['tort', 'toot', 'trot', 'troy', 'tray', 'tram', 'cram']\n", + "['sews', 'pews', 'pees', 'peed', 'pied']\n", + "['lack', 'hack', 'hawk', 'haws', 'hows', 'tows']\n", + "['dots', 'dons', 'dens', 'dent', 'pent', 'pest', 'peso']\n", + "['ekes', 'eyes', 'byes', 'bees', 'beet', 'bent', 'lent', 'lept']\n", + "['ruin', 'rain', 'gain', 'grin', 'grid', 'arid', 'acid', 'aced', 'iced']\n", + "['sing', 'sins', 'bins', 'bias', 'bras', 'bray', 'tray', 'trap']\n", + "['lira', 'lire', 'wire', 'wise', 'wish']\n", + "['gash', 'cash', 'case', 'cape', 'rape']\n", + "['crop', 'coop', 'coot', 'loot', 'loft']\n" ] } ], @@ -2589,7 +2589,7 @@ }, { "cell_type": "code", - "execution_count": 38, + "execution_count": 41, "metadata": { "collapsed": false }, @@ -2600,7 +2600,7 @@ "['cops', 'coos', 'coon', 'coin', 'chin', 'thin', 'this', 'thus', 'thug']" ] }, - "execution_count": 38, + "execution_count": 41, "metadata": {}, "output_type": "execute_result" } @@ -2611,7 +2611,7 @@ }, { "cell_type": "code", - "execution_count": 39, + "execution_count": 42, "metadata": { "collapsed": false }, @@ -2622,7 +2622,7 @@ "[2204]" ] }, - "execution_count": 39, + "execution_count": 42, "metadata": {}, "output_type": "execute_result" } @@ -2633,7 +2633,7 @@ }, { "cell_type": "code", - "execution_count": 40, + "execution_count": 73, "metadata": { "collapsed": false }, @@ -2641,21 +2641,21 @@ { "data": { "text/plain": [ - "['hate', 'have', 'hove', 'love']" + "[2204]" ] }, - "execution_count": 40, + "execution_count": 73, "metadata": {}, "output_type": "execute_result" } ], "source": [ - "astar_search('hate', 'love')" + "[len(r) for r in reachables if 'stay' in r ]" ] }, { "cell_type": "code", - "execution_count": 41, + "execution_count": 43, "metadata": { "collapsed": false }, @@ -2663,51 +2663,43 @@ { "data": { "text/plain": [ - "['wars', 'ware', 'wave', 'wove', 'love']" + "['hate', 'have', 'hove', 'love']" ] }, - "execution_count": 41, + "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ - "astar_search('wars', 'love')" + "astar_search('hate', 'love')" ] }, { "cell_type": "code", - "execution_count": 61, + "execution_count": 44, "metadata": { "collapsed": false }, "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n", - "Wall time: 210 µs\n" - ] - }, { "data": { "text/plain": [ - "5" + "['wars', 'ware', 'wave', 'wove', 'love']" ] }, - "execution_count": 61, + "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ - "%time len(astar_search('wars', 'love'))" + "astar_search('wars', 'love')" ] }, { "cell_type": "code", - "execution_count": 62, + "execution_count": 45, "metadata": { "collapsed": false }, @@ -2717,7 +2709,7 @@ "output_type": "stream", "text": [ "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n", - "Wall time: 252 µs\n" + "Wall time: 850 µs\n" ] }, { @@ -2726,18 +2718,18 @@ "5" ] }, - "execution_count": 62, + "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ - "%time len(astar_search_closed('wars', 'love'))" + "%time len(astar_search('wars', 'love'))" ] }, { "cell_type": "code", - "execution_count": 63, + "execution_count": 46, "metadata": { "collapsed": false }, @@ -2746,28 +2738,28 @@ "name": "stdout", "output_type": "stream", "text": [ - "CPU times: user 24 ms, sys: 0 ns, total: 24 ms\n", - "Wall time: 24.2 ms\n" + "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n", + "Wall time: 353 µs\n" ] }, { "data": { "text/plain": [ - "404" + "5" ] }, - "execution_count": 63, + "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ - "%time len(dfs_search('wars', 'love'))" + "%time len(astar_search_closed('wars', 'love'))" ] }, { "cell_type": "code", - "execution_count": 64, + "execution_count": 47, "metadata": { "collapsed": false }, @@ -2776,58 +2768,50 @@ "name": "stdout", "output_type": "stream", "text": [ - "CPU times: user 5min 20s, sys: 76 ms, total: 5min 20s\n", - "Wall time: 5min 20s\n" + "CPU times: user 76 ms, sys: 0 ns, total: 76 ms\n", + "Wall time: 75.1 ms\n" ] }, { "data": { "text/plain": [ - "5" + "404" ] }, - "execution_count": 64, + "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ - "%time len(bfs_search('wars', 'love'))" + "%time len(dfs_search('wars', 'love'))" ] }, { "cell_type": "code", - "execution_count": 65, + "execution_count": null, "metadata": { "collapsed": false }, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "CPU times: user 1.44 s, sys: 0 ns, total: 1.44 s\n", - "Wall time: 1.43 s\n" - ] - }, - { - "data": { - "text/plain": [ - "5" - ] - }, - "execution_count": 65, - "metadata": {}, - "output_type": "execute_result" - } - ], + "outputs": [], + "source": [ + "# %time len(bfs_search('wars', 'love'))" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": false + }, + "outputs": [], "source": [ "%time len(bfs_search_closed('wars', 'love'))" ] }, { "cell_type": "code", - "execution_count": 42, + "execution_count": 50, "metadata": { "collapsed": false }, @@ -2838,7 +2822,7 @@ "['fear', 'feat', 'fest', 'lest', 'lost', 'lose', 'love']" ] }, - "execution_count": 42, + "execution_count": 50, "metadata": {}, "output_type": "execute_result" } @@ -2849,7 +2833,7 @@ }, { "cell_type": "code", - "execution_count": 43, + "execution_count": 51, "metadata": { "collapsed": false }, @@ -2860,7 +2844,7 @@ "['fail', 'fall', 'pall', 'pals', 'pass']" ] }, - "execution_count": 43, + "execution_count": 51, "metadata": {}, "output_type": "execute_result" } @@ -2871,7 +2855,7 @@ }, { "cell_type": "code", - "execution_count": 44, + "execution_count": 52, "metadata": { "collapsed": false }, @@ -2882,7 +2866,7 @@ "['star', 'soar', 'boar', 'boor', 'boon', 'born']" ] }, - "execution_count": 44, + "execution_count": 52, "metadata": {}, "output_type": "execute_result" } @@ -2893,7 +2877,7 @@ }, { "cell_type": "code", - "execution_count": 45, + "execution_count": 53, "metadata": { "collapsed": false }, @@ -2914,7 +2898,7 @@ " 'pass']" ] }, - "execution_count": 45, + "execution_count": 53, "metadata": {}, "output_type": "execute_result" } @@ -2925,7 +2909,7 @@ }, { "cell_type": "code", - "execution_count": 46, + "execution_count": 54, "metadata": { "collapsed": false }, @@ -2949,7 +2933,7 @@ " 'past']" ] }, - "execution_count": 46, + "execution_count": 54, "metadata": {}, "output_type": "execute_result" } @@ -2960,7 +2944,7 @@ }, { "cell_type": "code", - "execution_count": 47, + "execution_count": 55, "metadata": { "collapsed": false }, @@ -2971,7 +2955,7 @@ "[1]" ] }, - "execution_count": 47, + "execution_count": 55, "metadata": {}, "output_type": "execute_result" } @@ -2982,7 +2966,7 @@ }, { "cell_type": "code", - "execution_count": 48, + "execution_count": 56, "metadata": { "collapsed": false }, @@ -2993,7 +2977,7 @@ "[2204]" ] }, - "execution_count": 48, + "execution_count": 56, "metadata": {}, "output_type": "execute_result" } @@ -3004,7 +2988,7 @@ }, { "cell_type": "code", - "execution_count": 49, + "execution_count": 57, "metadata": { "collapsed": false }, @@ -3013,7 +2997,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "1 loop, best of 3: 7.9 s per loop\n" + "1 loop, best of 3: 12.3 s per loop\n" ] } ], @@ -3024,7 +3008,7 @@ }, { "cell_type": "code", - "execution_count": 50, + "execution_count": 58, "metadata": { "collapsed": false }, @@ -3033,7 +3017,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "10 loops, best of 3: 141 ms per loop\n" + "1 loop, best of 3: 200 ms per loop\n" ] } ], @@ -3044,7 +3028,7 @@ }, { "cell_type": "code", - "execution_count": 51, + "execution_count": 59, "metadata": { "collapsed": false }, @@ -3064,7 +3048,7 @@ " 'exit']" ] }, - "execution_count": 51, + "execution_count": 59, "metadata": {}, "output_type": "execute_result" } @@ -3075,7 +3059,7 @@ }, { "cell_type": "code", - "execution_count": 88, + "execution_count": 60, "metadata": { "collapsed": false }, @@ -3083,23 +3067,23 @@ { "data": { "text/plain": [ - "{2: [['heel', 'keel'], ['wane', 'wave'], ['cell', 'sell'], ['cons', 'cobs']],\n", - " 3: [['hank', 'haws'], ['bars', 'bets'], ['rats', 'paws'], ['lock', 'hack']],\n", - " 4: [['rule', 'sore'], ['wavy', 'rape'], ['peas', 'ping'], ['bond', 'toll']],\n", - " 5: [['cope', 'yowl'], ['lose', 'loci'], ['rump', 'dash'], ['four', 'dyes']],\n", - " 6: [['boon', 'sell'], ['lots', 'pomp'], ['cola', 'turn'], ['boos', 'laid']],\n", - " 7: [['eave', 'inns'], ['meek', 'mere'], ['keys', 'wily'], ['slam', 'yore']],\n", - " 8: [['hack', 'flip'], ['crag', 'huge'], ['flux', 'gill'], ['play', 'busy']],\n", - " 9: [['lacy', 'whey'], ['wren', 'rook'], ['lire', 'drip'], ['grab', 'lame']],\n", - " 10: [['over', 'turn'], ['worn', 'anew'], ['stow', 'elks'], ['ergo', 'rich']],\n", - " 11: [['bask', 'idea'], ['gabs', 'thud'], ['idea', 'clod'], ['mark', 'ibis']],\n", - " 12: [['umps', 'torn'], ['futz', 'shun'], ['abut', 'face'], ['slug', 'open']],\n", - " 13: [['umps', 'skin'], ['chum', 'rats'], ['fury', 'chum'], ['omen', 'zany']],\n", - " 14: [['chug', 'gaff'], ['atom', 'fizz']],\n", - " 15: [['chug', 'oxen']]}" + "{2: [['exes', 'exec'], ['rush', 'tush'], ['wile', 'wily'], ['shoo', 'shot']],\n", + " 3: [['bins', 'fink'], ['waft', 'wand'], ['heel', 'jell'], ['tent', 'west']],\n", + " 4: [['yore', 'polo'], ['hale', 'case'], ['horn', 'look'], ['tang', 'nuns']],\n", + " 5: [['crab', 'baas'], ['yens', 'dead'], ['work', 'paps'], ['tune', 'zaps']],\n", + " 6: [['mist', 'sold'], ['bats', 'sort'], ['leek', 'mads'], ['loop', 'dome']],\n", + " 7: [['rime', 'hoof'], ['grim', 'reed'], ['lies', 'eave'], ['ties', 'whiz']],\n", + " 8: [['drag', 'lied'], ['ages', 'yawl'], ['earl', 'deal'], ['gins', 'scab']],\n", + " 9: [['tyre', 'swum'], ['dike', 'flux'], ['hour', 'laze'], ['trek', 'bait']],\n", + " 10: [['ides', 'rasp'], ['egos', 'racy'], ['shim', 'ills'], ['bark', 'arty']],\n", + " 11: [['ergo', 'apex'], ['whey', 'owns'], ['anew', 'rapt'], ['thug', 'bate']],\n", + " 12: [['ream', 'imps'], ['meat', 'umps'], ['daze', 'knee'], ['clay', 'over']],\n", + " 13: [['oxen', 'blab'], ['blip', 'omen'], ['twig', 'ibis'], ['chew', 'umps']],\n", + " 14: [['amen', 'blip'], ['umps', 'futz'], ['amps', 'glib'], ['chum', 'whys']],\n", + " 15: [['thug', 'ibis']]}" ] }, - "execution_count": 88, + "execution_count": 60, "metadata": {}, "output_type": "execute_result" } @@ -3123,7 +3107,7 @@ }, { "cell_type": "code", - "execution_count": 91, + "execution_count": 64, "metadata": { "collapsed": true }, @@ -3148,29 +3132,7 @@ }, { "cell_type": "code", - "execution_count": 54, - "metadata": { - "collapsed": false - }, - "outputs": [ - { - "data": { - "text/plain": [ - "[('amen', 'doff', 15), ('chug', 'jinn', 14), ('amen', 'flog', 14)]" - ] - }, - "execution_count": 54, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "[(s[0], s[-1], len(s)) for s in solutions if len(s) >= 14]" - ] - }, - { - "cell_type": "code", - "execution_count": 55, + "execution_count": 66, "metadata": { "collapsed": false }, @@ -3179,7 +3141,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "1 loop, best of 3: 360 ms per loop\n" + "1 loop, best of 3: 487 ms per loop\n" ] } ], @@ -3190,7 +3152,7 @@ }, { "cell_type": "code", - "execution_count": 56, + "execution_count": 67, "metadata": { "collapsed": false }, @@ -3199,8 +3161,8 @@ "name": "stdout", "output_type": "stream", "text": [ - "CPU times: user 384 ms, sys: 0 ns, total: 384 ms\n", - "Wall time: 385 ms\n" + "CPU times: user 768 ms, sys: 0 ns, total: 768 ms\n", + "Wall time: 768 ms\n" ] }, { @@ -3209,7 +3171,7 @@ "14" ] }, - "execution_count": 56, + "execution_count": 67, "metadata": {}, "output_type": "execute_result" } @@ -3220,7 +3182,7 @@ }, { "cell_type": "code", - "execution_count": 57, + "execution_count": 68, "metadata": { "collapsed": false }, @@ -3229,8 +3191,8 @@ "name": "stdout", "output_type": "stream", "text": [ - "CPU times: user 124 ms, sys: 0 ns, total: 124 ms\n", - "Wall time: 121 ms\n" + "CPU times: user 176 ms, sys: 0 ns, total: 176 ms\n", + "Wall time: 176 ms\n" ] }, { @@ -3239,7 +3201,7 @@ "15" ] }, - "execution_count": 57, + "execution_count": 68, "metadata": {}, "output_type": "execute_result" } @@ -3250,7 +3212,7 @@ }, { "cell_type": "code", - "execution_count": 58, + "execution_count": 69, "metadata": { "collapsed": false }, @@ -3259,8 +3221,8 @@ "name": "stdout", "output_type": "stream", "text": [ - "CPU times: user 32 ms, sys: 0 ns, total: 32 ms\n", - "Wall time: 32.4 ms\n" + "CPU times: user 72 ms, sys: 0 ns, total: 72 ms\n", + "Wall time: 70.6 ms\n" ] }, { @@ -3269,7 +3231,7 @@ "14" ] }, - "execution_count": 58, + "execution_count": 69, "metadata": {}, "output_type": "execute_result" } @@ -3280,7 +3242,7 @@ }, { "cell_type": "code", - "execution_count": 59, + "execution_count": 70, "metadata": { "collapsed": false }, @@ -3289,8 +3251,8 @@ "name": "stdout", "output_type": "stream", "text": [ - "CPU times: user 16 ms, sys: 0 ns, total: 16 ms\n", - "Wall time: 17.1 ms\n" + "CPU times: user 32 ms, sys: 0 ns, total: 32 ms\n", + "Wall time: 35.7 ms\n" ] }, { @@ -3299,7 +3261,7 @@ "14" ] }, - "execution_count": 59, + "execution_count": 70, "metadata": {}, "output_type": "execute_result" } @@ -3310,7 +3272,7 @@ }, { "cell_type": "code", - "execution_count": 73, + "execution_count": 71, "metadata": { "collapsed": false }, @@ -3319,8 +3281,8 @@ "name": "stdout", "output_type": "stream", "text": [ - "CPU times: user 268 ms, sys: 4 ms, total: 272 ms\n", - "Wall time: 272 ms\n" + "CPU times: user 376 ms, sys: 4 ms, total: 380 ms\n", + "Wall time: 382 ms\n" ] }, { @@ -3329,7 +3291,7 @@ "14" ] }, - "execution_count": 73, + "execution_count": 71, "metadata": {}, "output_type": "execute_result" } @@ -3340,7 +3302,7 @@ }, { "cell_type": "code", - "execution_count": 74, + "execution_count": 72, "metadata": { "collapsed": false }, @@ -3349,8 +3311,8 @@ "name": "stdout", "output_type": "stream", "text": [ - "CPU times: user 64 ms, sys: 0 ns, total: 64 ms\n", - "Wall time: 64.1 ms\n" + "CPU times: user 72 ms, sys: 4 ms, total: 76 ms\n", + "Wall time: 76.9 ms\n" ] }, { @@ -3359,7 +3321,7 @@ "14" ] }, - "execution_count": 74, + "execution_count": 72, "metadata": {}, "output_type": "execute_result" } diff --git a/08-word-chains/word-chain-solution.ipynb b/08-word-chains/word-chain-solution.ipynb index 038b3c4..77dcdae 100644 --- a/08-word-chains/word-chain-solution.ipynb +++ b/08-word-chains/word-chain-solution.ipynb @@ -56,7 +56,7 @@ } ], "source": [ - "words = [w.strip() for w in open('08-words.txt').readlines()]\n", + "words = [w.strip() for w in open('08-offices.txt').readlines()]\n", "len(words)" ] }, @@ -365,7 +365,7 @@ { "data": { "text/plain": [ - "6" + "['boon', 'boot', 'bolt', 'belt', 'bell', 'sell']" ] }, "execution_count": 17, @@ -374,7 +374,7 @@ } ], "source": [ - "len(astar_search('vice', 'wars'))" + "astar_search_raw('boon', 'sell')" ] }, { @@ -385,20 +385,18 @@ }, "outputs": [ { - "ename": "KeyboardInterrupt", - "evalue": "", - "output_type": "error", - "traceback": [ - "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", - "\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)", - "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbfs_search\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'vice'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'wars'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", - "\u001b[0;32m\u001b[0m in \u001b[0;36mbfs_search\u001b[0;34m(start, goal, debug)\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 11\u001b[0m \u001b[0msuccessors\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mextend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcurrent\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m \u001b[0magenda\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0magenda\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0msuccessors\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 13\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0magenda\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 14\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mcurrent\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", - "\u001b[0;31mKeyboardInterrupt\u001b[0m: " - ] + "data": { + "text/plain": [ + "6" + ] + }, + "execution_count": 18, + "metadata": {}, + "output_type": "execute_result" } ], "source": [ - "len(bfs_search('vice', 'wars'))" + "len(astar_search('vice', 'wars'))" ] }, { @@ -407,6 +405,17 @@ "metadata": { "collapsed": false }, + "outputs": [], + "source": [ + "# len(bfs_search('vice', 'wars'))" + ] + }, + { + "cell_type": "code", + "execution_count": 20, + "metadata": { + "collapsed": false + }, "outputs": [ { "data": { @@ -414,7 +423,7 @@ "6" ] }, - "execution_count": 19, + "execution_count": 20, "metadata": {}, "output_type": "execute_result" } @@ -425,7 +434,7 @@ }, { "cell_type": "code", - "execution_count": 20, + "execution_count": 21, "metadata": { "collapsed": false }, @@ -436,7 +445,7 @@ "793" ] }, - "execution_count": 20, + "execution_count": 21, "metadata": {}, "output_type": "execute_result" } @@ -447,7 +456,7 @@ }, { "cell_type": "code", - "execution_count": 21, + "execution_count": 22, "metadata": { "collapsed": false }, @@ -456,7 +465,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "1000 loops, best of 3: 225 µs per loop\n" + "1000 loops, best of 3: 273 µs per loop\n" ] } ], @@ -467,7 +476,7 @@ }, { "cell_type": "code", - "execution_count": 22, + "execution_count": 23, "metadata": { "collapsed": false }, @@ -476,7 +485,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "10 loops, best of 3: 22.1 ms per loop\n" + "10 loops, best of 3: 25.6 ms per loop\n" ] } ], @@ -487,7 +496,7 @@ }, { "cell_type": "code", - "execution_count": 23, + "execution_count": 24, "metadata": { "collapsed": false }, @@ -496,7 +505,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "1000 loops, best of 3: 280 µs per loop\n" + "1000 loops, best of 3: 300 µs per loop\n" ] } ], @@ -507,38 +516,19 @@ }, { "cell_type": "code", - "execution_count": 24, + "execution_count": 25, "metadata": { "collapsed": false }, - "outputs": [ - { - "ename": "KeyboardInterrupt", - "evalue": "", - "output_type": "error", - "traceback": [ - "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", - "\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)", - "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mget_ipython\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrun_cell_magic\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'timeit'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m''\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"bfs_search('vice', 'wars')\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", - "\u001b[0;32m/usr/local/lib/python3.5/dist-packages/IPython/core/interactiveshell.py\u001b[0m in \u001b[0;36mrun_cell_magic\u001b[0;34m(self, magic_name, line, cell)\u001b[0m\n\u001b[1;32m 2113\u001b[0m \u001b[0mmagic_arg_s\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvar_expand\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mline\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstack_depth\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2114\u001b[0m \u001b[0;32mwith\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbuiltin_trap\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 2115\u001b[0;31m \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfn\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmagic_arg_s\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcell\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 2116\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2117\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n", - "\u001b[0;32m\u001b[0m in \u001b[0;36mtimeit\u001b[0;34m(self, line, cell)\u001b[0m\n", - "\u001b[0;32m/usr/local/lib/python3.5/dist-packages/IPython/core/magic.py\u001b[0m in \u001b[0;36m\u001b[0;34m(f, *a, **k)\u001b[0m\n\u001b[1;32m 186\u001b[0m \u001b[0;31m# but it's overkill for just that one bit of state.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 187\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mmagic_deco\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0marg\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 188\u001b[0;31m \u001b[0mcall\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mlambda\u001b[0m \u001b[0mf\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m*\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mf\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 189\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 190\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mcallable\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0marg\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", - "\u001b[0;32m/usr/local/lib/python3.5/dist-packages/IPython/core/magics/execution.py\u001b[0m in \u001b[0;36mtimeit\u001b[0;34m(self, line, cell)\u001b[0m\n\u001b[1;32m 1042\u001b[0m \u001b[0mnumber\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1043\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0m_\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m10\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1044\u001b[0;31m \u001b[0mtime_number\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtimer\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtimeit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnumber\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 1045\u001b[0m \u001b[0mworst_tuning\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mworst_tuning\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtime_number\u001b[0m \u001b[0;34m/\u001b[0m \u001b[0mnumber\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1046\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mtime_number\u001b[0m \u001b[0;34m>=\u001b[0m \u001b[0;36m0.2\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", - "\u001b[0;32m/usr/local/lib/python3.5/dist-packages/IPython/core/magics/execution.py\u001b[0m in \u001b[0;36mtimeit\u001b[0;34m(self, number)\u001b[0m\n\u001b[1;32m 137\u001b[0m \u001b[0mgc\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdisable\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 138\u001b[0m \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 139\u001b[0;31m \u001b[0mtiming\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minner\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mit\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtimer\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 140\u001b[0m \u001b[0;32mfinally\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 141\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mgcold\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", - "\u001b[0;32m\u001b[0m in \u001b[0;36minner\u001b[0;34m(_it, _timer)\u001b[0m\n", - "\u001b[0;32m\u001b[0m in \u001b[0;36mbfs_search\u001b[0;34m(start, goal, debug)\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 11\u001b[0m \u001b[0msuccessors\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mextend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcurrent\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m \u001b[0magenda\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0magenda\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0msuccessors\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 13\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0magenda\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 14\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mcurrent\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", - "\u001b[0;31mKeyboardInterrupt\u001b[0m: " - ] - } - ], + "outputs": [], "source": [ - "%%timeit\n", - "bfs_search('vice', 'wars')" + "# %%timeit\n", + "# bfs_search('vice', 'wars')" ] }, { "cell_type": "code", - "execution_count": 25, + "execution_count": 26, "metadata": { "collapsed": false }, @@ -547,7 +537,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "1 loop, best of 3: 1.12 s per loop\n" + "1 loop, best of 3: 664 ms per loop\n" ] } ], @@ -558,7 +548,7 @@ }, { "cell_type": "code", - "execution_count": 26, + "execution_count": 27, "metadata": { "collapsed": false }, @@ -567,7 +557,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "10 loops, best of 3: 127 ms per loop\n" + "10 loops, best of 3: 147 ms per loop\n" ] } ], @@ -594,7 +584,7 @@ }, { "cell_type": "code", - "execution_count": 27, + "execution_count": 28, "metadata": { "collapsed": true }, @@ -616,7 +606,39 @@ }, { "cell_type": "code", - "execution_count": 28, + "execution_count": 52, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "['bash',\n", + " 'cash',\n", + " 'dash',\n", + " 'gash',\n", + " 'hash',\n", + " 'lash',\n", + " 'mash',\n", + " 'sash',\n", + " 'wash',\n", + " 'rush',\n", + " 'rasp']" + ] + }, + "execution_count": 52, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "neighbours['rash']" + ] + }, + { + "cell_type": "code", + "execution_count": 29, "metadata": { "collapsed": false, "scrolled": true @@ -629,7 +651,7 @@ " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')" ] }, - "execution_count": 28, + "execution_count": 29, "metadata": {}, "output_type": "execute_result" } @@ -640,7 +662,31 @@ }, { "cell_type": "code", - "execution_count": 29, + "execution_count": 47, + "metadata": { + "collapsed": false, + "scrolled": true + }, + "outputs": [ + { + "data": { + "text/plain": [ + "(11,\n", + " 'bash, cash, dash, gash, hash, lash, mash, rasp, rush, sash, wash')" + ] + }, + "execution_count": 47, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len(reachable_in('rash', 1)), ', '.join(sorted('{}'.format(r) for r in reachable_in('rash', 1)))" + ] + }, + { + "cell_type": "code", + "execution_count": 30, "metadata": { "collapsed": false, "scrolled": true @@ -653,7 +699,7 @@ " '`base`, `bash`, `bask`, `bass`, `bast`, `bath`, `bosh`, `bush`, `case`, `cash`, `cask`, `cast`, `dash`, `dish`, `gash`, `gasp`, `gosh`, `gush`, `hash`, `hasp`, `hath`, `hush`, `lash`, `lass`, `last`, `lath`, `lush`, `mash`, `mask`, `mass`, `mast`, `math`, `mesh`, `mush`, `push`, `ramp`, `rasp`, `ruse`, `rush`, `rusk`, `rust`, `sash`, `sass`, `tush`, `wash`, `wasp`, `wish`')" ] }, - "execution_count": 29, + "execution_count": 30, "metadata": {}, "output_type": "execute_result" } @@ -664,7 +710,31 @@ }, { "cell_type": "code", - "execution_count": 30, + "execution_count": 51, + "metadata": { + "collapsed": false, + "scrolled": true + }, + "outputs": [ + { + "data": { + "text/plain": [ + "(47,\n", + " 'base, bash, bask, bass, bast, bath, bosh, bush, case, cash, cask, cast, dash, dish, gash, gasp, gosh, gush, hash, hasp, hath, hush, lash, lass, last, lath, lush, mash, mask, mass, mast, math, mesh, mush, push, ramp, rasp, ruse, rush, rusk, rust, sash, sass, tush, wash, wasp, wish')" + ] + }, + "execution_count": 51, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len(reachable_in('rash', 2)), ', '.join(sorted('{}'.format(r) for r in reachable_in('rash', 2)))" + ] + }, + { + "cell_type": "code", + "execution_count": 31, "metadata": { "collapsed": false, "scrolled": true @@ -676,7 +746,7 @@ "180" ] }, - "execution_count": 30, + "execution_count": 31, "metadata": {}, "output_type": "execute_result" } @@ -687,7 +757,7 @@ }, { "cell_type": "code", - "execution_count": 31, + "execution_count": 32, "metadata": { "collapsed": false, "scrolled": true @@ -699,7 +769,7 @@ "2195" ] }, - "execution_count": 31, + "execution_count": 32, "metadata": {}, "output_type": "execute_result" } @@ -710,7 +780,7 @@ }, { "cell_type": "code", - "execution_count": 32, + "execution_count": 33, "metadata": { "collapsed": false, "scrolled": true @@ -722,7 +792,7 @@ "2192" ] }, - "execution_count": 32, + "execution_count": 33, "metadata": {}, "output_type": "execute_result" } @@ -733,7 +803,7 @@ }, { "cell_type": "code", - "execution_count": 33, + "execution_count": 34, "metadata": { "collapsed": false, "scrolled": true @@ -743,7 +813,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "100 loops, best of 3: 9.26 ms per loop\n" + "100 loops, best of 3: 8.95 ms per loop\n" ] } ], @@ -754,7 +824,7 @@ }, { "cell_type": "code", - "execution_count": 34, + "execution_count": 35, "metadata": { "collapsed": false, "scrolled": true @@ -764,7 +834,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "100 loops, best of 3: 3.64 ms per loop\n" + "100 loops, best of 3: 4.14 ms per loop\n" ] } ], @@ -773,6 +843,228 @@ "len(reachable_in('rash', 10, trim_extras=True))" ] }, + { + "cell_type": "code", + "execution_count": 36, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "2188" + ] + }, + "execution_count": 36, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len(reachable_in('stay', 10))" + ] + }, + { + "cell_type": "code", + "execution_count": 37, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "2193" + ] + }, + "execution_count": 37, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "len(reachable_in('coax', 10))" + ] + }, + { + "cell_type": "code", + "execution_count": 38, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "280" + ] + }, + "execution_count": 38, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "stay5 = reachable_in('stay', 4)\n", + "len(stay5)" + ] + }, + { + "cell_type": "code", + "execution_count": 39, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "296" + ] + }, + "execution_count": 39, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "extras = set()\n", + "for w in stay5:\n", + " extras.update(neighbours[w])\n", + "extras.difference_update(stay5)\n", + "len(extras)" + ] + }, + { + "cell_type": "code", + "execution_count": 40, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "'leak drab twin glib yell jets heed prep dram step grey keep sacs hock bloc bees hews bend chit sots rent knit brat bobs news gram boot baas grad beet door keen toot mewl plus dial bows jeep boom aloe fret need foul beep brew peek veep poop blue weep akin coop lead foot deed hoot teem quit chop teed bias moor sack atop went bier vets teen pout eery leaf drag belt crag peed czar gees veil whip bout jock wees twit beck boos tell vial pees brag tout sped weed geed load book crop text deem shes mead mock very sewn feet sows cell leis dell hemp week yens than mean send chin sill reek wiry knot reed crew peps pest stem melt room coup yews dock less suck boon clef emit bras loot boob pegs pews bran thin well geek boss term pled whir feed whom rock foam dent glue mews rood goat next sort tens goop stay soft perk troy held meet fees best lees reel gent nest brow spec fest coat leek sues pier moot knob test bogs boys said heft hell flee thaw clue prom self felt hair shoe airs cent whet pock gets pent sics pelt bent club berm saws pets blur prod bops whim sick bell trap lets herd help chip loan sued pens dyer peep peel dual sits suet flue goad toad brad peck moan fell cock been whit lens leap omit wets char crow gout frog shoo nets fist root prim lean jell trig coot flea prop meek beef loam bolt chow skid chew crab floe yeps moat tram vent bets jeez soil soon yous unit newt lock bled deep fled tent tees poor heel grab skis rend lent draw know grow doer yock pert legs'" + ] + }, + "execution_count": 40, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "' '.join(extras)" + ] + }, + { + "cell_type": "code", + "execution_count": 41, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "['coax', 'coat', 'boat', 'boar', 'soar', 'star', 'stay']" + ] + }, + "execution_count": 41, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search('coax', 'stay')" + ] + }, + { + "cell_type": "code", + "execution_count": 42, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "CPU times: user 2.35 s, sys: 0 ns, total: 2.35 s\n", + "Wall time: 2.35 s\n" + ] + }, + { + "data": { + "text/plain": [ + "['coax', 'coat', 'chat', 'shat', 'slat', 'slay', 'stay']" + ] + }, + "execution_count": 42, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%time bfs_search_closed('coax', 'stay')" + ] + }, + { + "cell_type": "code", + "execution_count": 48, + "metadata": { + "collapsed": false + }, + "outputs": [], + "source": [ + "# %time bfs_search('coax', 'stay')" + ] + }, + { + "cell_type": "code", + "execution_count": 44, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "['czar', 'tzar', 'tear', 'sear', 'star', 'stay']" + ] + }, + "execution_count": 44, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "astar_search('czar', 'stay')" + ] + }, + { + "cell_type": "code", + "execution_count": 49, + "metadata": { + "collapsed": false + }, + "outputs": [], + "source": [ + "# %time bfs_search('czar', 'stay')" + ] + }, + { + "cell_type": "code", + "execution_count": 50, + "metadata": { + "collapsed": false + }, + "outputs": [], + "source": [ + "# %time bfs_search('coax', 'stay')" + ] + }, { "cell_type": "code", "execution_count": null, -- 2.34.1