## DEV Community 👩‍💻👨‍💻

Nicolas DUBIEN

Posted on • Updated on

# Advent of PBT 2021 - Day 13 - Solution

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:

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.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.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. 