Het spelbord van Ricochet Robots bestaat uit een rechthoekig $$m \times n$$ rooster met $$m$$ rijen en $$n$$ kolommen. Rondom het rooster staan muren. Tussen twee horizontaal of verticaal aangrenzende cellen kan ook een muur staan. In de cellen van het rooster staan 2 of meer robots, die elk een unieke kleur hebben. Gekleurde robots kunnen nooit in dezelfde cel staan. Er staat ook één witte robot op het spelbord. Die mag wel in dezelfde cel staan als een gekleurde robot.
Bij elke zet kan één gekleurde robot in één van vier mogelijke richtingen bewegen: naar boven (N), naar onder (S), naar links (W) en naar rechts (E). We stellen deze richtingen voor door de hoofdletters die tussen ronde haakjes staan in de vorige zin. De robot blijft in de gekozen richting glijden (als stond hij op ijs) tot hij tegen een muur of tegen een andere gekleurde robot botst. De robot wordt dus niet afgestopt door de witte robot.
Het doel is om met zo weinig mogelijk zetten een robot van een bepaalde kleur in de cel van de witte robot te krijgen. De gekleurde robots moeten samenwerken om dit doel te kunnen bereiken.
Een voorbeeld: op het spelbord hierboven staan twee robots. We duiden de oranje robot aan met de letter A en de groene robot met de letter B. We noteren een zet met de letter van de gekleurde robot die de beweging maakt, gevolgd door de letter van de richting waarin de robot glijdt. Er zijn minimaal zes zetten nodig om de groene robot tot bij de witte robot te brengen:
-
AW: de oranje robot (A) glijdt naar links (W)
-
BE: de groene robot (B) glijdt naar rechts (E)
-
BN: de groene robot (B) glijdt naar boven (N)
-
BW: de groene robot (B) glijdt naar links (W)
-
BS: de groene robot (B) glijdt naar onder (S)
-
AE: de oranje robot (A) glijdt naar rechts (E)
Druk op de knop naast het spelbord hierboven om deze zetten uit te voeren.
Opgave
Om naar de cellen van een $$m \times n$$ rooster te kunnen verwijzen, indexeren we de cellen van het rooster in leesvolgorde (van links naar rechts, en van boven naar onder) vanaf nul. In de inleiding hebben we deze indexering weergeven in de grijze vierkanten in de linkerbovenhoek van de cellen.
Definieer een klasse Spelbord waarmee robots op Ricochet Robots spelborden kunnen opgesteld en verplaatst worden. Bij het aanmaken van een nieuw spelbord (Spelbord) moeten zes argumenten doorgegeven worden:
-
het aantal rijen $$m$$ (int) van het rooster op het spelbord
-
het aantal kolommen $$n$$ (int) van het rooster op het spelbord
-
een collectie (list, tuple of set) met de index (int) van elke cel waaronder een muur staat
-
een collectie (list, tuple of set) met de index (int) van elke cel waar aan de rechterkant een muur staat
-
een reeks (list of tuple) met de index (int) van elke cel waarin een gekleurde robot staat; de robots op het spelbord worden aangeduid met de opeenvolgende letters van het alfabet (A, B, C, …) in de volgorde waarin hun posities opgelijst staan in dit argument
-
de index (int) van de cel waarin de witte robot staat
Bij de beschrijving van de muren houden we enkel rekening met muren tussen twee cellen van het rooster. De muren langs de rand worden niet opgegeven in de beschrijving van het spelbord. De klasse Spelbord mag ervan uitgaan dat er enkel geldige argumenten doorgegeven worden bij het aanmaken van een nieuw spelbord, zonder dat dit expliciet moet gecontroleerd worden.
Als er een spelbord $$s$$ (Spelbord) wordt doorgegeven aan de ingebouwde functie repr, dan moet die een string (str) teruggeven die leest als een Python expressie waarmee een nieuw spelbord (Spelbord) aangemaakt wordt met dezelfde opstelling van de muren en de robots als op spelbord $$s$$. Daarbij moeten de opstellingen van de horizontale en verticale muren voorgesteld worden als een tuple waarin de indices in stijgende volgorde opgelijst staan. De opstelling van de gekleurde robots moet ook als een tuple voorgesteld worden.
Als er een spelbord $$s$$ (Spelbord) wordt doorgegeven aan de ingebouwde functie str, dan moet die een stringvoorstelling (str) van spelbord $$s$$ teruggeven. Daarin worden de hoekpunten van de cellen voorgesteld door plustekens (+) die horizontaal en verticaal van elkaar worden gescheiden door één karakter: een koppelteken (-) waar een horizontale muur staat, een verticale streep (|) waar een verticale muur staat en een spatie waar geen muur staat. Een cel waar een gekleurde robot staat, wordt voorgesteld door de corresponderende letter van de robot: in kleine letters als de witte robot niet in die cel staat en in hoofdletters als de witte robot ook in die cel staat. Een cel waarin enkel de witte robot staat, wordt voorgesteld door een asterisk (*). Een cel waarin geen robots staan, wordt voorgesteld door een spatie. Zie onderstaande voorbeeld om een beeld te krijgen hoe de stringvoorstelling van het spelbord er precies moet uitzien.
Voorts moet je op een spelbord $$s$$ (Spelbord) minstens deze methoden kunnen aanroepen:
-
Een methode buur waaraan twee argumenten moeten doorgegeven worden: i) de index $$i$$ (int) van een cel in het rooster van spelbord $$s$$ en ii) een letter (str) die een richting aanduidt (N, E, S of W). Voor de letter die de richting aanduidt, mag de functie geen onderscheid maken tussen hoofdletters of kleine letters. Als er tussen cel $$i$$ en de aangrenzende cel in de opgegeven richting een muur staat (inclusief muren langs de rand) op spelbord $$s$$, dan moet de waarde None teruggegeven worden. Anders moet de index (int) teruggegeven worden van de cel die in de opgegeven richting grenst aan cel $$i$$.
-
Een methode glijden waaraan twee argumenten moeten doorgegeven worden: i) de index $$i$$ (int) van een cel in het rooster van spelbord $$s$$ en ii) een letter (str) die een richting aanduidt (N, E, S of W). Voor de letter die de richting aanduidt, mag de functie geen onderscheid maken tussen hoofdletters of kleine letters. De methode moet de index (int) teruggeven van de cel waarop een robot zou terechtkomen als hij vanaf cel $$i$$ zou glijden in de opgegeven richting.
- Een methode zet waaraan de beschrijving (str) van een zet moet doorgegeven worden: de letter van de robot die de beweging maakt, gevolgd door de letter van de richting waarin de robot glijdt. De methode mag ervan uitgaan dat het argument een geldige zet beschrijft (zonder dat dit expliciet moet gecontroleerd worden), en mag geen onderscheid maken tussen hoofdletters en kleine letters in de beschrijving. De methode moet de zet uitvoeren op spelbord $$s$$ door de aangeduide robot in de opgegeven richting te laten glijden, en moet een verwijzing naar spelbord $$s$$ teruggeven.
Voorbeeld
>>> spelbord = Spelbord(5, 6, [8, 9, 14, 20, 21], [1, 19, 20, 27], [11, 14], 7)
>>> print(spelbord)
+-+-+-+-+-+-+
| | |
+ + + + + + +
| * a|
+ + +-+-+ + +
| b |
+ + +-+ + + +
| | | |
+ + +-+-+ + +
| | |
+-+-+-+-+-+-+
>>> spelbord.buur(11, 'N')
5
>>> spelbord.buur(11, 'W')
10
>>> spelbord.buur(11, 'S')
17
>>> spelbord.buur(11, 'E')
>>> spelbord.buur(15, 'N')
>>> spelbord.buur(28, 'W')
>>> spelbord.buur(9, 'S')
>>> spelbord.buur(1, 'E')
>>> spelbord.glijden(11, 'N')
5
>>> spelbord.glijden(11, 'W')
6
>>> spelbord.glijden(11, 'S')
29
>>> spelbord.glijden(11, 'E')
11
>>> print(spelbord.zet('AW'))
+-+-+-+-+-+-+
| | |
+ + + + + + +
|a * |
+ + +-+-+ + +
| b |
+ + +-+ + + +
| | | |
+ + +-+-+ + +
| | |
+-+-+-+-+-+-+
>>> spelbord.zet('BE')
Spelbord(5, 6, (8, 9, 14, 20, 21), (1, 19, 20, 27), (6, 17), 7)
>>> spelbord.zet('bn').zet('bw').zet('bs')
Spelbord(5, 6, (8, 9, 14, 20, 21), (1, 19, 20, 27), (6, 8), 7)
>>> print(spelbord.zet('AE'))
+-+-+-+-+-+-+
| | |
+ + + + + + +
| A b |
+ + +-+-+ + +
| |
+ + +-+ + + +
| | | |
+ + +-+-+ + +
| | |
+-+-+-+-+-+-+