from itertools import product, permutations

def next_permutation(seq):
    """Like C++ std::next_permutation() but implemented as
    generator. Yields copies of seq."""
    def reverse(seq, start, end):
        # seq = seq[:start] + reversed(seq[start:end]) + \
        #       seq[end:]
        end -= 1
        if end <= start:
            return
        while True:
            seq[start], seq[end] = seq[end], seq[start]
            if start == end or start+1 == end:
                return
            start += 1
            end -= 1
    if not seq:
        raise StopIteration
    try:
        seq[0]
    except TypeError:
        raise TypeError("seq must allow random access.")
    first = 0
    last = len(seq)
    seq = seq[:]
    # Yield input sequence as the STL version is often
    # used inside do {} while.
    yield seq[:]
    if last == 1:
        raise StopIteration
    while True:
        next = last - 1
        while True:
            # Step 1.
            next1 = next
            next -= 1
            if seq[next] < seq[next1]:
                # Step 2.
                mid = last - 1
                while seq[next] >= seq[mid]:
                    mid -= 1
                seq[next], seq[mid] = seq[mid], seq[next]
                # Step 3.
                reverse(seq, next1, last)
                # Change to yield references to get rid of
                # (at worst) |seq|! copy operations.
                yield seq[:]
                break
            if next == first:
                raise StopIteration
    raise StopIteration

pentomino_order = 'FILNPTUVWXYZ'
#                  012345678901

# 61 50
# 89 4 10
# 7 11 23
pentominos = '''
.xx
xx.
.x.

xxxxx

...x
xxxx

xx..
.xxx

xx.
xxx

xxx
.x.
.x.

x.x
xxx

x..
x..
xxx

x..
xx.
.xx

.x.
xxx
.x.

..x.
xxxx

xx.
.x.
.xx'''

def process(pp):
    lines = pp.split()

    x = 0
    y = lines[0].index('x')

    items = []
    for i, line in enumerate(lines):
        for j, char in enumerate(line):
            if char == 'x':
                items.append((i-x, j-y))
    return items

def normalize(P):
    x = min(P)[0]
    y = min(P, key=lambda t:t[1])[1]

    return tuple(sorted([(i-x, j-y) for (i,j) in P]))

def rotate(pp, off, swap):
    if swap:
        return [(dy*off[0], dx*off[1]) for (dx,dy) in pp]
    else:
        return [(dx*off[0], dy*off[1]) for (dx,dy) in pp]

def rotations(pp):
    all_rots = [rotate(pp, x, swap) for x in product([-1,1], repeat=2) for swap in (False, True)]

    return set(normalize(x) for x in all_rots)

def place(pp, offx, offy):
    return [(i+offx, j+offy) for (i,j) in pp]

def adjacent(p1, p2):
    for k in p1:
        for y in p2:
            if abs(k[0]-y[0])+abs(k[1]-y[1]) == 1: return True
    return False

pentominos = [process(x) for x in pentominos.split('\n\n')]
rots = [rotations(x) for x in pentominos]

prods = {}

for p1 in range(12):
    for p1rot in rots[p1]:
        for p2 in range(12):
            if p1 == p2: continue
            for p2rot in rots[p2]:
                for p1y in range(6):
                    p1placed = place(p1rot, 0, p1y)
                    for p2x in range(6):
                        for p2y in range(6):
                            p2placed = place(p2rot, p2x, p2y)

                            if not (set(p1placed) & set(p2placed)) and adjacent(p1placed,p2placed):
                                prods.setdefault((min(p1,p2),max(p1,p2)), set()).add(normalize(p1placed+p2placed))

print("Part 1 done")

#uncomment the commented code below to get this list of partitions
solutions = [[1, 1, 2, 2, 3, 1, 1, 2, 3, 3, 3, 2],
[1, 2, 1, 3, 3, 2, 2, 3, 3, 1, 1, 2],
[1, 2, 2, 2, 1, 1, 3, 3, 2, 3, 3, 1],
[1, 2, 3, 1, 3, 2, 2, 1, 1, 3, 3, 2]]

can_match = set()

for s in solutions:
    groups = [tuple([x for x in range(12) if s[x]==i]) for i in range(1,4)]

    print ("NEW SOLUTION")
    for x in groups:
        print(" ".join(pentomino_order[y] for y in x))

    for p1 in range(12):
        for p2 in range(p1+1,12):
            for p3 in range(p1+1,12):
                for p4 in range(p3+1,12):
                    if len(set([p1,p2,p3,p4])) != 4: continue

                    if (p1,p2) in prods and (p3,p4) in prods:
                        common = prods[p1,p2] & prods[p3,p4]
                        if common:
                            for x in permutations([p1,p2,p3,p4]):
                                if x in groups:
                                    print("For group ", groups.index(x), sep=' ')
                                    print( next(iter(common)) )
                                #can_match.add(tuple(x))

# for k in next_permutation([1,1,1,1,2,2,2,2,3,3,3,3]):
#   min1 = k.index(1)
#   min2 = k.index(2)
#   min3 = k.index(3)
#   if not min1 < min2 < min3: continue

#   if all(tuple([x for x in range(12) if k[x]==i]) in can_match for i in range(1,4)):
#       print(k)