Renamed offices file to rooms

[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..5823e5a8f0238c5c2e6f8781d965a8cbcd0d8bae 100644 (file)
--- a/06-tour-shapes/tour-shapes-solution.ipynb
+++ b/06-tour-shapes/tour-shapes-solution.ipynb
@@ -293,7 +293,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 23,
+   "execution_count": 17,
    "metadata": {},
    "outputs": [
     {
@@ -302,7 +302,7 @@
        "226"
       ]
      },
-     "execution_count": 23,
+     "execution_count": 17,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -315,7 +315,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 24,
+   "execution_count": 18,
    "metadata": {},
    "outputs": [
     {
@@ -324,7 +324,7 @@
        "61762"
       ]
      },
-     "execution_count": 24,
+     "execution_count": 18,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -335,123 +335,127 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 45,
+   "execution_count": 19,
    "metadata": {},
    "outputs": [
     {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "1 loop, best of 3: 209 ms per loop\n"
-     ]
+     "data": {
+      "text/plain": [
+       "100"
+      ]
+     },
+     "execution_count": 19,
+     "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: 213 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": "code",
-   "execution_count": 31,
+   "cell_type": "markdown",
    "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"
-    }
-   ],
    "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))]"
+    "# Part 2"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 42,
-   "metadata": {},
-   "outputs": [
-    {
-     "data": {
-      "text/plain": [
-       "80622"
-      ]
-     },
-     "execution_count": 42,
-     "metadata": {},
-     "output_type": "execute_result"
-    }
-   ],
+   "execution_count": 22,
+   "metadata": {
+    "collapsed": true
+   },
+   "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",
-    ")"
+    "# %%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": 34,
+   "execution_count": 23,
+   "metadata": {
+    "collapsed": true
+   },
+   "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))]"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 24,
+   "metadata": {
+    "collapsed": true
+   },
+   "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": 25,
    "metadata": {},
    "outputs": [
     {
@@ -490,14 +494,13 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 30,
+   "execution_count": 26,
    "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 +514,7 @@
        " (19, 1)]"
       ]
      },
-     "execution_count": 30,
+     "execution_count": 26,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -523,33 +526,27 @@
   {
    "cell_type": "code",
    "execution_count": 27,
-   "metadata": {},
-   "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "1 loop, best of 3: 1min 28s per loop\n"
-     ]
-    }
-   ],
+   "metadata": {
+    "collapsed": true
+   },
+   "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 +571,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 51,
+   "execution_count": 29,
    "metadata": {},
    "outputs": [
     {
@@ -583,7 +580,7 @@
        "80622"
       ]
      },
-     "execution_count": 51,
+     "execution_count": 29,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -597,14 +594,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 52,
+   "execution_count": 30,
    "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.29 s per loop\n"
      ]
     }
    ],
@@ -640,6 +637,167 @@
     ")"
    ]
   },
+  {
+   "cell_type": "code",
+   "execution_count": 31,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "13"
+      ]
+     },
+     "execution_count": 31,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "len(goods)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 32,
+   "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": 32,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "sorted(good_is)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 33,
+   "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": 33,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "sorted(good_is, key=lambda p: p[1])"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 34,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "[(1, 1),\n",
+       " (2, 1),\n",
+       " (3, 4),\n",
+       " (4, 5),\n",
+       " (5, 7),\n",
+       " (6, 3),\n",
+       " (7, 1),\n",
+       " (8, 2),\n",
+       " (9, 2),\n",
+       " (11, 2),\n",
+       " (18, 1),\n",
+       " (19, 1),\n",
+       " (21, 1),\n",
+       " (24, 1),\n",
+       " (132, 2),\n",
+       " (26, 2),\n",
+       " (28, 1),\n",
+       " (29, 1),\n",
+       " (34, 2),\n",
+       " (36, 1),\n",
+       " (37, 3),\n",
+       " (166, 2),\n",
+       " (40, 2),\n",
+       " (41, 2),\n",
+       " (44, 3),\n",
+       " (46, 1),\n",
+       " (48, 2),\n",
+       " (50, 3),\n",
+       " (52, 2),\n",
+       " (53, 1),\n",
+       " (54, 1),\n",
+       " (56, 2),\n",
+       " (57, 3),\n",
+       " (58, 1),\n",
+       " (59, 2),\n",
+       " (61, 1),\n",
+       " (64, 1),\n",
+       " (66, 2),\n",
+       " (68, 1),\n",
+       " (70, 1),\n",
+       " (74, 1),\n",
+       " (75, 1),\n",
+       " (76, 3),\n",
+       " (77, 1),\n",
+       " (81, 1),\n",
+       " (82, 2),\n",
+       " (86, 1),\n",
+       " (88, 1),\n",
+       " (90, 1),\n",
+       " (94, 1),\n",
+       " (97, 1),\n",
+       " (98, 1),\n",
+       " (101, 2),\n",
+       " (106, 1),\n",
+       " (107, 1),\n",
+       " (114, 2),\n",
+       " (117, 3),\n",
+       " (127, 1)]"
+      ]
+     },
+     "execution_count": 34,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "[(l, len(l1s[l])) for l in l1s.keys()]"
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": null,