class Operator():
    # Represents a binary operator
    def __init__(self, matrix):
        self.matrix = tuple([tuple(j) for j in matrix])

    def __eq__(self, op2): # To identify duplicates
        return (self.matrix == op2.matrix)

    def __hash__(self): # To accelerate duplicate search
        return hash(self.matrix)

    def __repr__(self):
        return "Operator(" + str(self.matrix) + ")"
    
    def apply(self, s1, s2):
        # Generate a -> (s1(a) self s2(a))
        a = s1.value
        b = s2.value
        result = [self.matrix[a[i]+1][b[i]+1] for i in range(3)]
        return State(result)

    def apply_2d(self, s1, s2):
        # Generate (a, b) -> (s1(a) self s2(b))
        result = [[self.matrix[s1.value[i]+1][s2.value[j]+1] for i in range(3)] for j in range(3)]
        return Operator(result)

    def compose_right(self, op2):
        # Generate (a, b) -> (a self (a op2 b))
        result = [[self.matrix[i][op2.matrix[i][j]+1] for i in range(3)] for j in range(3)]
        return Operator(result)

    def compose_left(self, op2):
        # Generate (a, b) -> ((a op2 b) self b)
        result = [[self.matrix[op2.matrix[i][j]+1][j] for i in range(3)] for j in range(3)]
        return Operator(result)

    def is_degenerate(self):
        # Returns True if the operator is a constant
        val = self.matrix[0][0]
        for i in range(3):
            for j in range(1,3):
                if (self.matrix[i][j] != val):
                    return False
        return True

    def is_self_similar(self):
        for i in range(3):
            if (self.matrix[i][i]+1 != i):
                return False
        return True

    def is_commutative(self):
        for i in range(3):
            for j in range(3):
                if (self.matrix[i][j] != self.matrix[j][i]):
                    return False
        return True

    def is_associative(self):
        for i in range(3):
            for j in range(3):
                for k in range(3):
                    if (self.matrix[i][self.matrix[j][k]+1] != self.matrix[self.matrix[i][j]+1][k]):
                        return False
        return True

    def is_distributive(self, op_or):
        for i in range(3):
            for j in range(3):
                for k in range(3):
                    op_comp1 = self.matrix[op_or.matrix[i][j]+1][k]
                    op_comp2 = op_or.matrix[self.matrix[i][k]+1][self.matrix[j][k]+1]
                    if (op_comp1 != op_comp2):
                        return False
        return True

class State():
    # Represents an unary operator
    def __init__(self, value):
        self.value = tuple(value)

    def __eq__(self, s2):
        return (self.value == s2.value)

    def __hash__(self):
        return hash(self.value)

    def __repr__(self):
        return "State(" + str(self.value) + ")"

    def apply(self, s2):
        # Generate a -> self(s2(a))
        op_comp = [self.value[s2.value[i]+1] for i in range(3)]
        return State(op_comp)
    
    def apply_2d(self, op):
        # Generate (a, b) -> self(a op b)
        op_comp = [[self.value[op.matrix[i][j]+1] for i in range(3)] for j in range(3)]
        return Operator(op_comp)

    def is_degenerate(self):
        val = self.value[0]
        for i in self.value:
            if (val != i):
                return False
        return True
            

def is_half_deMorgan(op_or, op_and, op_not):
    result = True
    op_comp1 = op_not.apply_2d(op_or)
    op_comp2 = op_and.apply_2d(op_not, op_not)
    return op_comp1 == op_comp2

def gen_op(a=0, b=0, gop=[[0 for i in range(3)] for j in range(3)]):
    op = [[gop[j][i] for i in range(3)] for j in range(3)]
    b1 = b+1
    a1 = a
    if b1==3:
        a1 = a+1
        b1 = 0
    if (a >= 3 or b >= 3):
        yield Operator(op)
    else:
        for k in [-1, 0, 1]:
            op[a][b] = k
            yield from gen_op(a1, b1, op)

def gen_not(a=0, gop=[0 for i in range(3)]):
    op = [gop[i] for i in range(3)]
    if (a >= 3):
        yield State(op)
    else:
        for k in [-1, 0, 1]:
            op[a] = k
            yield from gen_not(a+1, op)

def chose2(vals):
    for i in vals:
        for j in vals:
            if (i!=j):
                yield (i, j)


def reachables(operators):
    # Populate the reachable operators with identities and constants
    reachables_default = {
        Operator([[1, 1, 1], [1, 1, 1], [1, 1, 1]]),          # (a, b) -> 1
        Operator([[0, 0, 0], [0, 0, 0], [0, 0, 0]]),          # (a, b) -> 0
        Operator([[-1, -1, -1], [-1, -1, -1], [-1, -1, -1]]), # (a, b) -> i
        Operator([[-1, -1, -1], [0, 0, 0], [1, 1, 1]]),       # (a, b) -> a
        Operator([[-1, 0, 1], [-1, 0, 1], [-1, 0, 1]])        # (a, b) -> b
    }
    reachables = reachables_default | set(operators)

    num_reachables = 0
    old_reachables = set()
    count = 0
    while (num_reachables < len(reachables) and len(reachables) < 3**9):
        num_reachables = len(reachables)
        new_reachables = reachables.copy()
        for f in reachables:
            for g in reachables:
                # No need to try pairs that were already tested
                if (not (f in old_reachables and g in old_reachables)):
                    result = f.compose_right(g) # (a, b) -> f(a, g(a, b))
                    #if (result not in new_reachables):
                        #print("r", len(new_reachables), f, g, result)
                    new_reachables.add(result)
                    
                    result = f.compose_left(g)  # (a, b) -> f(g(a, b), b)
                    #if (result not in new_reachables):
                        #print("l", len(new_reachables), f, g, result)
                    new_reachables.add(result)

            # Break early if everything has already been found
            if (len(new_reachables) == 3**9):
                break
            
        old_reachables = reachables
        reachables = new_reachables
        count += 1
        #print(count, len(reachables))
    return reachables

def is_complete(operators):
    return (len(reachables(operators)) == (3**9))