Map is an overloaded word in mathematics. It can mean a function, a morphism, a key-value table... I hate the word dictionary because it's long, and it shortens into dic which reads like dick; I don't like giggling while programming. It's also easier to say mp is a mapping from x to y. How do you say that with dictionary? "A dictionary that maps x to y?" Anyway, no biggy either way.
As for the removal of repetition using map, calling a map with a function on a tuple returns a list. Not much of my style. Though it's a perfectly valid use, and usable.
The defaultdict thing is nifty, so as the literal dictionary syntax.
I don't think the column and row are unclear. Did you mean shorten them up instead of simplifying? Do share. I guess comprehensions would have helped, but why bother so much on such a little piece of code.
Never the less I will/should incorporate some of the above comments into a final solution and put your name in there :)
Be fooled not. My last post was the kiddy stuff. Onto the manly stuff.
We were left with a map containing symmetric hashes. Each edge-hash maps to a list of
(box, edge-index) tuples. We're interested in lists of length two (a couple of boxes connected on an edge).
The following snippet will use mp to map each box to its neighbors (including how they fit, boxe's edge index and neighbor's edge index). But first lets strip out those hash keys from mp. We don't need them. All we need is what's mapped to. Excuse the naming. Flows should have been called couples.
couples = [mp[k] for k in mp if len(mp[k])==2]
[(400, 2), (500,0)]: This is an example couple found in couples. 400 and 500 are box indices. 2 and 0 are edge indices. Those two boxes are connected by those edges.
Next we transform couples into a neighbors mapping. The following snippet will allow us to see for each box what neighbors surround it. Sanely there should be at most 4.
neighbors = dict()
for couple in couples:
mapAppend(neighbors, couple[0][0], (couple[0][1], couple[1]))
mapAppend(neighbors, couple[1][0], (couple[1][1], couple[0]))
An example of the above would be
neighbors[400] == [(2, (500,0)), (0, (300, 1))]
This means block 400 has two neighbors, one on its edge2 and one on its edge0. On its edge2, the neighbor is block500. It matches on its edge0.
We have everything we need to start drumming up the final picture. Scared? You should be.
class Block:
def __init__(self, index, rot, pos):
self.index = index
self.rot = rot
self.pos = pos
self.isle = None
free = [k for k in neighbors]
blockMap = dict() #map index to block
islesMap = dict() #map index to isles
isles = []
class Block is what you describe the piece of puzzle as you move it around and rotate it. It contains the index of the bmp, its rotation, a position and the isle that it belongs to. Isles are sets of blocks that we have already matched and shouldn't break up while solving onward.
free are the free blocks that we haven't used up in making up the puzzle. Think of it as a bucket aside containing unused-yet pieces. We get the pieces from the keys of the neighbors map.
blockMap will give us a block instance for a block index. The block index should be out of the bucket and on the canvas to have a blockMap entry.
islesMap is a shortcut from the index to the corresponding isle (so that we don't have to pass through blockMap).
We'll use isles to manage our set of so far isles. Think of isles as grouped blocks that can all move together, rotate together (which they'll do). Blocks won't move in the internal frame of an isle.
The following piece of code is hard to break up because of indentation. I'll explain it in general, then add some inline comments.
The solution is formed by taking one piece in the free bucket at a time. We'll first wrap it up in its own isle. Then we'll check if each of its neighbors are already on the canvas. If a neighbor was expected but not found on the canvas, we don't worry about it. It'll be added later and it'll match us as a neighbor instead. If the neighbor is already on the canvas instead, the neighbor's isle will be moved so as to match the currently added block. There's one more thing we could do to avoid strangeness.
The newly found neighbor could already be in the same set as the last added block (by another neighbor's merge, remember 4 edges). Nothing needs be done in this case.
After moving the neighbor's container isle, the two isles become one.
The maximum number of isles in this particular dataset rises up to 263 and goes down to 1 in the end (no missing edges or pieces).
while(free):
# create a block and an isle
node = free.pop()
block = Block(node, 0, (0,0))
blockMap[block.index] = block
block.isle = [block];
isles.append(block.isle)
# get a list of current block's neighbors
blockNeighbors = neighbors[block.index]
for rotneighbor in blockNeighbors:
# which edge on current block
my_rot = rotneighbor[0]
# edge and index of neighbor block
neighborCouple = rotneighbor[1]
# take index of neighbor only
neighborIndex = neighborCouple[0]
#check if already on canvas
if neighborIndex in blockMap:
# we can safely get neighbor's block since its on canvas now
neighborBlock = blockMap[neighborIndex]
# ... and isle
neighborIsle = neighborBlock.isle
# if they're in different isles (which is most probable in the beginning)
if id(block.isle) != id(neighborIsle):
neighborRot = neighborCouple[1]
# rotation: 0 is left, 1 is down, 2 is right, 3 is up.
# solving for difference that will align the neighbors selected edge with current's selected edge
# + 2 is equivalent to 180 degree (face each other rather than face same direction)
rot_del = (my_rot + block.rot - neighborRot - neighborBlock.rot + 2)
# move_to_unit: where to place the neighbor block with respect to current block
move_to_unit = rotation[((my_rot+block.rot)%4+4)%4]
# move_to gives us the new absolute position of the neighbor
move_to = (block.pos[0]+move_to_unit[0], block.pos[1]+move_to_unit[1])
# moveRotateIsle: takes an isle, a position within that isle (a center of rotation),
# a place to move that center to, and a rotation delta around the center
moveRotateIsle(neighborIsle, neighborBlock.pos, move_to, rot_del)
# neighbor isle eats up current block's isle.
neighborIsle.extend(block.isle)
# block's isle is bye bye.
isles.remove(block.isle)
# move ownership to new isle
temp = block.isle
for b in temp:
b.isle = neighborIsle
What is left is an implementation of moveRotateIsle.
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)))
def moveRotateIsle(isle, center, to, rot):
# make sure rot is positive
rot = (rot%4+4)%4
# add 2 to that (perpendicular) and make sure it's positive
rot_perp = (((rot+2)%4)+4)%4
# basis contains the basis vectors corresponding to the rotation.
# basis[0] for example is ((1,0), (0,1)) which are usually called i and j.
# basis[1] is ((0, -1), (1,0)). More like -j, i.
# in the above:
# basis[0][0] rotated the other direction from basis[0][1] to give basis[1][0]
x = basis[rot][0]
y = basis[rot][1]
for b in isle:
# take isle's block, and get relative to center coordinates
b.pos = (b.pos[0]-center[0], b.pos[1]-center[1])
# change b's coordinates according to new basis (achieves rotation)
temp = (b.pos[0]*x[0] + b.pos[1]*y[0], b.pos[0]*x[1] + b.pos[1]*y[1])
# add the relative rotated coords to new center
b.pos = (temp[0]+to[0], temp[1]+to[1])
# rotate the block by the delta rotation. make sure its positive.
b.rot = (((b.rot+rot)%4)+4)%4
#done!
Phew. We're done
solving. Yes. That simple.
Now we need to output the stuff. I didn't use a png exporter (couldn't bother) so I just outputted bytes rotated to taste.
minX, minY, maxX, maxY just take the dimensions of the isle and normalize the block's positions.
I also do some tricks to spit out the blocks rotated correctly.
# this is a little thing that shows the resilience of the algo.
# it could be possible to have a set of pieces that end up as two puzzles or three.
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)