De grote honingspeurder (Indicator indicator¹) uit Afrika is verzot op bijenwas. Hij is echter niet altijd in staat om op zijn eentje een bijenkorf binnen te dringen. Daarom heeft hij een uniek samenwerkingsverband gesmeed met de mens. De vogel trekt de aandacht van lokale honingjagers met zijn ratelend geroep, vliegt in de richting van een bijenkorf, houdt regelmatig halt en roept dan opnieuw. Wanneer ze de bijenkorf bereiken, breekt de jager die open, bedwelmt de bijen met rook, neemt de honing eruit en laat de was over voor de vogel.

Deze samenwerking bespaart de mens gemiddeld 5,7 uur van de tijd om bijenkorven te zoeken, maar ze is niet onfeilbaar. "De grote honingspeurder heeft ons al naar de rand van een afgerond gebracht en tot bij een mannetjesolifant", rapporteren de biologen Lester Kort en Jennifer Horne. "In die gevallen waren er bijenkorven onderaan de klif (in een vallei) en achter de olifant. Zorg voor het welzijn van de begeleide personen behoort nu eenmaal niet tot het woordenboek van de honingspeurder."

Opgave

Een groep biologen is in de Keniaanse savanne bijenkorven in kaart aan het brengen. Hierbij laten ze zich leiden door de lokroep van de grote honingspeurder. Als ze zich tot bij een bijenkorf hebben laten leiden, dan duiden ze de locatie van de korf aan op een rechthoekige kaart. De kaart is onderverdeeld in vierkante gebieden. Zoals aangegeven in onderstaand voorbeeld zijn de rijen van de kaart van boven naar onder gelabeld met de hoofdletters A, B, …, en de kolommen van links naar rechts met de getallen 1, 2, 3, …. De vierkante gebieden zijn gelabeld met kleine letters die de soorten vegetatie aanduiden als herkenningspunten in de savanne.

Als de biologen met hulp van de honingspeurder een bijenkorf gevonden hebben, dan hebben ze geen enkel idee van de positie op de kaart waar ze vertrokken zijn. Gelukkig hebben ze een goed gevoel voor oriëntatie en kunnen ze de route die ze hebben afgelegd reconstrueren als een reeks opeenvolgende waarnemingen en bewegingen.

Een routebeschrijving kan omschreven worden als een string (str) waarin waarnemingen worden aangeduid met kleine letters die het soort vegetatie omschrijven en bewegingen met hoofdletters die de richting aangeven: L voor links, R voor rechts, O voor op en N voor neer. In een routebeschrijving wisselen waarnemingen en bewegingen elkaar steeds af, en de beschrijving begint en eindigt altijd met een waarneming. Indien het uitvoeren van een beweging zou leiden naar een vierkant buiten de kaart, dan wordt de beweging niet uitgevoerd en blijft men gewoon staan.

Je opdracht bestaat erin om voor een gegeven routebeschrijving alle mogelijke posities op de kaart te vinden waar de route kan eindigen. Deze geven de mogelijke posities van de bijenkorven aan. Stel dat we in bovenstaande kaart alle posities moeten vinden waar men kan eindigen als men de route bLaLa volgt. De mogelijke eindposities en de bijhorende routes worden aangegeven in onderstaande figuur.

In kolommen 2 en 5 staat er telkens een kleine letter b, en daar kan de route dus starten. Als we vanaf deze startposities naar links bewegen, dan komen we telkens op een vierkant terecht dat gelabeld is met de kleine letter a. We kunnen dus in alle gevallen de route verder blijven volgen. Als we nu opnieuw naar links bewegen, dan eindigen de routes die vertrokken zijn van kolom 5 op een vierkant in kolom 3. Daar staat telkens een kleine letter a, waardoor we de route volledig hebben kunnen volgen. De vierkanten in kolom 3 zijn daardoor mogelijke eindposities. De routes die vertrokken zijn vanaf kolom 2 eindigen na één beweging in kolom 1. Als we van daaruit terug naar links zouden bewegen, dan vallen we van de kaart. We blijven dus staan, maar eindigen zo terug op een vierkant met de kleine letter a. Ook in die gevallen hebben we dus de route volledig kunnen volgen, en zijn de vierkanten in kolom 1 mogelijke eindposities. 

