Shikaku (四角に切れ, shikaku ni kire) is een logische puzzel die bestaat uit een rechthoekig rooster waarvan sommige cellen genummerd zijn met een strikt positief natuurlijk getal. Dit is bijvoorbeeld de opgave van een $$5 \times 6$$ puzzel.

Je moet het rooster in rechthoekige stukken verdelen, zodat elk stuk een aantal cellen volledig bedekt. Het aantal cellen dat door een rechthoek bedekt wordt, noemen we de oppervlakte van de rechthoek. Bovendien moet elke rechthoek precies één genummerde cel bedekken waarvan het getal gelijk is aan de oppervlakte van de rechthoek. Een gevolg hiervan is dat de oppervlakte van het rooster gelijk moet zijn aan de som van alle getallen in het rooster. Dit is de unieke oplossing van bovenstaande voorbeeldpuzzel.

Opgave

Om naar de cellen in het rooster van een Shikaku-puzzel te kunnen verwijzen, worden de rijen van boven naar onder genummerd en de kolommen van links naar rechts, telkens vanaf nul. De positie van een cel in het rooster wordt voorgesteld door een tuple $$(r, k)$$, waarbij $$r \in \mathbb{N}$$ (int) het rijnummer en $$k \in \mathbb{N}$$ (int) het kolomnummer aanduidt.

Rechthoek

Definieer een klasse Rechthoek waarmee rechthoekige stukken van Shikaku-puzzels kunnen voorgesteld worden. Bij het aanmaken van een rechthoek (Rechthoek) moeten er drie of vier natuurlijke getallen $$r$$, $$k$$, $$h$$ en optioneel ook $$b$$ doorgegeven worden. Daarbij is $$(r, k)$$ de positie van de cel in het rooster van de puzzel die bedekt wordt door de linkerbovenhoek van de rechthoek, $$h$$ de hoogte van de rechthoek (uitgedrukt als een aantal rijen) en $$b$$ de breedte van de rechthoek (uitgedrukt als een aantal kolommen). We noemen $$(r, k)$$ ook de positie van de rechthoek. Als er geen vierde argument wordt doorgegeven, dan is de rechthoek een vierkant waarvan de breedte ($$b$$) en de hoogte ($$h$$) gelijk zijn.

Als er een rechthoek $$R$$ (Rechthoek) wordt doorgegeven aan de ingebouwde functie repr, dan moet die een expressie (str) teruggeven waarmee een nieuwe rechthoek (Rechthoek) aangemaakt wordt met dezelfde positie, hoogte en breedte als de rechthoek $$R$$. Daarbij moeten er altijd vier argumenten doorgeven worden (ook al zijn de hoogte en breedte gelijk), en moeten de argumenten telkens van elkaar gescheiden worden door een komma (,) en een spatie.

Op een rechthoek $$R$$ (Rechthoek) moet je minstens de volgende methoden kunnen aanroepen:

• Een methode oppervlakte waaraan geen argumenten moeten doorgegeven worden. De methode moet de oppervlakte (int) van rechthoek $$R$$ teruggeven.

• Een methode cellen waaraan geen argumenten moeten doorgegeven worden. De methode moet een verzameling (set) teruggeven met de posities (tuple) van alle cellen in het rooster die door rechthoek $$R$$ bedekt worden.

Als de operator <= gebruikt wordt om twee rechthoeken $$R_1$$ en $$R_2$$ (Rechthoek) met elkaar te vergelijken (R1 <= R2), dan moet dit een Booleaanse waarde (bool) opleveren die aangeeft of $$R_1$$ volledig ingesloten zit in de $$R_2$$. Anders gezegd, of alle cellen die bedekt worden door $$R_1$$ ook bedekt worden door $$R_2$$.

Als de operator & gebruikt wordt om de doorsnede van twee rechthoeken $$R_1$$ en $$R_2$$ (Rechthoek) te bepalen (R1 & R2), dan moet dit een nieuwe rechthoek (Rechthoek) opleveren die alle cellen bedekt die zowel door $$R_1$$ als door $$R_2$$ bedekt worden. Als $$R_1$$ en $$R_2$$ geen gemeenschappelijke cellen bedekken, dan moet de operator & de waarde None opleveren.

Shikaku

Definieer ook nog een klasse Shikaku waarmee Shikaku-puzzels kunnen voorgesteld worden, waarin rechthoekige stukken kunnen aangeduid en terug verwijderd worden. Bij het aanmaken van een puzzel (Shikaku) moet de locatie (str) doorgegeven worden van een tekstbestand dat de opgave van de puzzel beschrijft. De eerste regel van het bestand bevat twee natuurlijke getallen $$m$$ en $$n$$ die van elkaar gescheiden worden door een spatie. Ze geven aan dat het rooster van de puzzel bestaat uit $$m$$ rijen en $$n$$ kolommen. Daarna volgt voor elke genummerde cel in het rooster een regel waarop drie natuurlijke getallen staan die van elkaar gescheiden worden door een spatie: i) het rijnummer van de cel, ii) het kolomnummer van de cel en iii) het getal in de cel. De puzzel uit de inleiding wordt bijvoorbeeld beschreven door het volgende bestand:

5 6
0 3 10
1 5 5
2 0 2
3 2 9
4 0 4

Je mag ervan uitgaan dat het bestand altijd een geldige puzzel beschrijft, zonder dat dit expliciet moet gecontroleerd worden: alle cellen liggen in het rooster en de oppervlakte van het rooster is gelijk aan de som van alle getallen in het rooster. Bij aanvang zijn er nog geen rechthoekige stukken aangeduid in het rooster.

