|
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], |
|
]; |
|
} |
BUGFIXED
Coloring, most likely introduced by the attempt to "normalize" colors to an ordinal scale.
EDIT:
This bug is a result of a failure to properly account for "holes" that result from falsey spin values.