Intro

Een matroesjka (Russisch: Матрёшка) is een holle houten pop die onderdeel is van een reeks steeds kleinere in elkaar passende poppen. De poppen kunnen opengemaakt worden met een naad in de “buik”, behalve het kleinste, dat vaak als baby is beschilderd. Een matroesjka bestaat doorgaans uit zeven of acht poppetjes, maar ook andere aantallen komen voor. De prijs van de poppen is afhankelijk van het aantal poppetjes in de set (variërend van vier tot enkele tientallen), de kwaliteit van de afbeelding en de onderwerpen. Het zijn geliefde souvenirs bij de toeristen die Rusland bezoeken.

Er bestaat een hele variëteit aan Matroesjka’s¹. Het is dus ook mogelijk, maar zeker niet de bedoeling, om Matroesjka’s van verschillende typen in elkaar te steken om de eigenaar grondig te ergeren.

Opgave

Schrijf een predicaat ma_clean(+Mess, -Order) die een lijst van mogelijk verkeerd samengestelde Matroesjka’s neemt en een gesorteerde lijst van correct samengestelde Matroesjka’s teruggeeft.

Voorstelling van de poppen

Een pop van het type Type met grootte Grootte waarin een andere pop Kind zit wordt voorgesteld als: ma(Eigenschappen, Kind). Waarbij Eigenschappen een lijst is met daarin exact 1 voorkomen van type(Type) en size(Grootte). Deze lijst kan ook nog andere elementen bevatten, maar dat is niet belangrijk voor deze opgave. Als een pop geen kind heeft wordt empty gebruikt als Kind

Voorbeeld

De afbeelding boven de pijl in bovenstaande afbeelding kan gezien worden als

[
  ma([type(rood),size(4)], ma([type(groen),size(3)], empty) ),
  ma([size(3),type(blauw)], ma([size(2),type(geel)], empty) ),
  ma([type(geel),size(4)], ma([type(geel),size(3)], ma([type(rood),size(2)],empty)) ),
  ma([type(blauw),size(4)], ma([type(groen),size(2)], empty) ),
]

Deze moet omgezet worden in

[
  ma([type(blauw),size(4)],ma([size(3),type(blauw)],empty)),
  ma([type(geel),size(4)],ma([type(geel),size(3)],ma([size(2),type(geel)],empty))),
  ma([type(groen),size(3)],ma([type(groen),size(2)],empty)),
  ma([type(rood),size(4)],ma([type(rood),size(2)],empty))
]

Hint

Als hulp kun je gebruik maken van het vergelijkingspredicaat ma_order(-Pred, +Pop1, +Pop2) dat voor jullie is gedefinieerd is in deze database². Om dit predicaat te kunnen gebruiken moet je zelfma_type(+Pop,-Type) en ma_size(+Pop,-Grote) implementeren die respectievelijk het type en de grootte een pop ophalen. Deze ma_order/3 zal interessant blijken in combinatie met predsort/3³. Pas ma_order/3 niet aan, je hoeft het ook niet mee in te dienen.