Op een puzzel $$P$$ (Shikaku) moet je minstens de volgende methoden kunnen aanroepen:

• Een methode cellen waaraan een rechthoek $$R$$ (Rechthoek) moet doorgegeven worden. De methode moet een lijst (list) teruggeven met de posities (tuple) van alle genummerde cellen van puzzel $$P$$ die door rechthoek $$R$$ bedekt worden. De posities moeten opgelijst worden in de volgorde waarin je de cellen tegenkomt als je het rooster van puzzel $$P$$ in leesvolgorde overloopt: links naar rechts en van boven naar onder.

• Een methode getallen waaraan een rechthoek $$R$$ (Rechthoek) moet doorgegeven worden. De methode moet een lijst (list) teruggeven met de getallen (int) in alle genummerde cellen van puzzel $$P$$ die door rechthoek $$R$$ bedekt worden. De getallen moeten opgelijst worden in de volgorde waarin je de cellen tegenkomt als je het rooster van puzzel $$P$$ in leesvolgorde overloopt: links naar rechts en van boven naar onder.

• Een methode onbedekt waaraan geen argumenten moeten doorgegeven worden. De methode moet een verzameling (set) teruggeven met de posities (tuple) van alle genummerde cellen van puzzel $$P$$ die nog niet door een rechthoek bedekt zijn.

• Een methode bedekken waaraan een rechthoek $$R$$ (Rechthoek) moet doorgegeven worden. De methode moet zorgen dat puzzel $$P$$ bijgehoudt dat de cellen van rechthoek $$R$$ nu bedekt zijn, als aan de volgende voorwaarden voldaan is:

  • rechthoek $$R$$ bedekt enkel cellen die in het rooster van puzzel $$P$$ gelegen zijn

  • rechthoek $$R$$ bedekt geen cellen die al door andere rechthoeken bedekt zijn in puzzel $$P$$

  • rechthoek $$R$$ bedekt slechts één genummerde cel van puzzel $$P$$

  • de oppervlakte van rechthoek $$R$$ is gelijk aan het getal in de genummerde cel van puzzel $$P$$ die door rechthoek $$R$$ bedekt wordt

  Als minstens één van deze voorwaarden niet voldaan is, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige rechthoek.

• Een methode verwijderen waaraan de positie van een genummerde cel moet doorgegeven worden. Als de positie geen genummerde cel aanduidt in puzzel $$P$$ of als de genummerde cel niet door een rechthoek bedekt wordt in puzzel $$P$$, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige positie. Anders moet de rechthoek weggehaald worden die de genummerde cel bedekt in puzzel $$P$$, waardoor alle cellen die door deze rechthoek bedekt werden niet langer bedekt zijn.

• Een methode isopgelost waaraan geen argumenten moeten doorgegeven worden. De methode moet een Booleaanse waarde (bool) teruggeven die aangeeft of alle genummerde cellen in puzzel $$P$$ door rechthoeken bedekt zijn.

Voorbeeld

In onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand shikaku.txt zich in de huidige directory bevindt.

>>> groen = Rechthoek(0, 5, 5, 1)
>>> groen
Rechthoek(0, 5, 5, 1)
>>> groen.oppervlakte()
5
>>> groen.cellen()
{(4, 5), (1, 5), (0, 5), (2, 5), (3, 5)}
>>> blauw = Rechthoek(3, 0, 2)
>>> blauw
Rechthoek(3, 0, 2, 2)
>>> blauw.oppervlakte()
4
>>> blauw.cellen()
{(3, 0), (3, 1), (4, 1), (4, 0)}
>>> groen & blauw
>>> groen & Rechthoek(1, 1, 3, 5)
Rechthoek(1, 5, 3, 1)
>>> blauw & Rechthoek(1, 1, 3, 5)
Rechthoek(3, 1, 1, 1)
>>> Rechthoek(2, 3, 3, 2) <= Rechthoek(2, 2, 3)
True
>>> groen <= blauw
False

>>> shikaku = Shikaku('shikaku.txt')
>>> shikaku.cellen(blauw)
[(4, 0)]
>>> shikaku.getallen(blauw)
[4]
>>> shikaku.cellen(Rechthoek(1, 1, 3, 5))
[(1, 5), (3, 2)]
>>> shikaku.getallen(Rechthoek(1, 1, 3, 5))
[5, 9]
>>> shikaku.onbedekt()
{(1, 5), (2, 0), (3, 2), (0, 3), (4, 0)}
>>> shikaku.bedekken(blauw)
>>> shikaku.onbedekt()
{(1, 5), (3, 2), (2, 0), (0, 3)}
>>> shikaku.isopgelost()
False
>>> shikaku.bedekken(groen)
>>> shikaku.onbedekt()
{(2, 0), (3, 2), (0, 3)}
>>> shikaku.isopgelost()
False
>>> shikaku.bedekken(Rechthoek(1, 1, 3, 5))
Traceback (most recent call last):
AssertionError: ongeldig rechthoek
>>> shikaku.verwijderen((3, 0))
Traceback (most recent call last):
AssertionError: ongeldige positie
>>> shikaku.verwijderen((4, 0))
>>> shikaku.onbedekt()
{(2, 0), (3, 2), (4, 0), (0, 3)}
>>> shikaku.bedekken(blauw)
>>> shikaku.bedekken(Rechthoek(0, 0, 2, 5))  # paars
>>> shikaku.bedekken(Rechthoek(2, 0, 1, 2))  # bruin
>>> shikaku.bedekken(Rechthoek(2, 2, 3))     # roze
>>> shikaku.onbedekt()
set()
>>> shikaku.isopgelost()
True