Kattis-flipfive

index.js

const readline = require("readline");

const WHITE = "."; // 0
const SIZE = 3;
const SIZE_SQUARE = SIZE * SIZE;
const LEADING_ZEROS = "0".repeat(SIZE_SQUARE);

const inputData = [];
var rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.prompt();

rl.on("line", function (cmd) {
  inputData.push(cmd);
});

rl.on("close", function (cmd) {
  const p = inputData.shift();
  console.log(flipfive(parseInt(p, 10), inputData).join("\n"));
});

/**
 * https://vjudge.net/problem/Kattis-flipfive
 * @param {number} p
 * @param {string} str
 */
const flipfive = (p, dataArr) => {
  const results = [];

  if (p > 0 && p <= 50) {
    const arr = [];

    let tmp = "";
    dataArr.forEach((s, idx) => {
      tmp += s;
      if ((idx + 1) % 3 === 0) {
        arr.push(tmp);
        tmp = "";
      }
    });

    if (p !== arr.length) {
      throw new Error("wrong input");
    }

    arr.forEach((s) => results.push(flipfiveOne(s)));
  }
  return results;
};

/**
 * @param {string} str
 * @returns {number}
 */
const flipfiveOne = (str) => {
  let answer = 0; // P
  const expectedNum = parseInputStr(str);
  const startNum = 0; // [0, 0, 0, 0, 0, 0, 0 ,0 ,0]

  if (expectedNum === startNum) {
    return answer;
  }

  // use set to filter out duplicated combinations
  let cache = new Set([startNum]);

  while (true) {
    answer++;
    const newCache = [];

    for (const m of cache) {
      const result = flipfiveIt(expectedNum, m);
      if (typeof result === "boolean") {
        cache.clear();
        return answer;
      }
      newCache.push(...result);
    }

    cache = new Set(newCache);
  }
};

/**
 * returns true if current matrix matches the expected one after flip
 * otherwise returns all (9) combinations
 * @param {number} expectedNum
 * @param {number} matrix
 * @returns {boolean|number}
 */
const flipfiveIt = (expectedNum, matrix) => {
  const cache = [];

  for (let i = 0; i < SIZE; i++) {
    for (let j = 0; j < SIZE; j++) {
      const flippedMatrix = flipCells(matrix, i, j);
      if (expectedNum === flippedMatrix) {
        return true;
      }
      cache.push(flippedMatrix);
    }
  }

  return cache;
};

/**
 * @param {number} matrix
 * @param {number} i
 * @param {number} j
 * @returns {number}
 */
const flipCells = (num, i, j) => {
  // convert number to array, ex 0 to [0, 0, 0, 0, 0, 0, 0 ,0 ,0]
  const flippedMatrix = `${LEADING_ZEROS}${num}`.slice(-SIZE_SQUARE).split("");

  // filter out coords that are outside the grid
  const coords = [
    i * SIZE + j,
    isInRange(i - 1) && (i - 1) * SIZE + j,
    isInRange(i + 1) && (i + 1) * SIZE + j,
    isInRange(j - 1) && i * SIZE + (j - 1),
    isInRange(j + 1) && i * SIZE + (j + 1),
  ].filter((x) => typeof x === "number");

  // flip 0 to 1 or 1 to 0
  coords.forEach((x) => {
    flippedMatrix[x] = Math.abs(flippedMatrix[x] - 1);
  });

  return parseInt(flippedMatrix.join(""), 10);
};

const isInRange = (x) => x >= 0 && x < SIZE;

/**
 * @param {string} str
 * @returns {number}
 */
const parseInputStr = (str) => {
  return parseInt(
    str
      .split("\n")
      .map((line) => line.split("").map((c) => (c === WHITE ? 0 : 1)))
      .flat()
      .join(""),
    10
  );
};