Added more tour shape images

[ou-summer-of-code-2017.git] / 06-tour-shapes / tour-shapes-solution.ipynb

diff --git a/06-tour-shapes/tour-shapes-solution.ipynb b/06-tour-shapes/tour-shapes-solution.ipynb
index 9a0a4e14f53a311727a5fe383d50b41bc552d6fe..11bba605beee992edd10b613a5b619cb4f44ee78 100644 (file)
--- a/06-tour-shapes/tour-shapes-solution.ipynb
+++ b/06-tour-shapes/tour-shapes-solution.ipynb
@@ -11,7 +11,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 1,
+   "execution_count": 2,
    "metadata": {
     "collapsed": true
    },
@@ -28,7 +28,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 2,
+   "execution_count": 3,
    "metadata": {
     "collapsed": true
    },
@@ -55,7 +55,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 3,
+   "execution_count": 4,
    "metadata": {
     "collapsed": true
    },
@@ -67,7 +67,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 4,
+   "execution_count": 5,
    "metadata": {
     "collapsed": true
    },
@@ -86,7 +86,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 5,
+   "execution_count": 6,
    "metadata": {
     "collapsed": true
    },
@@ -105,7 +105,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 6,
+   "execution_count": 7,
    "metadata": {
     "collapsed": true
    },
@@ -122,7 +122,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 7,
+   "execution_count": 8,
    "metadata": {
     "collapsed": true
    },
@@ -134,7 +134,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 8,
+   "execution_count": 9,
    "metadata": {
     "collapsed": true
    },
@@ -148,7 +148,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 9,
+   "execution_count": 10,
    "metadata": {
     "collapsed": true
    },
@@ -174,7 +174,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 10,
+   "execution_count": 11,
    "metadata": {
     "collapsed": true
    },
@@ -197,7 +197,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 11,
+   "execution_count": 12,
    "metadata": {
     "collapsed": true
    },
@@ -210,7 +210,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 12,
+   "execution_count": 13,
    "metadata": {
     "collapsed": true
    },
@@ -221,7 +221,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 13,
+   "execution_count": 14,
    "metadata": {
     "collapsed": true
    },
@@ -236,7 +236,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 14,
+   "execution_count": 15,
    "metadata": {
     "collapsed": true
    },
@@ -248,7 +248,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 15,
+   "execution_count": 16,
    "metadata": {
     "collapsed": true
    },
@@ -260,7 +260,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 16,
+   "execution_count": 17,
    "metadata": {
     "collapsed": true
    },
@@ -293,7 +293,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 23,
+   "execution_count": 18,
    "metadata": {},
    "outputs": [
     {
@@ -302,7 +302,7 @@
        "226"
       ]
      },
-     "execution_count": 23,
+     "execution_count": 18,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -315,7 +315,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 24,
+   "execution_count": 19,
    "metadata": {},
    "outputs": [
     {
@@ -324,7 +324,7 @@
        "61762"
       ]
      },
