There is an array of arrays filled with numbers and letters. I want to collect the isolated ones in array of arrays. So, for example, if I call a function called findIsolated(type, matrix) with the "M" type and the matrix shown below, I would like it to return an array of arrays: [ [ {x:0,y:0},{x:0,y:1} ],[ {x:4,y:3},{x:4,y:4},{x:4,y:5} ] ]
If I called the function with findIsolated("V",matrix) it would return an array of array which has all the Vs in it.
matrix:
findIsolated("M",matrix) expected output:
How do I do this recursively? Honestly, I couldn't even figure out one step, so I don't write a minrep.
CodePudding user response:
Here is a solution. The idea is to traverse the matrix, and search the chars to the left and above of the current cell if they are already registered in the resulting array of sets. See explanation in comments:
function findIsolated(target, matrix) {
let result = [];
matrix.forEach((row, rIdx) => {
row.forEach((char, cIdx) => {
// only look at target char:
if(char === target) {
let found = false;
// check if the cell to the left is the same as the target char:
if(cIdx > 0 && row[cIdx - 1] === target) {
// search result set if cell to the left is already listed:
result.forEach(set => {
if(set.x === cIdx -1 && set.y === rIdx) {
// found it, so add this coordinate to the set:
set.push({ x: rIdx, y: cIdx});
found = true;
}
});
}
// check if the cell above is the same as the target char:
if(!found && rIdx > 0 && matrix[rIdx - 1][cIdx] === target) {
// search result set if cell to above is already listed:
result.forEach(set => {
if(set.x === cIdx && set.y === rIdx - 1) {
// found it, so add this coordinate to the set:
set.push({ x: rIdx, y: cIdx});
found = true;
}
});
}
if(!found) {
// target char has not been found in result, so start a new set
let set = [ { x: rIdx, y: cIdx} ];
result.push([ set ]);
}
}
});
});
return result;
}
const matrix = [
[ 'M', 'M', '0', 'V', 'V', '0' ],
[ '0', '0', '0', 'V', '0', '0' ],
[ '0', 'V', 'V', 'V', '0', '0' ],
[ '0', 'V', 'V', '0', '0', '0' ],
[ '0', '0', '0', 'M', 'M', 'M' ],
[ '0', '0', '0', '0', '0', '0' ],
];
console.log('M: ' JSON.stringify(findIsolated('M', matrix)));
console.log('V: ' JSON.stringify(findIsolated('V', matrix)));
Output:
M: [[[{"x":0,"y":0}]],[[{"x":0,"y":1}]],[[{"x":4,"y":3}]],[[{"x":4,"y":4}]],[[{"x":4,"y":5}]]]
V: [[[{"x":0,"y":3}]],[[{"x":0,"y":4}]],[[{"x":1,"y":3}]],[[{"x":2,"y":1}]],[[{"x":2,"y":2}]],[[{"x":2,"y":3}]],[[{"x":3,"y":1}]],[[{"x":3,"y":2}]]]
CodePudding user response:
So eventually, after someone downvoted my question which I could never understand, I finally made it work recursively.
const findIsolated = (type, _map) => {
const map = JSON.parse(JSON.stringify(_map));
map.forEach((row, rowIndex) => {
row.forEach((cell, cellIndex) => {
map[rowIndex][cellIndex] = { value: cell, x: rowIndex, y: cellIndex, visited: false }
})
})
const isolatedsOfType = [];
map.flat().forEach(element => {
if (element.value === type && !element.visited) {
let separateArrays = [];
traverse(element, type, map, separateArrays);
isolatedsOfType.push(separateArrays);
}
})
return isolatedsOfType;
}
const traverse = (item, type, map, separateArrays) => {
map[item.x][item.y].visited = true;
separateArrays.push({ x: item.x, y: item.y });
traverseNeighbors(item, type, map).forEach(neighbor => {
if (!neighbor.visited) {
traverse(neighbor, type, map, separateArrays);
}
})
}
const traverseNeighbors = (item, type, map) => {
const neighbors = [];
if (item.x 1 < map.length && map[item.x 1][item.y].value === type) {
neighbors.push(map[item.x 1][item.y]);
}
if (item.y 1 < map.length && map[item.x][item.y 1].value === type) {
neighbors.push(map[item.x][item.y 1]);
}
return neighbors;
}
const matrix = [
["M", "M", "0", "V", "V", "0"],
["0", "0", "0", "V", "0", "0"],
["0", "V", "V", "V", "0", "0"],
["0", "V", "V", "0", "0", "0"],
["0", "0", "0", "M", "M", "M"],
["0", "M", "0", "0", "0", "0"],
];
console.log(findIsolated("M", matrix))
I doubt that this is more optimal than the answer added previously, but I needed a recoursive way.
Output:
[
[ { x: 0, y: 0 }, { x: 0, y: 1 } ],
[ { x: 4, y: 3 }, { x: 4, y: 4 }, { x: 4, y: 5 } ]
]