import logging
log = logging.getLogger(__name__)

class Matrix:
    def __init__(self, w, h):
        self.w = w
        self.h = h
        self.m = [0] * (w*h)

    def __getitem__(self, key):
        return self.m[key[0]*self.w+key[1]]

    def __setitem__(self, key, value):
        self.m[key[0]*self.w+key[1]] = value

    def __repr__(self):
        return self.toString('\n')

    def toString(self, separator='|'):
        result = ''
        for row in range(self.h):
            for col in range(self.w):
                result += str(self[row, col])
            result += separator
        return result

    def clone(self):
        result = Matrix(self.w, self.h)
        result.m = list(self.m)
        return result

    def reduce(self):
        fullRows = {}
        fullCols = {}
        for row in range(self.h):
            for col in range(self.w):
                if self[row, col]:
                    fullRows[row] = 1
                    fullCols[col] = 1
        newm = []
        rows = fullRows.keys()
        rows.sort()
        for row in rows:
            newm.extend(self.m[row*self.w:(row+1)*self.w])
        self.m = newm
        self.h = len(rows)
        newm = []
        cols = fullCols.keys()
        mincol = min(cols)
        maxcol = max(cols)
        for row in range(self.h):
            newm.extend(self.m[row*self.w+mincol:row*self.w+maxcol+1])
        self.m = newm
        self.w = maxcol-mincol+1

    def rotate(self):
        result = Matrix(self.h, self.w)
        for row in range(self.h):
            for col in range(self.w):
                result[col, result.w-row-1] = self[row, col]
        return result

    def mirror(self):
        result = Matrix(self.w, self.h)
        for row in range(self.h):
            for col in range(self.w):
                result[row, self.w-col-1] = self[row, col]
        return result

def uniq(seq): 
    keys = {} 
    for e in seq: 
        keys[repr(e)] = e
    return keys.values()

class Namino:
    def __init__(self, units):
        self.units = units
        self.state = 'Created'

    def title(self):
        if self.state == 'Computed':
            return "Computed namino with %d units, %d pieces" % (
                    self.units, len(self.pieces))
        return "Namino with %d units" % self.units

    def compute(self):
        l = self.computeRaw()
        self.reduce(l)
        result = []
        seen = {}
        for matrix in uniq(l):
            if not seen.has_key(matrix.toString()):
                result.append(matrix)
                seen[matrix.toString()] = 1
                for i in range(3):
                    matrix = matrix.rotate()
                    seen[matrix.toString()] = 1
                matrix = matrix.mirror()
                seen[matrix.toString()] = 1
                for i in range(3):
                    matrix = matrix.rotate()
                    seen[matrix.toString()] = 1
        self.pieces = result
        self.state = 'Computed'

    def reduce(self, l):
        for m in l:
            m.reduce()
        
    def computeRaw(self):
        root = Matrix(self.units*2-1,self.units*2-1)
        root[self.units-1, self.units-1] = 1
        generation = [root]
        i = self.units-1
        while i > 0:
            generation = uniq(self.nextGeneration(generation))
            i -= 1
        return generation

    def nextGeneration(self, l):
        l2 = []
        for m in l:
            l2.extend(self.next(m))
        return l2

    def next(self, m):
        result = []
        for row in range(m.h):
            for col in range(m.w):
                left = (col != 0) and m[row, col-1]
                right = (col != m.w-1) and m[row, col+1]
                up = (row != 0) and m[row-1, col]
                down = (row != m.h-1) and m[row+1, col]
                if (not m[row, col]) and (left or right or up or down):
                    m2 = m.clone()
                    m2[row, col] = 1
                    result.append(m2)
        return result

if __name__ == '__main__':
    pentominos = Namino(5)
    pentominos.compute()
    for piece in pentominos.pieces:
        print(piece)