Detecting closed loop in a 2D array pattern

Question

Let's assume that 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 can I determine if the pattern of 1s is a closed loop? I have struggled with this for a few days. I have tried a recursive loop to find neighbors and words, but when you have a more complex pattern it won't 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],
]

Do someone have a magic algorithm to solve this ? :(

Answer 1

As Dagrooms said, try to find 1(s) with only one adjacent 1. Code looks like:

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 rows and columns are the 2d array size.

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's 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 Extract the loop(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 to threat if there's more than one loop, thougth for one loop it's 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

Safer 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);
}

Modified previous JSFiddle