We wensen een rechthoekige ruimte te bedekken met tapijten. Zowel de ruimte als de tapijten hebben gehele afmetingen, en ook de tapijten zijn rechthoekig. We stellen daarom de ruimte zelf voor via een 2-dimensionale lijst van gehele getallen. Bevat een cel het getal 0, dan stelt dit een onbedekte cel van de ruimte voor. Bevat een cel een strikt positief geheel getal n, dan geeft dit aan dat de cel door het tapijt met rangnummer n bedekt wordt.

Programmer in de klasse Tatami:

• een constructor, met 2 argumenten, namelijk het aantal rijen en het aantal kolommen van de 2D lijst die de ruimte voorstelt
• de methode __str__() levert als stringgedaante van elk element van de 2D-lijst, gescheiden door een \n (neem dus een nieuwe regel per rij, zodat je makkelijk kan volgen hoe de ruimte opgevuld wordt)
• de operator @= heeft als effect dat geprobeerd wordt een nieuw tapijt in de ruimte te leggen. Het rechteroperand is een tuple van 4 getallen (r, k, dr, dk), namelijk:
  • r het rijnummer van de linkerbovenhoek van een nieuw tapijt
  • k het kolomnummer van de linkerbovenhoek van het nieuwe tapijt
  • dr het aantal rijen dat het tapijt beslaat
  • dk het aantal kolommen dat het tapijt beslaat
  Je mag aannemen dat deze getallen strikt positief zijn en geheel (dus van type int. Er wordt een nieuw tapijt aangebracht op voorwaarde dat:
  • het tapijt binnen de ruimte past als het op de opgegeven positie zou gelegd worden
  • geen enkele van de cellen die door het nieuwe tapijt ingenomen wordt al bezet is door een ander tapijt
  Indien succesvol, wordt de 2D-lijst aangepast met de informatie van het nieuwe tapijt, waarbij dit nieuwe tapijt dus ook een volgnummer toegewezen krijgt. De operator @ kan via de magic function __matmul__(self, other) gerealiseerd worden. De versie @= via __imatmul__(self, other).
• de methode conflicten() kijkt na of er zich in de ruimte situaties voordoen waarbij 4 verschillende tapijten in een hoekpunt samenkomen. Het resultaat is een set van tuples, waarbij elk tuple uit 4 gehele getallen bestaat, die de rangnummers van 4 verschillende tapijten voorstellen die elkaar raken in een hoekpunt. Binnen elk tuple zijn de getallen van klein naar groot geordend.
• de methode opvullen() heeft twee argumenten, namelijk de lengte en breedte van een tapijt. Het is de bedoeling om de gegeven ruimte volledig te vullen met tapijten van die afmetingen (die dus qua oriëntatie horizontaal of verticaal kunnen gelegd worden). De methode levert een lijst op van zoveel mogelijk oplossingen, waarbij elke oplossing gekenmerkt wordt door een 2D-lijst (namelijk de vulling van de ruimte). Oplossingen voldoen hierbij aan:
  • de volledige ruimte wordt opgevuld
  • voor 2 tapijten met rangnummers a en b met a strikt kleiner dan b, geldt:
    • OFWEL ligt de linkerbovenhoek van a boven de linkerbovenhoek van b
    • OFWEL ligt de linkerbovenhoek van a op dezelfde rij als b. In dit geval bevindt de linkerbovenhoek van a zich links van b (dus kleiner kolomnummer)
  Merk op dat in de oplossingen wel degelijk conflicten mogen voorkomen (m.a.w. het is toegelaten dat vier verschillende tapijten in een hoekpunt mekaar raken).
Het Dodona-verbeterscript gebruikt om je oplossing voor opvullen() na te kijken volgende functies:
• check_oplossing(): genereert een lijst van tuples. Per oplossing wordt een tuple gegenereerd met 4 getallen 0 of 1. Een waarde 0 geeft aan dat je oplossing wat dit aspect betreft OK is, een waarde 1 geeft aan dat er iets fout is met je oplossing. De elementen van elk tuple hebben volgende betekenis: betekenis
  • kloppen de dimensies van je oplossing ? (per oplossing een lijst van m elementen, die elk een lijst van n elementen zijn)
  • bevat je oplossing geen lege posities ? (de oplossing mag het getal 0 niet bevatten, anders is er een onbedekte ruimte)
  • is de nummering van de tapijten in je oplossing correct ? (conform de posities van de linkerbovenhoeken)
  • heeft elk tapijt in je oplossing de correcte dimensie ?
  Per oplossing in je lijst van oplossingen, vind je dus idealiter het tuple (0, 0, 0, 0) als resultaat.
• check_dubbels() : kijkt na of je oplossing identieke kopijen bevat (moet dus False opleveren)

Voorbeeld

Tabblad 1

t = Tatami(6, 4)
t @= (3, 0, 3, 2)
print(t) #uitvoer zonder #-teken !
#[0, 0, 0, 0]
#[0, 0, 0, 0]
#[0, 0, 0, 0]
#[1, 1, 0, 0]
#[1, 1, 0, 0]
#[1, 1, 0, 0]
t @= (3, 2, 2, 1)
print(t) #uitvoer zonder #-teken !
#[0, 0, 0, 0]
#[0, 0, 0, 0]
#[0, 0, 0, 0]
#[1, 1, 2, 0]
#[1, 1, 2, 0]
#[1, 1, 0, 0]
for a in [(3, 1, 1, 2), (2, 3, 1, 3), (3, 1, 3, 2)]:
	t @= a
print(t) #uitvoer zonder #-teken !
#[0, 0, 0, 0]
#[0, 0, 0, 0]
#[0, 0, 0, 0]
#[1, 1, 2, 0]
#[1, 1, 2, 0]
#[1, 1, 0, 0]

t = Tatami(6, 4)
t @= (3, 1, 2, 3)
print(t) #uitvoer zonder #-teken !
#[0, 0, 0, 0]
#[0, 0, 0, 0]
#[0, 0, 0, 0]
#[0, 1, 1, 1]
#[0, 1, 1, 1]
#[0, 0, 0, 0]
t @= (1, 2, 1, 1)
print(t) #uitvoer zonder #-teken !
#[0, 0, 0, 0]
#[0, 0, 2, 0]
#[0, 0, 0, 0]
#[0, 1, 1, 1]
#[0, 1, 1, 1]
#[0, 0, 0, 0]
for a in [(2, 1, 1, 1), (0, 2, 3, 3), (1, 0, 1, 3)]:
	t @= a
print(t) #uitvoer zonder #-teken !
#[0, 0, 0, 0]
#[0, 0, 2, 0]
#[0, 3, 0, 0]
#[0, 1, 1, 1]
#[0, 1, 1, 1]
#[0, 0, 0, 0]

Tabblad 2

>>> t = Tatami(8,6)
for tapijt in [(0, 0, 2, 3), (0, 3, 2, 3), (2, 0, 2, 3), (2, 3, 2, 3), (4, 0, 2, 3), (4, 3, 2, 3), (6, 0, 2, 3)]:
	t @= tapijt
print(t) #uitvoer zonder #-teken !
#[1, 1, 1, 2, 2, 2]
#[1, 1, 1, 2, 2, 2]
#[3, 3, 3, 4, 4, 4]
#[3, 3, 3, 4, 4, 4]
#[5, 5, 5, 6, 6, 6]
#[5, 5, 5, 6, 6, 6]
#[7, 7, 7, 0, 0, 0]
#[7, 7, 7, 0, 0, 0]
print(t.conflicten()) #{(3, 4, 5, 6), (1, 2, 3, 4)}

t = Tatami(8,5)# doctest: +NEWCONTEXT
for tapijt in [(0, 0, 2, 1), (0, 1, 2, 1), (0, 2, 2, 1), (0, 3, 1, 2), (1, 3, 1, 2), (2, 0, 2, 1), (2, 1, 1, 2), (2, 3, 2, 1), (2, 4, 2, 1), (3, 1, 1, 2), (4, 0, 2, 1), (4, 1, 2, 1), (4, 2, 1, 2)]:
	t @= tapijt
print(t) #uitvoer zonder #-teken !
#[1, 2, 3, 4, 4]
#[1, 2, 3, 5, 5]
#[6, 7, 7, 8, 9]
#[6, 10, 10, 8, 9]
#[11, 12, 13, 13, 0]
#[11, 12, 0, 0, 0]
#[0, 0, 0, 0, 0]
#[0, 0, 0, 0, 0]
print(t.conflicten()) #{(6, 10, 11, 12), (3, 5, 7, 8), (1, 2, 6, 7)}

Tabblad 3

m = Tatami(8, 6)
opl = m.opvullen(2, 3)
print(sorted(opl))
#[[[1, 1, 1, 2, 2, 2], [1, 1, 1, 2, 2, 2], [3, 3, 3, 4, 4, 4], [3, 3, 3, 4, 4, 4], [5, 5, 5, 6, 6, 6], [5, 5, 5, 6, 6, 6], [7, 7, 7, 8, 8, 8], [7, 7, 7, 8, 8, 8]], [[1, 1, 1, 2, 2, 2], [1, 1, 1, 2, 2, 2], [3, 3, 4, 4, 5, 5], [3, 3, 4, 4, 5, 5], [3, 3, 4, 4, 5, 5], [6, 6, 7, 7, 8, 8], [6, 6, 7, 7, 8, 8], [6, 6, 7, 7, 8, 8]], [[1, 1, 2, 2, 3, 3], [1, 1, 2, 2, 3, 3], [1, 1, 2, 2, 3, 3], [4, 4, 4, 5, 5, 5], [4, 4, 4, 5, 5, 5], [6, 6, 7, 7, 8, 8], [6, 6, 7, 7, 8, 8], [6, 6, 7, 7, 8, 8]], [[1, 1, 2, 2, 3, 3], [1, 1, 2, 2, 3, 3], [1, 1, 2, 2, 3, 3], [4, 4, 5, 5, 6, 6], [4, 4, 5, 5, 6, 6], [4, 4, 5, 5, 6, 6], [7, 7, 7, 8, 8, 8], [7, 7, 7, 8, 8, 8]]]
check_oplossing(opl, 8, 6, 2, 3) #enkel in Dodona!
#[(0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0)]
check_dubbels(opl) #enkel in Dodona!
#False

m = Tatami(6, 8) 
opl = m.opvullen(2, 3)
print(sorted(opl))
#[[[1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 2, 2, 2, 3, 3], [4, 4, 4, 5, 5, 5, 3, 3], [4, 4, 4, 5, 5, 5, 6, 6], [7, 7, 7, 8, 8, 8, 6, 6], [7, 7, 7, 8, 8, 8, 6, 6]], [[1, 1, 1, 2, 2, 3, 3, 3], [1, 1, 1, 2, 2, 3, 3, 3], [4, 4, 4, 2, 2, 5, 5, 5], [4, 4, 4, 6, 6, 5, 5, 5], [7, 7, 7, 6, 6, 8, 8, 8], [7, 7, 7, 6, 6, 8, 8, 8]], [[1, 1, 2, 2, 2, 3, 3, 3], [1, 1, 2, 2, 2, 3, 3, 3], [1, 1, 4, 4, 4, 5, 5, 5], [6, 6, 4, 4, 4, 5, 5, 5], [6, 6, 7, 7, 7, 8, 8, 8], [6, 6, 7, 7, 7, 8, 8, 8]], [[1, 1, 2, 2, 3, 3, 4, 4], [1, 1, 2, 2, 3, 3, 4, 4], [1, 1, 2, 2, 3, 3, 4, 4], [5, 5, 6, 6, 7, 7, 8, 8], [5, 5, 6, 6, 7, 7, 8, 8], [5, 5, 6, 6, 7, 7, 8, 8]]]
check_oplossing(opl, 6, 8, 2, 3) #enkel in Dodona!
#[(0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0)]
check_dubbels(opl) #enkel in Dodona!
#False