Mierencommunicatie verloopt hoofdzakelijk door middel van geurstoffen, die feromonen genoemd worden. Ze worden bijvoorbeeld gebruikt om aan te geven waar er voedsel te vinden is. Zo kan een voedselverzamelaar een spoor op de grond achterlaten om andere voedselverzamelaars te informeren waar er voedsel te vinden is. Mieren die het feromonenspoor volgen, zorgen voor een versterking van het signaal, waardoor nog meer mieren het spoor blijven volgen totdat het voedsel is uitgeput. Het feromonenspoor wordt dan niet langer versterkt en vervaagt langzaam.

Behalve feromonensporen gebruiken mieren verschillende soorten informatie om de weg naar hun nest terug te vinden. Zo tellen ze bijvoorbeeld het aantal stappen dat ze hebben genomen sinds hun vertrek, hebben ze een ingebouwd kompas en slaan ze herkenningspunten op in hun geheugen. Mieren die een feromonenspoor verliezen (bijvoorbeeld omdat ze door een mens op een andere plaats worden neergezet) hebben het vaak moeilijker om hun nest terug te vinden.

Opgave

We simuleren het gedrag van een mier die op basis van een verstoord feromonenspoor de weg naar zijn nest probeert terug te vinden. De omgeving waarin de mier zich beweegt, wordt voorgesteld als een vierkant $$n \times n$$ rooster met $$n$$ rijen en $$n$$ kolommen. De mier bevindt zich initieel in de linkeronderhoek van het rooster en zijn nest bevindt zich in de rechterbovenhoek van het rooster. Elke cel van het rooster bevat een feromonenspoor dat wijst naar boven, onder, links of rechts. Bij elke simulatiestap verplaatst de mier zich naar de naburige cel die wordt aangegeven door het feromonenspoor, waarna de richting van het spoor op de cel die wordt verlaten 90° in wijzerzin gedraaid wordt. Indien de mier niet in de aangegeven richting kan bewegen omdat ze tegen de rand van het rooster aanloopt, blijft ze op haar huidige positie staan, maar wordt de richting van het spoor op de cel wel nog 90° in wijzerzin gedraaid.

De originele configuratie van een vierkant $$n \times n$$ rooster met feromonensporen wordt gegeven als een string bestaande uit $$n^2$$ karakters, die de richtingaanwijzers in het rooster voorstellen. De opeenvolgende karakters moeten van links naar rechts en van boven naar onder in het $$n \times n$$ rooster ingevuld worden. De volgende vier karakters worden gebruikt als richtingaanwijzers:

• >: het feromonenspoor leidt naar rechts

• <: het feromonenspoor leidt naar links

• ^: het feromonenspoor leidt naar boven

• v: het feromonenspoor leidt naar onder

Een positie in het rooster wordt voorgesteld als een tuple waarvan het eerste element de rij-index aangeeft en het tweede element de kolom-index aangeeft. Hierbij worden de rijen van het rooster genummerd van boven naar onder, en de kolommen van links naar rechts, waarbij de nummering telkens start vanaf nul. Gevraagd wordt:

• Schrijf een functie rooster waaraan een natuurlijk getal $$n$$ en een string moeten doorgegeven worden. De functie moet een lijst van lijsten teruggeven die een $$n \times n$$ rooster van richtingaanwijzers voorstelt, waarbij de opeenvolgende karakters van de gegeven string van links naar rechts en van boven naar onder in het $$n \times n$$ rooster moeten ingevuld worden. Indien de gegeven string niet bestaat uit $$n^2$$ karakters, dan moet de functie een AssertionError opwerpen met de boodschap ongeldige argumenten.

• Schrijf een functie tekst waaraan een $$n \times n$$ rooster van richtingaanwijzers moet doorgegeven worden, voorgesteld als een lijst van lijsten. De functie moet een string met de voorstelling van het vierkant $$n \times n$$ rooster teruggeven, waarbij alle symbolen op dezelfde rij van elkaar moeten gescheiden worden door spaties, en alle rijen op afzonderlijke regels staan.

• Schrijf een functie stap waaraan twee argumenten moeten doorgegeven worden: i) een $$n \times n$$ rooster van richtingaanwijzers voorgesteld als een lijst van lijsten, en ii) een positie in het rooster. De functie moet één enkele stap van de simulatie uitvoeren, waarbij de mier vertrekt vanop de aangegeven positie in het rooster. Hierbij moet de functie de richtingaanwijzer op de huidige positie aanpassen, en de nieuwe positie teruggeven waarop de mier zich bevindt na het uitvoeren van de simulatiestap.

• Schrijf een functie stappen waarmee een volledige simulatie wordt uitgevoerd van de bewegingen die de mier maakt vanaf zijn startpositie in de linkeronderhoek van het rooster tot aan zijn nest in de rechterbovenhoek van het rooster. Aan de functie moet de originele configuratie van het $$n \times n$$ rooster met richtingaanwijzers doorgegeven worden, voorgesteld als een lijst van lijsten. De functie moet een lijst van posities teruggeven die start met de positie in de linkeronderhoek van het rooster, gevolgd door de posities waarop de mier zich bevond na elke stap uit de simulatie. Na het uitvoeren van de functie, moet het rooster de configuratie van de richtingaanwijzers bevatten op het ogenblik dat de mier zijn nest bereikt heeft.

Voorbeeld

>>> vierkant = rooster(4, '>>>>^<^v^v^^>>v>')
>>> vierkant
[['>', '>', '>', '>'], ['^', '<', '^', 'v'], ['^', 'v', '^', '^'], ['>', '>', 'v', '>']]
>>> print(tekst(vierkant))
> > > >
^ < ^ v
^ v ^ ^
> > v >
>>> stap(vierkant, (3, 0))
(3, 1)
>>> print(tekst(vierkant))
> > > >
^ < ^ v
^ v ^ ^
v > v >
>>> stap(vierkant, (3, 1))
(3, 2)
>>> print(tekst(vierkant))
> > > >
^ < ^ v
^ v ^ ^
v v v >

>>> vierkant = rooster(4, '>>>>^<^v^v^^>>v>')
>>> print(tekst(vierkant))
> > > >
^ < ^ v
^ v ^ ^
> > v >
>>> stappen(vierkant)    
[(3, 0), (3, 1), (3, 2), (3, 2), (3, 1), (3, 1), (3, 0), (3, 0), (3, 0), (2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (0, 3)]
>>> print(tekst(vierkant))
v v v >
> < ^ v
> v ^ ^
> ^ ^ >

>>> rooster(4, '>>>>^<^v^v^>>v>')
Traceback (most recent call last):
AssertionError: ongeldige argumenten