Het schiereiland Manhattan vormt
één van de vijf stadsdelen van New York. Dit stadsdeel staat
bekend om zijn wolkenkrabbers, brede avenues, het financiële centrum
Wall Street en de vele, gele taxi's die er rondrijden. De straten van
Manhattan zijn ingedeeld volgens het rechthoekige Commissioners' Plan
van 1811. Het gebied wordt doorsneden door avenues (noord-zuid)
en streets (oost-west).
Manhattan Commissioner's Plan
Veronderstel een gegeven rechthoekig rooster dat een deelgebied van Manhattan met streets en
avenues voorstelt. Op verschillende kruispunten zijn pompstations te
vinden waar taxi's kunnen tanken. Wanneer een taxi zonder benzine dreigt
te vallen, kan de chauffeur op zijn GPS de coördinaten van het
dichtsbijzijnde pompstation aflezen. Er is echter een bug in de
software van de GPS geslopen. Als er vanaf een kruispunt meerdere
"dichtste" pompstations zijn, dan raakt de GPS het noorden kwijt, waardoor
de chauffeur in paniek slaat en een aanrijding veroorzaakt. Dergelijke
kruispunten worden daarom ook dode punten genoemd.
Opgave
In Manhattan wordt een kruispunt (verder
kortweg punt genoemd) op een rechthoekig rooster steeds
voorgesteld als een tuple , waarbij , en . Het punt in de linkerbovenhoek van het
rooster is dus het punt , en het punt in de rechteronderhoek is
het punt . Dit is ook de voorstelling van punten zoals die in
deze opgave gebruikt worden.
In Manhattan wordt de afstand tussen twee kruispunten en
berekend als waarbij
de absolute waarde van voorstelt. Deze afstand wordt immers niet
voor niets de Manhattan-afstand (of city block distance)
genoemd. Schrijf een functie manhattanAfstand
die de Manhattan-afstand tussen twee gegeven kruispunten als resultaat teruggeeft. De coördinaten van
de twee punten moeten als argument aan de functie doorgegeven worden.
Gebruik de functie manhattanAfstand
om een functie doodpunt te
schrijven die een Booleaanse waarde teruggeeft
die aangeeft of een gegeven kruispunt een dood punt is of niet. Aan deze
functie moeten twee argumenten doorgegeven worden: de coördinaten
van het kruispunt waarvoor moet bepaald worden of het al dan niet een
dood punt is, en een lijst van punten die de locaties van de
pompstations op het rooster aangeven.
Schrijf een functie manhattan
waaraan drie argumenten moeten doorgegeven worden: het aantal streets
, het aantal avenues , en een lijst van punten die de locaties van
de pompstations op het rooster aangeven. De functie moet
een voorstelling van het rechthoekig rooster uitschrijven,
waarbij kruispunten worden aangeduid met een sterretje (*).
Kruispunten waarop een pompstation gelegen is moeten echter voorgesteld
worden met de letter P, en
kruispunten die dode punten zijn moeten
voorgesteld worden met de letter D.
Voorbeeld
In het voorbeeld rooster dat
in onderstaande interactieve Python sessie wordt afgebeeld is
bijvoorbeeld een dood punt, omdat de twee pompstations die op de
vierde avenue gelegen zijn allebei op afstand 4 van het punt
liggen.