Updated some solutions

diff --git a/02-lifts/lifts-solution.ipynb b/02-lifts/lifts-solution.ipynb
index e938ff7e1e0f53e794396b867f79db8e929ee444..08e3e77784f66e7bc85dce33075acd4ed01cbd29 100644 (file)
--- a/02-lifts/lifts-solution.ipynb
+++ b/02-lifts/lifts-solution.ipynb
@@ -191,7 +191,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
-   "version": "3.6.1"
+   "version": "3.5.2+"
   }
  },
  "nbformat": 4,

diff --git a/word-chains/word-chain-solution.ipynb b/word-chains/word-chain-solution.ipynb
index 0052abce5b05c22c7669b120bca349d24c2d1937..e90cacaabbe306e738ac03b11ccfddfc0d247d3e 100644 (file)
--- a/word-chains/word-chain-solution.ipynb
+++ b/word-chains/word-chain-solution.ipynb
@@ -118,6 +118,20 @@
     "collapsed": true
    },
    "outputs": [],
+   "source": [
+    "def extend_raw(chain):\n",
+    "    nbrs = [w for w in adjacents(chain[-1]) if w in words]\n",
+    "    return [chain + [s] for s in nbrs\n",
+    "           if s not in chain]"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 8,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
    "source": [
     "def bfs_search(start, target, debug=False):\n",
     "    return bfs([[start]], target, debug=debug)"
@@ -125,7 +139,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 8,
+   "execution_count": 9,
    "metadata": {
     "collapsed": true
    },
@@ -150,7 +164,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 9,
+   "execution_count": 10,
    "metadata": {
     "collapsed": true
    },
@@ -162,7 +176,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 10,
+   "execution_count": 11,
    "metadata": {
     "collapsed": true
    },
@@ -187,7 +201,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 57,
+   "execution_count": 12,
    "metadata": {
     "collapsed": true
    },
@@ -201,7 +215,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 55,
+   "execution_count": 13,
    "metadata": {
     "collapsed": true
    },
@@ -227,7 +241,47 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 58,
+   "execution_count": 14,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "def astar_search_raw(start, target, debug=False):\n",
+    "    agenda = [(distance(start, target), [start])]\n",
+    "    heapq.heapify(agenda)\n",
+    "    return astar_raw(agenda, target, debug=debug)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 15,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "def astar_raw(agenda, goal, debug=False):\n",
+    "    finished = False\n",
+    "    while not finished and agenda:\n",
+    "        _, current = heapq.heappop(agenda)\n",
+    "        if debug:\n",
+    "            print(current)\n",
+    "        if current[-1] == goal:\n",
+    "            finished = True\n",
+    "        else:\n",
+    "            successors = extend_raw(current)\n",
+    "            for s in successors:\n",
+    "                heapq.heappush(agenda, (len(current) + distance(s[-1], goal) - 1, s))\n",
+    "    if agenda:\n",
+    "        return current\n",
+    "    else:\n",
+    "        return None        "
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 16,
    "metadata": {},
    "outputs": [
     {
@@ -236,7 +290,7 @@
        "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
       ]
      },
-     "execution_count": 58,
+     "execution_count": 16,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -247,7 +301,27 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 60,
+   "execution_count": 17,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "['vice', 'dice', 'dire', 'dare', 'ware', 'wars']"
+      ]
+     },
+     "execution_count": 17,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "astar_search_raw('vice', 'wars')"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 18,
    "metadata": {},
    "outputs": [
     {
@@ -256,7 +330,7 @@
        "6"
       ]
      },
-     "execution_count": 60,
+     "execution_count": 18,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -267,7 +341,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 15,
+   "execution_count": 19,
    "metadata": {},
    "outputs": [
     {
@@ -276,7 +350,7 @@
        "6"
       ]
      },
-     "execution_count": 15,
+     "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -287,7 +361,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 16,
+   "execution_count": 20,
    "metadata": {},
    "outputs": [
     {
@@ -296,7 +370,7 @@
        "793"
       ]
      },
-     "execution_count": 16,
+     "execution_count": 20,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -307,14 +381,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 17,
+   "execution_count": 21,
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "10000 loops, best of 3: 154 µs per loop\n"
+      "10000 loops, best of 3: 153 µs per loop\n"
      ]
     }
    ],
@@ -325,14 +399,32 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 18,
+   "execution_count": 22,
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "1 loop, best of 3: 1min 40s per loop\n"
+      "100 loops, best of 3: 15.8 ms per loop\n"
+     ]
+    }
+   ],
+   "source": [
+    "%%timeit\n",
+    "astar_search_raw('vice', 'wars')"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 23,
+   "metadata": {},
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "1 loop, best of 3: 1min 42s per loop\n"
      ]
     }
    ],
@@ -343,14 +435,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 19,
+   "execution_count": 24,
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "10 loops, best of 3: 86.3 ms per loop\n"
+      "10 loops, best of 3: 88 ms per loop\n"
      ]
     }
    ],
@@ -377,7 +469,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 37,
+   "execution_count": 25,
    "metadata": {
     "collapsed": true
    },
@@ -399,7 +491,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 38,
+   "execution_count": 26,
    "metadata": {
     "scrolled": true
    },
@@ -411,7 +503,7 @@
        " '`bash`, `cash`, `dash`, `gash`, `hash`, `lash`, `mash`, `rasp`, `rush`, `sash`, `wash`')"
       ]
      },
-     "execution_count": 38,
+     "execution_count": 26,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -422,7 +514,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 39,
+   "execution_count": 27,
    "metadata": {
     "scrolled": true
    },
@@ -434,7 +526,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": 39,
+     "execution_count": 27,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -445,7 +537,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 40,
+   "execution_count": 28,
    "metadata": {
     "scrolled": true
    },
@@ -456,7 +548,7 @@
        "180"
       ]
      },
-     "execution_count": 40,
+     "execution_count": 28,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -467,7 +559,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 48,
+   "execution_count": 29,
    "metadata": {
     "scrolled": true
    },
@@ -478,7 +570,7 @@
        "2195"
       ]
      },
-     "execution_count": 48,
+     "execution_count": 29,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -489,7 +581,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 47,
+   "execution_count": 30,
    "metadata": {
     "scrolled": true
    },
@@ -500,7 +592,7 @@
        "2192"
       ]
      },
-     "execution_count": 47,
+     "execution_count": 30,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -511,7 +603,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 46,
+   "execution_count": 31,
    "metadata": {
     "scrolled": true
    },
@@ -520,7 +612,7 @@
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "100 loops, best of 3: 5.97 ms per loop\n"
+      "100 loops, best of 3: 5.96 ms per loop\n"
      ]
     }
    ],
@@ -531,7 +623,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 44,
+   "execution_count": 32,
    "metadata": {
     "scrolled": true
    },
@@ -540,7 +632,7 @@
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "100 loops, best of 3: 3.1 ms per loop\n"
+      "100 loops, best of 3: 2.75 ms per loop\n"
      ]
     }
    ],