Flow Free is een puzzel die gespeeld wordt op een rechthoekig $$m \times n$$ rooster met $$m$$ rijen en $$n$$ kolommen, waarvan sommige cellen een gekleurde cirkel bevatten. Voor elke kleur zijn er exact twee cellen met een cirkel van die kleur. De andere cellen zijn initieel nog leeg.

Het doel is om cirkels met dezelfde kleur te verbinden met "pijpleidingen", zodat elke cel van het rooster uiteindelijk bezet is. Pijpleidingen kunnen enkel naar boven, onder, links en rechts bewegen, en mogen noch zichzelf noch andere pijpleidingen kruisen. Hieronder zie je bijvoorbeeld hoe een Flow Free puzzel op een $$9 \times 9$$ rooster opgelost wordt.

Opgave

Om te kunnen verwijzen naar de cellen in het rooster van een Flow Free puzzel, nummeren we de rijen (resp. kolommen ) van boven naar onder (resp. van links naar rechts) vanaf 0. Daardoor kunnen we de positie van een cel aanduiden met een tuple $$(r, k)$$, waarbij $$r$$ (int) de rij en $$k$$ (int) de kolom aanduidt waarop de cel voorkomt in het rooster.

Definieer een klasse FlowFree waarmee we het spelverloop van Flow Free puzzels kunnen voorstellen. Bij het aanmaken van een nieuwe puzzel (FlowFree) moeten drie argumenten doorgegeven worden: i) het aantal rijen van het rooster (int), ii) het aantal kolommen van het rooster (int) en iii) een reeks (list of tuple) met posities (tuple) van cellen in het rooster waarin gekleurde cirkels voorkomen. Daarbij bevat elk paar cellen op de twee volgende posities telkens cirkels met dezelfde kleur, die voorgesteld worden door de volgende hoofdletter in het alfabet: de eerste en tweede cel hebben dezelfde kleur (voorgesteld door de letter A), de derde en vierde cel hebben dezelfde kleur, maar een andere dan de vorige (voorgesteld door de letter B), enzoverder. Voor de configuratie van de gekleurde cellen in het rooster (derde argument) moet dus gelden dat:

• ze wordt voorgesteld als een reeks (list of tuple)

• ze een even aantal posities bevat

• ze enkel geldige posities van cellen in het rooster bevat

• ze allemaal verschillende posities bevat

Als niet aan deze voorwaarden voldaan is, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige configuratie.

Als er een puzzel $$p$$ (FlowFree) wordt doorgegeven aan de ingebouwde functie str, dan moet die een stringvoorstelling (str) van het rooster van puzzel $$p$$ teruggeven, met een opmaak zoals aangegeven in onderstaand voorbeeld. Hierbij stelt een hoofdletter een cel met een cirkel van de corresponderende kleur voor. Een punt (.) stelt een lege cel voor. Een segment van een pijpleiding die door een cel loopt, wordt voorgesteld door één van deze karakters:

━ | ┛ ┗ ┏ ┓

Op een puzzel $$p$$ (FlowFree) moet je minstens de volgende methoden kunnen aanroepen:

• Een methode ispositie waaraan twee argumenten moeten doorgegeven worden: i) een getal $$r$$ (int), en ii) een getal $$k$$ (int). De methode moet een Booleaanse waarde (bool) teruggeven, die aangeeft of $$(r, k)$$ een geldige positie aanduidt van een cel binnen het rooster van puzzel $$p$$.

• Een methode pijpleiding waaraan drie argumenten moeten doorgegeven worden: i) een getal $$r$$ (int), ii) een getal $$k$$ (int) en iii) een reeks letters (str) die de routebeschrijving van de pijpleiding naar naburige cellen aangeeft: U (naar boven), D (naar onder), L (naar links) en R (naar rechts). Bij de interpretatie van de routebeschrijving mag geen onderscheid gemaakt worden tussen hoofdletters en kleine letters. De methode moet een lijst (list) teruggeven met de posities (tuple) van de opeenvolgende cellen waarlangs de pijpleiding loopt, te beginnen bij startpositie $$(r, k)$$. De methode mag het rooster van puzzel $$p$$ niet aanpassen.

• Een methode verbinden waaraan dezelfde drie argumenten moeten doorgegeven worden als aan de methode pijpleiding, met dezelfde betekenis. De methode moet het rooster van puzzel $$p$$ aanpassen, zodat de gegeven pijpleiding er wordt in weergegeven. De methode moet een verwijzing naar puzzel $$p$$ (FlowFree) teruggeven.

