#!/usr/bin/env python

COLOR = True
FIX_DEAD_CELLS = False

from bool_solve import *
from sys import stderr
from math import ceil, floor
from copy import copy

try:
    import psyco
    psyco.full()
except ImportError:
    pass

O = True
_ = False

if COLOR:
    rep = { True : "\x1b[0;91m#\x1b[0m",
            False: "-",
            None : "\x1b[0;92m?\x1b[0m",
          }
else:
    rep = { True : "#",
            False: "-",
            None : "?",
          }

from array import array
class Matrix:
    def __init__(self, width, height, default = None):
        self.__width__ = width
        self.__internal__ = [default] * (width * height)

    def __getitem__(self, (x, y)):
        return self.__internal__[x + (y * self.__width__)]

    def __setitem__(self, (x, y), val):
        self.__internal__[x + (y * self.__width__)] = val

'''
state = [[ _, _, _, _, _ ],
         [ _, _, O, _, _ ],
         [ _, _, _, O, _ ],
         [ _, O, O, O, _ ],
         [ _, _, _, _, _ ]]
'''
#'''
state = [[ _, _, _, _, _ ],
         [ _, O, O, O, _ ],
         [ _, O, _, O, _ ],
         [ _, O, O, O, _ ],
         [ _, _, _, _, _ ]]
#'''
'''
state = [[ _, _, _, _ ],
         [ _, O, _, _ ],
         [ _, _, O, _ ],
         [ _, _, _, _ ]]
'''
'''
state = [[ _, _, _ ],
         [ _, O, _ ],
         [ _, _, _ ]]
'''

def bool_fold(grid, fold_op, destroy = True):
    if not destroy:
        grid = copy(grid)

    assert(len(grid) > 0)
    if len(grid) == 1:
        return grid[0]

    h = len(grid) / 2.
    hh = int(ceil(h))
    hl = int(floor(h))

    root  = [fold_op, None, None]


            # nodes to go in this branch
                   # Parent
                         # Index in the parent branch
    stack = [(hh, root, 1), (hl, root, 2)]
    while len(grid) > 0:
        num, p, i = stack.pop()
        if num == 1:
            p[i] = grid.pop()

        else:
            node  = [fold_op, None, None]
            p[i] = node

            h = num / 2.
            hh = int(ceil(h))
            hl = int(floor(h))
            stack.append((hh, node, 1))
            stack.append((hl, node, 2))

    return root


def get_true_tree(x, y, width, height):
    sz = serialize
    possibilities = []
    combinations = []

    #################################################################
    # Alive cell, two neighbours
    for ix in xrange(-1, 2):
        for iy in xrange(-1, 2):

            if (ix, iy) == (0, 0): continue

            for jx in xrange(-1, 2):
                for jy in xrange(-1, 2):
                    if (jx, jy) == (ix, iy): continue
                    if (jx, jy) == (0, 0)  : continue

                    combinations.append(((ix, iy), (jx, jy), True))

    #################################################################
    # Three neighbours
    for ix in xrange(-1, 2):
        for iy in xrange(-1, 2):

            if (ix, iy) == (0, 0): continue

            for jx in xrange(-1, 2):
                for jy in xrange(-1, 2):
                    if (jx, jy) == (ix, iy): continue
                    if (jx, jy) == (0, 0)  : continue

                    for kx in xrange(-1, 2):
                        for ky in xrange(-1, 2):
                            if (kx, ky) in ((ix, iy), (jx, jy)): continue

                            if (kx, ky) == (0, 0): continue

                            combinations.append(((ix, iy), (jx, jy), (kx, ky)))

    #################################################################
    # Possibility resolution
    for combination in combinations:
        grid = []
        if True in combination: grid = [sz(x, y)]
        for _x in xrange(-1, 2):
            for _y in xrange(-1, 2):
                if _x != 0 or _y != 0:
                    data = sz((x + _x) % width, (y + _y) % height)
                    if (_x, _y) in combination:
                        grid.append(data)
                    else:
                        grid.append((NOT_OP, data))

        possibilities.append(bool_fold(grid, AND_OP))

    return bool_fold(possibilities, OR_OP)

def add_pairs(num, target, log = ()):
    for ix in xrange(-1, 2):
        for iy in xrange(-1, 2):

            if (ix, iy) in log: continue
            elif num == 1: target.append(log + ((ix, iy),))
            else:          add_pairs(num - 1, target, log + ((ix, iy),))

def get_false_tree(x, y, width, height):
    sz = serialize

    possibilities = []
    combinations = []

    combinations.append( () ) # No neighbours

    # One neighbour
    for ix in xrange(-1, 2):
        for iy in xrange(-1, 2):

            if (ix, iy) == (0, 0): continue
            combinations.append(((ix, iy), ))

    #################################################################
    # Dead cell, two neighbours
    add_pairs(2, combinations, (False, (0, 0)))

    # >3 neighbours
    add_pairs(4, combinations, (False, ))

    # 5, 6, 7, 8
    for i in xrange(5, 9):
        add_pairs(9 - i, combinations)

    #################################################################
    # Possibility resolution
    for combination in combinations:
        grid = []
        inverted = False in combination
        if (0, 0) in combination:
            grid.append(sz(x, y))

        for _x in xrange(-1, 2):
            for _y in xrange(-1, 2):
                if _x == 0 and _y == 0: continue
                data = sz((x + _x) % width, (y + _y) % height)
                if ((_x, _y) in combination) ^ inverted:
                    grid.append(data)
                else:
                    grid.append((NOT_OP, data))

        possibilities.append(bool_fold(grid, AND_OP))

    return bool_fold(possibilities, OR_OP)

# Assert rectangular field
def life_reverse(state, fix_dead = False):
    print >>stderr, "Generating code..."

    requisites = []
    height = len(state)
    width  = len(state[0])
    for y in xrange(height):
        for x in xrange(width):
            if   state[y][x] == True:
                requisites.append(get_true_tree(x, y, width, height))

            elif state[y][x] == False and fix_dead:
                requisites.append(get_false_tree(x, y, width, height))
                #requisites.append((NOT_OP, get_true_tree(x, y, width, height)))

    f = bool_fold(requisites, AND_OP)

    print >>stderr, "Solving equation..."
    return get_solutions(f)


def show_state(state):
    for row in state:
        for c in row:
            if c: print "#",
            else: print " ",
        print ""


def show_solution_state(state, width, height):
    m = Matrix(width, height, None)
    for s in state:
        b = not s.inverted
        x, y = unserialize(s.name)
        m[x, y] = b

    for x in xrange(width):
        for y in xrange(height):
            c = m[x, y]
            print rep[c],

        print ""

def serialize(row, col):
    return "%s.%s" % (row, col)

def unserialize(s):
    row, col = s.split(".")
    return int(row), int(col)

solutions = life_reverse(state, FIX_DEAD_CELLS)

if not solutions:
    print "Unreversable state"

else:
    first = True

    for solution in solutions:
        if not first: print "\x1b[0;93m" + ("-" * (len(state) * 2)) + "\x1b[0m"
        else: first = False

        #print_solutions(solution)
        #show_state(state)
        show_solution_state(solution, len(state[0]), len(state))

    print len(solutions), "solutions"