Skip to content

Instantly share code, notes, and snippets.

@aprescott
Last active April 11, 2016 00:37
Show Gist options
  • Save aprescott/913cf40dd6ee7f97170340552a2ddbc3 to your computer and use it in GitHub Desktop.
Save aprescott/913cf40dd6ee7f97170340552a2ddbc3 to your computer and use it in GitHub Desktop.
// 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];
}
@aprescott
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment