3
\$\begingroup\$

My goal is to find the largest connected "cell" of 1's in a matrix.

My approach has been to search the surrounding area of a cell that is not on a border and then if it hasn't been visited, and has a value of 1, increment the group. I am absolutely sure that there are better, more recursive solutions out there, but I would greatly appreciate if someone would at least point me in the right direction. I feel as though I'm getting closer. Algorithms are still very new to me.

Example test case

[[0, 0, 1, 1],
 [0, 0, 1, 0],
 [0, 0, 1, 1],
 [0, 0, 0, 0]];

Answer is 5 because there are 5 connected 1s of the largest group

    <html>
<head>
</head>
<body>
<script type="text/javascript">
test = [[0, 0, 1, 1],
        [0, 0, 1, 0],
        [0, 0, 1, 1],
        [0, 0, 0, 0]];


// Answer should be 5

var Cell = function(x, y, val) {
    this.row = x;
    this.col = y;
    this.val = val;
    this.visited = false;
}

Cell.prototype.visit = function() {
    this.visited = true;
}

var CellMatrix = function(arr) {
    inst = [];
    for(i=0; i < arr[0].length; i++) {
        for(k=0; k < arr.length; k++) {
            inst.push(new Cell(i, k, arr[i][k]));
        }
    }
    this.length = inst.length;
    //console.log(inst);
    return inst;
}

function find(row, col, cells) {
    for(i=0; i < cells.length; i++) {
        cell = cells[i];
        if((cell.row == row) && (cell.col == col) && (!cell.visited))
            return cell;
        else {
            continue;
        }
    }
    return false;
}

function findLargestGrouping(cells, rows, cols) {
    console.log(cells);
    groups = []
    for(i=0; i < cells.length; i++) {
        cell = cells[i];
        // not a border cell
        if( (cell.row > 0) && (cell.row < (rows - 1))  )
        {
            if( (cell.col > 0) && (cell.col < (cols - 1)) ) {
                // console.log("cell at row " + cell.row + " col " + cell.col + " and val " + cell.val);
                groups.push(searchNeighbors(cell, cells));
            }
        }
        else { continue; }
    }
    return Math.max.apply(Math, groups);
}

function searchNeighbors(cell, matrix) {
    neighbors = [[cell.row - 1, cell.col - 1], // top left
                [cell.row - 1, cell.col], // top center
                [cell.row - 1, cell.col + 1], // top right
                [cell.row, cell.col - 1], // center left
                [cell.row, cell.col + 1], // center right
                [cell.row + 1, cell.col - 1], // bottom left
                [cell.row + 1, cell.col], // bottom center
                [cell.row + 1, cell.col + 1]];

    results = 0;
    for(i=0; i < neighbors.length; i++) {
        _row = neighbors[i][0];
        _col = neighbors[i][1];
        _cell = find(_row, _col, matrix);
        console.log("cell at row " + cell.row + " col " + cell.col + " and val " + cell.val);
        if(_cell) {
            if(!_cell.visited) {
                _cell.visit();
                results += 1;
            }
        }
    }
    return results;
}

window.onload = function() {
    matrix = new CellMatrix(test);
    results = findLargestGrouping(matrix, 4, 4);
    console.log(results);
}
</script>
</body>
</html>
\$\endgroup\$
1
  • \$\begingroup\$ You should have a look at the A* (A-star) path finding algorithm, that (i guess) you could adapt to your needs. \$\endgroup\$ Nov 3, 2015 at 22:52

1 Answer 1

1
\$\begingroup\$

You have a lot of global variables. Almost all of them, actually. I only see two var declarations, and those two are probably the ones that matter least (though all declarations matter - don't skip 'em).

You're lucky you're not calling functions with loops from inside other loops. Otherwise they'd both be using the same i variable, and things would get weird. Or rather, get broken.

So fix that first! Try running your code through jshint, for instance, to get some basic refactoring/bug checking.

Secondly, while I applaud striving for object-oriented JS, it seems overwrought in this case.

If the task is indeed to find cells with a 1 in them, and all other cells have a 0, then there's a shortcut to take. Since zero is false'y, and one is truth'y, they can pull double-duty as the visited flag: If a cell is zero, it's either been visited or is not worth visiting. In other words, we can ignore every cell that's false'y.

So if you just set cells to 0, false, or null along the way, they'll be ignored later on. Same effect as your visited, but without the need for instantiating objects.

As for recursion, that's definitely an option here. Here's one such implementation:

function largestGroup(matrix) {
  var counts = [0];

  // count connected cells, starting with cell i,j
  function countConnected(i, j) {
    if(matrix[i][j]) {
      matrix[i][j] = null;
      return neighborsOf(i, j).reduce(function (sum, coord) {
        return sum + countConnected(coord[0], coord[1]); // recursion
      }, 1);
    }
    return 0;
  }

  // get neighbor coordinates of i,j
  // (ignores those that are false'y)
  function neighborsOf(i, j) {
    return [
      [i-1, j], [i+1, j],     // up and down
      [i, j-1], [i, j+1],     // left and right
      [i-1, j-1], [i-1, j+1], // diagonally up
      [i+1, j-1], [i+1, j+1]  // diagonally down
    ].filter(function (coord) {
      // keep only those coordinates that match cells that
      // a) exist, and
      // b) contain something thruthy
      return matrix[coord[0]] && matrix[coord[0]][coord[1]];
    });
  }

  // copy matrix to avoid modifying the original
  matrix = matrix.slice().map(function (row) {
    return row.slice();
  });

  // look for cells with something in 'em, and
  // start counting connected cells from there
  for(var i = 0 ; i < matrix.length ; i++) {
    for(var j = 0 ; j < matrix[i].length ; j++) {
      if(matrix[i][j]) {
        counts.push(countConnected(i, j));
      }
    }
  }

  return Math.max.apply(null, counts);
}

It starts by copying the matrix, since it's going to be modifying it, and we don't want to modify the input - other code may hold references to it.

After that, it starts looping through its copy, looking for the first truth'y cell. It then calls countConnected with that cell's coordinates, which, in turn, calls itself on each neighboring cell that's of interest (i.e. not zero). Any cell that's visited gets set to null, which, like zero, is false'y. Thus visited cells are ignored.

Each truthy cell that's visited by countConnected will add 1 to the count; any false'y cells will add zero. And since cells are set to null the first time they're counted, they won't be counted twice.

\$\endgroup\$
3
  • \$\begingroup\$ @willredington315 Glad you found it useful. But stick around and see if there aren't better answers coming your way. I'm sure there's a smarter way than what I propose. And don't forget to click the checkmark on whichever answer you think is best - it'll mark you question as answered \$\endgroup\$
    – Flambino
    Nov 3, 2015 at 19:58
  • \$\begingroup\$ Two more quick questions: 1) How are there not any repitions when finding the neighborsOf a paritcular cell? 2) What does the line "return matrix[coord[0]] && matrix[coord[0]][coord[1]]" mean? \$\endgroup\$ Nov 5, 2015 at 15:02
  • \$\begingroup\$ @willredington315 1) There is still repetition. But it doesn't lead to recursion; the neighbor coordinates are found, but immediately ignored if the neighbor cell is zero. Which also involves your other question: That line evaluates to return either true or false. The first check is to see if a matrix row exists at coord[0] (it'll be undefined otherwise, which is false'y). The second is wether the row and column exists. If it does, but contains zero, it'll be false'y. So in all it says "return true if a cell exists at this row/ column and it isn't zero; otherwise return false" \$\endgroup\$
    – Flambino
    Nov 5, 2015 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.