+ {
+ "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|)$."
+ ]
+ },
projects / ou-summer-of-code-2017.git / commitdiff