Advent of PBT 2021 - Day 13

/**
 * Solver of nonograms.
 *
 * Nonogram is a game in which the user is asked to colorize a grid
 * based on hints. A cell in the grid will be either filled or not.
 *
 * For instance, the grid below:
 *
 *        12
 *      3211
 *
 * 1 2  ????
 * 1 1  ????
 *   3  ????
 * 1 1  ????
 *
 * Will result in:
 *
 *        12
 *      3211
 *
 * 1 2  x.xx
 * 1 1  x..x
 *   3  xxx.
 * 1 1  .x.x
 *
 * To define this grid you'll have to pass:
 * - rows:    [[1,2],[1,1],[3],[1,1]]
 * - columns: [[3],[2],[1,1],[2,1]]
 *
 * @param rows - For each row, the set of hints concerning the
 *               number of filled cells
 * @param columns - For each column, the set of hints concerning
 *                  the number of filled cells
 */
declare function nonogramSolver(
  rows: number[][],
  columns: number[][]
): string;

it("should be able to solve our nonogram", () => {
  // Arrange
  const rows = [[1, 2], [1, 1], [3], [1, 1]];
  const columns = [[3], [2], [1, 1], [2, 1]];
  let expectedSolution = "";
  expectedSolution += "x.xx\n";
  expectedSolution += "x..x\n";
  expectedSolution += "xxx.\n";
  expectedSolution += ".x.x";

  // Act
  const solution = nonogramSolver(rows, columns);

  // Assert
  expect(solution).toEqual(expectedSolution);
});

it("should be able to solve nonogram with non unique solution", () => {
  // Arrange
  const rows = [[1], [1]];
  const columns = [[1], [1]];
  let expectedSolutionA = "";
  expectedSolutionA += ".x\n";
  expectedSolutionA += "x.";
  let expectedSolutionB = "";
  expectedSolutionB += "x.\n";
  expectedSolutionB += ".x";

  // Act
  const solution = nonogramSolver(rows, columns);

  // Assert
  const isA = solution === expectedSolutionA;
  const isB = solution === expectedSolutionB;
  expect(isA || isB).toBe(true);
});