Je krijgt een reeks balkvormige dozen met dimensies (lengte, breedte, hoogte). Die dozen kunnen vrij geroteerd worden, zodat er eigenlijk 6 3-tallen met elke doos overeenkomen. We beschouwen enkel de oriëntaties waarbij $$lengte <= breedte $$ zodat je per fysieke doos hoogstens drie verschillende oriëntaties kan beschouwen.

Het probleem dat zich stelt is een zo hoog mogelijke toren te bouwen, waarbij het grondvlak van elke doos binnen het topvlak van de doos eronder past (m.a.w. lengte en breedte van het grondvlak van de bovenste doos zijn strikt kleiner dat resp. lengte en breedte van het topvlak van de doos eronder).

In deze oefening bouwen we een aantal klassen om dit stapelprobleem op te lossen via een aantal verschillende strategiëen.

Klasse Doos

Een fysieke door wordt gekenmerkt door 3 dimensies, namelijk lengte, breedte en hoogte. Programmeer in deze klasse:

• een constructor met 3 argumenten (alle geheel en strikt positief), namelijk lengte, breedte en hoogte. Je mag er NIET vanuit gaan dat $$lengte <= breedte$$, maar bij opslag in een object zorg je ervoor dat $$lengte <= breedte$$ (m.a.w. je draait in gedachten de doos over 90 graden).
• de methode `__str__()` levert lengte, breedte en hoogte van de doos, gescheiden door komma's en omringd door rechte haakjes (geen spaties).
• de operater < in de uitdrukking a < b (met a en b beide objecten van de klasse Doos levert True indien doos a in een stapel ONDER doos b kan staan. De operator levert False in het andere geval.
• de operator * in de uitdrukking a * i met a een object van de klasse Doos en $$i$$ een geheel getal gelijk aan 0, 1 of 2 levert altijd een nieuwe Doos namelijk:
  • indien $$i == 0$$ : een kopie van de doos a
  • indien $$i == 1$$ : een geroteerde versie van de doos a waarbij de originele lengte van a nu de hoogte van de nieuwe doos wordt (en de andere dimensies van de originele doos dus lengte en breedte van de nieuwe doos)
  • indien $$i == 2$$ : een geroteerde versie van de doos a waarbij de originele breedte van a nu de hoogte van de nieuwe doos wordt (en de andere dimensies van de originele doos dus lengte en breedte van de nieuwe doos)
  Zorg ervoor dat bij het resultaat (de nieuwe doos) nog steeds geldt dat $$lengte <= breedte$$.

Voorbeeld

doos1 = Doos(1, 4, 3)
doos2 = Doos(10, 8, 7)
print(doos1) #[1,4,3]
print(doos2) #[8,10,7]
doos1 < doos2 #False
doos2 < doos1 #True
print(doos1*0) #[1,4,3]
print(doos1*1) #[3,4,1]
print(doos1*2) #[1,3,4]

Klasse StapelProbleem

Een object van deze klasse stelt een probleemstelling voor, gekenmerkt door de dozen die kunnen gestapeld worden. Programmeer in deze klasse:

• een constructor zonder argumenten
• de methode `__str__()` levert als stringgedaante '(aantal_dozen,[doos0,doos1,...])', dus het aantal dozen in het probleem (geheel getal), gevolgd door een komma, en dit gevolgd door de stringgedaante van alle dozen. Deze stringgedaantes zijn gescheiden door komma's en gevat tussen vierkante haakjes. Het gehaal is gevat tussen ronde haakjes.
• de operator += in de uitddrukking a += d met a een object van de klasse StapelProbleem heeft als effect:
  • indien d een object van de klasse Doos is, wordt deze doos aan het probleem toegevoegd
  • indien d een tuple is, dan mag je onderstellen dat het gaat om een tuple met 3 componenten, namelijk getallen geschikt om aan de constructor van de klasse Doos toe te leveren, en een nieuwe doos te construeren.
  De volgorde van toevoegen is belangrijk (o.a. voor de stringgedaante van het probleem, waarin de dozen in volgorde van toevoegen weergegeven worden).
• de methode geldige_stapel() heeft twee argumenten, namelijk:
  • een lijst van gehele getallen, die rangnummers voorstellen van dozen van het probleem (rangnummer conform de volgorde van toevoegen van de dozen aan het probleem)
  • een lijst gehele getallen, allen 0, 1 of 2, die een rotatie van de gelijkstandige doos uit het eerste argument weergeven
  De methode levert True als resultaat, indien het om een geldige stapeling gaat. Dit is het geval indien tegelijk voldaan is aan:
  • het eerste argument bevat geen dubbels
  • alle waarden van het eerste argument zijn geldige waarden
  • de stapeling is correct, m.a.w. het grondvlak van een doos die boven een ander staat past binnen het bovenvlak van die andere doos, waarbij de rotaties uit het tweede argument in rekening gebracht worden.
  Het resultaat van de methode is False in alle andere gevallen. (Je mag aannemen dat het tweede argument geldige waarden bevat en de correcte lengte heeft).
• de methode hoogte() heeft 2 argumenten, identiek qua type en betekenis aan de methode geldige_stapel() en levert een geheel getal als resultaat, namelijk:
  • de waarde -1 indien de stapeling ongeldig is
  • de hoogte van de totale stapeling indien deze wel geldig is
• de methode zoek_stapel() heeft 1 argument, namelijk een object over een methode bouw_stapel() beschikt. Het enige argument van de methode bouw_stapel() is een object van de klasse StapelProbleem. Het resultaat van de methode zoek_stapel() is een tuple van 2 lijsten. De eerste lijst is een lijst van rangnummers (verwijzend naar een doos van het probleem), en de tweede lijst bestaat uit gehele getallen 0, 1 of 2 (evenveel elementen als de eerste lijst). Deze laatste lijst bevat de rotaties die moeten toegepast worden op de gelijkstandige dozen van de eerste lijst om de stapel te vormen. Deze lijsten worden verkregen door beroep te doen op de methode bouw_stapel() van het argument van de methode zoek_stapel() (zie verder).

Voorbeeld

sp = StapelProbleem()
for (l, b, h) in zip([8, 15, 4],[17, 11, 16],[9, 11, 9]):
	sp += Doos(l, b, h)
print(sp) #(3,[[8,17,9],[11,15,11],[4,16,9]])
for (l, b, h) in zip([18, 18, 19],[10, 15, 12],[15, 12, 14]):
	sp += (l, b, h)
print(sp) #(6,[[8,17,9],[11,15,11],[4,16,9],[10,18,15],[15,18,12],[12,19,14]])
sp.geldige_stapel([2, 5], [2, 1]) #False
sp.hoogte([2, 5], [2, 1]) #-1
sp.geldige_stapel([4, 5, 1, 0], [0, 2, 2, 2]) #True
sp.hoogte([4, 5, 1, 0], [0, 2, 2, 2]) #63
sp.geldige_stapel([4, 1], [0, 0]) #True
sp.hoogte([4, 1], [0, 0]) #23

Elk van onderstaande klassen beschikt over de methode bouw_stapel() met als enig argument een object van de klasse StapelProbleem. Het resultaat van de methode is een oplossing van het stapelprobleem, verkregen door toepassing van een welbepaalde strategie (zie beschrijving van de klassen zelf). Het resultaat van de methode bouw_stapel() is een tuple, bestaande uit twee lijsten (dit zijn de lijsten zoals beschreven in de methode zoek_stapel() van de klasse StapelProbleem). De strategieën EenvoudigeStrategie en SorteerStrategie leveren een oplossing waarbij de dozen in hun originele stand gebruikt worden (de 2de lijst bestaat dus steeds enkel uit nullen). In de strategie RoteerSorteerStrategie worden ook andere standen van de dozen beschouwd.

De tekst hieronder beschrijft telkens de te volgen strategie bij het genereren van oplossingen voor het stapelprobleem.

Klasse EenvoudigeStrategie

Beschouw de dozen in de volgorde en stand waarin ze toegevoegd werden aan het probleem. Start bij de eerste doos, en probeer alle dozen te stapelen in de volgorde waarin ze toegevoegd werden. Sla dozen die niet passen over.

Klasse SorteerStrategie

Sorteer de dozen volgens dalende oppervlakte van hun grondvlak, in de stand waarin ze toegevoegd werden (voor gelijke oppervlakten wordt de originele ordening gerespecteerd). Pas dezelfde strategie als in de klasse EenvoudigeStrategie toe op de dozen, in deze aangepaste volgorde. Let erop dat rangnummers in het resultaat verwijzen naar de ORIGINELE volgorde van de dozen.

Klasse RoteerSorteerStrategie

Bouw een lijst van alle mogelijke standen van elke doos, en sorteer deze lijst (die dus 3x meer dozen bevat) volgens hetzelfde criterium als in de klasse SorteerStrategie vermeld. Bouw nu een stapel, gebruik makend van dezelfde aanpak (dus probeer de dozen in deze nieuwe volgorde te stapelen, en sla dozen over die niet passen). Hierbij moet je ervoor zorgen dat elke doos maar 1 keer gebruikt kan worden: zodra je een doos gebruikt hebt in de stapeling, kan je geroteerde versies van diezelfde doos (die eventueel verderop in de lijst voorkomen) niet meer gebruiken.

Voorbeeld

sp = StapelProbleem()
for (l, b, h) in zip([9, 14, 17, 20, 16, 4, 16],[20, 7, 6, 19, 7, 15, 4],[8, 16, 7, 18, 17, 11, 10]):
	sp += Doos(l, b, h)
print(sp) #(7,[[9,20,8],[7,14,16],[6,17,7],[19,20,18],[7,16,17],[4,15,11],[4,16,10]])
eenvoudig = EenvoudigeStrategie()
eenvoudig.bouw_stapel(sp) #([0, 1], [0, 0])
sorteer = SorteerStrategie()
sorteer.bouw_stapel(sp) #([3, 4, 5], [0, 0, 0])
roteer_sorteer = RoteerSorteerStrategie()
roteer_sorteer.bouw_stapel(sp) #([3, 4, 1, 5, 0, 2], [0, 1, 1, 1, 2, 2])
sp.zoek_stapel(eenvoudig) #([0, 1], [0, 0])
sp.zoek_stapel(sorteer) #([3, 4, 5], [0, 0, 0])
sp.zoek_stapel(roteer_sorteer) #([3, 4, 1, 5, 0, 2], [0, 1, 1, 1, 2, 2])