De positie van een vierkant op de kaart wordt door de biologen aangeduid met een label (een string) dat bestaat uit het rijlabel gevolgd door het kolomlabel. In Python is het echter gebruikelijk om rijen en kolommen te indexeren met natuurlijke getallen. Hierbij worden de rijen genummerd van boven naar onder en de kolommen van links naar rechts, telkens vanaf nul. Schrijf daarom eerst de volgende twee functies:

• Een functie coord2label die voor een gegeven rij- en kolomindex (int; twee afzonderlijke argumenten) het corresponderende label (str) teruggeeft.

• Een functie label2coord die voor een gegeven label (str) de corresponderende rij- (int) en kolomindex (int) teruggeeft als een tuple.

Je mag er hierbij van uitgaan dat het aantal rijen op de kaart nooit groter wordt dan 26. Gebruik nu de voorgaande functies bij de implementatie van de volgende functies.

• Schrijf een functie waarneming waaraan drie argumenten moeten doorgegeven worden: i) het aantal rijen (int) van een rechthoekige kaart, ii) een string (str) van kleine letters die de labels van de vierkanten op de kaart aangeven, als we de vierkanten doorlopen van links naar rechts en van boven naar onder, en iii) het label (str) van een vierkant op de kaart. De functie moet de kleine letter (str) teruggeven die op het vierkant van de kaart staat dat door het label wordt aangeduid.

• Gebruik de functie waarneming om een functie eindpunt te schrijven waaraan vier argumenten moeten doorgegeven worden. De eerste drie argumenten zijn dezelfde als bij de functie waarneming. Het vierde argument is een string (str) die een routebeschrijving bevat. Het label geeft een startpunt aan op de kaart. De functie moet het label (str) van het eindpunt op de kaart aangeven dat bereikt wordt als men de gegeven route volledig volgt. Als het niet mogelijk is om vanaf het gegeven startpunt de gegeven route volledig te volgen, dan moet de functie de waarde None teruggeven.

• Gebruik de functie eindpunt om een functie bijenkorven te schrijven waaraan drie argumenten moeten doorgegeven worden. De eerste twee argumenten zijn dezelfde als bij de functies waarneming en eindpunt. Het derde argument is een string (str) die een routebeschrijving bevat. De functie moet een lijst (list) teruggeven met de labels (str) van alle mogelijke eindposities die men kan bereiken als de gegeven route gevolgd wordt. Hetzelfde label mag hoogstens één keer in deze lijst voorkomen, en de labels moeten in lexicografische volgorde opgelijst worden.

Voorbeeld

>>> coord2label(0, 0)
'A1'
>>> coord2label(1, 5)
'B6'
>>> coord2label(7, 4)
'H5'

>>> label2coord('A1')
(0, 0)
>>> label2coord('B6')
(1, 5)
>>> label2coord('H5')
(7, 4)

>>> waarneming(2, 'abaabcabaabc', 'A1')
'a'
>>> waarneming(2, 'abaabcabaabc', 'B6')
'c'

>>> eindpunt(2, 'abaabcabaabc', 'A5', 'bLaLa')
'A3'
>>> eindpunt(2, 'abcdeecdea', 'B4', 'eLdLcOb')
'A2'
>>> eindpunt(2, 'abcdeecdea', 'A3', 'cRdOcLbLaNa')

>>> bijenkorven(2, 'abaabcabaabc', 'bLaLa')
['A1', 'A3', 'B1', 'B3']
>>> bijenkorven(2, 'abcdeecdea', 'eLdLcOb')
['A2']
>>> bijenkorven(2, 'abcdeecdea', 'cRdOcLbLaNa')
[]

We merken hierbij op dat de mogelijke routes die leiden naar de vier mogelijke eindpunten van het eerste voorbeeld van de functie bijenkorven grafisch worden weergegeven in de tekst hierboven.

Voor het tweede voorbeeld geven we hieronder een weergave van de rechthoekige kaart met de rij- en kolomlabels zoals ze door de biologen gebruikt worden. De labels van de vierkanten die tot een mogelijke route behoren hebben we weergegeven in het zwart, de labels die niet tot een route behoren in het grijs. De labels die een startpunt vormen van een mogelijke route staan in het blauw, de labels die een eindpunt vormen in het geel, en de labels die zowel startpunt als eindpunt zijn, staan in het groen. Deze voorstelling wordt ook gebruikt als feedback voor de testgevallen die een verkeerd antwoord geven voor de functie bijenkorven.

  12345

A abcde
B ecdea