# Liste des pentominos
pentominos = {'F': ['XX \n XX\n X ', '  X\nXXX\n X ', ' X \nXX \n XX',
    ' X \nXXX\nX  ', ' XX\nXX \n X ', ' X \nXXX\n  X', ' X \n XX\nXX ',
    'X  \nXXX\n X '], 'I': ['XXXXX', 'X\nX\nX\nX\nX'], 'L': ['   X\nXXXX',
    'X \nX \nX \nXX', 'XXXX\nX   ', 'XX\n X\n X\n X', 'X   \nXXXX',
    'XX\nX \nX \nX ', 'XXXX\n   X', ' X\n X\n X\nXX'], 'N': ['  XX\nXXX ',
    'X \nX \nXX\n X', ' XXX\nXX  ', 'X \nXX\n X\n X', 'XX\n XXX',
    ' X\nXX\nX \nX ', 'XXX \n  XX', ' X\n X\nXX\nX '], 'P': [' XX\nXXX',
    'X\nXX\nXX', 'XXX\nXX ', 'XX\nXX\n X', 'XX \nXXX', 'XX\nXX\nX ',
    'XXX\n XX', ' X\nXX\nXX'], 'U': ['X X\nXXX', 'XX\nX \nXX', 'XXX\nX X',
    'XX\n X\nXX'], 'T': ['XXX\n X \n X ', '  X\nXXX\n  X', ' X \n X \nXXX',
    'X  \nXXX\nX  '], 'W': ['XX \n XX\n  X', '  X\n XX\nXX ', 'X  \nXX \n XX',
    ' XX\nXX \nX  '], 'V': ['XXX\n  X\n  X', '  X\n  X\nXXX', 'X  \nX  \nXXX',
    'XXX\nX  \nX  '], 'Y': ['  X \nXXXX', 'X \nX \nXX\nX ', 'XXXX\n X  ',
    ' X\nXX\n X\n X', ' X  \nXXXX', 'X \nXX\nX \nX ', 'XXXX\n  X ',
    ' X\n X\nXX\n X'], 'X': [' X \nXXX\n X '], 'Z': ['XX \n X \n XX',
    'X\nXXX\nX  ', ' XX\n X \nXX ', 'X  \nXXX\n  X']}

# TODO
# iterer les pentominos sur une matrice 10x6
# sauf le dernier X sur une 5x3
# transformer les formes obtenues en long
# iterer
def matrix(text):
    result = []
    lines = text.splitlines()
    for line in lines:
        if line:
            row = []
            for bit in line:
                row.append((bit == 'X') and 1 or 0)
            result.append(row)
    return result

def linearise(m):
    value = 0L
    offset = 1L
    for y in range(6):
        for x in range(10):
            if m[y][x]:
                value |= offset
            offset <<= 1
    return value

def isvalid(m):
    bounddown = 1023L
    boundup = 1151795604700004352L
    boundleft = 1127000493261825L
    boundright = 577024252550054400L
    full = 1152921504606846975L
    while m != full:
        # Trouver un trou
        offset = 1L
        while m & offset:
            offset <<= 1
        # Remplir depuis ce trou
        holes = [offset]
        count = 0
        while holes:
            offset = holes.pop()
            if not (m & offset):
                m |= offset
                count += 1
                if not (offset & boundleft):
                    holes.append(offset >> 1)
                if not (offset & boundright):
                    holes.append(offset << 1)
                if not (offset & bounddown):
                    holes.append(offset >> 10)
                if not (offset & boundup):
                    holes.append(offset << 10)
        # Si le compte % 5 != 0
        if count % 5:
            return False
    return True

def iterate(m, width, height):
    result = []
    for y0 in range(height-len(m)+1):
        for x0 in range(width-len(m[0])+1):
            iteration = map(list, [[0]*10]*6)
            for y in range(len(m)):
                for x in range(len(m[0])):
                    iteration[y+y0][x+x0] = m[y][x]
            iteration = linearise(iteration)
            if isvalid(iteration):
                result.append(iteration)
    return result

def shapes(letter, width=10, height=6):
    result = []
    for element in pentominos[letter]:
        result.extend(iterate(matrix(element), width, height))
    return result

def templates():
    result = {}
    for letter in ('F', 'I', 'L', 'N', 'P', 'U', 'T', 'W', 'V', 'Y', 'Z'):
        result[letter] = shapes(letter)
    result['X'] = shapes('X', 6, 4)
    return result

def writeSvg(solution, count):
    colors = ("#c83939","#39c8c6","#a139c8","#87c839","#c8399e","#398ac8",
        "#39c85e","#c8b239","#ff0000","#00ff00","#0000ff","#a6a6a6")
    filename = "solutions/solution%d.svg" % count
    file = open(filename, 'wt+')
    file.write('<?xml version="1.0"?>\n<svg width="500" height="300">\n')
    for i in range(12):
        form = solution[i]
        for y in range(6):
            for x in range(10):
                if form % 2:
                    file.write('<rect fill="%s" height="50" width="50" x="%d" y="%d"/>' % (
                        colors[i], x*50, y*50 ))
                form >>= 1
    file.close()
    print "Solution %d written to %r" % (count, filename)

def place(remaining, board, forms, current=(), count = [1]):
    if not remaining:
        writeSvg(current, count[0])
        count[0] += 1
    else:
        for form in forms[remaining[0]]:
            if not (board & form):
                if isvalid(board | form):
                    place(remaining[1:], board | form, forms, current + (form,), count)

place(('X', 'F', 'I', 'L', 'N', 'P', 'U', 'T', 'W', 'V', 'Y', 'Z'), 0L, templates())