Terwijl ik aan het prutsen was met de verfemmer-tool¹ in GIMP², kreeg ik plots het volgende idee voor een spelletje dat iemand eens zou moeten ontwikkelen voor op de smartphone. Het spel wordt gespeeld op een rechthoekig rooster van gekleurde ronde tegels.

Een van die tegels — de druppeltegel — wordt initieel ingekleurd met alle kleuren van de regenboog (in onderstaande figuur is dat de tegel in de linkerbovenhoek van het rooster). Door gekleurde verfdruppels te laten vallen op de druppeltegel ontstaat een vlek die overloopt naar alle aangrenzende tegels in de vier hoofdrichtingen (geen diagonalen). Het doel is om met zo weinig mogelijk druppels een vlek te maken in een bepaalde kleur (de doelkleur) die is overgelopen naar alle tegels van het rooster.

Bij aanvang van het spel beslaat de vlek enkel de druppeltegel. Het uitbreiden van die vlek verloopt in twee stappen. Als je een druppel van een bepaalde kleur laat vallen op de druppeltegel, dan veranderen alle tegels die deel uitmaken van de vlek naar die kleur. Daarna breidt de vlek uit naar alle aangrenzende tegels met diezelfde kleur. Dit wordt geïllustreerd in onderstaande figuur.

Aanvankelijk beslaat de vlek enkel de druppeltegel (in de linkerbovenhoek). Als we een oranje druppel laten vallen op de druppeltegel, dan wordt die tegel (de enige van de vlek) oranje. Daarna breidt de vlek uit naar alle andere tegels op de bovenste rij, omdat die ook een oranje kleur hebben. Als we nu een groene druppel laten vallen op de druppeltegel, dan worden alle tegels van de vlek (de tegels op de bovenste rij) groen. Daarna loopt de vlek over naar twee extra groene tegels op de tweede kolom. Door de kleuren van de volgende druppels strategisch te kiezen, slagen we erin om de vlek stelselmatig groter te maken.

Opgave

We stellen elke kleur voor door een unieke letter. Het rooster van gekleurde tegels kan dan voorgesteld worden door elke rij op een afzonderlijke regel te zetten, en de letters die corresponderen met de kleur van de opeenvolgende tegels op een rij na elkaar te zetten, van elkaar gescheiden door een spatie. De druppeltegel wordt aangeduid met een sterretje (*). Tegels die deel uitmaken van de vlek worden voorgesteld met een hoofdletter, de andere tegels met een kleine letter. Het rooster dat we krijgen bij aanvang van het spelletje uit de inleiding ziet er dan als volgt uit.

* o o o
b g v r
r g b g
v o b r

Als we een oranje (O) druppel laten vallen op de druppeltegel, dan breidt de vlek zich als volgt uit over het rooster (we blijven de druppeltegel voorstellen met een sterretje).

* O O O
b g v r
r g b g
v o b r

Als we daarna een groene (G) druppel laten vallen op de druppeltegel, dan wordt de vlek groen en breidt die zich als volgt uit over het rooster.

* G G G
b G v r
r G b g
v o b r

Gevraagd wordt om een klasse Rooster te schrijven waarmee roosters van gekleurde tegels kunnen voorgesteld worden, zoals die gebruikt worden in het spelletje dat we in de inleiding omschreven hebben. Deze klasse moet minstens de volgende methoden ondersteunen:

• Een initialisatiemethode waaraan twee argumenten moeten doorgegeven worden: i) een natuurlijk getal $$k \geq 2$$ dat aangeeft uit hoeveel kolommen het rooster bestaat en ii) een string met letters die de kleuren van de tegels in het rooster aangeven bij aanvang van het spelletje. Hierbij overlopen we de tegels van het rooster van links naar rechts en van boven naar onder. De positie van de druppeltegel wordt aangeduid met een sterretje (*).

• Een methode druppel waaraan een letter moet doorgegeven worden. Met deze methode simuleren we het laten vallen van een druppel op de druppeltegel in de opgegeven kleur. De methode moet een referentie teruggeven naar het object waarop de methode wordt aangeroepen.

• Een methode druppels waaraan een string met één of meer letters moet doorgegeven worden. Met deze methode simuleren we het laten vallen van een aantal opeenvolgende druppels op de druppeltegel in de opeenvolgende kleuren uit de gegeven string. De methode moet een referentie teruggeven naar het object waarop de methode wordt aangeroepen.

• Een methode gewonnen waaraan een letter moet doorgegeven worden die correspondeert met de doelkleur. De methode moet een Booleaanse waarde teruggeven, die aangeeft of de vlek zich reeds over het volledige rooster heeft uitgebreid én de gegeven doelkleur heeft.

Zorg ervoor dat elk object van de klasse Rooster een eigenschap druppeltegel heeft die verwijst naar een tuple $$(r, k)$$, waarbij $$r$$ en $$k$$ respectievelijk de rij en de kolom van het rooster aanduiden waarop de druppeltegel te vinden is. Hierbij worden de rijen van boven naar onder genummerd, en de kolommen van links naar rechts, telkens vanaf nul.

Zorg er ook voor dat de ingebouwde functie print kan gebruikt worden om een stringvoorstelling van de objecten van de klasse Rooster uit te schrijven. Deze voorstelling moet overeenkomen met het formaat dat we hierboven gebruikt hebben, inclusief het gebruik van een sterretje (*) om de positie van de druppeltegel aan te duiden.

Voorbeeld

>>> rooster = Rooster(4, '*OOOBGVRRGBGVOBR')
>>> print(rooster)
* o o o
b g v r
r g b g
v o b r
>>> rooster.druppeltegel
(0, 0)
>>> rooster.gewonnen('O')
False
>>> print(rooster.druppel('O'))
* O O O
b g v r
r g b g
v o b r
>>> rooster.gewonnen('O')
False
>>> print(rooster.druppel('G'))
* G G G
b G v r
r G b g
v o b r
>>> rooster.gewonnen('O')
False
>>> print(rooster.druppels('OBR'))
* R R R
R R v R
R R R g
v R R R
>>> rooster.gewonnen('O')
False
>>> print(rooster.druppels('VGR'))
* R R R
R R R R
R R R R
R R R R
>>> rooster.gewonnen('O')
False
>>> rooster.gewonnen('R')
True
>>> print(rooster.druppel('O'))
* O O O
O O O O
O O O O
O O O O
>>> rooster.gewonnen('O')
True
>>> rooster.gewonnen('R')
False