• Een methode isopgelost waaraan geen argumenten moeten doorgegeven worden. De methode moet een Booleaanse waarde (bool) teruggeven, die aangeeft of elke cel van het rooster bezet is door een cirkel of door het segment van een pijpleiding.

De drie argumenten die aan de methoden pijpleiding en verbinden doorgegeven worden, moeten een geldige pijpleiding door het rooster van puzzel $$p$$ beschrijven. Als dat niet het geval is, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige pijpleiding, zonder dat daarbij het rooster van puzzel $$p$$ aangepast wordt. De beschrijving van een pijpleiding moet immers voldoen aan de volgende voorwaarden:

• de eerste twee argumenten duiden een geldige positie van een cel binnen het rooster aan

• het derde argument is een string (String) die enkel uit de opgegeven letters bestaat (zonder onderscheid te maken tussen hoofdletters en kleine letters)

• de pijpleiding blijft binnen het rooster

• de pijpleiding begint en eindigt bij cellen met dezelfde hoofdletter (cirkels met dezelfde kleur)

• de pijpleiding eindigt bij een andere cel dan waar ze begon

• de pijpleiding kruist zichzelf niet

• de pijpleiding kruist geen andere pijpleidingen (inclusief hun start- en eindposities)

Voorbeeld

>>> puzzel = FlowFree(5, 5, [(0, 1), (3, 0), (0, 2), (4, 0), (0, 3), (4, 3), (1, 3), (2, 2), (4, 2), (3, 3)])
>>> print(puzzel)
.ABC.
...D.
..D..
A..E.
B.EC.
>>> puzzel.ispositie(2, 3)
True
>>> puzzel.ispositie(8, 3)
False
>>> puzzel.pijpleiding(1, 3, 'dl')                     # D (rood)
[(1, 3), (2, 3), (2, 2)]
>>> print(puzzel.verbinden(1, 3, 'dl'))
.ABC.
...D.
..D┛.
A..E.
B.EC.
>>> puzzel.pijpleiding(4, 2, 'RU')                     # pijpleiding loopt door andere cirkel
Traceback (most recent call last):
AssertionError: ongeldige pijpleiding
>>> puzzel.pijpleiding(4, 2, 'UR')                     # E (oranje)
[(4, 2), (3, 2), (3, 3)]
>>> print(puzzel.verbinden(4, 2, 'UR'))
.ABC.
...D.
..D┛.
A.┏E.
B.EC.
>>> puzzel.pijpleiding(0, 1, 'lddd')                   # A (geel)
[(0, 1), (0, 0), (1, 0), (2, 0), (3, 0)]
>>> print(puzzel.verbinden(0, 1, 'lddd'))
┏ABC.
|..D.
|.D┛.
A.┏E.
B.EC.
>>> puzzel.pijpleiding(0, 2, 'dLLdRddL')               # pijpleiding kruist een andere pijpleiding
Traceback (most recent call last):
AssertionError: ongeldige pijpleiding
>>> puzzel.pijpleiding(0, 2, 'dLdddL')                 # B (blauw)
[(0, 2), (1, 2), (1, 1), (2, 1), (3, 1), (4, 1), (4, 0)]
>>> print(puzzel.verbinden(0, 2, 'dLdddL'))
┏ABC.
|┏┛D.
||D┛.
A|┏E.
B┛EC.
>>> puzzel.isopgelost()
False
>>> puzzel.pijpleiding(0, 3, 'RddddL')                 # C (groen)
[(0, 3), (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (4, 3)]
>>> print(puzzel.verbinden(0, 3, 'RddddL'))
┏ABC┓
|┏┛D|
||D┛|
A|┏E|
B┛EC┛
>>> puzzel.isopgelost()
True

>>> FlowFree(5, 5, [(0, 1), (3, 0), (0, 2)])           # oneven aantal posities
Traceback (most recent call last):
AssertionError: ongeldige configuratie
>>> FlowFree(5, 5, [(0, 1), (3, 0), (0, 2), (0, 1)])   # zelfde positie komt meerdere keren voor
Traceback (most recent call last):
AssertionError: ongeldige configuratie
>>> FlowFree(5, 5, [(0, 1), (3, 0), (0, 2), (5, 3)])   # positie buiten het rooster
Traceback (most recent call last):
AssertionError: ongeldige configuratie