gistfile1.py

from PIL import Image
from random import shuffle
from math import log, sqrt
from itertools import permutations
from heapq import heappush, heappop, nlargest
from sys import argv

NUMBER_OF_COLUMNS = 20

def get_pixel_value(im, x, y):
   width, _ = im.size
   data = im.getdata()
   pixel = data[y * width + x]
   return pixel

def calculate_difference(vector_one, vector_two):
	sum_squared_differences = 0.0
	for pixel in xrange(0, len(vector_one)):
		for channel in [0, 1, 2]:
			pixel_one = vector_one[pixel][channel] / 255.0
			pixel_two = vector_two[pixel][channel] / 255.0
			diff_squared = (log(pixel_one + 1.0 / 256.0, 10) - log(pixel_two + 1.0 / 256.0, 10))**2
			sum_squared_differences += diff_squared
	return sqrt(sum_squared_differences)

def load_shreds(image):
	shreds = []
	for shred_number in xrange(NUMBER_OF_COLUMNS):
		x1, y1 = shred_width * shred_number, 0
		x2, y2 = x1 + shred_width, height
		shreds.append(image.crop((x1, y1, x2, y2)))
	return shreds

def shred_difference(shred1, shred2):
	shred1_border = []
	shred2_border = []

	for y in xrange(0, height):
		shred1_border.append(get_pixel_value(shred1, shred_width-1, y))
		shred2_border.append(get_pixel_value(shred2, 0, y))

	return calculate_difference(shred1_border, shred2_border)

def unshred_image(shreds, sequence, filename):
	if len(sequence) != NUMBER_OF_COLUMNS:
		print 'alert!'
		return
	
	unshredded = Image.new("RGBA", image.size)
	destination_offset = 0
	for shred_number in sequence:
		destination_point = (destination_offset * shred_width, 0)
		unshredded.paste(shreds[shred_number], destination_point)
		destination_offset += 1
	unshredded.save(filename, "JPEG")

unshreddeds = []
def combine(heap, unshredded):
	unshredded_score, unshredded = unshredded

	filtered = filter(lambda x: x is not None, unshredded)
	if len(filtered) == NUMBER_OF_COLUMNS:
		while None in unshredded:
			i = unshredded.index(None)
			if i > 0 and i < len(unshredded)-1:
				seeking = (unshredded[i-1], unshredded[i+1])
				for s, p in heap:
					if seeking == p:
						unshredded_score += s
						break
			del unshredded[i]
				
		unshreddeds.append((unshredded_score, filtered))
		return
	
	if len(heap) == 0:
		return
	
	score, perms = heappop(heap)
	if len(unshredded) == 0:
		# Just started
		combine(heap, (score, [perms[0], perms[1]]))
	
	elif perms[0] in unshredded and perms[1] in unshredded:
		# Both shreds have already been placed
		combine(heap, (unshredded_score, unshredded))

	elif perms[0] in unshredded:
		i = unshredded.index(perms[0])
		if i == len(unshredded)-1:
			# At the end of the sequence, simply expand it
			unshredded.append(perms[1])
			unshredded_score += score
		
		elif unshredded[i+1] is None:
			# There's a None to the right, see if we can get rid of it, otherwise insert
			if unshredded[i+2] == perms[1]:
				del unshredded[i+1]
			else:
				unshredded.insert(i+1, perms[1])
			unshredded_score += score

		combine(heap, (unshredded_score, unshredded))

	elif perms[1] in unshredded:
		i = unshredded.index(perms[1])
		if i == 0:
			# At the beginning of the sequence, simply expand it
			unshredded.insert(0, perms[0])
			unshredded_score += score
		
		elif unshredded[i-1] is None:
			# There's a None to the left, see if we can get rid of it, otherwise insert
			if unshredded[i-2] == perms[0]:
				del unshredded[i-1]
			else:
				unshredded.insert(i, perms[0])
			unshredded_score += score
	
		combine(heap, (unshredded_score, unshredded))

	else:
		# Neither shred has been placed. They can be placed at the border of the image
		# or anywhere there's a None.
		unshredded_score += score

		potentials = [0, len(unshredded)]
		for i in xrange(1, len(unshredded)):
			if unshredded[i] is None:
				potentials.append(i)
			
		for p in potentials:
			new_unshredded = list(unshredded)
			
			if p == 0:
				new_unshredded.insert(p, None)
			new_unshredded.insert(p, perms[1])
			new_unshredded.insert(p, perms[0])
			if p != 0:
				new_unshredded.insert(p, None)

			combine(list(heap), (unshredded_score, new_unshredded))

def sorter(a, b):
	if a[0] == b[0]:
		for i in xrange(len(a[1])):
			if a[1][i] != b[1][i]:
				return cmp(a[1][i], b[1][i])
	return cmp(a[0], b[0])

if len(argv) != 3:
	print "bad arguments"

else:
	image = Image.open(argv[1])
	width, height = image.size
	shred_width = width / NUMBER_OF_COLUMNS

	shreds = load_shreds(image)

	h = []
	for perm in permutations(range(len(shreds)), 2):
		heappush(h, (shred_difference(shreds[perm[0]], shreds[perm[1]]), perm))
	combine(h, (0, []))

	unshreddeds.sort(cmp=sorter)
	unshred_image(shreds, unshreddeds[0][1], argv[2])