gistfile1.js

"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);
		}
	}
}