import numpy as np


def check_associativity(cayley: np.array, semigroup: list) -> bool:
    n = cayley.shape[0]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                q = semigroup.index(cayley[i, k])
                p = semigroup.index(cayley[j, i])
                if cayley[p, k] != cayley[j, q]:
                    return False
    return True


def get_right_ideal(element, semigroup, cayley):
    i = semigroup.index(element)
    return set(cayley[i])


def get_left_ideal(element, semigroup, cayley):
    i = semigroup.index(element)
    return set(cayley.T[i])


def get_semigroup_ideals(semigroup, cayley):
    right_ideals = {}
    left_ideals = {}
    for element in semigroup:
        right_ideals[element] = get_right_ideal(element, semigroup, cayley)
        left_ideals[element] = get_left_ideal(element, semigroup, cayley)
    return right_ideals, left_ideals


def create_table(semigroup, translations):
    cayley = []
    for i in semigroup:
        row = []
        for j in semigroup:
            word = i + j
            word = translate_word(word, translations)
            row.append(word)
        cayley.append(row)
    return np.array(cayley)


def translate_word(word, translations):
    while True:
        tmp = word
        for key, val in translations:
            word = word.replace(key, val)
        if tmp == word:
            break
    return word


def create_grin_relation(semigroup, right_ideals, left_ideals):
    n = len(semigroup)
    r = np.zeros((n, n), dtype=bool)
    l = np.zeros((n, n), dtype=bool)
    for i in range(n):
        for j in range(n):
            element1 = semigroup[i]
            element2 = semigroup[j]
            r[i][j] = (right_ideals[element1] == right_ideals[element2])
            l[i][j] = (left_ideals[element1] == left_ideals[element2])
    return r, l


def dfs(graph, used, v, l, is_transposed=False):
    used[v] = True

    if is_transposed:
        l.append(v)

    for i in range(len(graph)):
        if not(used[i]) and graph[v][i]:
            dfs(graph, used, i, l, is_transposed)

    if not is_transposed:
        l.append(v)


def get_egg_box(grin_relation, semigroup):
    n = len(grin_relation)
    used = np.zeros(n)

    component = []
    order = []

    for i in range(n):
        if not used[i]:
            dfs(grin_relation, used, i, order)

    used = np.zeros(n)
    egg_box = []
    for i in range(n):
        v = order[n - 1 - i]
        if not used[v]:
            dfs(grin_relation.T, used, v, component, True)
            egg_box.append(component.copy())
            component.clear()

    return [[semigroup[elem] for elem in egg] for egg in egg_box]


def print_cayley(semigroup, cayley):
    n = len(semigroup)
    m = max(np.char.str_len(cayley.flatten()))
    print(' ' * (m + 2) + '\u2502', end='')
    for i in range(n):
        print(semigroup[i].rjust(m + 1, ' ') + ' ', end='')
    print()
    print('\u2500' * (m + 2) + '\u253C' + '\u2500' * ((m + 2) * n))
    for i in range(n):
        print(semigroup[i].rjust(m + 1, ' ') + ' \u2502', end='')
        for j in range(n):
            print(cayley[i, j].rjust(m + 1, ' '), end=' ')
        print()


def print_ideals(semigroup, right_ideals, left_ideals):
    for element in semigroup:
        r = right_ideals[element]
        l = right_ideals[element]
        print(f"({element}] = {{{', '.join(r)}}}")
        print(f"[{element}) = {{{', '.join(l)}}}")
        print(f"[{element}] = {{{', '.join(r | l)}}}")


def make_semigroup():
    print("Введите элементы полугруппы:")
    semigroup = set(input().split())

    print("Введите количество преобразований:") 
    k = int(input())

    print(f"Введите преобразования:")
    translations = []
    for _ in range(k):
        key, val = input().split()
        translations.append((key, val))

    while True:
        new_elements = set()
        for i in semigroup:
            for j in semigroup:
                word = i + j
                word = translate_word(word, translations)
                new_elements.add(word)        
        tmp = semigroup.copy()
        semigroup |= new_elements
        if tmp == semigroup:
            break

    semigroup = list(semigroup)
    semigroup.sort()

    return semigroup, translations


def main():
    semigroup, translations = make_semigroup()
    print("Полугруппа:")
    print(semigroup)

    print("Таблица Кэли:")
    cayley = create_table(semigroup, translations)
    print_cayley(semigroup, cayley)

    if not check_associativity(cayley, semigroup):
        print("Ассоциативность для данной таблицы Кэли не выполняется")
        return

    print("Отношение Грина:")
    right_ideals, left_ideals = get_semigroup_ideals(semigroup, cayley)
    r, l = create_grin_relation(semigroup, right_ideals, left_ideals)
    d = r + l
    print(d.astype(int))

    print("Идеалы:")
    print_ideals(semigroup, right_ideals, left_ideals)

    print("egg-box диаграмма:")
    egg_box = get_egg_box(d, semigroup)
    print(egg_box)


if __name__ == "__main__":
    main()