Chat that we had today :)

test.js

const printMatrix = (matrix) => matrix.forEach((line,j) => console.log('('+j+')',line));

// USES ALGORITHM THAT I DESCRIBED WHICH WAS WRONG!!!!
const countIslandsMyAlgorithm = (matrix) => {
	const checkCounterMatrix = (counterMatrix,i,j) => {
		if((i-1 >= 0) && (counterMatrix[i-1][j] !== 0)) return counterMatrix[i-1][j];
		if((j-1 >= 0) && (counterMatrix[i][j-1] !== 0)) return counterMatrix[i][j-1];

		// this 2 cases are never considered in any of the matrices, this causes issues
		if((i+1 < matrix.length) && (matrix[i+1][j] !== 0)) return counterMatrix[i+1][j] = 0;
		if((j+1 < matrix[i].length) && (matrix[i][j+1] !== 0)) return counterMatrix[i][j+1] = 0;
		return 0;
	};


	const counterMatrix = matrix.map((line) => Array(line.length).fill(0));

	let counter = 0;
	matrix.forEach((line,i) => line.forEach((cell,j) => {
		if(cell === 1) {

			counterMatrix[i][j] = checkCounterMatrix(counterMatrix,i,j);
			if(counterMatrix[i][j] === 0) counterMatrix[i][j] = ++counter; 
		}
	}));
	console.log('Counter matrix:');
	printMatrix(counterMatrix);
	console.log('Found',counter,'islands!');
};

// USES DEPTH FIRST SEARCH
const countIslandsDFS = (matrix) => {
	const depthFirstSearch = (matrix,visited,i,j,mark) => {
		if(visited[i][j]) return;

		visited[i][j] = mark;

		if((i-1 >= 0) && (matrix[i-1][j] !== 0)) depthFirstSearch(matrix,visited,i-1,j,mark);
		if((j-1 >= 0) && (matrix[i][j-1] !== 0)) depthFirstSearch(matrix,visited,i,j-1,mark);
		if((i+1 < matrix.length) && (matrix[i+1][j] !== 0)) depthFirstSearch(matrix,visited,i+1,j,mark);
		if((j+1 < matrix[i].length) && (matrix[i][j+1] !== 0)) depthFirstSearch(matrix,visited,i,j+1,mark);
	};

	const visited = matrix.map((line) => Array(line.length).fill(0));

	let counter = 0;
	matrix.forEach((line,i) => line.forEach((cell,j) => {
		if(cell === 1 && visited[i][j] === 0) {
			counter++;
			depthFirstSearch(matrix,visited,i,j,counter);
		}

	}));

	console.log('Visited matrix:');
	printMatrix(visited);
	console.log('Found',counter,'islands!');
};

const matrix1 = [
	[0,0,0,0,0,0,0,0,0,0,0],
	[0,1,0,0,0,0,1,0,0,0,0],
	[0,1,0,0,0,1,1,1,0,0,0],
	[0,1,1,1,0,0,1,0,0,0,0],
	[0,0,0,0,0,0,0,0,0,0,0],
	[0,0,1,0,1,0,0,1,0,0,0],
	[0,0,0,0,1,1,1,1,0,0,0],
	[0,0,0,0,0,0,0,0,0,0,0],
];

console.log('Input matrix:');
printMatrix(matrix1);
countIslandsMyAlgorithm(matrix1);
countIslandsDFS(matrix1);

/*
// Expected result

$ node test.js
Input matrix:
(0) [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
(1) [ 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0 ]
(2) [ 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0 ]
(3) [ 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0 ]
(4) [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
(5) [ 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0 ]
(6) [ 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0 ]
(7) [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
Counter matrix:
(0) [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
(1) [ 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0 ]
(2) [ 0, 1, 0, 0, 0, 3, 2, 2, 0, 0, 0 ]
(3) [ 0, 1, 1, 1, 0, 0, 2, 0, 0, 0, 0 ]
(4) [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
(5) [ 0, 0, 4, 0, 5, 0, 0, 6, 0, 0, 0 ]
(6) [ 0, 0, 0, 0, 5, 5, 5, 6, 0, 0, 0 ]
(7) [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
Found 6 islands!
Visited matrix:
(0) [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
(1) [ 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0 ]
(2) [ 0, 1, 0, 0, 0, 2, 2, 2, 0, 0, 0 ]
(3) [ 0, 1, 1, 1, 0, 0, 2, 0, 0, 0, 0 ]
(4) [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
(5) [ 0, 0, 3, 0, 4, 0, 0, 4, 0, 0, 0 ]
(6) [ 0, 0, 0, 0, 4, 4, 4, 4, 0, 0, 0 ]
(7) [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
Found 4 islands!

*/