X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=06-tour-shapes%2Ftour-shapes-solution.ipynb;h=11bba605beee992edd10b613a5b619cb4f44ee78;hb=f5546f4bdd695947de8f72d64e571789f6cebaef;hp=9a0a4e14f53a311727a5fe383d50b41bc552d6fe;hpb=d91c9d64d82c20a1ee9feea1c2e403f5f013a7f3;p=ou-summer-of-code-2017.git diff --git a/06-tour-shapes/tour-shapes-solution.ipynb b/06-tour-shapes/tour-shapes-solution.ipynb index 9a0a4e1..11bba60 100644 --- 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,