In een bepaalde regio liggen er heel wat ziekenhuizen dicht bij elkaar. De concurrentie tussen deze ziekenhuizen is moordend, en dat valt letterlijk te nemen. Bij noodoproepen worden patiënten door een ziekenwagen immers niet altijd naar het dichtsbijzijnde ziekhuis gebracht. Hierdoor gaat kostbare tijd verloren, soms met dodelijke gevolgen. De plaatselijke overheid wil hier paal en perk aan stellen, en vaardigt een nieuwe regelgeving uit die ziekenwagens verplicht om hun patiënten altijd naar het dichtsbijzijnde ziekhuis te brengen. Hiervoor moet een plan opgesteld worden dat de regio opdeelt in zones waarin telkens één ziekenhuis gelegen is.

Zoneplan dat werd opgesteld voor 20 ziekenhuizen (gelegen op locaties aangeduid met een zwart punt), waarbij afstanden berekend werden op basis van de Euclidische afstand.

Zoneplan dat werd opgesteld voor 20 ziekenhuizen (gelegen op locaties aangeduid met een zwart punt), waarbij afstanden berekend werden op basis van de Manhattan-afstand.

De overheid vraagt je om een indeling van een regio te maken, zodat het dichtste ziekenhuis op elk punt in een zone telkens het enige ziekenhuis is dat in die zone gelegen is. De individuele ziekenhuizen willen echter hun invloedssfeer zo groot mogelijk houden, en daarom is er nog wat discussie over de manier waarop de afstand tussen twee punten moet berekend worden. Onderstaande tabel bevat een aantal mogelijke definities die de ziekenhuizen hebben voorgesteld om de afstand tussen twee punten $$(x_1, y_1)$$ en $$(x_2, y_2)$$ te berekenen.

naam	formule
Euclidische afstand	$$d=\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$$
Manhattan-afstand	$$d=\|x_1-x_2\| + \|y_1-y_2\|$$
schaakbord-afstand	$$d=\max(\|x_1-x_2\|,\|y_1-y_2\|)$$

Opgave

Beschouw een rechthoekige regio waarin een aantal ziekenhuizen gelegen zijn. We hebben deze regio opgedeeld in vierkante cellen die een rooster vormen, zodat elke cel hoogstens één ziekenhuis bevat. De rijen en kolommen van het rooster worden respectievelijk van boven naar onder en van links naar rechts genummerd vanaf 0. De cellen van het rooster waarin een ziekenhuis gelegen is, markeren we met een (unieke) hoofdletter en de overige cellen markeren we met een punt. Daardoor kan de ligging van de ziekenhuizen in de regio voorgesteld worden door een kaart die de volgende vorm heeft:

......B..
.........
...A.....
.........
.......D.
.........
.C.......
.....E...
.........

De positie van een cel in het rooster wordt voorgesteld door een tuple $$(r, k)$$. Hierbij stelt $$r$$ het rijnummer en $$k$$ het kolomnummer voor van de cel in het rooster. Gevraagd wordt:

