Geek Answers Handbook

Closed loop detection in a two-dimensional array

Suppose you get the following array:

foo = [ [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,1,1,1,1,1,0,0], [0,0,0,1,0,0,0,1,0,0], [0,0,0,1,0,0,0,1,0,0], [0,0,0,1,1,1,0,1,0,0], [0,0,0,0,0,1,0,1,0,0], [0,0,0,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], ]

How to determine if pattern 1s is a closed loop? I struggled with this for several days. I tried a recursive loop to search for neighbors and words, but when you have a more complex template, it will not work, for example:

 foo = [ [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,1,1,1,0,0,0,0], [0,0,0,1,0,1,0,0,0,0], [0,0,0,1,0,1,0,0,0,0], [0,0,0,1,1,1,1,1,0,0], [0,0,0,0,0,1,0,0,0,0], [0,0,0,0,0,1,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0], ]

Does anyone have a magic algorithm to solve this ?: (

+5
source share
1 answer

As Dagrooms said, try finding 1 (s) with only one adjacent 1. The code is as follows:

 function isValid1(x,y){ return (foo[x-1][y] + foo[x+1][y] + foo[x][y-1] + foo[x][y + 1])>1; } function validLoop(){ for(var i = 0; i < rows; i++){ for(var j = 0; j < columns; j++){ if(foo[i][j] === 1 && !isValid1(i,j)) { return false; } } } return true; }

where the rows and columns are the size of the 2d array.

UPDATE

This will return true if there is at least one closed loop:

 function numTouching1(x,y){ return foo[x - 1][y] + foo[x + 1][y] + foo[x][y - 1] + foo[x][y + 1]; } function validLoop(){ var n = 0, x = 0; // x is current point number of touching 1 and n is total for(var i = 0; i < rows; i++){ for(var j = 0; j < columns; j++){ if(foo[i][j] === 1) { x = numTouching1(i, j) - 2; if(x === -1 || x === 1 || x === 2){ n += x; } } } } return n > -1; }

JSFiddle: https://jsfiddle.net/AdminXVII/b0f7th5d/

UPDATE 2 Remove the cycle (s):

 function numTouching1(x,y){ return foo[x - 1][y] + foo[x + 1][y] + foo[x][y - 1] + foo[x][y + 1]; } function extractLoop(){ for(var i = 0; i < rows; i++){ for(var j = 0; j < columns; j++){ if(foo[i][j] === 1 && numTouching1(i, j) === 1){ foo[i][j] = 0; extractLoop();break; } } } }

JSFiddle: https://jsfiddle.net/AdminXVII/b0f7th5d/7/

UPDATE 3

This is a threat if more than one cycle, per cycle, is slower.

 function numTouching1(x, y) { return foo[x - 1][y] + foo[x + 1][y] + foo[x][y - 1] + foo[x][y + 1]; } function extractLoop() { for (var i = 0; i < rows; i++) { for (var j = 0; j < columns; j++) { if (foo[i][j] === 1 && numTouching1(i, j) === 1) { foo[i][j] = 0; extractLoop(); break; } } } } function validLoop(){ extractLoop(); for(var i = 0; i < rows; i++){ for(var j = 0; j < columns; j++){ if(foo[i][j] === 1 && numTouching1(i,j) == 2) { return true; } } } return true; }

JSFiddle: https://jsfiddle.net/AdminXVII/w7zcgpyL/

UPDATE 4

More secure numTouching1() method:

 function numTouching1(x, y) { return ((x > 0) ? foo[x - 1][y] : 0) + ((x < rows-1) ? foo[x + 1][y] : 0) + ((y > 0) ? foo[x][y - 1] : 0) + ((y < columns-1) ? foo[x][y + 1] : 0); }

Changed previous JSFiddle

+5
source

More articles:


All Articles