Skip to content

Instantly share code, notes, and snippets.

@bmershon
Last active July 23, 2017 23:48
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bmershon/67a9e48a3718d1ec1e81a240f51b6101 to your computer and use it in GitHub Desktop.
Save bmershon/67a9e48a3718d1ec1e81a240f51b6101 to your computer and use it in GitHub Desktop.
Grid Cycles
scrolling: yes
border: no
height: 960
license: MIT

Best viewed fullscreen.

Scroll for examples.

Imagine a person standing in each cell. Now tell each person to move simultaneously to an adjacent cell in the grid with the rule that each must not move in the oppose direction of a neighbor who is entering their cell; that is, no two people may simultaneously cross the same edge as they move to an adjacent cell.

This visualization illustrates the valid patterns in which all 36 people could move. It becomes immediately clear that the migration patterns on a 6 x 6 grid take the form of cycles moving either clockwise or counter-clockwise. Unlike musical chairs, each person must end up in a different adjacent cell.

// https://en.wikipedia.org/wiki/Disjoint-set_data_structure
(function(self) {
function DisjointSet() {
this.index_ = {};
}
function Node(id) {
this.id_ = id;
this.parent_ = this;
this.rank_ = 0;
}
DisjointSet.prototype.makeSet = function(id) {
if (!this.index_[id]) {
let created = new Node(id);
this.index_[id] = created;
}
}
// Returns the id of the representative element of this set that (id)
// belongs to.
DisjointSet.prototype.find = function(id) {
if (this.index_[id] === undefined) {
return undefined;
}
let current = this.index_[id].parent_;
while (current !== current.parent_) {
current = current.parent_;
}
return current.id_;
}
DisjointSet.prototype.union = function(x, y) {
let xRoot = this.index_[this.find(x)];
let yRoot = this.index_[this.find(y)];
if (xRoot === undefined || yRoot === undefined || xRoot === yRoot) {
// x and y already belong to the same set.
return;
}
if (xRoot.rank < yRoot.rank) { // Move x into the set y is a member of.
xRoot.parent_ = yRoot;
} else if (yRoot.rank_ < xRoot.rank_) { // Move y into the set x is a member of.
yRoot.parent_ = xRoot;
} else { // Arbitrarily choose to move y into the set x is a member of.
yRoot.parent_ = xRoot;
xRoot.rank_++;
}
}
// Returns the current number of disjoint sets.
DisjointSet.prototype.size = function() {
let uniqueIndices = {};
Object.keys(this.index_).forEach((id) => {
let representative = this.find(id);
uniqueIndices[id] = true;
});
return Object.keys(uniqueIndices).length;
}
self.DisjointSet = DisjointSet;
})(self);
<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
background: #222;
overflow-x: hidden;
width: 100%;
}
.cell rect {
fill: none;
stroke: #444;
stroke-width: 1px;
stroke-opacity: 0.5;
stroke-dasharray: none;
}
line {
fill: none;
stroke-width: 2px;
}
</style>
<script src="https://d3js.org/d3.v4.min.js" charset="utf-8"></script>
<body>
</body>
<script>
var computing = false;
var worker = new Worker("./worker.js");
var svg,
margin = { top: 20, left: 20, right: 20, bottom: 20},
width = +Math.floor(d3.select("body").style("width").replace("px", "")) - 16,
height = width;
// Grid size.
var N = 6;
var numPerLine = width >= 960 ? 5 : 1;
var spacing = Math.floor(width / numPerLine) - 1;
var exampleSize = spacing * 0.5;
var cellSize = Math.round(exampleSize / (N - 1));
var container = d3.select("body");
var lastExample;
container = container.append("div");
// Dispatcher.
worker.onmessage = function(event) {
switch (event.data.type) {
case "example":
update(event.data.example);
break;
case "progress": // Updated whenever solutions are found.
console.log(event.data.solution);
break;
case "paused":
computing = false;
maybeCompute();
break;
case "done":
console.log("There are", event.data.solution, "examples.");
worker.terminate();
break;
}
};
// Update with data or when no data is specified, update the progress bar only.
function update(data) {
// Flow examples left to right and top to bottom.
lastExample = container.append("svg")
.datum(data)
var cell = lastExample
.attr("width", spacing)
.attr("height", spacing)
.append("g")
.classed("example", true)
.attr("transform", (d, i) => "translate(" + (spacing / 4) + "," + spacing / 4 + ")")
.selectAll(".row")
.data((d) => d)
.enter().append("g")
.classed("row", true)
.attr("transform", (d, i) => "translate(0," + i * cellSize + ")")
.selectAll(".cell")
.data((d) => d)
.enter().append("g")
.classed("cell", true)
.attr("transform", (d, i) => "translate(" + i * cellSize + ",0)")
.style("stroke", (d) => d.hex)
.style("fill", (d) => d.hex)
.style("stroke-dasharray", (d) => {
return (d.orientation) ? [cellSize / 5, cellSize / 5, cellSize / 5].join(",") : null;
});
cell.selectAll("rect")
.data([0, 1, 2, 3])
.enter().append("rect")
.attr("x", (d, i) => {
return ((i % 3 === 0) ? 0 : cellSize) - cellSize / 2;
})
.attr("y", (d, i) => {
return ((i < 2) ? cellSize : 0) - cellSize/ 2;
})
.attr("width", cellSize)
.attr("height", cellSize);
cell.selectAll("line")
.data((d) => d.edges)
.enter().append("line")
.attr("x1", (d, i) => {
return (i % 3 === 0) ? 0 : cellSize;
})
.attr("x2", (d, i) => {
return (i < 2) ? cellSize : 0;
})
.attr("y1", (d, i) => {
return (i < 2) ? 0 : cellSize;
})
.attr("y2", (d, i) => {
return (i % 3 === 0) ? 0 : cellSize;
})
.style("opacity", (d) => (d) ? 1 : 0);
cell.selectAll("circle")
.data((d) => d.edges)
.enter().append("circle")
.attr("cx", (d, i) => {
return (i % 3 === 0) ? 0 : cellSize;
})
.attr("cy", (d, i) => {
return (i < 2) ? 0 : cellSize;
})
.attr("r", 0.1 * cellSize)
.style("opacity", (d) => (d) ? 1 : 0);
}
computing = true;
worker.postMessage({ type: "start", n: N, limit: 1});
d3.select(window)
.on("scroll", maybeCompute)
.each(maybeCompute);
function maybeCompute() {
if (!computing && lastExample && lastExample.node().getBoundingClientRect().top < height) {
computing = true;
worker.postMessage({ type: "resume"});
}
}
</script>
(function(self) {
// Generator function for the powerset of the given set.
function* powerset(set) {
// Represent 2^n in binary as an array of digits. Least significant last.
let n = (new Array(set.length).fill(1));
yield set;
while (decrement(n)) {
yield set.filter((d, i) => n[i] === 1);
}
}
// Subtracts one from an array representing a binary number.
// Returns true if the number is greater than 0 and false if it is already 0.
function decrement(b) {
let i = b.lastIndexOf(1);
if (i > -1) {
b[i] = 0;
for (let k = i + 1; k < b.length; k++) {
b[k] = 1;
}
return true;
}
// b is already 0.
return false;
}
self.powerset = powerset;
})(self);
// Computes powersets based on bitmasking, except the mask specifically targets
// useful patterns for cycles on a grid.
(function(self) {
// Generator function for the powerset of the given set.
function* powersetStar(set) {
// Represent 2^n in binary as an array of digits. Least significant last.
let n = (new Array(set.length).fill(1));
let pattern = [];
// Checkerboard pattern;
for (let i = 0; i < n.length; i++) {
n[i] = (i % 2 === 0) ? 0 : 1;
let l = Math.sqrt(set.length);
if (i % l === 0) {
pattern = pattern.concat((new Array(l).fill(Math.floor((i / l) % 2 == 0) ? 1 : 0)));
}
}
n = mask(n, (a, i) => a || pattern[i]);
yield set.filter((d, i) => n[i] === 1);
while (decrementStar(n)) {
yield set.filter((d, i) => n[i] === 1);
}
}
// Subtracts one from an array representing a binary number.
// Returns true if the number is greater than 0 and false if it is already 0.
function decrementStar(b) {
let i = b.lastIndexOf(1);
if (i > -1) {
b[i] = 0;
for (let k = i + 1; k < b.length; k++) {
b[k] = 1;
}
return true;
}
// b is already 0.
return false;
}
// AND b with mask (the mask must be at least as long as b).
function mask(b, predicate) {
let copy = b.slice(0);
for (let k = 0; k < b.length; k++) {
copy[k] = predicate(b[k], k);
}
return copy;
}
self.powersetStar = powersetStar;
})(self);
if (typeof importScripts === 'function') {
importScripts(
"disjoint-set.js",
"powerset.js",
"restricted-powerset.js",
"https://d3js.org/d3.v4.min.js");
}
var N,
limit,
counter,
interval = 1e4,
seen,
next,
total,
solution = 0,
generator,
stopped = false;
onmessage = function(event) {
switch (event.data.type) {
case "start":
start(event);
resume();
break;
case "pause":
stopped = true;
break;
case "resume":
stopped = false;
resume();
break;
}
}
function start(event) {
counter = 0;
N = event.data.n;
limit = event.data.limit;
total = Math.pow(2, (N - 1) * (N - 1));
// Generator for powersets of an array.
generator = powersetStar(d3.range((N - 1) * (N - 1)));
next = generator.next();
seen = next.value.reduce(function(sum, value, i) {
return sum + (value > 0 ? Math.pow(2, next.value.length - value) : 0);
}, 0);
}
function resume(event) {
counter = 0;
while (!stopped && counter < limit) {
// The generator is exhausted.
if (next.done) break;
let subset = next.value;
let matrix = squareMatrix(N + 1, (i, j) => {
return {
spin: false,
color: (i === 0 || i === N || j === 0 || j === N) ? -1 : undefined,
edges: [true, true, true, true] // top, right, bottom, left
};
});
let palette = new DisjointSet();
let currentColor = -1;
palette.makeSet(-1);
subset.forEach((d) => {
matrix[1 + Math.floor(d / (N - 1))][1 + (d % (N - 1))].spin = true;
});
// Validate matrix masks.
(() => {
for (let i = 1; i < N + 1; i++) {
for (let j = 1; j < N + 1; j++) {
// Inspect left, diagonal, and top neighbor to determine validity.
// There are four configurations.
if ((matrix[i][j].spin && matrix[i][j - 1].spin && matrix[i - 1][j - 1].spin && matrix[i - 1][j].spin)
|| matrix[i][j].spin && !matrix[i][j - 1].spin && matrix[i - 1][j - 1].spin && !matrix[i - 1][j].spin
|| !matrix[i][j].spin && !matrix[i][j - 1].spin && !matrix[i - 1][j - 1].spin && !matrix[i - 1][j].spin
|| !matrix[i][j].spin && matrix[i][j - 1].spin && !matrix[i - 1][j - 1].spin && matrix[i - 1][j].spin) {
return false;
}
}
}
// A species is found.
counter++;
// Determine "topology" of a valid matrix.
// Produce different orientations to be counted and rendered with consistent
// colorings.
for (let i = 1; i < N; i++) {
for (let j = 1; j < N; j++) {
let center = matrix[i][j];
let directions = neighbors(matrix, i, j);
[top, right, bottom, left] = directions;
// Color associations stay with each example, and for convenience, each
// cell.
center.palette = palette;
if (center.spin) {
if (left.spin && top.spin) {
palette.union(left.color, top.color);
center.color = left.color;
left.edges[1] = false;
top.edges[2] = false;
center.edges[3] = false;
center.edges[0] = false;
} else if (left.spin) {
center.color = left.color;
center.edges[3] = false;
left.edges[1] = false;
} else if (top.spin) {
center.color = top.color;
center.edges[0] = false;
top.edges[2] = false;
} else {
palette.makeSet(center.color = ++currentColor);
}
} else { // No spin.
if (!left.spin && !top.spin) {
palette.union(left.color, top.color);
center.color = left.color;
left.edges[1] = false;
top.edges[2] = false;
center.edges[3] = false;
center.edges[0] = false;
} else if (!left.spin) {
center.color = left.color;
center.edges[3] = false;
left.edges[1] = false;
} else if (!top.spin) {
center.color = top.color;
center.edges[0] = false;
top.edges[2] = false;
} else {
palette.makeSet(center.color = ++currentColor);
}
// Check for leaks.
for (let k = 0; k < 4; k++) {
let d = directions[k];
if (d.color === -1) {
center.edges[k] = false;
palette.union(center.color, -1);
}
}
}
}
}
// Fix holes that leaked.
for (let i = 1; i < N; i++) {
for (let j = 1; j < N; j++) {
let center = matrix[i][j];
neighbors(matrix, i, j).forEach((d, i) => {
if (!center.spin && palette.find(center.color) !== palette.find(-1) && d.spin) {
d.edges[(i + 2) % 4] = false;
}
});
}
}
let colors = [];
let normalize = {}; // Mapping from color to its order.
// Count distinct colors.
for (let k = 0; k <= currentColor; k++) {
let c = palette.find(k);
if (c === k && c !== palette.find(-1)) {
colors.push(k);
normalize[k] = colors.length - 1;
}
}
Color = d3.scaleSequential(d3.interpolateRainbow)
.domain([0, Object.keys(normalize).length]);
// Ensure rending color reflects merged colors.
for (let i = 1; i < N; i++) {
for (let j = 1; j < N; j++) {
let center = matrix[i][j];
if (center.color === -1 || palette.find(-1) === palette.find(center.color)) {
center.hex = 'none';
} else {
center.hex = Color(normalize[palette.find(center.color)]);
}
}
}
let polarityGenerator = powerset(colors);
while (true) {
let coloring = polarityGenerator.next();
let selection = coloring.value;
if (coloring.done) break;
// Produce alternate orientations for each example.
for (let i = 1; i < N; i++) {
for (let j = 1; j < N; j++) {
let center = matrix[i][j];
center.orientation = (selection.indexOf(palette.find(center.color)) !== -1);
}
}
postMessage({
"type": "example",
"example": squareMatrix(N - 1, (i, j) => matrix[i + 1][j + 1]),
});
}
solution += Math.pow(2, colors.length);
postMessage({
"type": "progress",
"solution": solution,
});
return true;
})();
seen++;
next = generator.next();
}
if (next.done) {
postMessage({
"type": "done",
"solution": solution,
});
} else {
postMessage({
"type": "paused"
});
}
}
// Returns an n x n matrix, filled using the fill function, which is passed
// the row and column index for each cell to be created.
function squareMatrix(n, fill) {
return d3.range(n).map((row, i) => {
return d3.range(n).map((element, j) => {
return fill(i, j);
});
});
}
// [top, right, bottom, left]
function neighbors(matrix, i, j) {
return [
matrix[i - 1][j],
matrix[i][j + 1],
matrix[i + 1][j],
matrix[i][j - 1],
];
}
@bmershon
Copy link
Author

bmershon commented Jul 21, 2017

BUG

FIXED

Coloring, most likely introduced by the attempt to "normalize" colors to an ordinal scale.

      let colors = [];
      let normalize = {}; // Mapping from color to its order.

      // Count distinct colors.
      for (let k = 0; k <= currentColor; k++) {
        if (palette.find(k) === k) {
          colors.push(k);
          normalize[k] = colors.length - 1;
        }
      }

      Color = d3.scaleSequential(d3.interpolateRainbow)
              .domain([0, colors.length]);

      // Ensure rending color reflects merged colors.
      for (let i = 1; i < N; i++) {
        for (let j = 1; j < N; j++) {     
          let center = matrix[i][j];   
          if (center.color === -1 || palette.find(-1) === palette.find(center.color)) {
            center.hex = 'none';		
          } else {
            center.hex = Color(normalize[palette.find(center.color)]);
          }
        }
      }

screen shot 2017-07-20 at 6 51 47 pm

EDIT:

This bug is a result of a failure to properly account for "holes" that result from falsey spin values.

@bmershon
Copy link
Author

bmershon commented Jul 22, 2017

BUG

  • Fix Overcounting the number of colors used.

@bmershon
Copy link
Author

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