Our algorithm was: **nonogramSolver**.

Go to the subject itself for more details

CodeSandbox with a possible set of properties you may have come with: https://codesandbox.io/s/advent-of-pbt-day-13-solution-2hyoz?file=/src/index.spec.ts&previewwindow=tests

## Property 1: should respect the constraints when filling the grid

I initially wanted to check that the solver was building THE right grid. But actually there is no unicity of the solution (from time to time). So instead of checking if we get the right grid, we can check that the grid follows the requirements.

In other words if the row number 1 requires: [1, 2], then I should have one "cross" then one or many "dots" then two "crosses".

for any constraints

it should follows the constraints

In other words:

for any already filled grid

if I compute the constraints followed by this grid

and pass them to the solver

then the answer of the solver should also result in the same constraints

Written with fast-check:

```
it("should respect the constraints when filling the grid", () => {
fc.assert(
fc.property(
fc
.record({
numRows: fc.integer({ min: 1, max: 10 }),
numColumns: fc.integer({ min: 1, max: 10 })
})
.chain(({ numRows, numColumns }) =>
fc.array(
fc.array(fc.constantFrom(".", "x"), {
minLength: numColumns,
maxLength: numColumns
}),
{ minLength: numRows, maxLength: numRows }
)
),
(initialGrid) => {
// Arrange
const constraints = gridToConstraints(initialGrid);
// Act
const solution = nonogramSolver(constraints.rows, constraints.columns);
// Assert
const gridSolution = solution.split("\n").map((line) => line.split(""));
expect(gridToConstraints(gridSolution)).toEqual(constraints);
}
)
);
});
```

The only thing missing is the helper `gridToConstraints`

extracting the constraints for an already filled grid. I drafted a dummy implementation for it:

```
function gridToConstraints(
grid: string[][]
): { rows: number[][]; columns: number[][] } {
const rows: number[][] = [];
for (let rowIndex = 0; rowIndex !== grid.length; ++rowIndex) {
const row: number[] = [];
let numX = 0;
for (let colIndex = 0; colIndex !== grid[0].length + 1; ++colIndex) {
const c = grid[rowIndex][colIndex];
if (c === "x") {
++numX;
} else if (numX !== 0) {
row.push(numX);
numX = 0;
}
}
rows.push(row);
}
const columns: number[][] = [];
for (let colIndex = 0; colIndex !== grid[0].length; ++colIndex) {
const column: number[] = [];
let numX = 0;
for (let rowIndex = 0; rowIndex !== grid.length + 1; ++rowIndex) {
const c = grid[rowIndex]?.[colIndex];
if (c === "x") {
++numX;
} else if (numX !== 0) {
column.push(numX);
numX = 0;
}
}
columns.push(column);
}
return { rows, columns };
}
```

But we might probably have something even simpler and less error-prone to build this one.

Back to "Advent of PBT 2021" to see topics covered during the other days and their solutions.

More about this serie on @ndubien or with the hashtag #AdventOfPBT.

## Top comments (0)