depth-first-partition.js

// Iterative depth-first search traversal as a partition.
// Start from startingPoint, and iteratively follow all neighbors.
//
// If inclusionCondition is true for a neighbor, include it,
// otherwise, exclude it. At the end, return two arrays:
// One for the included neighbors, another for the remaining
// neighbors.
//
// Example: Say you have a grid which contains certain points
// which are all adjacent-connected:
//
//   ---------------
//   --*--*----***--
//   --*-***---*-*--
//   --***-**--*-*--
//   -------******--
//
// You want all the starred (*) points. Pick any of them as
// a starting point. Say each grid point (starred or not) exists
// in a data structure such that `point.neighbors()` returns
// the 4 adjacent neighboring grid points.
//
//   var partition = partitionTraverse(startingPoint, function(neighbor) {
//     return neighbor.value == "*";
//   });
//   var allStarPoints = partition[0];
//   var boundaryPoints = partition[1];
//
// Here, allStarPoints is an array of all the star points.
// boundaryPoints is the set of points adjacent to the
// chain of star points. The inclusion function determines
// what makes a neighboring point part of the same chain of
// points: its `value` is also *.
//
// To give a more concrete example, say the grid is instead this:
//
//   -------
//   --***--
//   --*-*--
//   --***--
//   -------
//
// Starting at any star (*) point and using the same code
// as above will give boundaryPoints as the X points of:
//
//   --XXX--
//   -X***X-
//   -X*X*X-
//   -X***X-
//   --XXX--
//
var partitionTraverse = function(startingPoint, inclusionCondition) {
  let checkedPoints = [];
  let boundaryPoints = [];
  let pointsToCheck = [];

  pointsToCheck.push(startingPoint);

  while (pointsToCheck.length > 0) {
    const point = pointsToCheck.pop();

    if (checkedPoints.indexOf(point) > -1) {
      // skip it, we already checked
    } else {
      checkedPoints.push(point);

      //
      // NOTE: point.neighbors() here should be replaced with
      // whatever code you need to actually return the neighbors
      // of the point.
      //
      point.neighbors().forEach(neighbor => {
        if (checkedPoints.indexOf(neighbor) > -1) {
          // skip this neighbor, we already checked it
        } else {
          if (inclusionCondition(neighbor)) {
            pointsToCheck.push(neighbor);
          } else {
            boundaryPoints.push(neighbor);
          }
        }
      });
    }
  }

  return [checkedPoints, boundaryPoints];
}

This is particularly useful for checking go territory:

var partition = partitionTraverse(emptyPoint, function(point) {
  return point.isEmpty() || point.isDead();
});

var emptyPoints = partition[0];
var occupiedBoundaryPoints = partition[1];
// if occupiedBoundaryPoints has both black and white stones, it's ambiguous,
// otherwise you know the colour of the territory.