Quinquagintus Tricartius had een groot probleem. Bij de heraanleg van zijn atrium bestelde hij per ongeluk in plaats van vierkante tegels alleen maar driekwartstegels. Deze zien er uit als een L en beslaan ¾ van een \(2 \times 2\) vierkant. Hoe kon hij nu alsnog zijn atrium betegelen zonder nieuwe tegels te moeten kopen? Gelukkig kwam zijn goede vriend, Julius Caesar, op bezoek. Deze aanschouwde de opengebroken vloer, het afvoerputje en de tegels, en zag onmiddelijk een oplossing. “Triviaal,” sprak Julius, “Divide et impera!” En inderdaad, met een verdeel-en-heers algoritme betegelde Quinquagintus zijn vloer perfect.

Het is namelijk mogelijk om ieder vierkant rooster met 1 gat (het afvoerputje) waarbij de dimensie een macht van twee is, op te vullen met L-vormige tegels zodat het vakje van het afvoerputje het enige vakje is waar geen tegel op ligt. Zie hieronder voor een voorbeeld waar het afvoerputje op positie \((2, 2)\) ligt.

Opgave

Implementeer de klasse DriekwartsBetegeling, die Quinquagintus kan gebruiken om de gekozen betegeling door te geven aan zijn slaven. Hiervoor schrijf je volgende methoden:

• Een initialisatiemethode (__init__) waar een natuurlijk getal k aan meegegeven wordt. Deze methode initialiseert een vierkant met zijde \(2^k\) (niet zijde k!). Deze betegeling sla je op als een rooster van getallen, waarin elke tegel een uniek getal krijgt, zoals in bovenstaande tekening. Een 0-waarde stelt een (nog) onbetegeld vakje voor. Wanneer alles betegeld is, heeft enkel het vakje van het afvoerputje de waarde 0.

• Een triviale methode zijde zonder argumenten die de lengte van de zijde, \(2^k\), terug geeft.

• Een triviale methode tegelnummer die 2 getallen rij en kolom als argumenten heeft. Deze methode moet het nummer van de tegel op rij rij en kolom kolom teruggeven.

• Een methode plaats_tegel die 3 getallen rij, kolom en vorm als argumenten heeft. Deze methode moet een tegel plaatsen in het \(2 \times 2\) vierkantje met linkerbovenhoek op rij rij en kolom kolom. Het ontbrekende vakje van de L-vormige tegel ligt ofwel linksboven (vorm is 0), rechtsboven (vorm is 1), linksonder (vorm is 2) of rechtsonder (vorm is 3). Zo zullen de oproepen plaatsTegel(1, 1, 3), plaatsTegel(2, 2, 0) en plaatsTegel(1, 5, 2) de twee gekleurde tegels (5, 8 en 6) in bovenstaande tekening plaatsen. Neem als nummer van de tegel altijd het laagst mogelijke natuurlijk getal dat nog niet voorkomt in het rooster.

• een methode plaats_tegels die 1 verplichte parameter afvoer heeft. Deze parameter is een tuple \((r, k)\) waarbij \(r\) de rij en \(k\) de kolom van het afvoerputje bevat. Deze methode moet de verdeel-en-heers strategie implementeren die het vierkant betegelt.

Als cadeautje krijg je hieronder skeletcode waarin zich reeds de headers van bovenstaande klasse en methoden bevinden, samen met een handige methode om een betegeling af te drukken in prachtige ASCII-art.

Voorbeelden

>>> betegeling01 = DriekwartsBetegeling(1)
>>> betegeling01.zijde()
2
>>> betegeling01.plaats_tegel(0, 0, 0)
>>> print(betegeling01)
+--+--+
| 0| 1|
+--+  +
| 1  1|
+--+--+
>>> betegeling01 = DriekwartsBetegeling(2)
>>> betegeling01.plaats_tegels((1, 1))
>>> print(betegeling01)
+--+--+--+--+
| 3  3| 4  4|
+  +--+--+  +
| 3| 0| 1| 4|
+--+--+  +--+
| 5| 1  1| 2|
+  +--+--+  +
| 5  5| 2  2|
+--+--+--+--+