-     "execution_count": 24,
+     "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -335,123 +335,121 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 45,
+   "execution_count": 31,
    "metadata": {},
    "outputs": [
     {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "1 loop, best of 3: 209 ms per loop\n"
-     ]
+     "data": {
+      "text/plain": [
+       "100"
+      ]
+     },
+     "execution_count": 31,
+     "metadata": {},
+     "output_type": "execute_result"
     }
    ],
    "source": [
-    "%%timeit\n",
-    "sum(len(t) for t in tours if valid(trace_tour(t)))"
+    "sum(1 for t in tours if valid(trace_tour(t)))"
    ]
   },
   {
-   "cell_type": "markdown",
+   "cell_type": "code",
+   "execution_count": 20,
    "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "123845"
+      ]
+     },
+     "execution_count": 20,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
    "source": [
-    "# Part 2"
+    "sum(len(t) for t in tours)"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 25,
+   "execution_count": 21,
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "1 loop, best of 3: 1min 29s per loop\n"
+      "1 loop, best of 3: 211 ms per loop\n"
      ]
     }
    ],
    "source": [
     "%%timeit\n",
-    "[(i, j) \n",
-    " for i, pi in enumerate(tours) \n",
-    " for j, pj in enumerate(tours)\n",
-    " if i != j\n",
-    " if not valid(trace_tour(pi))\n",
-    " if not valid(trace_tour(pj))\n",
-    " if valid(trace_tour(pi + pj))]"
+    "sum(len(t) for t in tours if valid(trace_tour(t)))"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "# Part 2"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 31,
+   "execution_count": 23,
    "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "[(16, 125),\n",
-       " (70, 48),\n",
-       " (91, 128),\n",
-       " (110, 134),\n",
-       " (116, 194),\n",
-       " (123, 51),\n",
-       " (136, 9),\n",
-       " (142, 193),\n",
-       " (152, 63),\n",
-       " (168, 150),\n",
-       " (201, 83),\n",
-       " (208, 204),\n",
-       " (212, 113)]"
-      ]
-     },
-     "execution_count": 31,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
+   "outputs": [],
    "source": [
-    "[(i, j) \n",
-    " for i, pi in enumerate(tours) \n",
-    " for j, pj in enumerate(tours)\n",
-    " if i != j\n",
-    " if not valid(trace_tour(pi))\n",
-    " if not valid(trace_tour(pj))\n",
-    " if valid(trace_tour(pi + pj))]"
+    "# %%timeit\n",
+    "# [(i, j) \n",
+    "#  for i, pi in enumerate(tours) \n",
+    "#  for j, pj in enumerate(tours)\n",
+    "#  if i != j\n",
+    "#  if not valid(trace_tour(pi))\n",
+    "#  if not valid(trace_tour(pj))\n",
+    "#  if valid(trace_tour(pi + pj))]"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 42,
+   "execution_count": null,
    "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "80622"
-      ]
-     },
-     "execution_count": 42,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
+   "outputs": [],
    "source": [
-    "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
-    "    +\n",
-    "    sum(len(pi + pj) \n",
-    "     for i, pi in enumerate(tours) \n",
-    "     for j, pj in enumerate(tours)\n",
-    "     if i != j\n",
-    "     if not valid(trace_tour(pi))\n",
-    "     if not valid(trace_tour(pj))\n",
-    "     if valid(trace_tour(pi + pj)))\n",
-    ")"
+    "# [(i, j) \n",
+    "#  for i, pi in enumerate(tours) \n",
+    "#  for j, pj in enumerate(tours)\n",
+    "#  if i != j\n",
+    "#  if not valid(trace_tour(pi))\n",
+    "#  if not valid(trace_tour(pj))\n",
+    "#  if valid(trace_tour(pi + pj))]"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "# (sum(len(t) for t in tours if valid(trace_tour(t)))\n",
+    "#     +\n",
+    "#     sum(len(pi + pj) \n",
+    "#      for i, pi in enumerate(tours) \n",
+    "#      for j, pj in enumerate(tours)\n",
+    "#      if i != j\n",
+    "#      if not valid(trace_tour(pi))\n",
+    "#      if not valid(trace_tour(pj))\n",
+    "#      if valid(trace_tour(pi + pj)))\n",
+    "# )"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 34,
+   "execution_count": 24,
    "metadata": {},
    "outputs": [
     {
@@ -490,14 +488,13 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 30,
+   "execution_count": 25,
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "[(0, 124),\n",
-       " (1, 1),\n",
+       "[(1, 1),\n",
        " (2, 1),\n",
        " (3, 4),\n",
        " (4, 5),\n",
@@ -511,7 +508,7 @@
        " (19, 1)]"
       ]
      },
-     "execution_count": 30,
+     "execution_count": 25,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -524,32 +521,24 @@
    "cell_type": "code",
    "execution_count": 27,
    "metadata": {},
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "1 loop, best of 3: 1min 28s per loop\n"
-     ]
-    }
-   ],
+   "outputs": [],
    "source": [
-    "%%timeit\n",
-    "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
-    "    +\n",
-    "    sum(len(pi + pj) \n",
-    "     for i, pi in enumerate(tours) \n",
-    "     for j, pj in enumerate(tours)\n",
-    "     if i != j\n",
-    "     if not valid(trace_tour(pi))\n",
-    "     if not valid(trace_tour(pj))\n",
-    "     if valid(trace_tour(pi + pj)))\n",
-    ")"
+    "# %%timeit\n",
+    "# (sum(len(t) for t in tours if valid(trace_tour(t)))\n",
+    "#     +\n",
+    "#     sum(len(pi + pj) \n",
+    "#      for i, pi in enumerate(tours) \n",
+    "#      for j, pj in enumerate(tours)\n",
+    "#      if i != j\n",
+    "#      if not valid(trace_tour(pi))\n",
+    "#      if not valid(trace_tour(pj))\n",
+    "#      if valid(trace_tour(pi + pj)))\n",
+    "# )"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 50,
+   "execution_count": 28,
    "metadata": {
     "collapsed": true
    },
@@ -574,7 +563,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 51,
+   "execution_count": 29,
    "metadata": {},
    "outputs": [
     {
@@ -583,7 +572,7 @@
        "80622"
       ]
      },
-     "execution_count": 51,
+     "execution_count": 29,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -597,14 +586,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 52,
+   "execution_count": 32,
    "metadata": {},
    "outputs": [
     {
      "name": "stdout",
      "output_type": "stream",
      "text": [
-      "1 loop, best of 3: 1.16 s per loop\n"
+      "1 loop, best of 3: 1.27 s per loop\n"
      ]
     }
    ],
@@ -640,6 +629,90 @@
     ")"
    ]
   },
+  {
+   "cell_type": "code",
+   "execution_count": 33,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "13"
+      ]
+     },
+     "execution_count": 33,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "len(goods)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 37,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[(16, 125),\n",
+       " (70, 48),\n",
+       " (91, 128),\n",
+       " (110, 134),\n",
+       " (116, 194),\n",
+       " (123, 51),\n",
+       " (136, 9),\n",
+       " (142, 193),\n",
+       " (152, 63),\n",
+       " (168, 150),\n",
+       " (201, 83),\n",
+       " (208, 204),\n",
+       " (212, 113)]"
+      ]
+     },
+     "execution_count": 37,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "sorted(good_is)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 38,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[(136, 9),\n",
+       " (70, 48),\n",
+       " (123, 51),\n",
+       " (152, 63),\n",
+       " (201, 83),\n",
+       " (212, 113),\n",
+       " (16, 125),\n",
+       " (91, 128),\n",
+       " (110, 134),\n",
+       " (168, 150),\n",
+       " (142, 193),\n",
+       " (116, 194),\n",
+       " (208, 204)]"
+      ]
+     },
+     "execution_count": 38,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "sorted(good_is, key=lambda p: p[1])"
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": null,