Een nonogram is een Japanse beeldpuzzel waarbij een verborgen afbeelding moet gevonden worden. Deze afbeelding kan gevormd worden door de vakjes van een rechthoekig rooster zwart of wit te kleuren, rekening houdend met de reeks natuurlijke getallen die voor elke rij en elke kolom van het rooster wordt opgegeven. Deze getallen geven aan hoeveel opeenvolgende zwarte vakjes er op die rij of kolom staan. Als de opgave bijvoorbeeld de getallenreeks 4 8 3 aangeeft, betekent dit dat de rij of kolom bestaat uit reeksen van vier, acht en drie opeenvolgende zwarte vakjes, in die volgorde, en dat er minstens één wit vakje staat tussen elk van deze opeenvolgende reeksen.

Opgave

Voor deze opgave moet je een vereenvoudigde versie van de nonogrampuzzel oplossen. Zoals bij de originele puzzel worden voor elke rij de reeksen opeenvolgende zwarte vakjes opgegeven. De omschrijving voor de kolommen hebben we echter niet langer nodig. Elke reeks opeenvolgende zwarte vakjes wordt nu immers omschreven door een koppel natuurlijke getallen $$(s, l)$$, waarbij $$s$$ en $$l$$ respectievelijk de startpositie en de lengte van de reeks aangeven. Het meest linkse vakje van van een rij staat hierbij op positie nul.

Merk op dat de volgorde waarin de reeksen opeenvolgende zwarte vakjes worden opgegeven nu niet langer een rol speelt. Een rij van een nonogrampuzzel kan dus omschreven worden door een container (een lijst, tuple, verzameling, …) van tuples. Elk van deze tuples bestaat dan uit twee natuurlijke getallen die respectievelijk de startpositie en de lengte van de reeks opeenvolgende zwarte vakjes aangeven. Gevraagd wordt:

• Schrijf een functie breedte waaraan de omschrijving van een rij van een nonogrampuzzel moet doorgegeven worden. De functie moet als resultaat de minimale breedte van die rij teruggeven. De minimale breedte is het minimaal aantal vakjes dat de rij moet hebben, zodat alle vakjes uit de omschrijving zwart gemaakt kunnen worden.

• Schrijf een functie regel waaraan de omschrijving van een rij van een nonogrampuzzel moet doorgegeven worden. De functie moet de stringvoorstelling van deze regel teruggeven, waarbij witte vakjes worden voorgesteld door spaties en zwarte vakjes door hekjes (#). De functie heeft een tweede optionele parameter waaraan het aantal vakjes op de rij kan doorgegeven worden. Indien geen waarde wordt doorgegeven aan deze parameter, dan moet de minimale breedte van de rij gebruikt worden zoals bepaald door de functie breedte.

• Schrijf een functie nonogram waaraan de locaties van twee tekstbestanden moeten doorgegeven worden. Het eerste tekstbestand bevat de opgave van een nonogrampuzzel. Elke regel van het bestand omschrijft de corresponderende regel van de verborgen afbeelding. Deze omschrijving bestaat uit koppels natuurlijke getallen: elk koppel bestaat uit twee natuurlijke getallen, van elkaar gescheiden door een komma en ingesloten tussen ronde haakjes. De koppels zelf worden telkens van elkaar gescheiden door een puntkomma. Behalve tussen de cijfers van eenzelfde natuurlijk getal, mogen binnen de omschrijving voorts op elke plaats spaties staan. Het eerste en tweede getal van elk koppel geven respectievelijk de startpositie en de lengte aan van een reeks opeenvolgende zwarte vakjes op de regel van de afbeelding.
  De functie moet de verborgen afbeelding die omschreven wordt door de opgave van de nonogrampuzzel wegschrijven naar een nieuw tekstbestand, waarvan de locatie als tweede argument aan de functie werd doorgegeven. Elke regel van de afbeelding moet hierbij gegenereerd worden door de functie regel, op basis van de corresponderende omschrijving uit de opgave van de puzzel. De breedte van de afbeelding wordt bepaald als de grootst mogelijke minimale breedte van alle rijen die in de opgave van de nonogrampuzzel omschreven worden.

Voorbeeld

Bij onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand domoor.puzzel.txt zich in de huidige directory bevindt. Klik op de naam van het oplossingsbestand om de oplossing te bekijken die voor deze puzzel moet gegenereerd worden.

>>> breedte([(2, 12)])
14
>>> breedte(((1, 3), (7, 2), (12, 3)))
15
>>> breedte({(10, 5), (1, 2), (5, 3)})
15

>>> regel([(2, 12)])
'  ############'
>>> regel(((1, 3), (7, 2), (12, 3)), 20)
' ###   ##   ###     '
>>> regel({(10, 5), (1, 2), (5, 3)})
' ##  ###  #####'

>>> nonogram('domoor.puzzel.txt', 'domoor.oplossing.txt')