06-tour-shapes/tour-shapes-solution.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "You've arrived at your destination and are looking forward to seeing the site. But it's a large site and you'll need a guide.\n",
   8     "\n",
   9     "Each guide posts the route they'll take on a board, described the by steps they'll take. The steps are either `F` (take a step forward), `L` (turn left 90⁰ then take a step forward) or `R` (turn right 90⁰ then take a step forward). For example, the route `FFRRFLRRFR` will look like this (assuming you start facing right; the blob shows the starting point):\n",
  10     "\n",
  11     "\n",
  12     "![Sample valid tour](question-example-tour-000-s0010-m000-trim.png)\n",
  13     "\n",
  14     "A sample valid tour\n",
  15     "\n",
  16     "while the tour `FFLLRLRLLFLR` looks like this (again, assuming you start facing right):\n",
  17     "\n",
  18     "![Sample valid tour](question-example-tour-001-s0012-m000-trim.png) \n",
  19     "\n",
  20     "A sample valid tour\n",
  21     "\n",
  22     "However, some of the tour guides are charlatans. They have tour that either doesn't return you to your starting place, or loops around to visit the same place more than once. For example, the tour `RRFFLLFFFFLF` doesn't return to your starting place:\n",
  23     "\n",
  24     "![Sample invalid tour](question-example-tour-002-s0012-m001-trim.png)\n",
  25     "\n",
  26     "An invalid tour\n",
  27     "\n",
  28     "and the tour `RRLLRRFFRFRFLR` may get you back to where you started, but only after going around a small loop:\n",
  29     "\n",
  30     "![Sample invalid tour](question-example-tour-003-s0014-m001-trim.png)\n",
  31     "\n",
  32     "A sample invalid tour\n",
  33     "\n",
  34     "You're only interested in valid tours, the ones that return you to your starting place and don't visit any other spot more than once. (It doesn't matter what direction you're facing when you return to your starting place, just that you return there at the end of the tour.)\n",
  35     "\n",
  36     "In fact, you've got your daily fitness tracker widget to keep happy. Even on holiday, you need to keep up the number of steps you take. You're interested in the total length of all the valid tours. In the examples here, the total length of the two valid tours is 10 + 12 = 22 steps.\n",
  37     "\n",
  38     "# Part 1\n",
  39     "\n",
  40     "The tours are given in [06-tours.txt](06-tours.txt), one tour per line. \n",
  41     "\n",
  42     "What is the total length of all the valid tours?\n"
  43    ]
  44   },
  45   {
  46    "cell_type": "markdown",
  47    "metadata": {},
  48    "source": [
  49     "It seems you've done your guides a disservice.\n",
  50     "\n",
  51     "Yes, there are some charlatans around. But some of the tours a split between two guides. Each posted tour alone looks like it would be incomplete, but when you finish the first leg of a tour, you pick up a new guide and continue, eventually returning you to your starting place.\n",
  52     "\n",
  53     "For instance, the tours `FFRFLLFFFRLRRFFFLFLRRFLLFFFFFRFLFFFFFRLLFRFRLLFFFFF` and `FLRFFRLLFRFFFLFFLFFRFRRLLFFRLFFFFFLLFFRFRFL` are both incomplete; on its own, each tour would leave you stranded. \n",
  54     "\n",
  55     "![A split tour](question-example-tour-004-s0051-m001-trim.png)\n",
  56     "\n",
  57     "A split tour \n",
  58     "\n",
  59     "![More of a split tour](question-example-tour-005-s0043-m001-trim.png)\n",
  60     "\n",
  61     "More of a split tour\n",
  62     "\n",
  63     "But if you do one then the other, the complete 94-step tour is valid:\n",
  64     "\n",
  65     "![Split tour combined](question-example-tour-006-s0094-m000-trim.png)\n",
  66     "\n",
  67     "The split tour combined\n",
  68     "\n",
  69     "(You start the second half of the tour heading left, so turn the second picture 180⁰ to visualise it.)\n",
  70     "\n",
  71     "Luckily for you, tour guides only act alone or in pairs, and never in teams of three or more. \n",
  72     "\n",
  73     "(Because of way the initial facing changes the way a tour unfolds, it's generally the case that tour A followed by tour B is different from B followed by A.)\n",
  74     "\n",
  75     "# Part 2\n",
  76     "\n",
  77     "The tours are still given in [06-tours.txt](06-tours.txt), one tour per line. Your definition of a valid tour now includes the combination of two partial tours, so long as the combined tour never crosses itself and returns you to your staring place. With this new definition of valid tours, what is the total length of all the valid tours?"
  78    ]
  79   },
  80   {
  81    "cell_type": "code",
  82    "execution_count": 1,
  83    "metadata": {
  84     "collapsed": true
  85    },
  86    "outputs": [],
  87    "source": [
  88     "import collections\n",
  89     "import enum\n",
  90     "import random\n",
  91     "import os\n",
  92     "\n",
  93     "import matplotlib.pyplot as plt\n",
  94     "%matplotlib inline\n"
  95    ]
  96   },
  97   {
  98    "cell_type": "code",
  99    "execution_count": 2,
 100    "metadata": {
 101     "collapsed": true
 102    },
 103    "outputs": [],
 104    "source": [
 105     "class Direction(enum.Enum):\n",
 106     "    UP = 1\n",
 107     "    RIGHT = 2\n",
 108     "    DOWN = 3\n",
 109     "    LEFT = 4\n",
 110     "    \n",
 111     "turn_lefts = {Direction.UP: Direction.LEFT, Direction.LEFT: Direction.DOWN,\n",
 112     "              Direction.DOWN: Direction.RIGHT, Direction.RIGHT: Direction.UP}\n",
 113     "\n",
 114     "turn_rights = {Direction.UP: Direction.RIGHT, Direction.RIGHT: Direction.DOWN,\n",
 115     "               Direction.DOWN: Direction.LEFT, Direction.LEFT: Direction.UP}\n",
 116     "\n",
 117     "def turn_left(d):\n",
 118     "    return turn_lefts[d]\n",
 119     "\n",
 120     "def turn_right(d):\n",
 121     "    return turn_rights[d]\n"
 122    ]
 123   },
 124   {
 125    "cell_type": "code",
 126    "execution_count": 3,
 127    "metadata": {
 128     "collapsed": true
 129    },
 130    "outputs": [],
 131    "source": [
 132     "Step = collections.namedtuple('Step', ['x', 'y', 'dir'])\n",
 133     "Mistake = collections.namedtuple('Mistake', ['i', 'step'])"
 134    ]
 135   },
 136   {
 137    "cell_type": "code",
 138    "execution_count": 4,
 139    "metadata": {
 140     "collapsed": true
 141    },
 142    "outputs": [],
 143    "source": [
 144     "def advance(step, d):\n",
 145     "    if d == Direction.UP:\n",
 146     "        return Step(step.x, step.y+1, d)\n",
 147     "    elif d == Direction.DOWN:\n",
 148     "        return Step(step.x, step.y-1, d)\n",
 149     "    elif d == Direction.LEFT:\n",
 150     "        return Step(step.x-1, step.y, d)\n",
 151     "    elif d == Direction.RIGHT:\n",
 152     "        return Step(step.x+1, step.y, d)"
 153    ]
 154   },
 155   {
 156    "cell_type": "code",
 157    "execution_count": 5,
 158    "metadata": {
 159     "collapsed": true
 160    },
 161    "outputs": [],
 162    "source": [
 163     "def step(s, current):\n",
 164     "    if s == 'F':\n",
 165     "        return advance(current, current.dir)\n",
 166     "    elif s == 'L':\n",
 167     "        return advance(current, turn_left(current.dir))\n",
 168     "    elif s == 'R':\n",
 169     "        return advance(current, turn_right(current.dir))\n",
 170     "    else:\n",
 171     "        raise ValueError"
 172    ]
 173   },
 174   {
 175    "cell_type": "code",
 176    "execution_count": 6,
 177    "metadata": {
 178     "collapsed": true
 179    },
 180    "outputs": [],
 181    "source": [
 182     "def trace_tour(tour, startx=0, starty=0, startdir=Direction.RIGHT):\n",
 183     "    current = Step(startx, starty, startdir)\n",
 184     "    trace = [current]\n",
 185     "    for s in tour:\n",
 186     "        current = step(s, current)\n",
 187     "        trace += [current]\n",
 188     "    return trace    "
 189    ]
 190   },
 191   {
 192    "cell_type": "code",
 193    "execution_count": 7,
 194    "metadata": {
 195     "collapsed": true
 196    },
 197    "outputs": [],
 198    "source": [
 199     "def positions(trace):\n",
 200     "    return [(s.x, s.y) for s in trace]"
 201    ]
 202   },
 203   {
 204    "cell_type": "code",
 205    "execution_count": 8,
 206    "metadata": {
 207     "collapsed": true
 208    },
 209    "outputs": [],
 210    "source": [
 211     "def valid(trace):\n",
 212     "    return (trace[-1].x == 0 \n",
 213     "            and trace[-1].y == 0 \n",
 214     "            and len(set(positions(trace))) + 1 == len(trace))"
 215    ]
 216   },
 217   {
 218    "cell_type": "code",
 219    "execution_count": 9,
 220    "metadata": {
 221     "collapsed": true
 222    },
 223    "outputs": [],
 224    "source": [
 225     "def valid_prefix(tour):\n",
 226     "    current = Step(0, 0, Direction.RIGHT)\n",
 227     "    prefix = []\n",
 228     "    posns = []\n",
 229     "    for s in tour:\n",
 230     "        current = step(s, current)\n",
 231     "        prefix += [s]\n",
 232     "        if (current.x, current.y) in posns:\n",
 233     "            return ''\n",
 234     "        elif current.x == 0 and current.y == 0: \n",
 235     "            return ''.join(prefix)\n",
 236     "        posns += [(current.x, current.y)]\n",
 237     "    if current.x == 0 and current.y == 0:\n",
 238     "        return ''.join(prefix)\n",
 239     "    else:\n",
 240     "        return ''"
 241    ]
 242   },
 243   {
 244    "cell_type": "code",
 245    "execution_count": 10,
 246    "metadata": {
 247     "collapsed": true
 248    },
 249    "outputs": [],
 250    "source": [
 251     "def mistake_positions(trace, debug=False):\n",
 252     "    mistakes = []\n",
 253     "    current = trace[0]\n",
 254     "    posns = [(0, 0)]\n",
 255     "    for i, current in enumerate(trace[1:]):\n",
 256     "        if (current.x, current.y) in posns:\n",
 257     "            if debug: print(i, current)\n",
 258     "            mistakes += [Mistake(i+1, current)]\n",
 259     "        posns += [(current.x, current.y)]\n",
 260     "    if (current.x, current.y) == (0, 0):\n",
 261     "        return mistakes[:-1]\n",
 262     "    else:\n",
 263     "        return mistakes + [Mistake(len(trace)+1, current)]"
 264    ]
 265   },
 266   {
 267    "cell_type": "code",
 268    "execution_count": 11,
 269    "metadata": {
 270     "collapsed": true
 271    },
 272    "outputs": [],
 273    "source": [
 274     "def returns_to_origin(mistake_positions):\n",
 275     "    return [i for i, m in mistake_positions\n",
 276     "           if (m.x, m.y) == (0, 0)]"
 277    ]
 278   },
 279   {
 280    "cell_type": "code",
 281    "execution_count": 12,
 282    "metadata": {
 283     "collapsed": true
 284    },
 285    "outputs": [],
 286    "source": [
 287     "sample_tours = ['FFLRLLFLRL', 'FLLFFLFFFLFFLFLLRRFR', 'FFRLLFRLLFFFRFLLRLLRRLLRLL']"
 288    ]
 289   },
 290   {
 291    "cell_type": "code",
 292    "execution_count": 13,
 293    "metadata": {
 294     "collapsed": true
 295    },
 296    "outputs": [],
 297    "source": [
 298     "def bounds(trace):\n",
 299     "    return (max(s.x for s in trace),\n",
 300     "            max(s.y for s in trace),\n",
 301     "            min(s.x for s in trace),\n",
 302     "            min(s.y for s in trace))"
 303    ]
 304   },
 305   {
 306    "cell_type": "code",
 307    "execution_count": 14,
 308    "metadata": {
 309     "collapsed": true
 310    },
 311    "outputs": [],
 312    "source": [
 313     "plot_wh = {Direction.UP: (0, 1), Direction.LEFT: (-1, 0),\n",
 314     "           Direction.DOWN: (0, -1), Direction.RIGHT: (1, 0)}"
 315    ]
 316   },
 317   {
 318    "cell_type": "code",
 319    "execution_count": 15,
 320    "metadata": {
 321     "collapsed": true
 322    },
 323    "outputs": [],
 324    "source": [
 325     "def chunks(items, n=2):\n",
 326     "    return [items[i:i+n] for i in range(len(items) - n + 1)]"
 327    ]
 328   },
 329   {
 330    "cell_type": "code",
 331    "execution_count": 39,
 332    "metadata": {
 333     "collapsed": true
 334    },
 335    "outputs": [],
 336    "source": [
 337     "def plot_trace(trace, colour='k', highlight_start=True,\n",
 338     "               xybounds=None, fig=None, subplot_details=None, filename=None):\n",
 339     "    plt.axis('on')\n",
 340     "    plt.axes().set_aspect('equal')\n",
 341     "    \n",
 342     "    if highlight_start:\n",
 343     "        plt.axes().add_patch(plt.Circle((trace[0].x, trace[0].y), 0.2, color=colour))\n",
 344     "\n",
 345     "    for s, t in chunks(trace, 2):\n",
 346     "        w, h = plot_wh[t.dir]\n",
 347     "        plt.arrow(s.x, s.y, w, h, head_width=0.1, head_length=0.1, fc=colour, ec=colour, length_includes_head=True)\n",
 348     "    xh, yh, xl, yl = bounds(trace)\n",
 349     "    if xybounds is not None:    \n",
 350     "        bxh, byh, bxl, byl = xybounds\n",
 351     "        plt.xlim([min(xl, bxl)-1, max(xh, bxh)+1])\n",
 352     "        plt.ylim([min(yl, byl)-1, max(yh, byh)+1])\n",
 353     "    else:\n",
 354     "        plt.xlim([xl-1, xh+1])\n",
 355     "        plt.ylim([yl-1, yh+1])\n",
 356     "    if filename:\n",
 357     "        plt.savefig(filename)"
 358    ]
 359   },
 360   {
 361    "cell_type": "code",
 362    "execution_count": 17,
 363    "metadata": {},
 364    "outputs": [
 365     {
 366      "data": {
 367       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAUQAAAEACAYAAADLIw+8AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAF05JREFUeJzt3XuQVeWd7vHv0xCgLwNRQUZgbI8mOdFJTlQsbGMue6JG\nyBiZWCbGk6pcjsRkalKmynjKSyxotKx4C14mkxAN5oBVKVHjBRwimNJ9FJ2ghRglwMjERERAcwQh\nfZO+/M4f/drV6eyGbvbqXt3b51O1i3V593p/u7p5+l1rr71fRQRmZgZVeRdgZjZSOBDNzBIHoplZ\n4kA0M0sciGZmiQPRzCwpOxAljZe0TtIGSS9JWlCizThJ90jaKuk/JB1dbr9mZlkrOxAj4h3gHyLi\nJOBEYI6kWX2aXQTsjogPArcCN5bbr5lZ1jI5ZY6IlrQ4HhgL9L3bey6wNC3fD5yRRb9mZlnKJBAl\nVUnaAOwCHouI5/o0mQ68BhARncDbkg7Pom8zs6xkNULsSqfMM4BTJZ3Qp4lKrPszg2Y2oozN8mAR\nsU9SEZgNbOq16zXg74AdksYAEyNiT9/nS3JImtmQiIi+A7O/ksW7zJMlTUrL1cCZwJY+zVYCX0vL\nXwQe7+94EVGxjwULFuReg1+fX9978fUNVBYjxKOApZKq6A7Y5RGxStJC4LmIeARYAtwtaSvwFvDl\nDPo1M8tU2YEYES8BJ5fYvqDX8jvAl8rty8xsKPmTKsOoUCjkXcKQ8usb3Sr99Q2EBnN+PdQkxUiq\nx8wqgyRiON5UMTOrFA5EM7PEgWhmljgQzcwSB6KZWeJANDNLHIhmZokD0cwscSCamSUORDOzxIFo\nZpY4EM3MEgeimVniQDQzSxyIZmaJA9HMLHEgmpklWcy6N0PS45I2SXpJ0iUl2nxa0tuSnk+Pq8vt\n18wsa1nMutcBXBoRL0iqA9ZLWhMRfacifTIizs2gPzOzIVH2CDEidkXEC2m5CdgMTC/R9KDzGZiZ\n5SnTa4iSjgFOBNaV2N0gaYOkf5d0Qpb9mpllIYtTZgDS6fL9wHfTSLG39UB9RLRImgM8BHwoq77N\nzLKQSSBKGkt3GN4dEQ/33d87ICPiV5J+LOnwiNjdt21jY2PPcqFQ8FyxZjZoxWKRYrE46OdlMi+z\npGXA/4uIS/vZPzUi3kjLs4B7I+KYEu08L7OZZW6g8zKXPUKUdDrwFeAlSRuAAK4C6oGIiDuA8yX9\nM9AOtAIXlNuvmVnWMhkhZsUjRDMbCgMdIfqTKmZmiQPRzCxxIJqZJQ5EM7PEgWhmljgQzcwSB6KZ\nWeJANDNLHIhmZokD0cwscSCamSUORDOzxIFoZpY4EM3MEgeimVniQDQzSxyIZmaJA9HMLHEgmpkl\nZQeipBmSHpe0SdJLki7pp93tkrZKekHSieX2a2aWtSxGiB3ApRFxAnAa8C+SPty7QZqc/riI+CDw\nLWBxBv3aCNbe3s7PfvYzzjzzTPbu3Zt3OZnbu3cvjY2NXHCBJ5CsJGVPQxoRu4BdablJ0mZgOrCl\nV7O5wLLUZp2kSb3narbK0d7eztKlS/n+979Pc3Mz7e3t7N69m0mTJuVdWib27t3LLbfcws0330xn\nZydVVb7qVEnKDsTeJB0DnAis67NrOvBar/XX0zYHYoVob2/nrrvuYv78+TQ3N9Pc3AxAdXU1v/3t\nb9m9e3fOFZZn//79rF69mptvvpmuri5aW1sBqKqqYv369TlXV773v//9HHfccXmXkbvMAlFSHXA/\n8N2IaOq7u8RTSk7A3NjY2LNcKBQoFAoZVWhD6aKLLuLuu+9+d/7bnu2tra184QtfyLGyodXV1cUp\np5ySdxmZWL16NZ/97GfzLiMTxWKRYrE4+CdGRNkPuoP1UbrDsNT+xcAFvda3AFNLtAsbnY466qgA\n4qyzzorq6uqQFEDU1dXFK6+8knd5Zevq6opVq1bFCSecELW1tUH3H/SoqanJu7SyXXfddTFmzJg4\n6aSToqurK+9yhkTKloNmWVYXQO4CNkXEbf3sXwF8FUBSA/B2+PphRVqzZg1PP/00Z5xxBtXV1bS1\nteVdUiYkMWfOHDZu3Mh9993H8ccfT3V1dd5lla2pqYnrr7+ezs5OXn75ZZ544om8S8pV2afMkk4H\nvgK8JGkD3X85rwLq6U7lOyJilaTPSfovoBn4Rrn92sh10kkn8dhjj7FhwwYefPBBjjrqqLxLysy7\nwTh79mxWr17Npk2b8i6pLLfffjsdHR0ANDc3c9lll7F+/XqkUle5Kp8iSl7Ky4WkGEn12MBNmzaN\nnTt34p/f6NHU1MS0adP485//3LOttraWFStW8JnPfCbHyrKXrm0fNOV9z4DZe9Qdd9xBS0tLz2hQ\nEs3NzVx11VU5V5afTG+7MbPR49xzz+25fejqq6/mnHPO4dRTT+Xkk0/OubL8+JTZMuFT5tFNEitW\nrODzn/983qUMCZ8ym5kNkgPRzCxxIJqZJQ5EM7PEgWhmljgQzcwSB6KZWeJANDNLHIhmZokD0cws\ncSCamSUORDOzxIFoZpY4EM3MEgeimVniQDQzSzIJRElLJL0h6cV+9n9a0tuSnk+Pq7Po18wsS1lN\nIfBz4F+BZQdo82REnJtRf2ZmmctkhBgRa4E9B2n23pzX0MxGjeG8htggaYOkf5d0wjD2a2Y2IMM1\n6956oD4iWiTNAR4CPlSqYWNjY89yoVCgUCgMR31mVkGKxSLFYnHQz8ts1j1J9cDKiPgfA2j7B2Bm\nROzus92z7o1SnnVvdPOse92yPGUW/VwnlDS11/IsuoN4d6m2ZmZ5yeSUWdIvgAJwhKRtwAJgHBAR\ncQdwvqR/BtqBVuCCLPo1M8tSJoEYEf/zIPv/Dfi3LPoyMxsq/qSKmVniQDQzSxyIZmaJA9HMLHEg\nmpklDkQzs8SBaGaWOBDNzBIHoplZ4kA0M0sciGZmiQPRzCxxIJqZJQ5EM7PEgWhmljgQzcwSB6KZ\nWeJAtEO2b98+jj32WCZPnszOnTsBmDx5MtOmTWP79u05V2c2eA5EO2Q1NTXs37+ft956q2fbW2+9\nRVNTE4cddliOlZkdmkwCUdISSW9IevEAbW6XtFXSC5JOzKLfSjCap+0cO3YsP/jBD6irq+vZVlNT\nw5VXXkltbW2OldmBjObfuaGW1Qjx58DZ/e1Mk9MfFxEfBL4FLM6o31Fr7969LFiwgCOOOIKnn346\n73IO2YUXXsikSZN61seOHcsll1ySY0V2IA899BBTpkxh0aJFtLa25l3OiJNJIEbEWmDPAZrMBZal\ntuuASb3nan4veTcIp0+fzk033URbW1vP9bfRqPcosaamhiuuuMKjwxFs27Zt7N27l/nz5zNt2jQH\nYx+ZTEM6ANOB13qtv562vTFM/ecuIrjsssv46U9/SldXV88vYU1NDQsXLmTNmjU5V3jourq6iAiq\nqqoqdnT4yiuvcMMNN4z6081Vq1ZRVVVFc3MzAPPnz+faa6/NuaqRY7gCUSW2lfzNamxs7FkuFAoU\nCoWhqWiY/eQnP2HRokVMmDCBtra2nu2tra1s3LiRjRs35lhdNq6//vqKHB12dHRwyimnsGfPgU6C\nRo8xY8b0LDc3NzN+/HimTZvG6aefnmNV2SoWixSLxcE/MSIyeQD1wIv97FsMXNBrfQswtUS7qFQL\nFiwIIO6888448sgjo7a2NoCYOHFi3HfffXmXZwewbNmyqK6ujgkTJsSOHTvyLqcst912W4wfPz6A\nqKuri/r6+li+fHl0dnbmXdqQStly0BzL8rYbUXokCLAC+CqApAbg7Yh4z5wu9zZv3jy2b9/Orbfe\nypFHHklTU1PeJdkBdHR0cOWVV9La2kpXV1dFnF62t7dTX1/PkiVLeOWVV/jSl75EVZXvwAOyGSEC\nvwB2AO8A24Bv0P1u8sW92vwI+C/gt8DJ/RxniP9O5OfdEWJv+/fvj5UrV0Zra2tOVdnBLFu2LOrq\n6oLuSzyjfpS4d+/eWLVqVcWPCPtigCNExQi6SCwpRlI9WWpsbGThwoWj/qL8e0lHRwfHHHMMr7/+\nes+2cePGcdFFF/HjH/84x8pssCQREf2dwfbwONmsH2vXrmXHjh0991lOmDCB973vfSxdupSOjo6c\nq7OhMFzvMpuNOp/85CdZtWoVAHPmzGHq1KksXryYI444grFj/V+nEvmnataPMWPGMHv27J71j370\no3+xbpXHp8xmZokD0cwscSCamSUORDOzxIFoZpY4EM3MEgeimVniQDQzSxyIZmaJA9HMLHEgmpkl\nDkQzs8SBaGaWOBDNzBIHoplZ4kA0M0syCURJsyVtkfSypMtL7P+apDclPZ8e/yuLfs3MslT2N2ZL\nqqJ7Rr0z6J557zlJD0fElj5N74mIS8rtz8xsqGQxQpwFbI2IVyOiHbgHmFui3UFnvDIzy1MWgTgd\neK3X+va0ra/zJL0g6V5JMzLo18wsU1lMMlVq5Nd38uEVwC8iol3St4CldJ9i/5XGxsae5UKhQKFQ\nyKBEM3svKRaLFIvFQT8vi0DcDhzda30G3dcSe0TEnl6rdwI39Hew3oFoZnYo+g6mFi5cOKDnZXHK\n/BzwAUn1ksYBX6Z7RNhD0t/2Wp0LbMqgXzOzTJU9QoyITknfAdbQHbBLImKzpIXAcxHxCHCJpHOB\ndmA38PVy+zUzy1omE9VHxKPAf++zbUGv5auAq7Loy8xsqPiTKmZmiQPRzCxxIJqZJQ5EM7PEgWhm\nljgQzcwSB6KZWeJANDNLHIhmZokD0cwscSCamSWZfJbZStuzZw9PPvkkzz77LL/85S8B+PrXv05D\nQwOnnnoqJ554IpK/SNxspFBE3+9yzY+kGEn1HKrNmzdzzTXX8NBDDzFu3Diampro6urq2V9TU0NV\nVRWTJ0/m8ssvZ968eYwd679NI5kkzjnnHFauXJl3KXYIJBERBx19+JQ5Qx0dHVx77bXMnDmTe++9\nl7a2Nvbt2/cXYQjQ0tJCU1MTf/zjH7nsssv42Mc+xu9+97ucqjazdzkQM9LW1sbs2bO5/vrraW1t\n/asQ7E9zczObN29m1qxZ/PrXvx7iKs3sQByIGYgIzjvvPJ555hlaWloO6fktLS3MnTuXdevWDUGF\nZjYQDsQM3HnnnTz55JO0traWdZyWlhbOO++8QwpVMyufA7FMf/rTn7j00ktpbm7O5Hh79uxh/vz5\nmRzLzAbHgVimO+64Y8DXCweitbWVxYsXe5RoloNMAlHSbElbJL0s6fIS+8dJukfSVkn/IenoUscZ\nbSKC22+/vexT5b4k9dy3OBLt3Lkz0z8CI83rr7+edwmWk7IDUVIV8CPgbODvgQslfbhPs4uA3RHx\nQeBW4MZy+x0JduzYwb59+zI/blNTE6tXr878uFl45513OProozn22GNZvnx5xQXj+vXrmTFjBg0N\nDaxduzbvcmyYZTFCnAVsjYhXI6IduIfuuZd7mwssTcv3A2dk0G/u1q9fz7hx44bk2L/5zW+G5Ljl\niggigldffZV58+ZVXDC2tbUxceJE1q1bx9lnn+1gfI/J4uMR04HXeq1vpzskS7ZJ8zi/LenwiNid\nQf+52bVrFx0dHUNy7N///vcj/mN9TU1NNDU1MW/ePL73ve8hie3bt+ddVmZaWlp6ghG6P2FklS2L\nQCz1v7bv5+/6tlGJNgA0Njb2LBcKBQqFQhmlmWXjIx/5CD/84Q/zLsMGqFgsUiwWB//Ed0+BDvUB\nNACP9lq/Ari8T5tfAaem5THAm/0cK0aThx9+OCZOnBh0h3umj+OOOy7vl1dSa2trjBkzJoCoq6uL\n+vr6WL58eXR2duZdWibWrl3b8zOtqamJhoaGeOqpp/Iuy8qUsuWgeZbFCPE54AOS6oGdwJeBC/u0\nWQl8DVgHfBF4PIN+czdz5kz2798/JMduaGgYkuOWSxKSqK+v58Ybb+T888+nqqpy7t6aMGEC+/bt\no6GhgZtuuolPfOITeZdkw6jsQIzua4LfAdbQ/SbNkojYLGkh8FxEPAIsAe6WtBV4i+7QHPWmTZvG\nxIkTaWtry/S4dXV1PdetRprx48ezbds2pk6dWlFB+K6ZM2eyfft2pk+fnncplgN//VeZrrvuOq67\n7rpM70Wsra3lzTff9EV8s4z467+GycUXX5zpSKm6uppvf/vbDkOzHDgQyzRlyhQWLVpEbW1tJsc7\n/PDDueaaazI5lpkNjgMxA9/85jf51Kc+RXV1dVnHqamp4YEHHvDo0CwnDsQMSOKBBx7g4x//+CGF\nmSRqa2t5+OGHmTWr7z3tZjZcHIgZmTBhAo8++ihXXnkl1dXVA76uWFtby/HHH8+6des488wzh7hK\nMzsQv8s8BDZv3sy1117Lgw8+yLhx42hubqazs7Nnf01NDZKYMmWKJ5kyGwYDfZfZgTiE9uzZw1NP\nPcWzzz7Lpk2b2L9/P5MnT+a0005j1qxZnobUbJg4EM3MEt+HaGY2SA5EM7PEgWhmljgQzcwSB6KZ\nWeJANDNLHIhmZokD0cwscSCamSUORDOzpKxAlHSYpDWS/lPSakmT+mnXKel5SRskPVROn2ZmQ6Ws\nzzJLugF4KyJulHQ5cFhEXFGi3b6ImDiA4/mzzGaWuWH5cgdJW4BPR8Qbkv4WKEbEh0u0+3NE/M0A\njudANLPMDdeXOxwZEW8ARMQuYEo/7cZLelbSM5LmltmnmdmQOOi3kkp6DJjaexMQwNWD6OfoiNgl\n6b8Bj0t6MSL+MLhSzcyG1kEDMSLO6m+fpDckTe11yvxmP8fYlf79g6QicBJQMhAbGxt7lguFAoVC\n4WAlmpn9hWKxSLFYHPTzsnhTZXdE3NDfmyqS3g+0RMR+SZOBp4G5EbGlxPF8DdHMMjdcb6ocDtwL\n/B2wDfhiRLwtaSbwrYi4WNJpwE+BTrqvWd4SEf+nn+M5EM0sc55CwMws8RQCZmaD5EA0M0sciGZm\niQPRzCxxIJqZJQ5EM7PEgWhmljgQzcwSB6KZWeJANDNLHIhmZokD0cwscSCamSUORDOzxIFoZpY4\nEM3MEgeimVniQDQzSxyIZmZJWYEo6XxJGyV1Sjr5AO1mS9oi6eU0O5+Z2YhT7gjxJeALwP/tr4Gk\nKuBHwNnA3wMXSvpwmf2OSocyT+xo4tc3ulX66xuIsgIxIv4zIrYCB5rNahawNSJejYh24B5gbjn9\njlaV/gvn1ze6VfrrG4jhuIY4HXit1/r2tM3MbEQZe7AGkh4DpvbeBATw/YhYOYA+So0ePfmymY04\nmUxUL+kJ4HsR8XyJfQ1AY0TMTutXABERN5Ro66A0syExkInqDzpCHIT+OnsO+ICkemAn8GXgwlIN\nB1KwmdlQKfe2m3+S9BrQADwi6Vdp+1GSHgGIiE7gO8Aa4HfAPRGxubyyzcyyl8kps5lZJRhxn1QZ\n6M3eo00l35wuaYmkNyS9mHctWZM0Q9LjkjZJeknSJXnXlCVJ4yWtk7Qhvb4Fedc0FCRVSXpe0ooD\ntRtxgcgAbvYebd4DN6f/nO7XVok6gEsj4gTgNOBfKulnFxHvAP8QEScBJwJzJM3Kuayh8F1g08Ea\njbhAHODN3qNNRd+cHhFrgT151zEUImJXRLyQlpuAzVTYfbQR0ZIWx9P9RmtFXUeTNAP4HPCzg7Ud\ncYFYoXxzegWQdAzdo6h1+VaSrXQ6uQHYBTwWEc/lXVPGbgH+NwMI+lwCUdJjkl7s9Xgp/fv5POoZ\nBr45fZSTVAfcD3w3jRQrRkR0pVPmGcCpkk7Iu6asSPpH4I00yhcHOfPM8j7EAYuIs/LoN0fbgaN7\nrc8AduRUiw2SpLF0h+HdEfFw3vUMlYjYJ6kIzGYA19tGidOBcyV9DqgG/kbSsoj4aqnGI/2UuVKu\nI/bcnC5pHN03px/w3a5R6KB/fUexu4BNEXFb3oVkTdJkSZPScjVwJrAl36qyExFXRcTREXEs3f/v\nHu8vDGEEBmJ/N3uPZpV+c7qkXwDPAB+StE3SN/KuKSuSTge+Anwm3ZryvKTZedeVoaOAJyS9QPe1\n0dURsSrnmnLjG7PNzJIRN0I0M8uLA9HMLHEgmpklDkQzs8SBaGaWOBDNzBIHoplZ4kA0M0v+P7R8\nnO0IPfrWAAAAAElFTkSuQmCC\n",
 368       "text/plain": [
 369        "<matplotlib.figure.Figure at 0x7f365877fd30>"
 370       ]
 371      },
 372      "metadata": {},
 373      "output_type": "display_data"
 374     }
 375    ],
 376    "source": [
 377     "plot_trace(trace_tour(sample_tours[0]))"
 378    ]
 379   },
 380   {
 381    "cell_type": "code",
 382    "execution_count": 37,
 383    "metadata": {},
 384    "outputs": [
 385     {
 386      "data": {
 387       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAN4AAAEACAYAAADcJMhcAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAE9ZJREFUeJzt3X1wlfWZxvHvffJOEqRCLYoL2qGuLzgo7QBVnIk7Rqho\nRZe26661gwwdba2lMy5qkSZIGSmtQ3EtO9VRtEwVLeIWsVLAbtaXSnVWqMmKIFOLKCijVTQkkJdz\n7x+BNEBITjgn5z4h12fmGc9Jfud5rmCu/J7nOYGfuTsikl2J6AAi/ZGKJxJAxRMJoOKJBFDxRAKo\neCIB0i6emZ1qZn8ws9fNrNbMbs5EMJHjmaX7Pp6ZDQWGuvsmMysD/he40t3fyERAkeNR2jOeu7/n\n7psOPK4HNgPD0t2vyPEso9d4ZnYacB7wp0zuV+R4k7HiHTjNXAF8/8DMJyJHkZ+JnZhZPm2lW+bu\nvz3KGP1SqPQL7m7djcnUjPcg8Lq7L+4mUE5tVVVV4Rn6QqZczZWLmVKVibcTLgT+DfgnM9toZq+a\n2aR09ytyPEv7VNPdXwTyMpBFpN/o17+5UlFRER3hCLmYCXIzVy5mSlXab6CnfCAzz9axRKKYGZ7F\nmysi0gMqnkgAFU8kgIonEkDFEwmg4okEUPFEAqh4IgFUPJEAKp5IABVPJICKJxJAxRMJoOKJBFDx\nRAKoeCIBVDyRACqeSAAVTySAiicSQMUTCaDiiQRQ8UQCqHgiAVQ8kQAqnkiAjBTPzB4ws/fN7LVM\n7E/keJepGW8pMDFD+xI57mWkeO7+AvBRJvYVobGxkYcffpiPPsqdLyGZTLJixQq2bdsWHeUQzz//\nPC+88EJ0jL4vgythjgBe6+LznmsaGhr8Zz/7mQ8aNMjz8vL8oYceio7kra2tvnz5ch8+fLjn5eX5\njBkzoiO5u/tzzz3n48aN84KCAj/77LOj4+SsA9/n3fcllUEp7aiPFe/ll1/2AQMGeHFxsQOeSCQc\nCN9OOukkLyoqCs/RcRsyZIjn5eWF5zh8e/XVV6O/jY6QavHSXhG2J6qrq9sfV1RUhC4seOedd9LQ\n0EBJSQlFRUW4O8OHD+fiiy8OywRQVlbG0qVLyc/PZ+/evSQSCaZPnx6a6cQTT2T58uV88MEH7N27\nF4AZM2aE5fnb3/7GE088wZw5c1i9enVYDoCamhpqamp6/sJU2pnKBpwG1Hbx+V7+WdMzl19+uQO+\ne/du/8EPfuDFxcX+9NNPR8dy97ZT4LvvvttPOOEE/9GPfhQdx93bToEfe+wxHzFihFdWVoZmmTx5\nspuZl5SUeF1dXWiWw5HNU03gEWAnsB94G5jWyZgsfNmpO1i8g/bv3x+YpnP79+/3ZDIZHeMQra2t\n3tzcHHb82tpaLykpab88uPzyy8OydCbV4mXkVNPd/zUT+4lUWFgYHeEIuZgpkUiQSMT93sUf//hH\nGhsbgbY7v6+88grJZDI007HoW2ml35sxYwZNTU0AzJ49m3feeafPlQ5UPOljzIyCggIA8vPzyc/P\n6v3BjFHxRAKoeCIBVDyRACqeSAAVTySAiicSQMUTCaDiiQRQ8UQCqHgiAVQ8kQAqnkgAFU8kgIon\nEkDFEwmg4okEUPFEAqh4IgFUPJEAKp5IABVPJICKJxJAxRMJoOLJEdydF198kSlTpjBkyBBKS0sZ\nMmQIlZWVrF27lmQyGR2xz+ub/xqo9Jq6ujquuuoqdu3aRUNDw8F1L2hoaGD9+vVs2LCBgQMH8vjj\nj3PhhRcGp+27NONJu5dffpkvf/nLbNu2jb1797aXrqP6+np27tzJpZdeypo1awJSHh/6ZfHq6ura\nlzjesGEDzc3NwYnivffee0ycOJH6+vqUxjc0NDB16lS2bNnSy8mOTxkpnplNMrM3zGyrmd2aiX32\nlvr6es477zy2bt0KwIQJE3jqqaeCU8X7xS9+0b4KT6r27dvHggULeinR8S3t4plZArgXmAicA1xj\nZmemu9/eUlZWxqRJk9qfl5aWMnHixMBE8Zqbm7n33nvZv39/j17X2trKY489xieffNJLyf6uubmZ\nN954o9ePky2ZmPHGAm+6+3Z3bwaWA1dmYL+9ZsGCBRQVFVFcXMxtt91GaWlpdKRQzz33HK2trcf0\n2ry8PFatWpXhREdavHgxZ511FpdeeimbNm3q9eP1ulRWr+xqA/4ZuK/D82uBezoZ15sLcfZYZWWl\nl5SUeH19fXSUdp988olXVlY6oK2Tzczal2AGfP78+dH/y45AFleEtU4+duTtMKC6urr9cUVFBRUV\nFRk4/LEpLy+nsbExp2a7n//856xbty46Rp8wduxYZs6cGR2Dmpoaampqev7CVNrZ1QaMB9Z0eH4b\ncGsn43r/x00PHL4GerRPP/3Uy8vL3cyyvq73+vXrvby8/JhmobKyMl+2bFmvZ/zpT3/qgFdWVvrG\njRt7/XjHihRnvEwULw/YBowACoFNwFmdjMvG152yXCve/Pnz20+hSkpKvK6uLmvHbmpq8kGDBh1T\n8UpKSnzPnj1Zybh58+ZeP066Ui1e2jdX3L0VuAlYC/wfsNzdN6e73/7mgQceaL/B0dLSwsMPP5y1\nYxcUFHDTTTdRVFTUo9fl5eXxjW98g4EDB/ZSsr8rKCjgzDNz9mZ5z6XSzkxs5NDs4p57M95f/vIX\nnzdvngP+0ksv+UcffZTV4+/atavHs15paalv2bIlqzlzHdma8SQzTj/9dEaPHg3A+PHjGTRoUFaP\nP3ToUH7/+99TVlaW0viSkhJWrFjBGWec0cvJjk8qnrQbO3YsL730EiNHjqS0tBSzI29Yl5WVccop\np7Bu3bpDfhFBekbFk0OMGjWKrVu3snbtWq688kqGDBnCgAEDGDx4MJdccgkrV65kx44d+psJadJf\nC5IjmBkXXHABTz75ZHSU45ZmPJEAKp5IABVPJICKJxJAxRMJoOKJBFDxRAKoeCIBVDyRACqeSAAV\nTySAiicSQMUTCaDiiQRQ8UQCqHgiAVQ8kQAqnkgAFU8kgIonEkDFEwmg4okEUPFEAvTL4rW0tNDS\n0gK0LfHb9k/ei2RPWsUzs6lmVmdmrWY2JlOhelN9fT0nnHACa9asAaCwsJBnnnkmOJX0N+nOeLXA\nVcD/ZCBLVpSWlh6y0EZxcTHnn39+YKK+JZlMtp8tyLFLq3juvsXd36Tz5Zhzkplx9913U1paSmFh\nIdOmTePkk0+OjpXzkskkjz/+OJ///Oe57LLLouP0ef1y7YSLL76YkSNHUldXx5w5c6LjtMvVa81l\ny5YxZ84cPvzwQ+rr69m+fTvf/va3QzOdfvrpzJo1i7y8vNAcx6rb4pnZOuBzHT9E28KEs939qZ4c\nrLq6uv1xRUUFFRUVPXl5xpgZ5557LnV1dTk12+3cuZNEIsGuXbtyKtd1111HXl5e+4q1APfff39g\nojYNDQ3MmzcvNENNTQ01NTU9f2Eqq1d2twH/DYzpZkwvrsPZc7m2Imxzc7MPGzbM8/Ly/MYbb4yO\ncwjAV65c6ePGjfOCggI/++yzQ/PMnz/fCwsLfeDAgV5fXx+a5XAErAjbZ67zctGjjz7Knj17aG1t\nZenSpezatSs60iHGjRvHhg0bePbZZ/nlL38ZlqO+vp4FCxbQ1NRES0sL99xzT1iWdKT7dsIUM9sB\njAdWm5nuyx+juXPnsm/fPhKJBC0tLSxevDg6UqcuuugiJkyYEHb8hx56iMbGRhKJBE1NTSxcuJBk\nMhmW51ile1fzv9z9H9y9xN1PdvevZCpYf7NkyRKmTp1KMplk0aJFTJ8+PTpSTrr66qtZtGgRyWSS\nUaNGsXTpUhKJPvh7IKmcj2ZiI4eup9xz7xrP3X3VqlU5l8m97brl3XffjY5xCMCrqqqiYxyBgGs8\nEUmRiicSQMUTCaDiiQRQ8UQCqHgiAVQ8kQAqnkgAFU8kgIonEkDFEwmg4okEUPFEAqh4IgFUPJEA\nKp5IABVPJICKJxJAxRMJoOKJBFDxRAKoeCIBVDyRACqeSAAVTySAiicSQMUTCZDuakELzWyzmW0y\nsyfMbGCmgvWWxsZGxowZw+rVqwE47bTT2LBhQ3Cq3FRVVcWIESMA+OIXv8iNN94YnOj4ke6MtxY4\nx93PA94Ebk8/Uu8qKChg9+7d7c/fffddysvLAxPlrqKiIt5//30APvjgg765Kk+OSneZrvXufnBx\nsg3AqelH6l35+fncddddlJWVkUgkmDRpEuecc050rCM8//zzXHDBBTz44INhGW6++WYKCwuBth9Y\nubRefF/X7RroPXA9sDyD++s111xzDbfffjuNjY0sWLAgOs4Rxo8fT21tLQ0NDZSXlzN69OiwLN/8\n5jdZsmQJ06ZNY+jQoWE5jjfdFs/M1gGf6/ghwIHZ7v7UgTGzgWZ3f6SrfVVXV7c/rqiooKKioueJ\nMyA/P5/JkyezatWqnJrtRo0aRVFREa+88kr7Kqdr165l7dq1wclg9uzZ0RHatbS0MHjw4PbZOFJN\nTQ01NTU9f2Eqi+h1tQHfAl4EiroZ15vrAfZYLi5M6e6+e/dunzlzppeUlHheXp7PmDEjOlLO+dWv\nfuUFBQU+bNgwb2lpiY5zCLKxMKWZTQJmAV919/3p7EvafPazn2XRokVs376dmTNn8vWvfz06Uk5p\naWnhtttuo7m5mT179vDII12eZOUsayvpMb7Y7E2gEPjwwIc2uPt3jjLW0zlWpl1xxRWsXr2aXMok\n3Vu2bBnXX389LS0tAJxyyins2LEjZ+64mhnubt2NS/eu5hfcfYS7jzmwdVo6kUw566yzmDJlCgCl\npaVce+21OVO6nuh7iaVf+9KXvsRvfvMbAG655RZ+8pOfBCc6NiqeSAAVTySAiicSQMUTCaDiiQRQ\n8UQCqHgiAVQ8kQAqnkgAFU8kgIonEkDFEwmg4okEUPFEAqh4IgFUPJEAKp5IABVPJICKJxJAxRMJ\noOKJBFDxRAKoeCIBVDyRACqeSAAVTySAiicSIN1luu40sz+b2UYzW2NmOb9kaDKZ5IYbbmD16tUA\nfO1rX+Ott94KTiX9Tboz3kJ3H+3u5wNPA1UZyNSr9u3bx69//ev25ytXruSvf/1rXCDpl9Jdpqu+\nw9NSIJlenN43YMAAbr/9dkpKSgAYPXp02JLQAPPmzeP++++nubk5LMPhli9fTnV1NXv27ImO0m7j\nxo1897vfZceOHdFRMiOVZWO72oAfA28DrwGDuxiX+XVvj9Gnn37q5eXlXlRU5M8++2xoliFDhnhx\ncbGfdNJJft9993lTU1NoHnf3yspKz8/P99LSUq+qqvKPP/44OpLfddddnkgkvLi42KdNm+aAV1VV\nRcc6AikuxZxKsdYdKNXBrfbAf684bNytQHUX+8nSl56aO+64wwFt3WyJRMKLiorCcwBuZu2ZAH/y\nySejv42OkGrx0lqKuSMzGw487e7nHuXzXlX190vAioqK0FM8gNraWpqamkIzXHTRRTQ3N5Ofn881\n11zD9OnTKS4uDs00bdo0amtrKSkpYcKECcyaNYvPfOYzoZmWLFnC0qVLGTBgACNGjGDhwoVMnjw5\nNBNATU0NNTU17c/nzp2b0lLM6Z5mjuzw+HvA412M7d0fNX3U1Vdf7dOmTfO33347Okq7uXPnemVl\npb/66qvRUdr97ne/8zFjxvgzzzzjyWQyOs5RkY0Zz8xWAGfQdlNlO3CDu+86ylhP51gifYGZpTTj\nZexUs9sDqXjSD6RaPP3mikgAFU8kgIonEkDFEwmg4okEUPFEAqh4IgFUPJEAKp5IABVPJICKJxJA\nxRMJoOKJBFDxRAKoeCIBVDyRACqeSAAVTySAiicSQMUTCaDiiQRQ8UQCqHgiAVQ8kQAqnkgAFU8k\ngIonEkDFEwmQkeKZ2S1mljSzEzOxP5HjXdrFM7NTgUtoW6arT+m4oGCuyMVMkJu5cjFTqjIx4y0C\n/j0D+8m6XPwfl4uZIDdz5WKmVKVVPDO7Atjh7rUZyiPSL+R3N8DM1gGf6/gh2haDvwP4IVB52OdE\npBvHvCKsmY0C1gMNtBXuVOBdYKy77+5kvJaDlX4hq0sxm9lbwBh3/ygjOxQ5jmXyfTxHp5oiKcnY\njCciqcvqb66Y2Z1m9mcz22hma8xsaDaPf5RMC81ss5ltMrMnzGxgDmSaamZ1ZtZqZmOCs0wyszfM\nbKuZ3RqZ5SAze8DM3jez16KzHGRmp5rZH8zsdTOrNbObu3yBu2dtA8o6PP4e8J/ZPP5RMl0CJA48\nXgDclQOZ/hH4AvAH2q6bo3IkgG3ACKAA2AScmQN/PhOA84DXorN0yDQUOO/A4zJgS1d/Vlmd8dy9\nvsPTUiCZzeN3xt3Xu/vBHBtouzsbyt23uPubxF8zjwXedPft7t4MLAeuDM6Eu78A5NRNPHd/z903\nHXhcD2wGhh1tfLfv42Wamf0YuA74GLg428fvxvW0fXNJm2HAjg7P36GtjNIFMzuNthn5T0cbk/Hi\ndfGG+2x3f8rd7wDuOHC98D2gOtMZeprpwJjZQLO7P9LbeVLNlAM6m3F1N64LZlYGrAC+f9gZ3iEy\nXjx3r+x+FACPAk+TheJ1l8nMvgVcBvxTb2c5qAd/TpHeAYZ3eH4qsDMoS84zs3zaSrfM3X/b1dhs\n39Uc2eHplbSdB4cys0nALOCr7r4/Ok8nIq/zXgFGmtkIMysE/gVYFZinIyP+GvhwDwKvu/vi7gZm\n9X08M1sBnEHbTZXtwA3uvitrATrP9CZQCHx44EMb3P07gZEwsynAfwBDaLsW3uTuXwnKMglYTNsP\n6QfcfUFEjo7M7BGgAhgMvA9UufvS4EwXAs8BtbSdjjvwQ3df0+n4bBZPRNron34QCaDiiQRQ8UQC\nqHgiAVQ8kQAqnkgAFU8kgIonEuD/ASU6nY4Iqz1YAAAAAElFTkSuQmCC\n",
 388       "text/plain": [
 389        "<matplotlib.figure.Figure at 0x7f36586f87b8>"
 390       ]
 391      },
 392      "metadata": {},
 393      "output_type": "display_data"
 394     }
 395    ],
 396    "source": [
 397     "plot_trace(trace_tour(sample_tours[1]))"
 398    ]
 399   },
 400   {
 401    "cell_type": "code",
 402    "execution_count": 38,
 403    "metadata": {},
 404    "outputs": [
 405     {
 406      "data": {
 407       "image/png": "iVBORw0KGgoAAAANSUhEUgAAASMAAAEACAYAAAD4GBC1AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAF09JREFUeJzt3Xt0lfWd7/H3d+eyE66pKKBSSq2OOKNUqYuCTns27XQE\nFZiWqR1mTk+9VFyWHkRQlF4MtHAEl4wtpfUPxrKWPSLL6upoVQJ20Q0yFktRCgVRVASngBqWQkIu\nhOR7/sgmK3qAJO4nz/Mj+/NaKyt7J7/8Pr/cPvnt/TzwmLsjIpK0VNILEBEBlZGIBEJlJCJBUBmJ\nSBBURiISBJWRiAShOIpJzOwt4BDQAjS5+6go5hWRwhFJGdFaQhl3fz+i+USkwET1MM0inEtEClBU\nBeLAajPbZGY3RzSniBSQqB6mXeHuB8zsLOA5M3vF3TdENLeIFIBIysjdD+Rev2dmvwFGAR8qIzPT\nP4ITKVDubh2Nyfthmpn1MrM+udu9gX8E/nKSBSX2UllZqfwCzFZ+8vmdFcXOaBDwm9zOpxh4xN3X\nRDCviBSQvMvI3XcDl0awFhEpYAVzOD6TySi/ALOVn3x+Z1lXHtPlFWTmcWWJSDjMDI/jCWwRkSio\njEQkCCojEQmCykhEgqAyEpEgqIxEJAgqIxEJgspIRIKgMhKRIKiMRCQIKiMRCYLKSESCoDISkSCo\njEQkCCojEQmCykhEgqAyEpEgqIxEJAgqIxEJgspIRIKgMhKRIERWRmaWMrOXzOypqOYUkcIR5c7o\nNmBHhPOJSAGJpIzMbAhwNfAfUczXU9XW1rJ06VL279+f9FJEgpP35a1zHgDuBPpHNF+PUlNTw5Il\nS1i0aBH19fW0tLQwderU2PKLioooKSmJLU/k48j7irJmdg0w3t2/a2YZYJa7TzjBOK+srGy7n8lk\nTpvL7ubrrLPOorq6Gmi7umbsa9i8eTMjR46MPVcKTzabJZvNtt2fN29ep64oi7vn9QL8H2Av8Caw\nH6gFHj7BOC9UgE+cONErKiq8qKjIf/GLX8SWvWDBAk+lUj5u3LjYMkXay/3ud9glee+M2jOz/0Hr\nzmjiCd7nUWadTsyMxYsXc+utt7JixQomTJjAwIEDuz23traWc845h5qaGsrLy9m4cSMjRozo9lyR\n9nKPBjrcGek8oxiVl5dz0003xVJEAOvWrePIkSMANDY2smLFilhyRT6OqJ7ABsDd1wHropxTPr7x\n48ezZcsWRowYwS9/+UsmT56c9JJETko7ox4slUpxySWXADB8+HD69OmT8IpETk5lJCJBUBmJSBBU\nRiISBJWRiARBZSQiQVAZiUgQVEYiEgSVkYgEQWUkIkFQGYlIEFRGIhIElZGIBEFlJCJBUBmJSBBU\nRiISBJWRiARBZSQiQVAZiUgQVEYiEgSVkYgEQWUkIkFQGYlIEPIuIzNLm9mLZvaymW0zs8ooFtYT\ntLS08NRTTwGwfv163nzzzYRXJBKuvC/i6O6NZjbW3evMrAj4LzNb5e5/jGB9p7Vt27YxadIkAJ5+\n+mlKS0t57LHHEl6VSJgieZjm7nW5m2laC86jmDdq1dXVzJkzhz/+MZ6eHDFiBBdffDEA6XSamTNn\nxpIrcjqK5PLWZpYCNgOfAX7u7puimDcqBw4c4P777+fBBx+koaGBLVu2cOedd8aS/c1vfpO7776b\nkSNHMnr06FgyRU5HkZSRu7cAl5lZP+A/zexv3X3HR8fNnTu37XYmkyGTyUQR36GRI0eyf//+tvtV\nVVVUVVXFkn3cggULYs077uDBg5SXl/Pee+8lki+FJ5vNks1mu/xx5h7tIyozuweodfd//8jbPeqs\nLqyJL3zhCxw+fJitW7dy5513smjRokTWErfZs2ezePFiRo0axR/+8IeklyMFyMxwd+toXBRH0840\ns/652+XAPwA78503agMHDuTll18mm81y1113Jb2cWBw8eJCf//zntLS0sHXrVjZs2JD0kkROKoon\nsM8Gfm9mW4AXgdXu/mwE80bOzPjiF7/IGWeckfRSYrF582bq6+sBqKurY82aNQmvSOTkoji0vw0Y\nGcFaJGJf+cpXeP/996moqGDNmjWMHTs26SWJnJTOwO7BzIz+/fsD0K9fP4qLIzleIdItVEYiEgSV\nkYgEQWUkIkFQGYlIEFRGIhIElZGIBEFlJCJBUBmJSBBURiISBJWRiARBZSQiQVAZiUgQVEYiEgSV\nkYgEQWUkIkFQGYlIEFRGIhIElZGIBEFlJCJBUBmJSBBURiISBJWRiAQhiivKDjGztWa2w8y2mdn0\nKBYWBXfnoYceAqCqqor169cnvCIRORlz9/wmMBsMDHb3LWbWB9gMTHL3nR8Z5/lmdVV1dTWDBg1q\nu1+o15s3MzZu3MjnP//5pJciBcjMcHfraFzeOyN3P+DuW3K3a4FXgHPznTcKZ555JlOmTCGVSlFe\nXs68efNiy/7Wt77F0qVLaWxsjC2zI9lslkmTJrF79+7Ys92dJ598kq9+9ascPHgw9vxjx47x8MMP\n8/Wvfz2R70lDQwM//elPufHGG2PPPl3kvTP60GRmw4AscHGumNq/L/adEcDu3bs5//zzOeuss5g2\nbRpmHRZ0JH74wx/Sq1cvysrKmDNnDnfccUcsuSdiZgwfPpy9e/fS2NjIVVddxZgxY2LLT6fTLFu2\njP3791NbW8v111/PZz7zmdjyi4qKWLp0KYcOHeLIkSPMnj2bvn37xpZ/9OjRtj9MdXV1/PjHP44t\nG2Dq1KkMHDgw1sz2OrsziqyMcg/RssCP3f3JE7zfKysr2+5nMhkymUwk2R258cYbWb58eSxZH1Va\nWsrRo0dZuXIl3/jGNxJZw2WXXcaf//xnkvhjAPCJT3yCmpoajh07lkj+GWecQU1NDU1NTYnk9+7d\nm6amJo4ePZpI/qBBg9i3bx+pVDzHq7LZLNlstu3+vHnzOlVGuHveL0AxUAXcdooxXkjS6bRXVFT4\nAw884IAvXrw4sbW0tLT47373O//sZz/rgK9atSrW/ObmZn/iiSf8vPPOc8C3b98ea35TU5M/9NBD\nPnjwYDcz/+CDD2LNr6ur88WLF3tFRYX36tUrttx3333Xy8vLvby83B977LHYcj8q97vfcY90ZlCH\nk8DDwL93MKa7P+egvPHGG15fX+/unngZHdfS0uI7duzwlpaWRPKbm5v9lVdeSSTbvbWUXnvttcTy\n6+rq/M0334wt7/bbb/fS0lIHfNiwYd7c3BxbdnudLaMoDu1fCfwb8CUze9nMXjKzcfnOe7o777zz\nKCsrS3oZH2JmXHTRRbE9b/ZRqVSK4cOHJ5INUFxczAUXXJBYfnl5OZ/+9Kdjy9u+fXvbQ8OamhoO\nHz4cW/bHUZzvBO7+X0BRBGsRkQitXr2aa6+9lmeeeYbq6uqkl9MhnYEtIkFQGYlIEFRGIhIElZGI\nBEFlJCJBUBmJSBBURiISBJWRiARBZSQiQVAZiUgQVEYiEgSVkYgEQWUkIkFQGYlIEFRGIhIElZGI\nBEFlJCJBUBmJSBBURiISBJWRiARBZSQiQVAZiUgQVEYiEoRIysjMHjKzd8xsaxTz9RR1dXXMnDkT\ngKVLl7J69eqEVyQSrqh2RsuBqyKaq8d4++23+clPfgLAW2+9xcqVKxNekUi4Iikjd98AvB/FXN0p\nm80yevRofv3rX8eSd+GFF3L11VdjZqTTaSorK2PJlcK2YsUKrrjiCtavX5/0Urok78tbnw7Wrl3L\nHXfcwauvvkpdXR3XXXcd48aNiyW7pqYGd2fy5MkMGzYslkwJR2NjI7Nnz+a1116LLbOqqgqA8ePH\nU1paGltuvmIto7lz57bdzmQyZDKZWHK//OUvk0qlKCkpaXvb8W9YHCoqKrjnnntiy5NwzJs3jyVL\nliSS3dzczJEjR2LfkWezWbLZbNc/0N0jeQE+BWw9xfs9KYBfe+21PmPGDC8tLfX58+cnthYpHIcO\nHfI+ffp4SUmJf+9734stt7Ky0ktLS33WrFn+3nvvxZZ7Mrnf/Q47xFrH5s/MhgG/dfdLTvJ+jyqr\nq8yMyZMn8/jjj3Po0CH69euHmSWyFikcP/rRj1iwYAFHjx6lrKyM/fv3U1FR0e25LS0t1NTU0L9/\n/27P6gwzw907/IWL6tD+CuAF4G/MbK+Z3RDFvN2hf//+KiKJRX19PUePHgXgnHPO4ciRI7HkplKp\nYIqoKyJ5zsjd/zWKeUR6knvvvZf+/fszZ84c3njjjaSXEzydgS0iQVAZiUgQVEYiEgSVkYgEQWUk\nIkFQGYlIEFRGIhIElZGIBEFlJCJBUBmJSBBURiISBJWRiARBZSQiQVAZiUgQVEYiEgSVkYgEQWUk\nIkFQGYlIEFRGIhIElZGIBEFl1ENVV1ezaNEiLrnkEoYMGcKFF17I9OnT9R/DS7AK4vLWhcTdmTt3\nLvfddx9mRn19fdv7du/ezbJlyxg/fjyPPPII5eXlCa5U5MO0M+phpk+fzv33309DQ8OHigigqamJ\nhoYGVq1axdixY9uu6SUSgqgu4jjOzHaa2WtmdlcUc0ahsbGR6667DoAnnniC++67L+EVda+qqiqW\nL19OXV3dKcc1NDSwdetW5s+fH9PKRDqWdxmZWQpYClwF/B0wxcyG5ztvFBoaGnj66aeB1kvsPv/8\n87FlJ3Ep74ULF3b6qqX19fX87Gc/o6mpqVvWktSlzEPJl66LYmc0Ctjl7nvcvQlYCUyKYN689e/f\nn1mzZlFWVkZZWRkLFy6MLfuiiy7ia1/7Gjt37owl769//Ssvvvhilz6mubmZZ599NvK1vPXWW5x9\n9tnMmjWL6urqyOfvyKZNmxg8eDDz58+npqYm9nz5eCzfvyBmNhm4yt2n5u7/T2CUu0//yDhP4q/V\nBx98wODBgwEoLS2NLbempoZUKkU6nWbMmDGsWrWqW/Off/55JkyYwKFDh7r0cel0OvJ1HS+AdDpN\nKpXiyiuv7HJRRpFfXl5OUVERt912W2IPSRcsWMAPfvCDgt6pmRnubh2Ni+Jo2olCTviVnzt3btvt\nTCZDJpOJIP7UKioqWLp0KTfffDONjY3dntfe8R/AtWvXsmzZMqZNm9btWV3V2NjYbV+XlpYWAA4f\nPpzIDqWlpYXm5mYWLFiQWBkdOHCAVCrF/v37OfvssxNZQ9yy2SzZbLbrH+jueb0Ao4GqdvfvBu46\nwTgvJEOGDPFMJuObNm1ywBcvXtyteXv27PGysjKn9Q9Bp1769u3rjz/+eORref31171v375+ww03\n+N69eyOfvyMvvPCC9+nTx2fOnOlPPvmkJ/Wz9+6773p5ebmXlJT4rbfemsgaQpD7+nfcJZ0ZdMoJ\noAh4HfgUUApsAS46wbg4Pu9gHDt2rO12HGXk7j569Ogul1FDQ0O3rKX955+E4/nr1q1LrIxuv/12\nLy4udsCLi4t93759iawjaZ0to7yfwHb3ZuC7wBpgO7DS3V/Jd97TXVFRUeyZd999N7179+7U2LKy\nMm655RbS6XS3rCWJzz+kfIChQ4e2PXweM2ZMrM9Zno4iOc/I3avc/UJ3v8Dd4ztkJR8yceJEJk+e\nTK9evU45Lp1Oc8EFFzBv3ryYVlaYZsyY0fZc1fr16xkwYEDCKwqbzsDuQcyM5cuXc9NNN5FOp/+/\nXU9RURG9evXiiiuuYMOGDR2WlkicVEY9TCqVYsmSJezatYsZM2YwdOhQAAYMGMCUKVPYsGEDa9eu\npV+/fgmvVOTDVEY91Cc/+UkWLlzInj17AHjmmWf41a9+xWWXXZbwykROTGUkIkFQGYlIEFRGIhIE\nlZGIBEFlJCJBUBmJSBBURiISBJWRiARBZSQiQVAZiUgQVEYiEgSVkYgEQWUkIkFQGYlIEFRGIhIE\nlZGIBEFlJCJBUBmJSBBURiISBJWRiAQhrzIys382s7+YWbOZjYxqUT3Fvn37uPTSSwGYNWsW9957\nb8IrKizLly9n8uTJAFx88cVs37494RXJqeS7M9oGfBVYF8FaepyioiJ27NgBQGlpKQ0NDbFlx5kV\nqqamJmpqagDYuXNnrFeZ1de/6/IqI3d/1d13ARbRenqUQYMGccstt1BSUkJJSQkzZ86MJffQoUMM\nGDCAsWPH8qc//SmWzBBdf/319OvXDzNjwoQJDB8+PJbcRx99lIqKCmbNmsWRI0diyewJ7Pi1wPOa\nxOz3wCx3f+kUYzyKrNPNO++8w7nnnktzc3Ps2WZGOp2moaGBTZs2cfnll8e+hqQ9+OCDfOc734k9\nN5VKUVJSQnNzM8eOHaMQf/aPMzPcvcMNS3EnJnoOGNT+TYAD33f333ZlUXPnzm27nclkyGQyXfnw\n09KgQYN49NFHY72ufW1tLXv27KG0tJRUKsXUqVP53Oc+F1t+SL797W+zbds21q9fH1vm8eemSkpK\nGDBgAAsWLIgtOwTZbJZsNtvlj9POqAeqra3l8ssv55prrmHOnDmceeaZSS+poKxZs4Zp06ZRWVnJ\nlClTYn2uKkSd3RlFWUZ3uPvmU4xRGYkUoM6WUb6H9v/JzN4GRgNPm9mqfOYTkcIVyc6oU0HaGYkU\npFh2RiIiUVEZiUgQVEYiEgSVkYgEQWUkIkFQGYlIEFRGIhIElZGIBEFlJCJBUBmJSBBURiISBJWR\niARBZSQiQVAZiUgQVEYiEgSVkYgEQWUkIkFQGYlIEFRGIhIElZGIBEFlJCJBUBmJSBDyvW7afWb2\nipltMbMnzKxfVAsTkcKS785oDfB37n4psAuYk/+SusfHufa38k//bOUnn99ZeZWRu//O3VtydzcC\nQ/JfUvdI+htSyPmF/Lkrv/OifM7oRkCXtxaRj6W4owFm9hwwqP2bAAe+7+6/zY35PtDk7iu6ZZUi\n0uOZu+c3gdm3gKnAl9y98RTj8gsSkdOWu1tHYzrcGZ2KmY0DZgNfPFURdXYxIlK48toZmdkuoBQ4\nmHvTRnf/ThQLE5HCkvfDNBGRKMR6BraZ/cjM/mxmL5tZlZkNjjk/sZM0zeyfzewvZtZsZiNjzB1n\nZjvN7DUzuyuu3Fz2Q2b2jpltjTO3Xf4QM1trZjvMbJuZTY85P21mL+Z+3reZWWWc+bk1pMzsJTN7\nKu7sXP5b7X7n/3jKwe4e2wvQp93t/w08GHP+PwCp3O2FwL0xZl8IXACsBUbGlJkCXgc+BZQAW4Dh\nMX7Ofw9cCmyN8/vcLn8wcGnudh/g1Tg//1xur9zrIlrPxRsVc/7twP8Fnkroe/Am8InOjI11Z+Tu\nte3u9gZaTja2m/ITO0nT3V919120nhoRl1HALnff4+5NwEpgUlzh7r4BeD+uvBPkH3D3LbnbtcAr\nwLkxr6EudzNN6wGj2J4XMbMhwNXAf8SVeaJl0MlHYLH/Q1kzm29me4F/Be6JO7+dQjhJ81zg7Xb3\n/5uYfxlDYWbDaN2lvRhzbsrMXgYOAM+5+6YY4x8A7iTGAjwBB1ab2SYzu/lUAyMvIzN7zsy2tnvZ\nlns9AcDdf+DuQ4FHaH2oFmt+bky3nKTZmeyYnWgXVnBHLMysD/A4cNtHdufdzt1b3P0yWnfhnzez\nv40j18yuAd7J7QyNeHfk7V3h7pfTukObZmZ/f7KBeZ1ndCLu/pVODn0UeAaYG2d+7iTNq4EvRZnb\nmewE/DcwtN39IcC+hNaSCDMrprWIfuXuTya1Dnc/bGZZYBywI4bIK4GJZnY1UA70NbOH3f1/xZDd\nxt0P5F6/Z2a/ofWpgw0nGhv30bTz292dROtj+Djzj5+kOdE7OEmzu5cSU84m4Hwz+5SZlQL/AsR9\nVCXJv8oAvwR2uPtP4w42szPNrH/udjmtB1B2xpHt7t9z96Hufh6t3/e1cReRmfXK7Uoxs97APwJ/\nOdn4uJ8zWph72LKF1m/MbTHn/4zWoyrP5Q53/iKuYDP7JzN7GxgNPG1m3f58lbs3A9+l9b962Q6s\ndPfY/gCY2QrgBeBvzGyvmd0QV3Yu/0rg34Av5Q4tv5T7gxSXs4Hf537eXwRWu/uzMeYnbRCwIfec\n2Ubgt+6+5mSDddKjiARB/+2siARBZSQiQVAZiUgQVEYiEgSVkYgEQWUkIkFQGYlIEFRGIhKE/wdL\nGE/mZ+od3gAAAABJRU5ErkJggg==\n",
 408       "text/plain": [
 409        "<matplotlib.figure.Figure at 0x7f3658758860>"
 410       ]
 411      },
 412      "metadata": {},
 413      "output_type": "display_data"
 414     }
 415    ],
 416    "source": [
 417     "plot_trace(trace_tour(sample_tours[2]))"
 418    ]
 419   },
 420   {
 421    "cell_type": "markdown",
 422    "metadata": {},
 423    "source": [
 424     "# Part 1"
 425    ]
 426   },
 427   {
 428    "cell_type": "code",
 429    "execution_count": 18,
 430    "metadata": {},
 431    "outputs": [
 432     {
 433      "data": {
 434       "text/plain": [
 435        "226"
 436       ]
 437      },
 438      "execution_count": 18,
 439      "metadata": {},
 440      "output_type": "execute_result"
 441     }
 442    ],
 443    "source": [
 444     "with open('06-tours.txt') as f:\n",
 445     "    tours = [t.strip() for t in f.readlines()]\n",
 446     "len(tours)"
 447    ]
 448   },
 449   {
 450    "cell_type": "code",
 451    "execution_count": 19,
 452    "metadata": {},
 453    "outputs": [
 454     {
 455      "data": {
 456       "text/plain": [
 457        "61762"
 458       ]
 459      },
 460      "execution_count": 19,
 461      "metadata": {},
 462      "output_type": "execute_result"
 463     }
 464    ],
 465    "source": [
 466     "sum(len(t) for t in tours if valid(trace_tour(t)))"
 467    ]
 468   },
 469   {
 470    "cell_type": "code",
 471    "execution_count": 20,
 472    "metadata": {},
 473    "outputs": [
 474     {
 475      "data": {
 476       "text/plain": [
 477        "100"
 478       ]
 479      },
 480      "execution_count": 20,
 481      "metadata": {},
 482      "output_type": "execute_result"
 483     }
 484    ],
 485    "source": [
 486     "sum(1 for t in tours if valid(trace_tour(t)))"
 487    ]
 488   },
 489   {
 490    "cell_type": "code",
 491    "execution_count": 21,
 492    "metadata": {},
 493    "outputs": [
 494     {
 495      "data": {
 496       "text/plain": [
 497        "123845"
 498       ]
 499      },
 500      "execution_count": 21,
 501      "metadata": {},
 502      "output_type": "execute_result"
 503     }
 504    ],
 505    "source": [
 506     "sum(len(t) for t in tours)"
 507    ]
 508   },
 509   {
 510    "cell_type": "code",
 511    "execution_count": 22,
 512    "metadata": {},
 513    "outputs": [
 514     {
 515      "name": "stdout",
 516      "output_type": "stream",
 517      "text": [
 518       "10 loops, best of 3: 196 ms per loop\n"
 519      ]
 520     }
 521    ],
 522    "source": [
 523     "%%timeit\n",
 524     "sum(len(t) for t in tours if valid(trace_tour(t)))"
 525    ]
 526   },
 527   {
 528    "cell_type": "markdown",
 529    "metadata": {},
 530    "source": [
 531     "# Part 2"
 532    ]
 533   },
 534   {
 535    "cell_type": "code",
 536    "execution_count": 23,
 537    "metadata": {},
 538    "outputs": [
 539     {
 540      "data": {
 541       "text/plain": [
 542        "80622"
 543       ]
 544      },
 545      "execution_count": 23,
 546      "metadata": {},
 547      "output_type": "execute_result"
 548     }
 549    ],
 550    "source": [
 551     "(sum(len(pi + pj)\n",
 552     " for i, pi in enumerate(tours) \n",
 553     " for j, pj in enumerate(tours)\n",
 554     " if i != j\n",
 555     " if not valid(trace_tour(pi))\n",
 556     " if not valid(trace_tour(pj))\n",
 557     " if valid(trace_tour(pi + pj))) \n",
 558     " + \n",
 559     " sum(len(t) for t in tours if valid(trace_tour(t))))"
 560    ]
 561   },
 562   {
 563    "cell_type": "code",
 564    "execution_count": 24,
 565    "metadata": {},
 566    "outputs": [
 567     {
 568      "name": "stdout",
 569      "output_type": "stream",
 570      "text": [
 571       "1 loop, best of 3: 1min 32s per loop\n"
 572      ]
 573     }
 574    ],
 575    "source": [
 576     "%%timeit\n",
 577     "[(i, j) \n",
 578     " for i, pi in enumerate(tours) \n",
 579     " for j, pj in enumerate(tours)\n",
 580     " if i != j\n",
 581     " if not valid(trace_tour(pi))\n",
 582     " if not valid(trace_tour(pj))\n",
 583     " if valid(trace_tour(pi + pj))]"
 584    ]
 585   },
 586   {
 587    "cell_type": "code",
 588    "execution_count": 25,
 589    "metadata": {
 590     "collapsed": true
 591    },
 592    "outputs": [],
 593    "source": [
 594     "# [(i, j) \n",
 595     "#  for i, pi in enumerate(tours) \n",
 596     "#  for j, pj in enumerate(tours)\n",
 597     "#  if i != j\n",
 598     "#  if not valid(trace_tour(pi))\n",
 599     "#  if not valid(trace_tour(pj))\n",
 600     "#  if valid(trace_tour(pi + pj))]"
 601    ]
 602   },
 603   {
 604    "cell_type": "code",
 605    "execution_count": 26,
 606    "metadata": {
 607     "collapsed": true
 608    },
 609    "outputs": [],
 610    "source": [
 611     "# (sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 612     "#     +\n",
 613     "#     sum(len(pi + pj) \n",
 614     "#      for i, pi in enumerate(tours) \n",
 615     "#      for j, pj in enumerate(tours)\n",
 616     "#      if i != j\n",
 617     "#      if not valid(trace_tour(pi))\n",
 618     "#      if not valid(trace_tour(pj))\n",
 619     "#      if valid(trace_tour(pi + pj)))\n",
 620     "# )"
 621    ]
 622   },
 623   {
 624    "cell_type": "code",
 625    "execution_count": 27,
 626    "metadata": {},
 627    "outputs": [
 628     {
 629      "name": "stdout",
 630      "output_type": "stream",
 631      "text": [
 632       "1 1\n",
 633       "2 1\n",
 634       "3 4\n",
 635       "4 5\n",
 636       "5 7\n",
 637       "6 3\n",
 638       "7 1\n",
 639       "8 2\n",
 640       "9 2\n",
 641       "11 2\n",
 642       "18 1\n",
 643       "19 1\n"
 644      ]
 645     }
 646    ],
 647    "source": [
 648     "l1s = {}\n",
 649     "for t in tours:\n",
 650     "    tr = trace_tour(t)\n",
 651     "    l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
 652     "    if l1 > 0:\n",
 653     "        if l1 not in l1s:\n",
 654     "            l1s[l1] = []\n",
 655     "        l1s[l1] += [t]\n",
 656     "\n",
 657     "for l1 in l1s:\n",
 658     "    if l1 < 20:\n",
 659     "        print(l1, len(l1s[l1]))"
 660    ]
 661   },
 662   {
 663    "cell_type": "code",
 664    "execution_count": 28,
 665    "metadata": {},
 666    "outputs": [
 667     {
 668      "data": {
 669       "text/plain": [
 670        "[(1, 1),\n",
 671        " (2, 1),\n",
 672        " (3, 4),\n",
 673        " (4, 5),\n",
 674        " (5, 7),\n",
 675        " (6, 3),\n",
 676        " (7, 1),\n",
 677        " (8, 2),\n",
 678        " (9, 2),\n",
 679        " (11, 2),\n",
 680        " (18, 1),\n",
 681        " (19, 1)]"
 682       ]
 683      },
 684      "execution_count": 28,
 685      "metadata": {},
 686      "output_type": "execute_result"
 687     }
 688    ],
 689    "source": [
 690     "[(l1, len(l1s[l1])) for l1 in l1s if l1 < 20]"
 691    ]
 692   },
 693   {
 694    "cell_type": "code",
 695    "execution_count": 29,
 696    "metadata": {
 697     "collapsed": true
 698    },
 699    "outputs": [],
 700    "source": [
 701     "# %%timeit\n",
 702     "# (sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 703     "#     +\n",
 704     "#     sum(len(pi + pj) \n",
 705     "#      for i, pi in enumerate(tours) \n",
 706     "#      for j, pj in enumerate(tours)\n",
 707     "#      if i != j\n",
 708     "#      if not valid(trace_tour(pi))\n",
 709     "#      if not valid(trace_tour(pj))\n",
 710     "#      if valid(trace_tour(pi + pj)))\n",
 711     "# )"
 712    ]
 713   },
 714   {
 715    "cell_type": "code",
 716    "execution_count": 30,
 717    "metadata": {
 718     "collapsed": true
 719    },
 720    "outputs": [],
 721    "source": [
 722     "good_is = []\n",
 723     "goods = []\n",
 724     "tried = []\n",
 725     "for l1 in l1s:\n",
 726     "    possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
 727     "    candidates = [t for i in possible_l1s for t in l1s[i]]\n",
 728     "    for t1 in candidates:\n",
 729     "        for t2 in candidates:\n",
 730     "            if t1 != t2:\n",
 731     "                t12 = t1 + t2\n",
 732     "                if (t12) not in tried:\n",
 733     "                    tried += [(t12)]\n",
 734     "                    if valid(trace_tour(t12)):\n",
 735     "                        good_is += [(tours.index(t1), tours.index(t2))]\n",
 736     "                        goods += [t12]"
 737    ]
 738   },
 739   {
 740    "cell_type": "code",
 741    "execution_count": 31,
 742    "metadata": {},
 743    "outputs": [
 744     {
 745      "data": {
 746       "text/plain": [
 747        "80622"
 748       ]
 749      },
 750      "execution_count": 31,
 751      "metadata": {},
 752      "output_type": "execute_result"
 753     }
 754    ],
 755    "source": [
 756     "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 757     "    +\n",
 758     "    sum(len(t12) for t12 in goods)\n",
 759     ")"
 760    ]
 761   },
 762   {
 763    "cell_type": "code",
 764    "execution_count": 32,
 765    "metadata": {},
 766    "outputs": [
 767     {
 768      "name": "stdout",
 769      "output_type": "stream",
 770      "text": [
 771       "1 loop, best of 3: 1.2 s per loop\n"
 772      ]
 773     }
 774    ],
 775    "source": [
 776     "%%timeit\n",
 777     "\n",
 778     "l1s = {}\n",
 779     "for t in tours:\n",
 780     "    tr = trace_tour(t)\n",
 781     "    l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
 782     "    if l1 > 0:\n",
 783     "        if l1 not in l1s:\n",
 784     "            l1s[l1] = []\n",
 785     "        l1s[l1] += [t]\n",
 786     "\n",
 787     "goods = []\n",
 788     "tried = []\n",
 789     "for l1 in l1s:\n",
 790     "    possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
 791     "    candidates = [t for i in possible_l1s for t in l1s[i]]\n",
 792     "    for t1 in candidates:\n",
 793     "        for t2 in candidates:\n",
 794     "            if t1 != t2:\n",
 795     "                t12 = t1 + t2\n",
 796     "                if (t12) not in tried:\n",
 797     "                    tried += [(t12)]\n",
 798     "                    if valid(trace_tour(t12)):\n",
 799     "                        goods += [t12]\n",
 800     "\n",
 801     "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
 802     "    +\n",
 803     "    sum(len(t12) for t12 in goods)\n",
 804     ")"
 805    ]
 806   },
 807   {
 808    "cell_type": "code",
 809    "execution_count": 33,
 810    "metadata": {},
 811    "outputs": [
 812     {
 813      "data": {
 814       "text/plain": [
 815        "13"
 816       ]
 817      },
 818      "execution_count": 33,
 819      "metadata": {},
 820      "output_type": "execute_result"
 821     }
 822    ],
 823    "source": [
 824     "len(goods)"
 825    ]
 826   },
 827   {
 828    "cell_type": "code",
 829    "execution_count": 34,
 830    "metadata": {},
 831    "outputs": [
 832     {
 833      "data": {
 834       "text/plain": [
 835        "[(16, 125),\n",
 836        " (70, 48),\n",
 837        " (91, 128),\n",
 838        " (110, 134),\n",
 839        " (116, 194),\n",
 840        " (123, 51),\n",
 841        " (136, 9),\n",
 842        " (142, 193),\n",
 843        " (152, 63),\n",
 844        " (168, 150),\n",
 845        " (201, 83),\n",
 846        " (208, 204),\n",
 847        " (212, 113)]"
 848       ]
 849      },
 850      "execution_count": 34,
 851      "metadata": {},
 852      "output_type": "execute_result"
 853     }
 854    ],
 855    "source": [
 856     "sorted(good_is)"
 857    ]
 858   },
 859   {
 860    "cell_type": "code",
 861    "execution_count": 35,
 862    "metadata": {},
 863    "outputs": [
 864     {
 865      "data": {
 866       "text/plain": [
 867        "[(136, 9),\n",
 868        " (70, 48),\n",
 869        " (123, 51),\n",
 870        " (152, 63),\n",
 871        " (201, 83),\n",
 872        " (212, 113),\n",
 873        " (16, 125),\n",
 874        " (91, 128),\n",
 875        " (110, 134),\n",
 876        " (168, 150),\n",
 877        " (142, 193),\n",
 878        " (116, 194),\n",
 879        " (208, 204)]"
 880       ]
 881      },
 882      "execution_count": 35,
 883      "metadata": {},
 884      "output_type": "execute_result"
 885     }
 886    ],
 887    "source": [
 888     "sorted(good_is, key=lambda p: p[1])"
 889    ]
 890   },
 891   {
 892    "cell_type": "code",
 893    "execution_count": 36,
 894    "metadata": {},
 895    "outputs": [
 896     {
 897      "data": {
 898       "text/plain": [
 899        "[(1, 1),\n",
 900        " (2, 1),\n",
 901        " (3, 4),\n",
 902        " (4, 5),\n",
 903        " (5, 7),\n",
 904        " (6, 3),\n",
 905        " (7, 1),\n",
 906        " (8, 2),\n",
 907        " (9, 2),\n",
 908        " (11, 2),\n",
 909        " (18, 1),\n",
 910        " (19, 1),\n",
 911        " (21, 1),\n",
 912        " (24, 1),\n",
 913        " (132, 2),\n",
 914        " (26, 2),\n",
 915        " (28, 1),\n",
 916        " (29, 1),\n",
 917        " (34, 2),\n",
 918        " (36, 1),\n",
 919        " (37, 3),\n",
 920        " (166, 2),\n",
 921        " (40, 2),\n",
 922        " (41, 2),\n",
 923        " (44, 3),\n",
 924        " (46, 1),\n",
 925        " (48, 2),\n",
 926        " (50, 3),\n",
 927        " (52, 2),\n",
 928        " (53, 1),\n",
 929        " (54, 1),\n",
 930        " (56, 2),\n",
 931        " (57, 3),\n",
 932        " (58, 1),\n",
 933        " (59, 2),\n",
 934        " (61, 1),\n",
 935        " (64, 1),\n",
 936        " (66, 2),\n",
 937        " (68, 1),\n",
 938        " (70, 1),\n",
 939        " (74, 1),\n",
 940        " (75, 1),\n",
 941        " (76, 3),\n",
 942        " (77, 1),\n",
 943        " (81, 1),\n",
 944        " (82, 2),\n",
 945        " (86, 1),\n",
 946        " (88, 1),\n",
 947        " (90, 1),\n",
 948        " (94, 1),\n",
 949        " (97, 1),\n",
 950        " (98, 1),\n",
 951        " (101, 2),\n",
 952        " (106, 1),\n",
 953        " (107, 1),\n",
 954        " (114, 2),\n",
 955        " (117, 3),\n",
 956        " (127, 1)]"
 957       ]
 958      },
 959      "execution_count": 36,
 960      "metadata": {},
 961      "output_type": "execute_result"
 962     }
 963    ],
 964    "source": [
 965     "[(l, len(l1s[l])) for l in l1s.keys()]"
 966    ]
 967   },
 968   {
 969    "cell_type": "code",
 970    "execution_count": null,
 971    "metadata": {
 972     "collapsed": true
 973    },
 974    "outputs": [],
 975    "source": []
 976   }
 977  ],
 978  "metadata": {
 979   "kernelspec": {
 980    "display_name": "Python 3",
 981    "language": "python",
 982    "name": "python3"
 983   },
 984   "language_info": {
 985    "codemirror_mode": {
 986     "name": "ipython",
 987     "version": 3
 988    },
 989    "file_extension": ".py",
 990    "mimetype": "text/x-python",
 991    "name": "python",
 992    "nbconvert_exporter": "python",
 993    "pygments_lexer": "ipython3",
 994    "version": "3.5.2+"
 995   }
 996  },
 997  "nbformat": 4,
 998  "nbformat_minor": 2
 999 }