Anthony Chung Anthony Chung - 3 months ago 18
Javascript Question

checking for exceptions in counting islands

when it comes to matrix traversals and any kind of search, I find that I often need to validate a potential item to either add to my queue or recurse over.

say we're looking at this matrix:

var matrixTest = [
[1,1,0,0,0],
[1,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,1]
]


In this case, I am iterating over all items and performing a BFS (marking as visited) when I encounter a 1.

I have a subroutine within my BFS function that, given a coordinate r and c, it validates all possible paths leading from it (r+1, r-1, c+1, c-1).

The problem is with this piece of code

if(!visitMap[r+1][c] && matrix[r+1][c] === 1) {
q.push([r+1, c])
}


visitMap is a matrix I created alongside the algorithm to ensure I'm not processing a point twice

matrix is the input matrix

However, it appears that I need to validate inputs before testing because JavaScript throws this error

TypeError: Cannot read property '3' of undefined


I presume this means that my "r+1" expression lies outside the bounds of the matrix, and thus processes as undefined.

It seems exceedingly tedious to add another layer of if/then flow to check the bounds of r+1, r-1, c+1, AND c-1.

Is there a particular code pattern you'd recommend using to avoid having to do this many times?

otherwise I think the code block will look like this:

if (r+1 < matrix.length) {

if(!visitMap[r+1][c] && matrix[r+1][c] === 1) {
q.push([r+1, c])
}
}

Answer

You can try to encapsulate the validation of bounds and your condition inside a function like this:

function pushToQueue(visitMap, matrix, r, c) { 
    if( typeof(matrix[r]) == "undefined"
        || typeof(matrix[r][c]) == "undefined" )  {
    return false; 
    }
    return !visitMap[r][c] && matrix[r][c] === 1; 
}

And you can call it like this:

if(pushToQueue(visitMap, matrix, r + 1, c)) {
   q.push([r+1, c]); 
}

if(pushToQueue(visitMap, matrix, r - 1, c)) {
  q.push([r-1, c]); 
} 
// etc ...
Comments