Lemmingen — een soort woelmuizen — staan erom bekend dat de grootte van hun populatie van jaar tot jaar zeer sterk kan fluctueren. Wanneer er overbevolking van lemmingen optreedt in een bepaald gebied, dan trekken de dieren vaak in groep weg. Deze massale trek spreekt zo tot de verbeelding dat er allerlei volksverhalen over zijn ontstaan. Zo zou de trek niet te stoppen zijn (het dier zou zelfmoord plegen om plaats te maken voor andere lemmingen), en zelfs geen halt houden voor de zee (waarin de dieren massaal zouden verdrinken) of onneembare obstakels (waarvoor de dieren zelfs spontaan zouden exploderen).
Deze volksverhalen werden verder gevoed door de Disney natuurfilm White Wilderness1 uit 1958, waarin duidelijk te zien is hoe lemmingen in grote getale over een klif vallen. Disney sleepte voor deze natuurfilm zelfs een Academy Award for Best Documentary Feature in de wacht. In de documentaire Cruel Camera2 uit 1982 werd echter onthuld dat de originele documentaire niet werd gefilmd in Antarctica, maar dat de lemmingen werden overgevlogen van Hudson Bay naar Calgary (Alberta, Canada), waar ze niet uit eigen beweging van een klif sprongen maar ervan gejaagd werden door de cameraploeg.
Het verhaal van de lemmingen inspireerde het Schotse softwarebedrijf DMA Design3 (tegenwoordig bekend als Rockstar North) tot het ontwikkelen van het computerspel Lemmings4. Het computerspel werd een absolute monsterhit tijdens de jaren '90. Via een luik in het plafond werden antropomorfe lemmingen in een level gedropt. Daar liepen ze achter elkaar in een lijn, om pas bij een obstakel te keren. De lemmingen liepen zelfs blindelings naar zaken toe die hen konden doden, zoals water, vuur, lava of een hoge val. Een speler kan een lemming één van de acht mogelijke functies toekennen, waaronder klimmen, graven en blokkeren. De bedoeling is om zo veel mogelijk lemmingen naar de uitgang te leiden door er onderweg zo weinig mogelijk te laten sneuvelen. Voor ieder level geldt een minimum overlevingspercentage. Wanneer dit niet gehaald wordt, dan moet het level opnieuw gespeeld worden.
Opgave
Voor deze opgave vragen we je om een vereenvoudigde simulatie te maken van een lemming in een level van het computerspel Lemmings. Een level van het computerspel bestaat uit een aantal cellen die gerangschikt zijn in de vorm van een rechthoek, en wordt omschreven in een tekstbestand. In die omschrijving geven spaties de vrije cellen aan, en worden cellen met een obstakel aangeduid met een hekje (#). Langs de buitenste rand van het level bevinden zich altijd obstakels. Een level kan er bijvoorbeeld als volgt uitzien.
################################# # # # # # # ### # ########### ### # ########### ######## # ########### ############## # #################################
Omdat elk level de vorm van een rechthoek aanneemt, zullen we de posities in de rechthoek aanduiden door de rijen van boven naar onder, en de kolommen van links naar rechts te nummeren vanaf nul. Voor het level dat we als voorbeeld gebruikt hebben, ziet de nummering er als volgt uit.
Als we via een luik in het plafond een lemming in het level droppen in kolom 3, dan valt de lemming naar beneden tot hij op positie $$(3, 3)$$ vaste grond onder de voeten krijgt. Als de lemming initieel naar links begint te stappen, dan ziet de situatie van het level er op dat moment als volgt uit.
Bij elke stap in de simulatie beweegt de lemming autonoom in een bepaalde richting. Stel dat de lemming zich naar rechts wil bewegen, dan zijn er drie verschillende mogelijkheden die worden geïllustreerd in onderstaande figuur.
We noemen de cel waarin de lemming zich momenteel bevindt de huidige cel. Als de cel rechts van de huidige cel vrij is (situatie links in bovenstaande figuur) dan verplaatst de lemming zich naar die cel. Daarna valt de lemming naar beneden totdat hij vaste grond onder de voeten heeft (indien dit nog niet het geval was). Als er rechts van de huidige cel een obstakel staat maar de cel boven dit obstakel vrij is (situatie midden in bovenstaande figuur), dan beweegt de lemming naar die vrije cel. Als de cellen rechts en rechtsboven de huidige cel beide een obstakel bevatten, dan blijft de lemming in de huidige cel staan maar beweegt de lemming zich vanaf nu naar links. De lemming gedraagt zich analoog indien hij zich in de volgende stap naar links wil bewegen.
Gevraagd wordt om een klasse Lemming te definiëren waarmee een simulatie van een lemming in een bepaald level van het computerspel Lemmings kan gemaakt worden in Python. Deze klasse moeten minstens de volgende methoden ondersteunen:
Een initialisatiemethode waaraan drie argumenten moeten doorgegeven worden: i) de locatie van een tekstbestand met de omschrijving van het level, ii) de kolom waar de lemming initieel in het level gedropt wordt via een luik in het plafond en iii) de richting waarin de lemming zich initieel beweegt. De richting wordt aangegeven door een kleiner dan teken (<) indien de lemming zich initieel naar links beweegt en met een groter dan teken (>) indien de lemming zich initieel naar rechts beweegt. Na het uitvoeren van de initialisatiemethode moet de lemming altijd vaste grond onder de voeten hebben.
Een methode positie die een tuple met drie elementen teruggeeft: i) het rijnummer van de cel waar de lemming zich momenteel bevindt, ii) het kolomnummer van de cel waar de lemming zich momenteel bevindt en iii) de richting waarin de lemming zich momenteel beweegt, aangegeven door een kleiner dan of groter dan teken (analoog als bij de initialisatiemethode).
Een methode stap waarmee één enkele stap van de simulatie van de lemming wordt uitgevoerd. De methode moet een tuple teruggeven met de positie en beweegrichting van de lemming na het uitvoeren van de stap, waarbij het tuple dezelfde vorm aanneemt als bij de methode positie.
Een methode stappen waaraan een getal $$n \in \mathbb{N}$$ moet doorgegeven worden. De methode moet $$n$$ stappen van de simulatie van de lemming uitvoeren, en moet een lijst teruggeven met de posities en beweegrichtingen van de lemming na het uitvoeren van elk van de opeenvolgende stappen. De positie en beweegrichting van de lemming moet weergegeven worden aan de hand van een tuple dat dezelfde vorm aanneemt als bij de methode positie.
Bovendien moet het mogelijk zijn om met de ingebouwde functie print een stringvoorstelling van de huidige positie en richting van de lemming in het level uit te schrijven. In deze stringvoorstelling moet het level op precies dezelfde manier weergegeven worden als die in het gegeven bestand werd voorgesteld. Daarbij moet de positie waar de lemming zich momenteel bevindt worden aangegeven door een kleiner dan teken (<) indien de lemming zich naar links beweegt en met een groter dan teken (>) indien de lemming zich naar rechts beweegt.
Voorbeeld
Bij onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand level.txt5 zich in de huidige directory bevindt.
>>> lemming = Lemming('level.txt', 3, '<')
>>> lemming.positie()
(3, 3, '<')
>>> print(lemming)
#################################
# #
# # #
# < ### #
########### ### #
########### ######## #
########### ############## #
#################################
>>> lemming.stap()
(3, 2, '<')
>>> lemming.stap()
(3, 1, '<')
>>> lemming.stap()
(3, 1, '>')
>>> lemming.stap()
(3, 2, '>')
>>> print(lemming)
#################################
# #
# # #
# > ### #
########### ### #
########### ######## #
########### ############## #
#################################
>>> lemming.stappen(5)
[(3, 3, '>'), (3, 4, '>'), (3, 5, '>'), (3, 6, '>'), (3, 7, '>')]
>>> print(lemming)
#################################
# #
# # #
# >### #
########### ### #
########### ######## #
########### ############## #
#################################
>>> lemming.stap()
(2, 8, '>')
>>> print(lemming)
#################################
# #
# > # #
# ### #
########### ### #
########### ######## #
########### ############## #
#################################
>>> lemming.stap()
(2, 9, '>')
>>> lemming.stap()
(1, 10, '>')
>>> print(lemming)
#################################
# > #
# # #
# ### #
########### ### #
########### ######## #
########### ############## #
#################################
>>> lemming.stap()
(6, 11, '>')
>>> print(lemming)
#################################
# #
# # #
# ### #
########### ### #
########### ######## #
###########> ############## #
#################################
>>> lemming.stappen(21)
[(6, 12, '>'), (5, 13, '>'), (5, 14, '>'), (4, 15, '>'), (4, 16, '>'), (3, 17, '>'), (3, 18, '>'), (3, 19, '>'), (4, 20, '>'), (4, 21, '>'), (4, 22, '>'), (5, 23, '>'), (5, 24, '>'), (5, 25, '>'), (5, 26, '>'), (6, 27, '>'), (6, 28, '>'), (6, 29, '>'), (6, 30, '>'), (6, 31, '>'), (6, 31, '<')]
>>> lemming.stappen(21)
[(6, 30, '<'), (6, 29, '<'), (6, 28, '<'), (6, 27, '<'), (5, 26, '<'), (5, 25, '<'), (5, 24, '<'), (5, 23, '<'), (4, 22, '<'), (4, 21, '<'), (4, 20, '<'), (3, 19, '<'), (3, 18, '<'), (3, 17, '<'), (4, 16, '<'), (4, 15, '<'), (5, 14, '<'), (5, 13, '<'), (6, 12, '<'), (6, 11, '<'), (6, 11, '>')]
>>> print(lemming)
#################################
# #
# # #
# ### #
########### ### #
########### ######## #
###########> ############## #
#################################Onderstaande animatie simuleert een aantal stappen van de lemming in het level uit bovenstaand voorbeeld, en maakt daarbij gebruik van de stringvoorstelling die ook door de ingebouwde functie print moet weergegeven worden. We hebben ook een expliciete animatie gemaakt van de valbewegingen van de lemming, maar deze vormen geen afzonderlijke stappen in de simulatie.
