Als je Google Maps¹ gebruikt om een route tussen twee punten $$p_0$$ en $$p_n$$ op te zoeken, dan wordt de routebeschrijving gegeven als een reeks van tussenpunten \[p_0, p_1, p_2, \ldots, p_n\] Als we de afstand tussen twee opeenvolgende punten $$p_i$$ en $$p_{i+1}$$ noteren als $$d(p_i, p_{i+1})$$, dan is de totale afstand van de route gelijk aan \[\sum_{i=0}^{n - 1} d(p_i, p_{i+1})\] Als de route terug eindigt op zijn beginpunt, dan moeten we hier finaal nog de afstand $$d(p_n, p_0)$$ bij optellen.

In deze opgave stellen we de coördinaten van een punt $$p$$ voor als een tuple $$(x, y)$$. Op basis van deze voorstelling kan de afstand tussen twee punten $$p_a = (x_a, y_a)$$ en $$p_b = (x_b, y_b)$$ op verschillende manieren gedefinieerd worden. De meest inituitieve afstand is de Euclidische afstand, die overeenkomt met de afstand in vogelvlucht. In de praktijk is deze afstand echter niet altijd even bruikbaar.

De Manhattan-afstand is een alternatieve afstand die zijn naam dankt aan het typische stratenpatroon van Manhattan². Daar staan alle straten ofwel loodrecht op elkaar of lopen ze evenwijdig met elkaar. In dat geval wordt de afstand gegeven als de som van het verschil van de $$x$$-coördinaten en het verschil van de $$y$$-coördinaten. Dit komt overeen met de weg die je zou afleggen om van het ene punt naar het andere punt te gaan als je enkel evenwijdig met de $$x$$-as en de $$y$$-as zou mogen wandelen.

De Chebyshev-afstand of de schaakbordafstand dankt zijn naam aan het feit dat ze op een discreet rooster overeenkomt met het aantal zetten die het schaakstuk koning nodig heeft om van het ene punt naar het andere punt te gaan. Dit aantal wordt gegeven door het maximum van het verschil van de $$x$$-coördinaten en het verschil van de $$y$$-coördinaten.

In onderstaande tabel vind je een overzicht van de verschillende formules voor de afstand tussen twee punten $$(x_a, y_a)$$ en $$(x_b, y_b)$$ zoals die wordt gedefinieerd door bovenvernoemde afstandsmaten.

naam	formule
Euclidische afstand	$$\sqrt{(x_a-x_b)^2 + (y_a-y_b)^2}$$
Manhattan-afstand	$$\|x_a-x_b\| + \|y_a-y_b\|$$
schaakbordafstand	$$\max(\|x_a-x_b\|,\|y_a-y_b\|)$$

Voorbereiding

In Python zijn functies zelf ook objecten, waardoor je ze kunt gebruiken zoals alle andere objecten. In het bijzonder kun je functies toekennen aan variabelen of doorgeven als argument aan andere functies. Bekijk bijvoorbeeld onderstaande drie functies.

def herhalen(waarde, functie, aantal):
    for i in range(aantal):
        waarde = functie(waarde)
    return waarde

def verhogen(waarde):
    return waarde + 1

def verlagen(waarde):
    return waarde - 1

Hieronder staat een voorbeeld van hoe deze functies gebruikt kunnen worden. Ga na hoe Python reageert als je achtereenvolgens de volgende instructies uitvoert binnen een interactieve Python sessie waarin je eerst zorgt dat bovenstaande functies gedefinieerd werden. Verzeker jezelf ervan dat je goed begrijpt waarom je een bepaalde waarde krijgt en wat er juist gebeurt in de interactieve sessie vooraleer je verder gaat met de eigenlijke opgave.

>>> verhogen(5)
>>> verlagen(101)
>>> herhalen(5, verhogen, 3)
>>> herhalen(5, verlagen, 3)
>>> herhalen(5, verlagen, verhogen(3))

Opgave

We stellen een punt voor als een tuple van twee reële getallen (float) die de $$x$$- en de $$y$$-coördinaat van een punt in het vlak voorstellen. Gevraagd wordt:

Schrijf drie functies euclidisch, manhattan en schaakbord die corresponderen met de gelijknamige concepten voor het begrip afstand zoals die in bovenstaande tabel gedefinieerd werden. Aan elk van deze functies moeten twee punten doorgegeven worden. De functies moeten als resultaat telkens de afstand (float) tussen de twee gegeven punten teruggeven, overeenkomstig de corresponderende afstandsformule.
Schrijf een functie parcours. Deze functie heeft een verplichte parameter punten waaraan een lijst (list) van punten moet doorgegeven worden. De functie moet de totale afstand (float) teruggeven die afgelegd wordt als men achtereenvolgens alle punten uit de lijst aandoet. Naast deze verplichte parameter, heeft de functie ook nog twee optionele parameters:
- cycle: aan deze parameter kan een Booleaanse waarde (bool) doorgegeven worden die aangeeft of men op het einde van de rit terugreist naar het beginpunt (True) of niet (False); de standaardwaarde van deze parameter is False
- afstand: aan deze parameter kan een afstandsfunctie (function) doorgegeven worden, die bij de berekening van de totale afstand gebruikt wordt om de afstand tussen twee opeenvolgende punten te bepalen; als geen waarde wordt doorgegeven aan deze parameter, dan wordt standaard de Euclidische afstand gebruikt

Voorbeeld

>>> euclidisch((42.36, 56.78), (125.65, 236.47))
198.05484139500354
>>> manhattan((42.36, 56.78), (125.65, 236.47))
262.98
>>> schaakbord((42.36, 56.78), (125.65, 236.47))
179.69

>>> parcours([(6.59, 6.73), (4.59, 5.54), (5.33, -13.98)])
21.861273201261746
>>> parcours(cycle=True, punten=[(6.59, 6.73), (4.59, 5.54), (5.33, -13.98)])
42.60956710702662
>>> parcours([(6.59, 6.73), (4.59, 5.54), (5.33, -13.98)], afstand=manhattan)
23.45
>>> parcours([(6.59, 6.73), (4.59, 5.54), (5.33, -13.98)], cycle=True, afstand=manhattan)
45.42