Here's my solution for those who care: (It's a cleaned up version of the one I submitted)
Start looking at where it says algo here. The top is full of the history of the app. I didn't omit it since I thought I would need it by the end.
The algo solves the puzzle by making pools of fitting pieces. When a common piece is found, two isles are merged.
import os
import math
import time
import sys
import array
from collections import Counter
W = 52
H = 52
S = 52
def pixel(bmp, col, row):
s = (col + row * W) * 3
return bmp[s:s+3]
def ptuple(pixel):
return (float(ord(pixel[0])), float(ord(pixel[1])), float(ord(pixel[2])))
def diff(tuple1, tuple2):
return (tuple1[0]-tuple1[0], tuple1[1]-tuple2[1], tuple1[2]-tuple2[2])
def square(t):
return t[0]*t[0]+t[1]*t[1]+t[2]*t[2]
def column(bmp, col):
pixels = b''
for row in range(1, H-1):
pixels = pixels + pixel(bmp, col, row)
return pixels
def columnRev(bmp, col):
pixels = b''
for row in range(1,H-1):
pixels = pixel(bmp, col, row) + pixels
return pixels
def row(bmp, row):
pixels = b''
for col in range(1,W-1):
pixels = pixels + pixel(bmp, col, row)
return pixels
def rowRev(bmp, row):
pixels = b''
for col in range(1,W-1):
pixels = pixel(bmp, col, row) + pixels
return pixels
def columnRgbs(bmp, col):
rgbs = []
for row in range(H):
rgbs.append(ptuple(pixel(bmp, col, row)))
return rgbs
def rowRgbs(bmp, row):
rgbs = []
for col in range(H):
rgbs.append(ptuple(pixel(bmp, col, row)))
return rgbs
def contrastScalar(center, left, right):
return center + (center - (left + right) * .5)
def contrastTuple(center, left, right):
return (contrastScalar(center[0], left[0], right[0]),
contrastScalar(center[1], left[1], right[1]),
contrastScalar(center[2], left[2], right[2]))
def contrast(rgbs):
for i in range(1, len(rgbs)-1):
for j in range(3):
rgbs[i] += contrastTuple(rgbs[i], rgbs[i-1], rgbs[i+1])
return rgbs
def rgbEdges(bmp):
return (contrast(columnRgbs(bmp, 1)), contrast(columnRgbs(bmp, W-2)), contrast(rowRgbs(bmp, 1)), contrast(rowRgbs(bmp, H-2)))
def edges(bmp):
return (column(bmp, 0)+column(bmp, 1), column(bmp, W-2)+column(bmp, W-1), row(bmp, 0)+row(bmp, 1), row(bmp, H-2)+row(bmp, H-1))
def edgesRev(bmp):
return (columnRev(bmp, 1)+columnRev(bmp, 0), columnRev(bmp, W-1)+columnRev(bmp, W-2), rowRev(bmp, 1)+rowRev(bmp, 0), rowRev(bmp, H-1)+rowRev(bmp, H-2))
def symHash(t):
return hash(array.array('B', [ord(k) for k in sorted(t[0])]).tostring())
hash1 = hash(bytearray(sorted(t[0])))
return hash1
hash2 = hash(t[1])
return hash((min(hash1,hash2),max(hash1,hash2)))
def edgesRot(bmp):
return (
(column(bmp,0)+column(bmp,1), columnRev(bmp,1)+columnRev(bmp,0)),
(row(bmp,H-1)+row(bmp,H-2), rowRev(bmp,H-2)+rowRev(bmp,H-1)),
(column(bmp,H-1)+column(bmp,H-2), columnRev(bmp,H-2)+columnRev(bmp,H-1)),
(row(bmp,0)+row(bmp,1), rowRev(bmp,1)+rowRev(bmp,0))
)
def edgesRotHash(edgeRot):
return (
symHash(edgeRot[0]),
symHash(edgeRot[1]),
symHash(edgeRot[2]),
symHash(edgeRot[3])
)
def vertHash(bmp, col):
pixels = b''
for row in range(1,H-1):
pixels = pixels + pixel(bmp, col, row)
return hash(pixels)
def horzHash(bmp, row):
pixels = b''
for col in range(1,W-1):
pixels = pixels + pixel(bmp, col, row)
return hash(pixels)
def match(left, right):
total = 0
for index in range(1,H-1):
variance = square(diff(left[index],right[index]))
total += variance * variance
return total
def mapAppend(map, key, value):
if key not in map:
map[key] = [value]
else:
map[key].append(value)
rotation = ((-1,+0), (+0,+1), (+1,+0), (+0,-1))
basis = (((1,0),(0,1)), ((0,-1),(1,0)), ((-1,0),(0,-1)), ((0,1), (-1,0)))
# data for each block in an isle
class Block:
def __init__(self, index, rot, pos):
self.index = index
self.rot = rot
self.pos = pos
self.isle = None
self.filename = ""
def t(self):
return (self.filename, self.index, self.rot, self.pos)
def moveRotateIsle(isle, center, to, rot):
rot = (rot%4+4)%4
rot_perp = (((rot+2)%4)+4)%4
x = basis[rot][0]
y = basis[rot][1]
for b in isle:
b.pos = (b.pos[0]-center[0], b.pos[1]-center[1])
temp = (b.pos[0]*x[0] + b.pos[1]*y[0], b.pos[0]*x[1] + b.pos[1]*y[1])
b.pos = (temp[0]+to[0], temp[1]+to[1])
b.rot = (((b.rot+rot)%4)+4)%4
testisle = [Block(0, 0, (0,0)), Block(1, 3, (1,0)), Block(2, 1, (0, 1)), Block(3, 1, (0, -1)), Block(4, 3, (-1, 0)), Block(5, 3, (0, -1))]
moveRotateIsle(testisle, (0,0), (0,0), 1)
print [b.t() for b in testisle]
# -------------------- algo starts here --------------------
bmps = []
path = 'data/'
listing = os.listdir(path)
for f in listing:
file_bytes = open(path + f, 'rb').read()
bmps.append(file_bytes)
mp = dict()
edges = []
rgbedges = []
free = []
for index in range(len(bmps)):
bmp = bmps[index]
hashes = edgesRotHash(edgesRot(bmp))
for rot in range(4):
mapAppend(mp, hashes[rot], (index,rot)) #hash to (neighbor rotation) couple
edges.append(hashes[rot])
lens = [len(mp[k]) for k in mp]
print Counter(lens)
neighbors = dict()
flows = [mp[k] for k in mp if len(mp[k])==2]
for flow in flows:
mapAppend(neighbors, flow[0][0], (flow[0][1], flow[1])) #index to (rotation neighbor couple)
mapAppend(neighbors, flow[1][0], (flow[1][1], flow[0])) #index to (rotation neighbor couple)
free = [k for k in neighbors]
blockMap = dict() #map index to block
islesMap = dict() #map index to isles
isles = []
i = 0
while(free):
node = free.pop()
block = Block(node, 0, (0,0))
block.filename = listing[node]
blockMap[block.index] = block
block.isle = [block];
isles.append(block.isle)
blockNeighbors = neighbors[block.index]
for rotneighbor in blockNeighbors:
my_rot = rotneighbor[0]
neighborCouple = rotneighbor[1]
neighborIndex = neighborCouple[0]
if neighborIndex in blockMap:
neighborBlock = blockMap[neighborIndex]
neighborIsle = neighborBlock.isle
neighborRot = neighborCouple[1]
rot_del = (my_rot + block.rot - neighborRot - neighborBlock.rot + 2)
move_to_unit = rotation[((my_rot+block.rot)%4+4)%4]
move_to = (block.pos[0]+move_to_unit[0], block.pos[1]+move_to_unit[1])
npos = neighborBlock.pos
if id(block.isle) != id(neighborIsle):
moveRotateIsle(neighborIsle, neighborBlock.pos, move_to, rot_del)
neighborIsle.extend(block.isle)
isles.remove(block.isle)
temp = block.isle
for b in temp:
b.isle = neighborIsle
i += 1
maxislescount = max([len(isle) for isle in isles])
maxisle = [isle for isle in isles if len(isle)==maxislescount][0]
minX = min(b.pos[0] for b in isle)
minY = min(b.pos[1] for b in isle)
maxX = max(b.pos[0] for b in isle)
maxY = max(b.pos[1] for b in isle)
print minX, minY, maxX, maxY
for b in maxisle:
b.pos = (b.pos[0]-minX,b.pos[1]-minY)
width = (maxX-minX+1)*50
height = (maxY-minY+1)*50
print width, height
size = width*height*3
result = bytearray(width*height*3)
count = (maxX-minX+1)*(maxY-minY+1)
print "count", count
num = 0
for b in maxisle:
if num % 100 == 0:
print num
bmp = bmps[b.index]
pos = b.pos
for i in range(50):
for j in range(50):
if b.rot == 0:
x = i
y = j
if b.rot == 1:
x = j
y = 49 - i
if b.rot == 2:
x = 49 - i
y = 49 - j
if b.rot == 3:
x = 49 - j
y = i
row = 50*(maxX-minX+1)
start = 50*(pos[0]+row*pos[1])
byte1 = bmp[((i+1) + 52*(j+1))*3]
byte2 = bmp[((i+1) + 52*(j+1))*3+1]
byte3 = bmp[((i+1) + 52*(j+1))*3+2]
result[(start + x + y * row)*3] = byte1
result[(start + x + y * row)*3+1] = byte2
result[(start + x + y * row)*3+2] = byte3
num += 1
f = open('data.raw', 'wb')
f.write(result)