X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=06-tour-shapes%2Ftour-shapes-solution.ipynb;h=ceb641fbc83c48136aee813d611d91993c902f3b;hb=093a2a306b3b0d536060e0bca23167d0c99dcd5a;hp=11bba605beee992edd10b613a5b619cb4f44ee78;hpb=ee8194796a73cdf220172b88acf1a81afa3a379e;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 11bba60..ceb641f 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": 2, + "execution_count": 1, "metadata": { "collapsed": true }, @@ -28,7 +28,7 @@ }, { "cell_type": "code", - "execution_count": 3, + "execution_count": 2, "metadata": { "collapsed": true }, @@ -55,7 +55,7 @@ }, { "cell_type": "code", - "execution_count": 4, + "execution_count": 3, "metadata": { "collapsed": true }, @@ -67,7 +67,7 @@ }, { "cell_type": "code", - "execution_count": 5, + "execution_count": 4, "metadata": { "collapsed": true }, @@ -86,7 +86,7 @@ }, { "cell_type": "code", - "execution_count": 6, + "execution_count": 5, "metadata": { "collapsed": true }, @@ -105,7 +105,7 @@ }, { "cell_type": "code", - "execution_count": 7, + "execution_count": 6, "metadata": { "collapsed": true }, @@ -122,7 +122,7 @@ }, { "cell_type": "code", - "execution_count": 8, + "execution_count": 7, "metadata": { "collapsed": true }, @@ -134,7 +134,7 @@ }, { "cell_type": "code", - "execution_count": 9, + "execution_count": 8, "metadata": { "collapsed": true }, @@ -148,7 +148,7 @@ }, { "cell_type": "code", - "execution_count": 10, + "execution_count": 9, "metadata": { "collapsed": true }, @@ -174,7 +174,7 @@ }, { "cell_type": "code", - "execution_count": 11, + "execution_count": 10, "metadata": { "collapsed": true }, @@ -197,7 +197,7 @@ }, { "cell_type": "code", - "execution_count": 12, + "execution_count": 11, "metadata": { "collapsed": true }, @@ -210,7 +210,7 @@ }, { "cell_type": "code", - "execution_count": 13, + "execution_count": 12, "metadata": { "collapsed": true }, @@ -221,7 +221,7 @@ }, { "cell_type": "code", - "execution_count": 14, + "execution_count": 13, "metadata": { "collapsed": true }, @@ -236,7 +236,7 @@ }, { "cell_type": "code", - "execution_count": 15, + "execution_count": 14, "metadata": { "collapsed": true }, @@ -248,7 +248,7 @@ }, { "cell_type": "code", - "execution_count": 16, + "execution_count": 15, "metadata": { "collapsed": true }, @@ -260,7 +260,7 @@ }, { "cell_type": "code", - "execution_count": 17, + "execution_count": 16, "metadata": { "collapsed": true }, @@ -293,7 +293,7 @@ }, { "cell_type": "code", - "execution_count": 18, + "execution_count": 17, "metadata": {}, "outputs": [ { @@ -302,7 +302,7 @@ "226" ] }, - "execution_count": 18, + "execution_count": 17, "metadata": {}, "output_type": "execute_result" } @@ -315,7 +315,7 @@ }, { "cell_type": "code", - "execution_count": 19, + "execution_count": 18, "metadata": {}, "outputs": [ { @@ -324,7 +324,7 @@ "61762" ] }, - "execution_count": 19, + "execution_count": 18, "metadata": {}, "output_type": "execute_result" } @@ -335,7 +335,7 @@ }, { "cell_type": "code", - "execution_count": 31, + "execution_count": 19, "metadata": {}, "outputs": [ { @@ -344,7 +344,7 @@ "100" ] }, - "execution_count": 31, + "execution_count": 19, "metadata": {}, "output_type": "execute_result" } @@ -382,7 +382,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "1 loop, best of 3: 211 ms per loop\n" + "1 loop, best of 3: 214 ms per loop\n" ] } ], @@ -400,24 +400,62 @@ }, { "cell_type": "code", - "execution_count": 23, + "execution_count": 36, "metadata": {}, - "outputs": [], + "outputs": [ + { + "data": { + "text/plain": [ + "80622" + ] + }, + "execution_count": 36, + "metadata": {}, + "output_type": "execute_result" + } + ], "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(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", + " + \n", + " sum(len(t) for t in tours if valid(trace_tour(t))))" ] }, { "cell_type": "code", - "execution_count": null, + "execution_count": 22, "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "1 loop, best of 3: 1min 32s 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))]" + ] + }, + { + "cell_type": "code", + "execution_count": 23, + "metadata": { + "collapsed": true + }, "outputs": [], "source": [ "# [(i, j) \n", @@ -431,8 +469,10 @@ }, { "cell_type": "code", - "execution_count": null, - "metadata": {}, + "execution_count": 24, + "metadata": { + "collapsed": true + }, "outputs": [], "source": [ "# (sum(len(t) for t in tours if valid(trace_tour(t)))\n", @@ -449,7 +489,7 @@ }, { "cell_type": "code", - "execution_count": 24, + "execution_count": 25, "metadata": {}, "outputs": [ { @@ -488,7 +528,7 @@ }, { "cell_type": "code", - "execution_count": 25, + "execution_count": 26, "metadata": {}, "outputs": [ { @@ -508,7 +548,7 @@ " (19, 1)]" ] }, - "execution_count": 25, + "execution_count": 26, "metadata": {}, "output_type": "execute_result" } @@ -520,7 +560,9 @@ { "cell_type": "code", "execution_count": 27, - "metadata": {}, + "metadata": { + "collapsed": true + }, "outputs": [], "source": [ "# %%timeit\n", @@ -586,14 +628,14 @@ }, { "cell_type": "code", - "execution_count": 32, + "execution_count": 30, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "1 loop, best of 3: 1.27 s per loop\n" + "1 loop, best of 3: 1.18 s per loop\n" ] } ], @@ -631,7 +673,7 @@ }, { "cell_type": "code", - "execution_count": 33, + "execution_count": 31, "metadata": {}, "outputs": [ { @@ -640,7 +682,7 @@ "13" ] }, - "execution_count": 33, + "execution_count": 31, "metadata": {}, "output_type": "execute_result" } @@ -651,7 +693,7 @@ }, { "cell_type": "code", - "execution_count": 37, + "execution_count": 32, "metadata": {}, "outputs": [ { @@ -672,7 +714,7 @@ " (212, 113)]" ] }, - "execution_count": 37, + "execution_count": 32, "metadata": {}, "output_type": "execute_result" } @@ -683,7 +725,7 @@ }, { "cell_type": "code", - "execution_count": 38, + "execution_count": 33, "metadata": {}, "outputs": [ { @@ -704,7 +746,7 @@ " (208, 204)]" ] }, - "execution_count": 38, + "execution_count": 33, "metadata": {}, "output_type": "execute_result" } @@ -713,6 +755,83 @@ "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,