Last active
August 29, 2015 13:57
-
-
Save boompig/9755120 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
"use strict"; | |
// white, black, grey are reserved, and should not be added here | |
var colours = [ | |
"red", | |
"green", | |
"blue" | |
]; | |
/** The colour to make squares once they're burned */ | |
var BURN = "grey"; | |
/************************* LOCKS *************/ | |
var spinlock = false; | |
function spinlock_acquire() { | |
while (spinlock) { | |
// do nothing | |
} | |
spinlock = true; | |
return spinlock; | |
} | |
function spinlock_release() { | |
spinlock = false; | |
} | |
/******************* END LOCKS *****************/ | |
function fastSolve(colourMap, G) { | |
var pt, x, y; | |
var borderSet = [[0, 0]]; | |
while (borderSet.length > 0) { | |
// get a non-burned point | |
do { | |
if (borderSet.length > 0) { | |
pt = borderSet.pop(); | |
x = pt[0]; | |
y = pt[1]; | |
} else { | |
// done | |
return; | |
} | |
} while (G[x][y] == BURN); | |
burnRegion(colourMap, x, y, borderSet, G); | |
} | |
} | |
/** | |
* Burn a region starting with a point | |
*/ | |
function burnRegion(colourMap, x, y, borderSet, G) { | |
var col = G[x][y]; // because colour changes | |
burnRegionRecursive(x, y, col, borderSet, G); | |
colourMap[col] += 1; | |
drawGraph(); | |
showColourMap(colourMap); | |
} | |
/** | |
* Return all points surrounding (x, y) on graph G | |
*/ | |
function getNeighbours(x, y) { | |
var succ = []; | |
if (x + 1 < G.length) | |
succ.push([x + 1, y]); | |
if (x > 0) | |
succ.push([x - 1, y]); | |
if (y + 1 < G[0].length) | |
succ.push([x, y + 1]); | |
if (y > 0) | |
succ.push([x, y - 1]); | |
return succ; | |
} | |
function burnRegionRecursive(x, y, col, borderSet, G) { | |
spinlock_acquire(); | |
G[x][y] = BURN; | |
spinlock_release(); | |
var nextPoints = getNeighbours(x, y); | |
var nextPt; | |
for (var i = 0; i < nextPoints.length; i++) { | |
nextPt = nextPoints[i]; | |
if (G[nextPt[0]][nextPt[1]] == col) { | |
burnRegionRecursive(nextPt[0], nextPt[1], col, borderSet, G); | |
} else if (G[nextPt[0]][nextPt[1]] != BURN) { | |
borderSet.push(nextPt); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment