"cell_type": "markdown",
"metadata": {},
"source": [
- "Given a sequence of {F|L|R}, each of which is \"move forward one step\", \"turn left, then move forward one step\", \"turn right, then move forward one step\":\n",
- "1. which tours are closed?\n",
- "2. what is the area enclosed by the tour?"
+ "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",
+ "\n",
+ "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",
+ "\n",
+ "\n",
+ "![Sample valid tour](question-example-tour-000-s0010-m000-trim.png)\n",
+ "\n",
+ "A sample valid tour\n",
+ "\n",
+ "while the tour `FFLLRLRLLFLR` looks like this (again, assuming you start facing right):\n",
+ "\n",
+ "![Sample valid tour](question-example-tour-001-s0012-m000-trim.png) \n",
+ "\n",
+ "A sample valid tour\n",
+ "\n",
+ "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",
+ "\n",
+ "![Sample invalid tour](question-example-tour-002-s0012-m001-trim.png)\n",
+ "\n",
+ "An invalid tour\n",
+ "\n",
+ "and the tour `RRLLRRFFRFRFLR` may get you back to where you started, but only after going around a small loop:\n",
+ "\n",
+ "![Sample invalid tour](question-example-tour-003-s0014-m001-trim.png)\n",
+ "\n",
+ "A sample invalid tour\n",
+ "\n",
+ "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",
+ "\n",
+ "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",
+ "\n",
+ "# Part 1\n",
+ "\n",
+ "The tours are given in [06-tours.txt](06-tours.txt), one tour per line. \n",
+ "\n",
+ "What is the total length of all the valid tours?\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "It seems you've done your guides a disservice.\n",
+ "\n",
+ "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",
+ "\n",
+ "For instance, the tours `FFRFLLFFFRLRRFFFLFLRRFLLFFFFFRFLFFFFFRLLFRFRLLFFFFF` and `FLRFFRLLFRFFFLFFLFFRFRRLLFFRLFFFFFLLFFRFRFL` are both incomplete; on its own, each tour would leave you stranded. \n",
+ "\n",
+ "![A split tour](question-example-tour-004-s0051-m001-trim.png)\n",
+ "\n",
+ "A split tour \n",
+ "\n",
+ "![More of a split tour](question-example-tour-005-s0043-m001-trim.png)\n",
+ "\n",
+ "More of a split tour\n",
+ "\n",
+ "But if you do one then the other, the complete 94-step tour is valid:\n",
+ "\n",
+ "![Split tour combined](question-example-tour-006-s0094-m000-trim.png)\n",
+ "\n",
+ "The split tour combined\n",
+ "\n",
+ "(You start the second half of the tour heading left, so turn the second picture 180⁰ to visualise it.)\n",
+ "\n",
+ "Luckily for you, tour guides only act alone or in pairs, and never in teams of three or more. \n",
+ "\n",
+ "(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",
+ "\n",
+ "# Part 2\n",
+ "\n",
+ "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?"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Worked solution: part 1\n",
+ "This is a case where I'd like to have a stronger type system than what Python provides. During my development on this problem, I had several cases where bugs would have been caught by a type-checking compiler. (Python does have [type checking](https://docs.python.org/3/library/typing.html) since Python 3.5, but I've never used it!)\n",
+ "\n",
+ "Validity checking is about finding the places you've been on the tour. But, while tracing the tour, it's not enough just to keep track of the current position: you also need to keep track of the current direction, so you know which direction to step next.\n",
+ "\n",
+ "This led me to having three different ways of representing a tour, which is why I wanted three different types.\n",
+ "\n",
+ "* A **tour** is the string that's the input: a sequence of `FLRFF`-type letters.\n",
+ "* A **trace** is a sequence of position/direction thingies, which you use to find out where the tour takes you.\n",
+ "* The **positions** are just the positions you get to, regardless of direction you happen to be.\n",
+ "\n",
+ "If we can find the **positions** of a **tour**, we can easily say if that **tour** is valid: it's valid if and only if:\n",
+ "1. The first position == the last position == (0, 0)\n",
+ "2. The length of the set of positions is one more than the length of the sequence of positions\n",
+ "\n",
+ "(Converting from a `list` to a `set` removes duplicates. If we only remove one duplicate, the end points, that means all the other positions are unique.)\n",
+ "\n",
+ "So, we can determine validity from **positions**, **positions** from a **trace**, and a **trace** from a tour. All we need to do now is build those transformations!\n",
+ "\n",
+ "A **tour** is just a string of characters. \n",
+ "\n",
+ "A **trace** is a list of **Step**s, and each step has an `x` and `y` position and a `direction`. The position is where that step starts. There's always one more **Step** in a **trace** than the length of the **tour**, as the **trace** is the end points of the steps and the **tour** is the steps themselves. (This is an example of a [fencepost correction](https://en.wikipedia.org/wiki/Off-by-one_error#Fencepost_error).)\n",
+ "\n",
+ "Writing this out explicitly for the first time makes me realise I got the name of `Step` very wrong!\n",
+ "\n",
+ "## Transformation 1: tour to trace\n",
+ "The first thing to fix is the direction. I could use numbers for the direction, but in this case I decided to use Python's `Enum` type to make the code more readable and prevent typos. Then I defined a couple of functions, `turn_left()` and `turn_right()`, to return the new direction after a left and right turn. \n",
+ "\n",
+ "With directions sorted, `advance()` takes a step a position and a direction, and moves to the new point in that direction. `step()` takes a tour instruction and a current `Step` and returns the new `Step`. `trace_tour()` takes a **tour** (and an optional starting position) and applies `step()` character by character to build a complete **trace**.\n",
+ "\n",
+ "(For those interested in higher order functions, you can't use a `map` to calculate a **trace**, as you can't treat each character in the **tour** independently. You could do it with `functools.reduce`, which is a left fold, building up the complete **trace** as the accumulated value. But I'll leave that as an exercise for the reader.)\n",
+ "\n",
+ "## Transformation 2: trace to positions\n",
+ "This is much simpler. Given a sequence of `Step`s, just pull out the `x` and `y` positions. I keep the position as a 2-tuple of `(x, y)`. It's done as a list comprehension, effectively a `map`.\n",
+ "\n",
+ "## Transformation 3: trace to validity\n",
+ "For no good reason, I decided to make the `valid()` predicate act on **trace**s, not **positions**. Still, it uses the **trace** to **positions** transformation internally.\n",
+ "\n",
+ "## Solving part 1\n",
+ "With the transformations above, it's easy to solve part 1. We read the list of **tour**s from the file, and use the comprehension to filter only the valid **tour**s (the `if valid(trace_tour(t))` part), converting the **tour** to its length, and using `sum` to add them all up."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Worked solution: part 2\n",
+ "Essentially, we take every **tour** and combine it with every other **tour** and, if the resulting combination is valid, add its length to the total. The problem is, the validity check is quite expensive and blindly testing every combination of **tour**s takes 1m 30s, which is a bit too long.\n",
+ "\n",
+ "The interesting part of this question is to reduce the number of possible combinations we check. \n",
+ "\n",
+ "* If a tour is valid by itself, we don't want to combine it with any other tours.\n",
+ "* If a tour loops back on itself, any combination it forms won't be valid, so we don't need to check it\n",
+ "* For two tours to form a valid combination, the overall displacement of the two tours (the distance from the origin to the end of the partial tour) has to be about the same.\n",
+ "\n",
+ "The first and third optimisations are the most powerful, dropping the total runtime down from 1½ minutes to under a second. The second optimisation brings the runtime down to about half a second. \n",
+ "\n",
+ "We can do the \"tour displacement\" optimisation by finding the **trace** of each **tour** then finding the distance from the start of the tour to the end. There are lots of distance metrics I could use, including the common Euclidean distance (found with Pythagoras's theorem), also known as the $L_2$ norm. But the maths is a be easier if I use the taxicab distance, also known as the $L_1$ norm. \n",
+ "\n",
+ "I use a `dict` called `l1s` to store this information. The key is the l1 norm, and the value is a list of **tour**s with that l1 norm. We can then go through the `l1s` dict, norm value by norm value, and pull out the tours that have a close displacement and therefore are worth checking whether the combination is valid. The combination is formed from `t1` (with this displacement) and `t2` (with a close displacement). If the combination is valid, it's added to the `goods` list. \n",
+ "\n",
+ "Careful dataset creation means that if `t1+t2` is valid, `t2+t1` isn't! If it were, there would be questions about whether `t1+t2` is a different tour from `t2+t1`, and it's easier to just not deal with that particular case in this problem.\n",
+ "\n",
+ "The second optimisation restricts the **tour**s that go into `l1s` by not including **tour**s that have loops. That's done with a new version of `valid()` called `valid_part()`"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## An aside on norms\n",
+ "> \"[Norm](https://en.wikipedia.org/wiki/Norm_%28mathematics%29)\" is the fancy maths name for \"distance\" (roughly). There are lots of ways of calculating it. The $L_2$ norm is the standard one we know and love:\n",
+ "\n",
+ "> * $L_2 = \\sqrt{|x|^2 + |y|^2}$\n",
+ "\n",
+ "> (where $|x|$ means the absolute value of $x$, ignoring sign; this is often implemented as `abs(x)`.)\n",
+ "\n",
+ "> We can apply norms to higher dimensional spaces by just putting more co-ordinate components in the root, like $L_2 = \\sqrt{\\dots + |w|^2 + |x|^2 + |y|^2 + |z|^2 + \\dots}$\n",
+ "\n",
+ "> Other norms use differnet powers, so we have:\n",
+ "\n",
+ "> * $L_3 = \\sqrt[3]{|x|^3 + |y|^3}$\n",
+ "> * $L_4 = \\sqrt[4]{|x|^4 + |y|^4}$\n",
+ "> * $L_p = \\sqrt[p]{|x|^p + |y|^p}$\n",
+ "\n",
+ "> Basically, as the norm number in increases, the norm puts more emphasis on the largest co-ordinate difference. There are a few special cases you may come across.\n",
+ "\n",
+ "> * $L_1 = \\sqrt[1]{|x|^1 + |y|^1} = |x| + |y|$, which is the distance if you can only move horizontally or vertically, not diagonally. It's also known as the Manhattan distance or taxicab distance, after US city layouts.\n",
+ "\n",
+ "> * $L_0 = \\sqrt[0]{|x|^0 + |y|^0}$, but as $0^0 = 0$ and $(\\mathrm{anything\\ else})^0 = 1$, this counts the number of coordinates that are non-zero. It's also known as the Hamming distance.\n",
+ "\n",
+ "> * $L_\\infty = \\sqrt[\\infty]{|x|^\\infty + |y|^\\infty}$, isn't meaningful in itself, but makes sense as the limiting case as $p \\to \\infty$ and is $max(|x|, |y|)$."
]
},
{
"cell_type": "code",
- "execution_count": 2,
+ "execution_count": 1,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 3,
+ "execution_count": 2,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 4,
+ "execution_count": 3,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 5,
+ "execution_count": 4,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 6,
+ "execution_count": 5,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 7,
+ "execution_count": 6,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 8,
+ "execution_count": 7,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 9,
+ "execution_count": 8,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 10,
+ "execution_count": 9,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 11,
+ "execution_count": 10,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 12,
+ "execution_count": 11,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 13,
+ "execution_count": 12,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 14,
+ "execution_count": 13,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 15,
+ "execution_count": 14,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 16,
+ "execution_count": 15,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 17,
+ "execution_count": 16,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
- "def plot_trace(trace, colour='k', xybounds=None, fig=None, subplot_details=None, filename=None):\n",
+ "def plot_trace(trace, colour='k', highlight_start=True,\n",
+ " xybounds=None, fig=None, subplot_details=None, filename=None):\n",
" plt.axis('on')\n",
" plt.axes().set_aspect('equal')\n",
+ " \n",
+ " if highlight_start:\n",
+ " plt.axes().add_patch(plt.Circle((trace[0].x, trace[0].y), 0.2, color=colour))\n",
+ "\n",
" for s, t in chunks(trace, 2):\n",
" w, h = plot_wh[t.dir]\n",
" 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",
" plt.savefig(filename)"
]
},
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "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",
+ "text/plain": [
+ "<matplotlib.figure.Figure at 0x7fc9c2dffcc0>"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "plot_trace(trace_tour(sample_tours[0]))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 18,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "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",
+ "text/plain": [
+ "<matplotlib.figure.Figure at 0x7fc9c2dc5cf8>"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "plot_trace(trace_tour(sample_tours[1]))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "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",
+ "text/plain": [
+ "<matplotlib.figure.Figure at 0x7fc9c2ceb748>"
+ ]
+ },
+ "metadata": {},
+ "output_type": "display_data"
+ }
+ ],
+ "source": [
+ "plot_trace(trace_tour(sample_tours[2]))"
+ ]
+ },
{
"cell_type": "markdown",
"metadata": {},
},
{
"cell_type": "code",
- "execution_count": 18,
+ "execution_count": 20,
"metadata": {},
"outputs": [
{
"226"
]
},
- "execution_count": 18,
+ "execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 19,
+ "execution_count": 21,
"metadata": {},
"outputs": [
{
"61762"
]
},
- "execution_count": 19,
+ "execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 31,
+ "execution_count": 22,
"metadata": {},
"outputs": [
{
"100"
]
},
- "execution_count": 31,
+ "execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 20,
+ "execution_count": 23,
"metadata": {},
"outputs": [
{
"123845"
]
},
- "execution_count": 20,
+ "execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 21,
+ "execution_count": 24,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 211 ms per loop\n"
+ "10 loops, best of 3: 192 ms per loop\n"
]
}
],
},
{
"cell_type": "code",
- "execution_count": 23,
+ "execution_count": 25,
"metadata": {},
- "outputs": [],
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "80622"
+ ]
+ },
+ "execution_count": 25,
+ "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": 26,
"metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 1min 30s 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": 27,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# [(i, j) \n",
},
{
"cell_type": "code",
- "execution_count": null,
- "metadata": {},
+ "execution_count": 28,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# (sum(len(t) for t in tours if valid(trace_tour(t)))\n",
},
{
"cell_type": "code",
- "execution_count": 24,
+ "execution_count": 57,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def valid_part(trace):\n",
+ " return ((trace[-1].x != 0 \n",
+ " or trace[-1].y != 0)\n",
+ " and len(set(positions(trace))) == len(trace))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 62,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "5 1\n",
+ "6 1\n",
+ "8 1\n",
+ "11 1\n",
+ "19 1\n"
+ ]
+ }
+ ],
+ "source": [
+ "l1s = {}\n",
+ "for t in tours:\n",
+ " tr = trace_tour(t)\n",
+ " if valid_part(tr):\n",
+ " l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
+ " if l1 not in l1s:\n",
+ " l1s[l1] = []\n",
+ " l1s[l1] += [t]\n",
+ "\n",
+ "for l1 in l1s:\n",
+ " if l1 < 20:\n",
+ " print(l1, len(l1s[l1])) "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 59,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "13"
+ ]
+ },
+ "execution_count": 59,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "good_is = []\n",
+ "goods = []\n",
+ "for l1 in l1s:\n",
+ " possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
+ " candidates = [t for i in possible_l1s for t in l1s[i]]\n",
+ " for t1 in l1s[l1]:\n",
+ " for t2 in candidates:\n",
+ " if t1 != t2:\n",
+ " t12 = t1 + t2 \n",
+ " if valid(trace_tour(t12)):\n",
+ " good_is += [(tours.index(t1), tours.index(t2))]\n",
+ " goods += [t12] \n",
+ "len(goods) "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 60,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "80622"
+ ]
+ },
+ "execution_count": 60,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
+ " +\n",
+ " sum(len(t12) for t12 in goods)\n",
+ ")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 64,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 517 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "\n",
+ "l1s = {}\n",
+ "for t in tours:\n",
+ " tr = trace_tour(t)\n",
+ " if valid_part(tr):\n",
+ " l1 = abs(tr[-1].x) + abs(tr[-1].y)\n",
+ " if l1 > 0:\n",
+ " if l1 not in l1s:\n",
+ " l1s[l1] = []\n",
+ " l1s[l1] += [t]\n",
+ "\n",
+ "good_is = []\n",
+ "goods = []\n",
+ "for l1 in l1s:\n",
+ " possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
+ " candidates = [t for i in possible_l1s for t in l1s[i]]\n",
+ " for t1 in l1s[l1]:\n",
+ " for t2 in candidates:\n",
+ " if t1 != t2:\n",
+ " t12 = t1 + t2 \n",
+ " if valid(trace_tour(t12)):\n",
+ " good_is += [(tours.index(t1), tours.index(t2))]\n",
+ " goods += [t12] \n",
+ " \n",
+ "(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
+ " +\n",
+ " sum(len(t12) for t12 in goods)\n",
+ ")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 67,
"metadata": {},
"outputs": [
{
},
{
"cell_type": "code",
- "execution_count": 25,
+ "execution_count": 66,
"metadata": {},
"outputs": [
{
" (19, 1)]"
]
},
- "execution_count": 25,
+ "execution_count": 66,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 27,
- "metadata": {},
+ "execution_count": 31,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"# %%timeit\n",
},
{
"cell_type": "code",
- "execution_count": 28,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
+ "execution_count": 63,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "13"
+ ]
+ },
+ "execution_count": 63,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
"source": [
"good_is = []\n",
"goods = []\n",
- "tried = []\n",
"for l1 in l1s:\n",
" possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
" candidates = [t for i in possible_l1s for t in l1s[i]]\n",
- " for t1 in candidates:\n",
+ " for t1 in l1s[l1]:\n",
" for t2 in candidates:\n",
" if t1 != t2:\n",
- " t12 = t1 + t2\n",
- " if (t12) not in tried:\n",
- " tried += [(t12)]\n",
- " if valid(trace_tour(t12)):\n",
- " good_is += [(tours.index(t1), tours.index(t2))]\n",
- " goods += [t12]"
+ " t12 = t1 + t2 \n",
+ " if valid(trace_tour(t12)):\n",
+ " good_is += [(tours.index(t1), tours.index(t2))]\n",
+ " goods += [t12]\n",
+ "len(goods)"
]
},
{
"cell_type": "code",
- "execution_count": 29,
+ "execution_count": 42,
"metadata": {},
"outputs": [
{
"80622"
]
},
- "execution_count": 29,
+ "execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 32,
+ "execution_count": 50,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 1.27 s per loop\n"
+ "1 loop, best of 3: 998 ms per loop\n"
]
}
],
" l1s[l1] = []\n",
" l1s[l1] += [t]\n",
"\n",
+ "good_is = []\n",
"goods = []\n",
- "tried = []\n",
"for l1 in l1s:\n",
" possible_l1s = [i for i in range(l1-1, l1+1) if i in l1s]\n",
" candidates = [t for i in possible_l1s for t in l1s[i]]\n",
- " for t1 in candidates:\n",
+ " for t1 in l1s[l1]:\n",
" for t2 in candidates:\n",
" if t1 != t2:\n",
- " t12 = t1 + t2\n",
- " if (t12) not in tried:\n",
- " tried += [(t12)]\n",
- " if valid(trace_tour(t12)):\n",
- " goods += [t12]\n",
- "\n",
+ " t12 = t1 + t2 \n",
+ " if valid(trace_tour(t12)):\n",
+ " good_is += [(tours.index(t1), tours.index(t2))]\n",
+ " goods += [t12] \n",
+ " \n",
"(sum(len(t) for t in tours if valid(trace_tour(t)))\n",
" +\n",
" sum(len(t12) for t12 in goods)\n",
},
{
"cell_type": "code",
- "execution_count": 33,
+ "execution_count": 47,
"metadata": {},
"outputs": [
{
"13"
]
},
- "execution_count": 33,
+ "execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 37,
+ "execution_count": 56,
"metadata": {},
"outputs": [
{
" (212, 113)]"
]
},
- "execution_count": 37,
+ "execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 38,
+ "execution_count": 55,
"metadata": {},
"outputs": [
{
" (208, 204)]"
]
},
- "execution_count": 38,
+ "execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
"sorted(good_is, key=lambda p: p[1])"
]
},
+ {
+ "cell_type": "code",
+ "execution_count": 54,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[(66, 2),\n",
+ " (68, 1),\n",
+ " (5, 1),\n",
+ " (6, 1),\n",
+ " (8, 1),\n",
+ " (74, 1),\n",
+ " (11, 1),\n",
+ " (76, 2),\n",
+ " (34, 2),\n",
+ " (81, 1),\n",
+ " (19, 1),\n",
+ " (21, 1),\n",
+ " (88, 1),\n",
+ " (132, 2),\n",
+ " (26, 2),\n",
+ " (28, 1),\n",
+ " (94, 1),\n",
+ " (37, 2),\n",
+ " (98, 1),\n",
+ " (36, 1),\n",
+ " (101, 2),\n",
+ " (166, 2),\n",
+ " (40, 2),\n",
+ " (41, 2),\n",
+ " (106, 1),\n",
+ " (107, 1),\n",
+ " (44, 2),\n",
+ " (48, 1),\n",
+ " (114, 2),\n",
+ " (117, 2),\n",
+ " (56, 2),\n",
+ " (57, 3),\n",
+ " (58, 1),\n",
+ " (59, 2),\n",
+ " (70, 1),\n",
+ " (127, 1)]"
+ ]
+ },
+ "execution_count": 54,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "[(l, len(l1s[l])) for l in l1s.keys()]"
+ ]
+ },
{
"cell_type": "code",
"execution_count": null,
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
- "version": "3.5.2+"
+ "version": "3.5.3"
}
},
"nbformat": 4,