In the late 1980's, Japanese Non Ishida and Tetsuya Nishio devised a very tricky form of logic puzzles. The first of its creators — Non Ishida — was a graphic designer and the graphical puzzles were also named after her: nonograms.

The assignment of a 2-color nonogram (left) and its unique solution (right).

A nonogram consists of a rectangular grid whose cells are white at the start. By coloring some of the cells and leaving others white, you work step by step towards a solution that also looks like a nice picture.

To the left of each row and above each column is a hint consisting of a series of colored numbers. The hints provide you all the necessary information to solve the puzzle. You never have to (and must never) guess! Some sense of logic is all you need.

Each colored number in a hint represents a number of consecutive cells of the indicated color. For example, the hint 4 8 3 indicates that the row (from left to right) or column (from top to bottom) consists of a sequence of four consecutive green cells, eight consecutive purple cells, and three consecutive green cells. Before, between and after the sequences of colored cells can be zero or more white cells.

Assignment

We take a text file containing an ASCII picture to make a Christmas puzzle in the form of a nonogram. All lines of the text file contain the same number of characters. Spaces represent white cells. All other characters represent colored cells: each different character is a different color. For example (nonogram.txt¹):

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

Your task is to determine hints for all rows and columns of a nonogram with the ASCII picture as a solution. Since we don't work with colors, a sequence of identical characters is represented by the length of the sequence followed by the character. For example, 6# represents a sequence of six consecutive hashes (#) and 1. represents a single dot (.) that is not preceded or followed by another dot. We represent a hint as a list (list) with the representations (str) of the colored sequences in a row (listed from left to right) or a column (listed from top to bottom). For example, the Christmas puzzle with hints derived from the above ASCII picture looks like this (click here to see the solution of the puzzle):

Assignment of our nonogram Christmas puzzle.

Your task:

Write a function hint that takes a row/column (str) from an ASCII picture. The function must return the hint for the given row/column.
Write a function row_hints that takes the location (str) of a text file containing an ASCII picture. The function must return a list (list) of hints for all rows of the ASCII picture (listed from top to bottom).
Write a function column_hints that takes the location (str) of a text file containing an ASCII picture. The function must return a list (list) of hints for all columns of the ASCII picture (listed from left to right).
Write a function issolution that takes three arguments: i) the location (str) of a text file containing an ASCII picture, ii) a list (list) of hints for all rows of a nonogram (listed from top to bottom) and iii) a list (list) of hints for all columns of a nonogram (listed from left to right). The function must return a Boolean value (bool) that indicates whether the given ASCII picture is a solution for a nonogram with the given hints.

Example

In the following interactive session, we assume the text file nonogram.txt² to be located in the current directory.

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

>>> rows = row_hints('nonogram.txt3')
>>> rows
[['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.']]

>>> cols = column_hints('nonogram.txt4')
>>> cols
[['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.']]

>>> issolution('nonogram.txt5', rows, cols)
True