Schrijf drie functies euclidischeAfstand, manhattanAfstand en schaakbordAfstand die corresponderen met de gelijknamige concepten voor het begrip afstand zoals die in bovenstaande tabel gedefinieerd werden. Aan elk van deze functies moeten verplicht twee argumenten doorgegeven worden. Elk argument is een tuple van 2 reële getallen die de $$x$$- en de $$y$$-coördinaat van een punt in het vlak voorstellen. Als resultaat geven deze functies telkens de afstand tussen de twee gegeven punten terug als een reëel getal, overeenkomstig de corresponderende definitie van afstand.
Schrijf een functie posities waaraan de naam van een tekstbestand moet doorgegeven worden. Dit tekstbestand moet de ligging van de ziekenhuizen in een bepaalde regio voorgestellen, volgens het formaat dat hierboven werd beschreven. De functie moet een tuple met drie elementen teruggeven, waarvan de eerste twee respectievelijk het aantal rijen en het aantal kolommen van het rechthoekige rooster aangeven waarin de regio werd opgedeeld. Het derde element is een dictionary, die de positie van elk ziekenhuis in de regio afbeeldt op de hoofdletter waarmee het ziekenhuis in het rooster gemarkeerd werd. De positie van een ziekenhuis komt hierbij overeen met de positie van de cel in het rooster waarin het ziekenhuis gelegen is.
Schrijf een functie dichtste waarmee het dichtste ziekenhuis kan bepaald worden vanaf een gegeven punt. Aan deze functie moeten twee argumenten doorgegeven worden: de positie van de cel waarin het gegeven punt gelegen is en een dictionary die de posities van de ziekenhuizen in de regio bevat. Deze dictionary moet dezelfde vorm hebben als de dictionaries die door de functie posities wordt teruggegeven (als derde element van het tuple). Om de afstand tussen het gegeven punt en een ziekenhuis te bepalen, moet een afstandsfunctie gebruikt worden waaraan twee celposities in het rooster moeten doorgegeven worden en die een reëel getal teruggeeft dat de afstand tussen deze twee cellen voorstelt. Standaard moet hiervoor de functie euclidischeAfstand gebruikt worden, maar de functie dichtste heeft ook nog een derde optionele parameter afstand waaraan een alternatieve afstandsfunctie kan doorgegeven worden. De functie moet de hoofdletter teruggeven waarmee het ziekenhuis gemarkeerd is dat dichtst bij het gegeven punt gelegen is. Indien het gegeven punt op gelijke dichtste afstand ligt van twee of meer ziekenhuizen, dan moet de alfabetisch eerst gerangschikte hoofdletter teruggegeven worden waarmee deze ziekenhuizen gemarkeerd zijn.
Schrijf een functie zones waaraan de naam van een tekstbestand moet doorgegeven worden. Dit tekstbestand moet de ligging van de ziekenhuizen in een bepaalde regio voorgestellen, volgens het formaat dat hierboven werd beschreven. Voor elke cel in het rooster die gemarkeerd wordt door een punt, moet de functie de hoofdletter bepalen van het dichtstbijzijnde ziekenhuis (cf. functie dichtste) en de corresponderende kleine letter invullen in plaats van het punt. Standaard moet het resultaat door de functie uitgeschreven worden. Als aan de functie echter ook nog een tweede bestandsnaam doorgegeven wordt, dan moet de functie het resultaat wegschrijven naar een bestand met de opgegeven naam. De functie heeft ook nog een derde optionele parameter afstand, die op dezelfde manier gebruikt wordt als de gelijknamige parameter van de functie dichtste.

Voorbeeld

Bij onderstaande voorbeeldsessie gaan we ervan uit dat het bestand ziekenhuizen.txt¹ zich in de huidige directory bevindt.

>>> euclidischeAfstand((0, 0), (3, 4))
5.0
>>> manhattanAfstand((0, 0), (3, 4))
7.0
>>> schaakbordAfstand((0, 0), (3, 4))
4.0

>>> posities('ziekenhuizen.txt')
(9, 9, {(0, 6): 'B', (4, 7): 'D', (7, 5): 'E', (2, 3): 'A', (6, 1): 'C'})

>>> dichtste((0, 0), {(0, 6): 'B', (4, 7): 'D', (7, 5): 'E', (2, 3): 'A', (6, 1): 'C'})
'A'
>>> dichtste((8, 8), {(0, 6): 'B', (4, 7): 'D', (7, 5): 'E', (2, 3): 'A', (6, 1): 'C'}, afstand=manhattanAfstand)
'E'

>>> zones('ziekenhuizen.txt')
aaaabbBbb
aaaaabbbb
aaaAaabdd
aaaaaaddd
ccaaaddDd
cccceeddd
cCcceeedd
ccceeEeee
ccceeeeee
>>> zones('ziekenhuizen.txt', afstand=manhattanAfstand)
aaaabbBbb
aaaaabbbb
aaaAaabdd
aaaaaaddd
ccaaaddDd
cccaeeddd
cCcceeedd
ccceeEeee
ccceeeeee
>>> zones('ziekenhuizen.txt', afstand=schaakbordAfstand)
aaaaabBbb
aaaaabbbb
aaaAaabbb
aaaaaaddd
caaaaadDd
ccccedddd
cCcceeedd
cccceEeed
cccceeeee
>>> zones('ziekenhuizen.txt', 'zones.txt')