Using sets in solution, stand-alone solution

[ou-summer-of-code-2017.git] / 10-word-search / wordsearch-solution.ipynb

diff --git a/10-word-search/wordsearch-solution.ipynb b/10-word-search/wordsearch-solution.ipynb
index 5c5269fe7aaef5a78b4d878ed05b0d19ab0df2f2..bf6f6c111d4a1fb3cbcd2e98855cae20994a4b14 100644 (file)
--- a/10-word-search/wordsearch-solution.ipynb
+++ b/10-word-search/wordsearch-solution.ipynb
@@ -185,7 +185,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 8,
+   "execution_count": 30,
    "metadata": {
     "collapsed": true
    },
@@ -195,7 +195,7 @@
     "    lines = [l.strip() for l in open(fn).readlines()]\n",
     "    w, h = [int(s) for s in lines[0].split('x')]\n",
     "    grid = lines[1:h+1]\n",
-    "    words = lines[h+1:]\n",
+    "    words = set(lines[h+1:])\n",
     "    return w, h, grid, words"
    ]
   },
@@ -237,7 +237,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 10,
+   "execution_count": 31,
    "metadata": {},
    "outputs": [
     {
@@ -246,7 +246,7 @@
        "(100, 100)"
       ]
      },
-     "execution_count": 10,
+     "execution_count": 31,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -265,7 +265,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 11,
+   "execution_count": 32,
    "metadata": {
     "collapsed": true
    },
@@ -281,7 +281,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 12,
+   "execution_count": 33,
    "metadata": {},
    "outputs": [
     {
@@ -290,7 +290,7 @@
        "8092"
       ]
      },
-     "execution_count": 12,
+     "execution_count": 33,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -301,14 +301,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 13,
+   "execution_count": 34,
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "1 loop, best of 3: 31.3 s per loop\n"
+      "1 loop, best of 3: 6.79 s per loop\n"
      ]
     }
    ],
@@ -319,23 +319,64 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 14,
+   "execution_count": 35,
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "1149"
+       "(1149, 1149, 1149)"
       ]
      },
-     "execution_count": 14,
+     "execution_count": 35,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
     "width, height, grid, words = puzzle\n",
-    "len(present_many(grid, words))"
+    "presences = present_many(grid, words)\n",
+    "found_words = [p[0] for p in presences]\n",
+    "len(presences), len(found_words), len(set(found_words))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 38,
+   "metadata": {},
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "1 loop, best of 3: 6.76 s per loop\n"
+     ]
+    }
+   ],
+   "source": [
+    "%%timeit\n",
+    "presences = present_many(grid, words)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 37,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "(1149, 1149)"
+      ]
+     },
+     "execution_count": 37,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "found_words = [p[0] for p in presences]\n",
+    "len(found_words), len(set(found_words))"
    ]
   },
   {
@@ -459,7 +500,7 @@
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "1 loop, best of 3: 31.4 s per loop\n"
+      "1 loop, best of 3: 30.8 s per loop\n"
      ]
     }
    ],