Gegeven bouwblokken van lengte a en b wensen we een muur te bouwen die uit een aantal bouwlagen bestaat. Elke laag heeft hierbij dezelfde breedte. Bouw een klasse BouwProbleem, en programmeer in het bijzonder:

• een constructor met 3 argumenten, namelijk de lengte van de blokken a en b en de breedte n van de te bouwen muur. Alle argumenten zijn geheel en strikt positief.
• een methode __str__() levert volgende string-gedaante [a,b,n] (dus de constructor-argumenten, gescheiden door komma's en omringd door vierkante haakjes, geen spaties, alle getallen worden in het int-formaat afgedrukt (dus %d als formaatstring)
• de operator += heeft het volgend effect:
  • indien het rechteroperand een lijst van gehele getallen is, wordt die lijst als nieuwe bouwlaag toegevoegd, op voorwaarde dat:
    • de lijst enkel de getallen a en b bevat
    • de gerealiseerde breedte overeenstemt met n
    Voldoet het rechteroperand niet, dan heeft de operator geen effect.
  • indien het rechteroperand een object is van het type BouwProbleem dan worden alle lagen van dit rechteroperand toegevoegd aan het linkeroperand, op voorwaarde dat de grootte gebruikte blokken overeenstemmen (zelfde lengtes als de bouwblokken van het linkeroperand) en de breedte van de lagen eveneens overeenstemmen. Is dit niet het geval, dan heeft de operator geen effect.
  • indien het rechteroperand van een ander type is dan hierboven aangegeven, dan heeft de operator geen effect.
• de methode lagen() levert de lagen van het bouwprobleem op, als een lijst-van-lijsten. Elke element stelt hierbij een succesvol toegevoegde laag als lijst voor, in de volgorde waarin ze aan het probleem toegevoegd werd.
• een bouwwerk is pas stevig als er geen naden in het bouwwerk voorkomen. We willen m.a.w. vermijden dat in 2 aanliggende lagen de randen van bouwblokken samenvallen (behalve uiteraard het begin- en eindpunt van de muur). Wanneer dit wel het geval is, spreken we van een conflict. Schrijf de methode conflicten() die een lijst van tuples teruggeeft. Elk tuple betreft een koppel aanliggende lagen waartussen minstens 1 conflict optreedt, en bevat 2 gehele getallen, namelijk:
  • het rangnummer van de onderste laag die een conflict genereert met de laag net erboven
  • een geheel getal dat het aantal conflicten (dus het aantal samenvallende randen op begin- en eindpunt van de muur na) aangeeft
  Deze lijst is opklimmend volgens het eerste tuple-element gesorteerd.
• de methode mogelijke_lagen() genereert alle mogelijke lagen om met de gegeven bouwblokken een laag van gewenste breedte te bouwen. Het resultaat is een lijst van lijsten, waarbij elk element een laag voorstelt via een lijst (die enkel uit de getallen a en b bestaat).
• de methode alle_oplossingen() heeft als enig argument een strikt positief geheel getal h. In de methode worden zoveel mogelijk verschillende oplossingen bepaald om met de gegeven probleemparameters (grootte van de blokken en breedte van de muur, aanliggende lagen vertonen geen naden) een muur te bouwen die precies h lagen hoog is. Het resultaat van deze methode is een lijst van 2D-lijsten, en elk van die 2D-lijsten stelt een oplossing van het bouwprobleem voor. Een dergelijke oplossing is dus een lijst-van-lijsten, waarbij elke lijst een laag voorstelt. (Een dergelijke laaglijst bevat dus enkel de getallen a en b).

Voorbeeld

Tabblad 1

m = BouwProbleem(3, 5, 21)
print(m) #[3,5,21]
m += [5, 5, 3, 5, 3]
print(m.lagen()) #[[5, 5, 3, 5, 3]]
m += [5, 5, 3, 5, 3]
print(m.lagen()) #[[5, 5, 3, 5, 3], [5, 5, 3, 5, 3]]

b = BouwProbleem(3, 5, 21)
for laag in [[5, 3, 5, 5, 3]]:
	b += laag
print(b.lagen()) #[[5, 3, 5, 5, 3]]

m += b
print(m.lagen()) #[[5, 5, 3, 5, 3], [5, 5, 3, 5, 3], [5, 3, 5, 5, 3]]

for laag in  [3, [5, 5, 5, 3, 5]]:
	m += laag
print(m.lagen()) #[[5, 5, 3, 5, 3], [5, 5, 3, 5, 3], [5, 3, 5, 5, 3]]'




m = BouwProbleem(3, 4, 20)
print(m) #[3,4,20]

m += [3, 3, 4, 4, 3, 3]
print(m.lagen()) #[[3, 3, 4, 4, 3, 3]]
m += 10
print(m.lagen()) #[[3, 3, 4, 4, 3, 3]]

b = BouwProbleem(3, 4, 20)
for laag in [[4, 3, 3, 3, 3]]:
	b += laag
print(b.lagen()) #[]

m += b
print(m.lagen()) #[[3, 3, 4, 4, 3, 3]]
for laag in  [[4, 4, 3, 3, 3, 3], 2, [3, 4, 4, 5, 3, 3]]:
	m += laag
print(m.lagen()) #[[3, 3, 4, 4, 3, 3], [4, 4, 3, 3, 3, 3]]

Tabblad 2

m = BouwProbleem(2, 3, 9)
for laag in [[3, 2, 2, 2], [2, 2, 2, 3], [2, 2, 3, 2], [2, 2, 2, 3], [3, 3, 3]]:
	m += laag
print(m.lagen()) #[[3, 2, 2, 2], [2, 2, 2, 3], [2, 2, 3, 2], [2, 2, 2, 3], [3, 3, 3]]
print(m.conflicten()) #[(1, 2), (2, 2), (3, 1)]
print(sorted(m.mogelijke_lagen())) #[[2, 2, 2, 3], [2, 2, 3, 2], [2, 3, 2, 2], [3, 2, 2, 2], [3, 3, 3]]


m = BouwProbleem(3, 2, 18)
for laag in [[2, 3, 2, 3, 2, 2, 2, 2], [2, 2, 3, 2, 3, 2, 2, 2], [2, 2, 2, 2, 3, 3, 2, 2], [2, 2, 3, 3, 3, 2, 3]]:
	m += laag
print(m.lagen()) #[[2, 3, 2, 3, 2, 2, 2, 2], [2, 2, 3, 2, 3, 2, 2, 2], [2, 2, 2, 2, 3, 3, 2, 2], [2, 2, 3, 3, 3, 2, 3]]
print(m.conflicten()) #[(0, 5), (1, 4), (2, 2)]
print(sorted(m.mogelijke_lagen())) #[[2, 2, 2, 2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 2, 2, 3, 3], [2, 2, 2, 2, 2, 3, 2, 3], [2, 2, 2, 2, 2, 3, 3, 2], [2, 2, 2, 2, 3, 2, 2, 3], [2, 2, 2, 2, 3, 2, 3, 2], [2, 2, 2, 2, 3, 3, 2, 2], [2, 2, 2, 3, 2, 2, 2, 3], [2, 2, 2, 3, 2, 2, 3, 2], [2, 2, 2, 3, 2, 3, 2, 2], [2, 2, 2, 3, 3, 2, 2, 2], [2, 2, 2, 3, 3, 3, 3], [2, 2, 3, 2, 2, 2, 2, 3], [2, 2, 3, 2, 2, 2, 3, 2], [2, 2, 3, 2, 2, 3, 2, 2], [2, 2, 3, 2, 3, 2, 2, 2], [2, 2, 3, 2, 3, 3, 3], [2, 2, 3, 3, 2, 2, 2, 2], [2, 2, 3, 3, 2, 3, 3], [2, 2, 3, 3, 3, 2, 3], [2, 2, 3, 3, 3, 3, 2], [2, 3, 2, 2, 2, 2, 2, 3], [2, 3, 2, 2, 2, 2, 3, 2], [2, 3, 2, 2, 2, 3, 2, 2], [2, 3, 2, 2, 3, 2, 2, 2], [2, 3, 2, 2, 3, 3, 3], [2, 3, 2, 3, 2, 2, 2, 2], [2, 3, 2, 3, 2, 3, 3], [2, 3, 2, 3, 3, 2, 3], [2, 3, 2, 3, 3, 3, 2], [2, 3, 3, 2, 2, 2, 2, 2], [2, 3, 3, 2, 2, 3, 3], [2, 3, 3, 2, 3, 2, 3], [2, 3, 3, 2, 3, 3, 2], [2, 3, 3, 3, 2, 2, 3], [2, 3, 3, 3, 2, 3, 2], [2, 3, 3, 3, 3, 2, 2], [3, 2, 2, 2, 2, 2, 2, 3], [3, 2, 2, 2, 2, 2, 3, 2], [3, 2, 2, 2, 2, 3, 2, 2], [3, 2, 2, 2, 3, 2, 2, 2], [3, 2, 2, 2, 3, 3, 3], [3, 2, 2, 3, 2, 2, 2, 2], [3, 2, 2, 3, 2, 3, 3], [3, 2, 2, 3, 3, 2, 3], [3, 2, 2, 3, 3, 3, 2], [3, 2, 3, 2, 2, 2, 2, 2], [3, 2, 3, 2, 2, 3, 3], [3, 2, 3, 2, 3, 2, 3], [3, 2, 3, 2, 3, 3, 2], [3, 2, 3, 3, 2, 2, 3], [3, 2, 3, 3, 2, 3, 2], [3, 2, 3, 3, 3, 2, 2], [3, 3, 2, 2, 2, 2, 2, 2], [3, 3, 2, 2, 2, 3, 3], [3, 3, 2, 2, 3, 2, 3], [3, 3, 2, 2, 3, 3, 2], [3, 3, 2, 3, 2, 2, 3], [3, 3, 2, 3, 2, 3, 2], [3, 3, 2, 3, 3, 2, 2], [3, 3, 3, 2, 2, 2, 3], [3, 3, 3, 2, 2, 3, 2], [3, 3, 3, 2, 3, 2, 2], [3, 3, 3, 3, 2, 2, 2], [3, 3, 3, 3, 3, 3]]

Tabblad 3

m = BouwProbleem(2, 3, 9)
print(sorted(m.alle_oplossingen(3))) #[[[2, 2, 2, 3], [3, 2, 2, 2], [2, 2, 2, 3]], [[2, 2, 3, 2], [3, 3, 3], [2, 2, 3, 2]], [[2, 2, 3, 2], [3, 3, 3], [2, 3, 2, 2]], [[2, 3, 2, 2], [3, 3, 3], [2, 2, 3, 2]], [[2, 3, 2, 2], [3, 3, 3], [2, 3, 2, 2]], [[3, 2, 2, 2], [2, 2, 2, 3], [3, 2, 2, 2]], [[3, 3, 3], [2, 2, 3, 2], [3, 3, 3]], [[3, 3, 3], [2, 3, 2, 2], [3, 3, 3]]]

m = BouwProbleem(2, 5, 19)
print(sorted(m.alle_oplossingen(1))) #[[[2, 2, 2, 2, 2, 2, 2, 5]], [[2, 2, 2, 2, 2, 2, 5, 2]], [[2, 2, 2, 2, 2, 5, 2, 2]], [[2, 2, 2, 2, 5, 2, 2, 2]], [[2, 2, 2, 5, 2, 2, 2, 2]], [[2, 2, 5, 2, 2, 2, 2, 2]], [[2, 2, 5, 5, 5]], [[2, 5, 2, 2, 2, 2, 2, 2]], [[2, 5, 2, 5, 5]], [[2, 5, 5, 2, 5]], [[2, 5, 5, 5, 2]], [[5, 2, 2, 2, 2, 2, 2, 2]], [[5, 2, 2, 5, 5]], [[5, 2, 5, 2, 5]], [[5, 2, 5, 5, 2]], [[5, 5, 2, 2, 5]], [[5, 5, 2, 5, 2]], [[5, 5, 5, 2, 2]]]