Eind jaren '80 bedachten de Japanners Non Ishida en Tetsuya Nishio een zeer uitdagende vorm van logische puzzels. De eerste bedenker — Non Ishida — was een grafisch vormgever en het is ook naar haar dat deze grafische puzzels vernoemd werden: nonogrammen.

De opgave van een nonogram met twee kleuren (links) en de unieke oplossing voor de puzzel (rechts).

Een nonogram bestaat uit een rechthoekig rooster waarvan de vakjes bij aanvang wit zijn. Door sommige vakjes in te kleuren en andere wit te laten, werk je stap voor stap naar een oplossing die er bovendien als een mooie tekening uitziet.

Links van elke rij en boven elke kolom staat een aanwijzing die bestaat uit een reeks gekleurde getallen. Meer heb je niet nodig om de puzzel op te lossen. Gokken hoef je nooit te doen. Dat mag ook niet! Logisch nadenken volstaat.

Elk gekleurd getal in een aanwijzing staat voor een aantal opeenvolgende vakjes in de aangegeven kleur. Zo geeft de aanwijzing 4 8 3 aan dat de rij (van links naar rechts) of kolom (van boven naar onder) bestaat uit een reeks van vier opeenvolgende groene vakjes, acht opeenvolgende paarse vakjes en drie opeenvolgende groene vakjes. Voor, tussen en na de reeksen opeenvolgende gekleurde vakjes kunnen telkens nul of meer witte vakjes staan.

Opgave

We nemen een tekstbestand met een ASCII-tekening om een kerstpuzzel mee te maken onder de vorm van een nonogram. Alle regels van het tekstbestand bevatten evenveel karakters. Spaties stellen witte vakjes voor. Alle andere karakters stellen gekleurde vakjes voor: elk verschillend karakter is een verschillende kleur. Bijvoorbeeld (nonogram.txt¹):

          .     .  .      +     .      .          .         
     .       .      .     #       .           .             
        .      .         ###            .      .      .     
      .      .   "#:. .:##"##:. .:#"  .      .              
          .      . "####"###"####"  .                       
       .     "#:.    .:#"###"#:.    .:#"  .        .       .
  .             "#########"#########"        .        .     
        .    "#:.  "####"###"####"  .:#"   .       .        
     .     .  "#######""##"##""#######"                  .  
                ."##"#####"#####"##"           .      .     
    .   "#:. ...  .:##"###"###"##:.  ... .:#"     .         
      .     "#######"##"#####"##"#######"      .     .      
    .    .     "#####""#######""#####"    .      .          
            .     "      000      "    .     .              
       .         .   .   000     .        .       .         
.. .. ..................O000O........................ ......

Jouw opdracht bestaat erin om aanwijzingen te bepalen voor alle rijen en kolommen van een nonogram die de ASCII-tekening als oplossing heeft. Omdat we niet met kleuren werken, wordt een reeks gelijke karakters voorgesteld door de lengte van de reeks gevolgd door het karakter. Zo stelt 6# een reeks van zes opeenvolgende hekjes (#) voor en stelt 1. één punt (.) voor dat niet wordt voorafgegaan of gevolgd door een ander punt. We stellen een aanwijzing voor als een lijst (list) met de voorstellingen (str) van de gekleurde reeksen op een rij (opgelijst van links naar rechts) of een kolom (opgelijst van boven naar onder). De kerstpuzzel met aanwijzingen voor bovenstaande ASCII-tekening ziet er dan bijvoorbeeld als volgt uit (klik hier om de oplossing van de puzzel te bekijken):

De opgave van onze nonogram-kerstpuzzel.

Gevraagd wordt:

Schrijf een functie aanwijzing waaraan een rij/kolom (str) uit een ASCII-tekening moet doorgegeven worden. De functie moet de aanwijzing voor de gegeven rij/kolom teruggeven.
Schrijf een functie rij_aanwijzingen waaraan de locatie (str) van een tekstbestand met een ASCII-tekening moet doorgegeven worden. De functie moet een lijst (list) met aanwijzingen voor alle rijen van de ASCII-tekening (opgelijst van boven naar onder) teruggeven.
Schrijf een functie kolom_aanwijzingen waaraan de locatie (str) van een tekstbestand met een ASCII-tekening moet doorgegeven worden. De functie moet een lijst (list) met aanwijzingen voor alle kolommen van de ASCII-tekening (opgelijst van links naar rechts) teruggeven.
Schrijf een functie isoplossing waaraan drie argumenten moeten doorgegeven worden: i) de locatie (str) van een tekstbestand met een ASCII-tekening, ii) een lijst (list) met aanwijzingen voor de rijen van een nonogram (opgelijst van boven naar onder) en iii) een lijst (list) met aanwijzingen voor de kolommen van een nonogram (opgelijst van links naar rechts). De functie moet een Booleaanse waarde (bool) teruggeven, die aangeeft of de gegeven ASCII-tekening een oplossing is voor een nonogram met de gegeven aanwijzingen.

Voorbeeld

In onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand nonogram.txt² zich in de huidige directory bevindt.

        >>> aanwijzing('ABBCCCDDDDEEEFFG')
['1A', '2B', '3C', '4D', '3E', '2F', '1G']
>>> aanwijzing(' A  BB   CCC    DDDD    EEE   FF  G ')
['1A', '2B', '3C', '4D', '3E', '2F', '1G']
>>> aanwijzing('          .      . "####"###"####"  .                       ')
['1.', '1.', '1"', '4#', '1"', '3#', '1"', '4#', '1"', '1.']
>>> aanwijzing('.. .. ..................O000O........................ ......')
['2.', '2.', '18.', '1O', '30', '1O', '24.', '6.']

