Puzzle Captcha: Solved.

puzzlecaptchasolved.user.js

// ==UserScript==
// @id             com.dtinth.puzzlecaptcha
// @name           Puzzle Captcha Solver
// @namespace      http://dt.in.th/
// @author         @dtinth
// @description    Solves captcha on https://puzzlecaptcha.apprabbit.com/. Written on 2011-07-29.
// @include        https://puzzlecaptcha.apprabbit.com/
// ==/UserScript==

// this function loads an image from URL,
// puts it in the canvas and return the canvas itself.
function imageToCanvas(url, callback) {

	// helper function to strip out higher bits, so we get the binary.
	function bin(str) {
		var out = '';
		for (var i = 0, l = str.length; i < l; i ++) {
			out += String.fromCharCode(str.charCodeAt(i) & 0xff);
		}
		return out;
	}

	// request the image file.
	GM_xmlhttpRequest({
		method: 'GET',
		url: url,
		overrideMimeType: "text/plain; charset=x-user-defined",
		onload: function(response) {

			// load the image file in the image.
			var image = new Image();
			
			image.addEventListener('load', function() {
				
				// put the image in canvas
				var canvas = document.createElement('canvas');
				canvas.width = image.width;
				canvas.height = image.height;
				canvas.getContext('2d').drawImage(image, 0, 0);
				callback(canvas);

			}, false);

			image.src = 'data:image/jpg;base64,' + btoa(bin(response.responseText));

		}
	});
}

// a helper function: logger
var log = function() {
	var div = document.createElement('div'), text = document.createTextNode('');
	div.setAttribute('style', 'position: fixed; top: 10px; right: 10px; background: #fcb;' +
		'color: #000; padding: 4px 5px; border: 1px solid #ccc');
	div.appendChild(text);
	div.style.display = 'none';
	document.body.appendChild(div);
	return function(x) {
		text.nodeValue = x;
		div.style.display = x == '' ? 'none' : 'block';
	};
}();

// this function loads all captcha images
function loadImages() {

	var cv = document.querySelectorAll('.puzzle .piece');
	var i = 0, l = cv.length;
	var images = [];

	// load the next image, or process all the images if all's done
	function next() {
		if (i >= l) return processImages(images);
		log('Loading image ' + (1 + i));
		var el = cv[i];
		var index = i;
		var str = '#' + index;
		imageToCanvas(el.querySelector('img').src, function(c) {
			images.push({
				canvas: c,
				element: el,
				toString: function() { return str; },
				index: index
			});
			next();
		});
		i ++;
	}
	next();

}

// a matrix to hold difference between edge of images.
function DistanceMap() {
	var data = {};
	this.set = function(i, j, val) {
		data[i + ':' + j] = val;
	};
	this.get = function(i, j) {
		return data[i + ':' + j];
	};
}

// given list of images, calculate the distances,
// and figure out the best way to order them, and actually order them!
function processImages(images) {

	log('Calculating distance...');
	var map = new DistanceMap;
	for (var i = 0; i < images.length; i ++) {
		for (var j = 0; j < images.length; j ++) {
			if (i != j) map.set(i, j, getDistance(images[i].canvas, images[j].canvas));
		}
	}

	log('Finding best permutation...');
	setTimeout(function() {
		
		var best;

		// try all permutation of the images.
		// find the most contiguous permutation of them.
		function permute(choices, permutation) {
			if (choices.length > 0) {
				var l = choices.length;
				for (var i = 0; i < l; i ++) {
					permutation.push(choices.shift());
					permute(choices, permutation);
					choices.push(permutation.pop());
				}
				return;
			}
			var info = {
				distance: 0,
				order: []
			};
			for (var i = 0; i < permutation.length; i ++) {
				info.order.push(permutation[i]);
				if (i + 1 < permutation.length) {
					info.distance += map.get(permutation[i].index, permutation[i + 1].index);
				}
			}
			if (!best || info.distance < best.distance) {
				best = info;
			}
		}

		permute(images, []);
		
		// re-order images in the dom tree.
		log('Re-ordering images...');
		setTimeout(function() {

			for (var i = 0; i < best.order.length; i ++) {
				best.order[i].element.parentNode.appendChild(best.order[i].element);
			}

			log('Updating captcha fields...');
			setTimeout(function() {
				unsafeWindow.updatePieceOrder();
				unsafeWindow.updatePuzzleOutput();
				log('Finished!');
				setTimeout(function() {
					log('');
				}, 2000);
			}, 0);

		}, 0);

	}, 0);
}

// given 2 canvas, this function returns the distance.
// the distance here is defined as the sum of the squares of
//    the color distance pixels at the bottom of a and top of b.
// the distance between two colors is defined as the euclidean distance
//    of 2 colors as if the red, green, blue components
//    are X, Y, Z axis in 3d space respectively.
// if the distance is very low, there is much chance that
// the image b should be at the bottom of a.
function getDistance(a, b) {

	var ac = a.getContext('2d');
	var bc = b.getContext('2d');
	var sum = 0;
	var ad = ac.getImageData(0, a.height - 1, a.width, 1);
	var bd = bc.getImageData(0, 0,            b.width, 1);

	for (var i = 0; i < ad.width && i < bd.width; i ++) {
		sum += Math.pow(ad.data[4 * i + 0] - bd.data[4 * i + 0], 2)
			+  Math.pow(ad.data[4 * i + 1] - bd.data[4 * i + 1], 2)
			+  Math.pow(ad.data[4 * i + 2] - bd.data[4 * i + 2], 2);
	}

	return sum;

}

(function() {
	var button = document.createElement('button');
	button.addEventListener('click', function(e) {
		button.parentNode.removeChild(button);
		loadImages();
		e.stopPropagation();
		e.preventDefault();
	}, false);
	button.innerHTML = 'Solve';
	button.style.fontSize = '15px';
	button.style.fontWeight = 'bold';
	var target = document.querySelector('label[for="id_captcha"]');
	target.parentNode.insertBefore(button, target);
	target.parentNode.insertBefore(document.createTextNode(' '), target);
})();