# nonogram

```python
"""
A nonogram is a logic puzzle, similar to a crossword, in which the player is given a blank grid and has to color it according to some instructions. Specifically, each cell can be either black or white, which we will represent as 0 for black and 1 for white.

+------------+
| 1  1  1  1 |
| 0  1  1  1 |
| 0  1  0  0 |
| 1  1  0  1 |
| 0  0  1  1 |
+------------+

For each row and column, the instructions give the lengths of contiguous runs of black (0) cells. For example, the instructions for one row of [ 2, 1 ] indicate that there must be a run of two black cells, followed later by another run of one black cell, and the rest of the row filled with white cells.

These are valid solutions: [ 1, 0, 0, 1, 0 ] and [ 0, 0, 1, 1, 0 ] and also [ 0, 0, 1, 0, 1 ]
This is not valid: [ 1, 0, 1, 0, 0 ] since the runs are not in the correct order.
This is not valid: [ 1, 0, 0, 0, 1 ] since the two runs of 0s are not separated by 1s.

Your job is to write a function to validate a possible solution against a set of instructions. Given a 2D matrix representing a player's solution; and instructions for each row along with additional instructions for each column; return True or False according to whether both sets of instructions match.

Example instructions #1

matrix1 = [[1,1,1,1],
           [0,1,1,1],
           [0,1,0,0],
           [1,1,0,1],
           [0,0,1,1]]
rows1_1    =  [], [1], [1,2], [1], [2]
columns1_1 =  [2,1], [1], [2], [1]
validateNonogram(matrix1, rows1_1, columns1_1) => True

Example solution matrix:
matrix1 ->
                                   row
                +------------+     instructions
                | 1  1  1  1 | <-- []
                | 0  1  1  1 | <-- [1]
                | 0  1  0  0 | <-- [1,2]
                | 1  1  0  1 | <-- [1]
                | 0  0  1  1 | <-- [2]
                +------------+
                  ^  ^  ^  ^
                  |  |  |  |
  column       [2,1] | [2] |
  instructions      [1]   [1]


Example instructions #2

(same matrix as above)
rows1_2    =  [], [], [1], [1], [1,1]
columns1_2 =  [2], [1], [2], [1]
validateNonogram(matrix1, rows1_2, columns1_2) => False

The second and third rows and the first column do not match their respective instructions.

Example instructions #3

matrix2 = [
[ 1, 1 ],
[ 0, 0 ],
[ 0, 0 ],
[ 1, 0 ]
]
rows2_1    = [], [2], [2], [1]
columns2_1 = [1, 1], [3]
validateNonogram(matrix2, rows2_1, columns2_1) => False

The black cells in the first column are not separated by white cells.

n: number of rows in the matrix
m: number of columns in the matrix
"""

matrix1 = [
    [1,1,1,1], # []
    [0,1,1,1], # [1] -> a single run of _1_ zero (i.e.: "0")
    [0,1,0,0], # [1, 2] -> first a run of _1_ zero, then a run of _2_ zeroes
    [1,1,0,1], # [1]
    [0,0,1,1], # [2]
]

# True
rows1_1 = [[],[1],[1,2],[1],[2]]
columns1_1 = [[2,1],[1],[2],[1]]
# False
rows1_2 = [[],[],[1],[1],[1,1]]
columns1_2 = [[2],[1],[2],[1]]

matrix2 = [
    [1,1],
    [0,0],
    [0,0],
    [1,0]
]
# False
rows2_1 = [[],[2],[2],[1]]
columns2_1 = [[1,1],[3]]
```

Encoding then compare with rows, cols

```
public class ValidNonogram {

    public boolean isValidNonogram(int[][] matrix, int[][] rows, int[][] cols)
    {
        for(int i = 0; i< matrix.length; i++)
        {
            List<Integer> currentRowEncoding = rowEncoding(matrix, i);
            int[] convertedRow = currentRowEncoding.stream().mapToInt(c -> c).toArray();
            if(!Arrays.equals(convertedRow, rows[i]))
            {
                return false;
            }
        }

        for(int j = 0; j< matrix[0].length; j++)
        {
            List<Integer> currentColEncoding = colEncoding(matrix, j);
            int[] convertedCol = currentColEncoding.stream().mapToInt(c -> c).toArray();
            if(!Arrays.equals(convertedCol, cols[j]))
            {
                return false;
            }
        }
        return true;
    }

    public List<Integer> rowEncoding(int[][] matrix, int rowNum)
    {
        List<Integer> res = new ArrayList<Integer>();
        int countZero = 0;
        for(int i  = 0; i< matrix[0].length; i++)
        {
            if(matrix[rowNum][i] == 0)
            {
                countZero++;
            }
            else if(countZero > 0)
            {
                res.add(countZero);
                countZero = 0;
            }
        }
        if(countZero > 0)
        {
            res.add(countZero);
        }
        return res;
    } 

    public List<Integer> colEncoding(int[][] matrix, int colNum)
    {
        List<Integer> res = new ArrayList<Integer>();
        int countZero = 0;
        for(int i  = 0; i< matrix.length; i++)
        {
            if(matrix[i][colNum] == 0)
            {
                countZero++;
            }
            else if(countZero > 0)
            {
                res.add(countZero);
                countZero = 0;
            }
        }
        if(countZero > 0)
        {
            res.add(countZero);
        }
        return res;
    } 
    
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/wayfair/oa/karat/nonogram.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.