>>> rijen = rij_aanwijzingen('nonogram.txt3')
>>> rijen
[['1.', '1.', '1.', '1+', '1.', '1.', '1.'], ['1.', '1.', '1.', '1#', '1.', '1.'], ['1.', '1.', '3#', '1.', '1.', '1.'], ['1.', '1.', '1"', '1#', '1:', '1.', '1.', '1:', '2#', '1"', '2#', '1:', '1.', '1.', '1:', '1#', '1"', '1.', '1.'], ['1.', '1.', '1"', '4#', '1"', '3#', '1"', '4#', '1"', '1.'], ['1.', '1"', '1#', '1:', '1.', '1.', '1:', '1#', '1"', '3#', '1"', '1#', '1:', '1.', '1.', '1:', '1#', '1"', '1.', '1.', '1.'], ['1.', '1"', '9#', '1"', '9#', '1"', '1.', '1.'], ['1.', '1"', '1#', '1:', '1.', '1"', '4#', '1"', '3#', '1"', '4#', '1"', '1.', '1:', '1#', '1"', '1.', '1.'], ['1.', '1.', '1"', '7#', '2"', '2#', '1"', '2#', '2"', '7#', '1"', '1.'], ['1.', '1"', '2#', '1"', '5#', '1"', '5#', '1"', '2#', '1"', '1.', '1.'], ['1.', '1"', '1#', '1:', '1.', '3.', '1.', '1:', '2#', '1"', '3#', '1"', '3#', '1"', '2#', '1:', '1.', '3.', '1.', '1:', '1#', '1"', '1.'], ['1.', '1"', '7#', '1"', '2#', '1"', '5#', '1"', '2#', '1"', '7#', '1"', '1.', '1.'], ['1.', '1.', '1"', '5#', '2"', '7#', '2"', '5#', '1"', '1.', '1.'], ['1.', '1"', '30', '1"', '1.', '1.'], ['1.', '1.', '1.', '30', '1.', '1.', '1.'], ['2.', '2.', '18.', '1O', '30', '1O', '24.', '6.']]

>>> kolommen = kolom_aanwijzingen('nonogram.txt4')
>>> kolommen
[['1.'], ['1.'], ['1.'], ['1.'], ['1.', '1.', '1.'], ['1.', '1.'], ['1.', '1.', '1.'], ['1.', '2.'], ['1.', '1.', '1"', '1.'], ['1#', '1.', '1.'], ['1.', '1.', '1:', '1.'], ['1.', '1.', '1.'], ['1"', '1.', '1.'], ['1.', '1.', '1"', '1"', '1.', '1#', '1.'], ['1#', '1#', '1"', '1.', '1#', '1.'], ['1.', '1:', '1:', '1#', '1.', '1#', '1"', '1.'], ['1.', '1.', '1"', '1.', '1#', '1.', '2#', '1.'], ['1"', '1.', '1#', '1#', '1"', '2#', '2.'], ['1#', '1#', '2#', '1.', '2#', '1"', '1.'], ['1.', '1:', '1"', '1#', '1"', '2#', '1:', '2#', '1.'], ['1.', '1.', '1#', '3#', '1"', '1#', '1"', '1#', '1.'], ['1#', '1.', '6#', '1"', '2.'], ['1.', '1#', '1:', '2#', '1"', '1#', '1"', '1#', '1"', '1.'], ['1:', '4#', '1"', '2#', '1"', '1#', '1.'], ['1#', '2"', '1#', '1"', '5#', '1O'], ['11#', '30'], ['1+', '2#', '1"', '2#', '1"', '1#', '3"', '2#', '30'], ['11#', '30'], ['1#', '2"', '1#', '1"', '5#', '1O'], ['1:', '4#', '1"', '2#', '1"', '1#', '1.'], ['1.', '1#', '1:', '2#', '1"', '1#', '1"', '1#', '1"', '1.'], ['1#', '1.', '6#', '1"', '1.'], ['1.', '1.', '1#', '3#', '1"', '1#', '1"', '1#', '1.'], ['1:', '1"', '1#', '1"', '2#', '1:', '2#', '2.'], ['1.', '1#', '1#', '2#', '1.', '2#', '1"', '1.'], ['1"', '1#', '1#', '1"', '2#', '1.'], ['2.', '1"', '1.', '1#', '2#', '1.'], ['1:', '1:', '1#', '1.', '1#', '1"', '1.'], ['1.', '1#', '1#', '1"', '1.', '1#', '1.'], ['1.', '1"', '1"', '1.', '1#', '1.', '1.'], ['1.', '1"', '1.'], ['1.', '1.'], ['1.', '1:', '1.', '2.'], ['1.', '1#', '1.'], ['1"', '1.'], ['1.', '1.', '1.', '1.'], ['1.', '1.'], ['1.', '1.', '1.', '1.'], ['1.'], ['1.', '1.'], ['1.', '1.', '2.'], ['1.', '1.', '1.'], ['1.'], ['1.'], ['1.', '1.', '1.', '1.'], ['1.'], ['1.'], ['1.', '1.'], ['1.'], ['1.', '1.']]

>>> isoplossing('nonogram.txt5', rijen, kolommen)
True