countRooms.js

const id = ({ i, j }) => `${i},${j}`;

const parse = (input) => {
  return input.split('\n').map((row) => row.split(''));
};

const getNeighbors = (maze, i, j) => {
  const di = [-1, 0, 1, 0];
  const dj = [0, 1, 0, -1];
  const ns = [];

  for (let direction = 0; direction < 4; direction++) {
    if (maze[i + di[direction]] && maze[i + di[direction]][j + dj[direction]]) {
      ns.push({
        i: i + di[direction],
        j: j + dj[direction],
        v: maze[i + di[direction]][j + dj[direction]],
        d: i,
      });
    }
  }

  return ns;
};

const dfs = (maze, root, visited) => {
  if (visited.has(id(root))) {
    return;
  }

  visited.add(id(root));

  const isValidNeighbor = ({ v }) => v === '0';

  getNeighbors(maze, root.i, root.j)
    .filter(isValidNeighbor)
    .forEach(({ i, j }) => dfs(maze, { i, j }, visited));
};

/**
 * Solution:
 * Iterate over the maze/map and for each "cell" - (i,j) go from it to all reachable nodes, meaning all the floors in the room.
 * Once we visited all reachable nodes from (i,j) then we can increment our room counter.
 * The process continue until we processed the entire maze/map
 */

const countRooms = (input) => {
  const maze = parse(input);
  const visited = new Set();
  let rooms = 0;

  maze.forEach((row, i) =>
    row.forEach((cell, j) => {
      if (cell === '0' && !visited.has(`${i},${j}`)) {
        // can be done using BFS as well
        dfs(maze, { i, j }, visited);
        rooms++;
      }
    })
  );

  return rooms;
};

///////// PART 2 ///////////


/** Problem
 * Construct paths between each room.
 * The path must start and end from a 0 cell and only pass through 1's
 * 
 */

/** Algorithm:  Brute force solution.
 *  Same as part one but now we will collect each rooms cells in a Map.
 *
 *  Next, Iterate over the rooms cells.
 *  For room i find all "border" cells, i.e cells next to '1'.
 *  Pick one of those cells, lets call that cell "ci".
 *  Go over rooms j where j > i.
 *  Find the "border" cells for room j.
 *  Pick one of those cells, lets call that cell "cj".
 *  Now apply dfs/bfs from "ci" to "cj".
 *  If we found that there is a path from "ci" to "cj" then  we will construct and print it, else, we print that there is no path.
 *  */
/**
 * Another option is do a multi source BFS through all of the current room neighbors.
 * This approach will also yield the shortest path between two rooms
 */



// Using dfs2 we will collect all the cells for each room
const dfs2 = (maze, i, j, visited, roomCells) => {
  if (visited.has(`${i},${j}`)) {
    return;
  }
  roomCells.push({ i, j });

  visited.add(`${i},${j}`);
  const isValidNeighbor = ({ v }) => v === '0';

  getNeighbors(maze, i, j)
    .filter(isValidNeighbor)
    .forEach(({ i, j }) => dfs2(maze, i, j, visited, roomCells));
};

/**
 * Using dfs3 we will find path from start to end.
 * One thing to note here, is that we are always looking for a cell "j", where "j" is a neighbor of "end".
 *  */
const dfs3 = (maze, start, end, paths, visited = new Set()) => {
  if (visited.has(id(start))) {
    return;
  }

  visited.add(id(start));

  const isValidNeighbor = ({ v }) => v === '1';
  const neighbors = getNeighbors(maze, start.i, start.j);

  // We are doing this check because we are only going to walk in one's and we are looking for a zero neighbor that matches our end coordinate
  if (neighbors.some(({ i, j }) => end.i === i && end.j === j)) {
    paths.set(id(end), id(start));
    return true;
  }

  return neighbors.filter(isValidNeighbor).some(({ i, j }) => {
    if (visited.has(id({ i, j }))) return false;

    paths.set(id({ i, j }), id(start));

    return dfs3(maze, { i, j }, end, paths, visited);
  });
};

const backtrackPath = (end, start, paths) => {
  if (paths.get(end) === start) {
    return `(${start}) -> (${end})`;
  }
  return `${backtrackPath(paths.get(end), start, paths)} -> (${end})`;
};

const pathsBetweenRooms = (input) => {
  const maze = parse(input);
  const visited = new Set();
  const roomsCells = new Map();
  let rooms = 0;

  maze.forEach((row, i) =>
    row.forEach((cell, j) => {
      if (cell === '0' && !visited.has(`${i},${j}`)) {
        const currentRoomCells = [];
        dfs2(maze, i, j, visited, currentRoomCells);
        roomsCells.set(rooms, currentRoomCells);
        rooms++;
      }
    })
  );


  for (let i = 0; i < rooms; i++) {
    for (let j = i + 1; j < rooms; j++) {
      findPath(
        roomsCells,
        i,
        j,
        maze
      );
    }
  }

};

const findPath = (roomsCells, i, j, maze) => {
  const paths = new Map();
  const originRoomCells = roomsCells.get(i);
  const originRoomCellsBoundaries = originRoomCells.filter(({ i, j }) =>
    getNeighbors(maze, i, j).some(({ v }) => v === '1')
  );
  const goalRoom = roomsCells.get(j);
  const goalRoomBoundaries = goalRoom.filter(({ i, j }) =>
    getNeighbors(maze, i, j).some(({ v }) => v === '1')
  );
  for (const start of originRoomCellsBoundaries) {
    for (const end of goalRoomBoundaries) {
      paths.set(`${i} -> ${j}`, new Map());
      if (dfs3(maze, start, end, paths.get(`${i} -> ${j}`))) {
        const path = paths.get(`${i} -> ${j}`);
        const route = backtrackPath(id(end), id(start), path);
        console.log(
          `To get from room ${i} to room ${j} and vice versa you should walk the following cords:\n${route}`
        );
        return 'FOUND';
      }
    }
  }

  console.log(
    `There is no way to get from room ${i} to room ${j} and vice versa.`
  );
};



console.log(
  countRooms(`11111111
10010001
11110101
10010001
11111111`)
); // 3


console.log(
  pathsBetweenRooms(`11111111
10010001
11110101
10010001
11111111`)
);

/** Possible output
To get from room 0 to room 1 and vice versa you should walk the following cords:
(1,1) -> (0,1) -> (0,2) -> (0,3) -> (0,4) -> (1,4)

To get from room 0 to room 2 and vice versa you should walk the following cords:
(1,1) -> (0,1) -> (0,2) -> (0,3) -> (0,4) -> (0,5) -> (0,6) -> (0,7) -> (1,7) -> (2,7) -> (3,7) -> (4,7) -> (4,6) -> (4,5) -> (4,4) -> (4,3) -> (3,3) -> (2,3) -> (2,2) -> (2,1) -> (3,1)

To get from room 1 to room 2 and vice versa you should walk the following cords:
(1,4) -> (0,4) -> (0,5) -> (0,6) -> (0,7) -> (1,7) -> (2,7) -> (3,7) -> (4,7) -> (4,6) -> (4,5) -> (4,4) -> (4,3) -> (3,3) -> (2,3) -> (1,3) -> (0,3) -> (0,2) -> (0,1) -> (0,0) -> (1,0) -> (2,0) -> (2,1) -> (3,1)
 */

console.log(
  countRooms(`1111011100
  1011111101
  1101111110
  1110111001
  1101111001
  1111100111
  1011111111
  1011110101
  1111100110
  1111110111`)
); // 13