If you use Google Maps¹ to look up a route between two points $$p_0$$ and $$p_n$$, the itinerary is given as a sequence of intermediate points \[p_0, p_1, p_2, \ldots, p_n\] If we write the distance between two consecutive points $$p_i$$ and $$p_{i+1}$$ as $$d(p_i, p_{i+1})$$, the total distance of the route equals \[\sum_{i=0}^{n - 1} d(p_i, p_{i+1})\] If the route ends back in its starting point, we finally also have to add the distance $$d(p_n, p_0)$$.

In this assignment, we represent the coordinates of a point $$p$$ as a tuple $$(x, y)$$. Based on this representation, the distance between two points $$p_a = (x_a, y_a)$$ and $$p_b = (x_b, y_b)$$ can be defined in different ways. The most intuitive distance is the Euclidean distance, that corresponds with the distance as the crow flies. In practice, however, this distance isn't always as useful.

The Manhattan-distance is an alternative distance that gets its name from the typical street pattern of Manhattan². There, all streets are either perpendicular or parallel to each other. The Manhattan-distance is given as the sum of the absolute difference of the $$x$$-coordinates and the absolute difference of the $$y$$-coordinates. This is equal to the road you would take from one point to another if you were only allowed to walk parallel with the $$x$$-axis and the $$y$$-axis.

The Chebyshev distance or chessboard distance gets its name from the fact that it corresponds with the amount of moves the chess piece king needs to cross a discrete grid. This distance is given by the maximum of the absolute difference of the $$x$$-coordinates and the absolute difference of the $$y$$-coordinates.

The table below gives an overview of the different formulas for the distance between two points $$(x_a, y_a)$$ en $$(x_b, y_b)$$ as defined by the distance measures above.

Preparation

In Python, functions are themselves objects, so that they can be used just like any other object. In particular, you can assign functions to variables or pass them as arguments to other functions. Take a look at the following three functions definitions.

def repeat(value, function, iterations):
    for i in range(iterations):
        value = function(value)
    return value

def increment(value):
    return value + 1

def decrement(value):
    return value - 1

Below you find an example of how these functions can be used. Verify how Python responds if you execute these instructions in succession in an interactive Python session in which you first define the above functions. Make sure you understand why you obtain a certain value and what happens exactly in the interactive session before moving on to the actual assignment.

>>> increment(5)
>>> decrement(101)
>>> repeat(5, increment, 3)
>>> repeat(5, decrement, 3)
>>> repeat(5, decrement, increment(3))

Assignment

We represent a point as a tuple containing two real valued numbers (float) that respectively indicate the $$x$$ and $$y$$ coordinates of a point in a plane. Your task:

• Write three functions euclidean, manhattan and chessboard that correspond with the distance concepts having the same name in the table above. Each of these functions takes two points (tuple), and must return the distance (float) between the given points according to the corresponding distance formula.

• Write a function route. This function has a mandatory parameter points that takes a list of points. The function must return the total distance (float) traveled if each of the points in the given list is visited in turn. Apart from the mandatory parameter, the function also has two optional parameters:

  • cycle: takes a Boolean value (bool) that indicates whether the end of the route is equal to its starting point (True) or not (False); the default value of this parameter is False

  • distance: takes a distance function (function) that is used to calculate the distance between two consecutive points in the given route; if no explicit value is passed to this parameter, the Euclidean distance must be used

Example

>>> euclidean((42.36, 56.78), (125.65, 236.47))
198.05484139500354
>>> manhattan((42.36, 56.78), (125.65, 236.47))
262.98
>>> chessboard((42.36, 56.78), (125.65, 236.47))
179.69

>>> route([(6.59, 6.73), (4.59, 5.54), (5.33, -13.98)])
21.861273201261746
>>> route(cycle=True, points=[(6.59, 6.73), (4.59, 5.54), (5.33, -13.98)])
42.60956710702662
>>> route([(6.59, 6.73), (4.59, 5.54), (5.33, -13.98)], distance=manhattan)
23.45
>>> route([(6.59, 6.73), (4.59, 5.54), (5.33, -13.98)], cycle=True, distance=manhattan)
45.42