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:

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.