# -*- coding: utf-8 -*-
"""
Created on Wed Apr 29 09:35:45 2026

@author: robin
"""

import sympy as sp
import matplotlib.pyplot as plt
import os
import matplotlib.pyplot as plt
import numpy as np

######################################################################################
### On regarde si deux polynômes A et B sont congrus modulo un polynôme M dans Z_p ###
######################################################################################

# Pour ce faire, étant donné que A est congru à B modulo M si et seulement si le reste
# de la division Euclidienne de A-B par M est nul, on crée des programmes permettant
# de calculer ces différentes informations #

# Pour ce faire, on créé d'abord un programme calculant le degré d'un polynôme #

def deg(P):
    i = len(P)-1
    liste=P[::-1] #On retourne la liste pour l'avoir dans le bon sens
    while i >= 0 and liste[i] == 0: # On regarde s'il n'y pas de zéro de tête qui font que le degré n'est pas len(P)-1
        i -= 1
    return i

# Ensuite, on effectue un programme calculany la soustraction de deux polynômes dans Z_p #

def soustraction(A, B, p):
    n=max(len(A), len(B))
    C=[0]*n # On crée d'abord une liste avec que des zéros puis on traite les différents cas
    for i in range(n):
        if i<len(A):
            a=A[i]
        elif i>=len(A):
            a=0
        if i<len(B):
            b=B[i]
        elif i>=len(B):
            b=0
        C[i]=a-b
        if p!=0:
            C[i] %= p
    return C

# On effectue à présent un programme rendant a si a est inversible dans Z_p et une erreur sinon #

def inverse_mod(a, p):       
    for x in range(1, p):
        if (a * x) % p == 1:
            return x
    raise ValueError("Pas inversible")

# On s'intéresse à présent à un programme donnant le reste de la division Euclidienne du polynôme A par le polynôme B dans Z_p #

def division_reste(A, B, p):
    R=[]
    for element in A:
        R.append(element)
     
    dB=deg(B)
    
    while len(R)>0 and (len(R)-1) >=dB: # la division continue tant qu'il reste des éléments dans R et que le degré de R est supérieur ou égal à B
        dR = len(R)-1
        
        if R[dR]==0:
            R_nouvel=[]
            for j in range(len(R)-1):
                R_nouvel.append(R[j])
            R=R_nouvel
            continue
        
        inv=inverse_mod(B[dB], p)
        coeff = (R[dR] * inv) % p
        
        shift = dR-dB
        
        for i in range(dB+1):
            R[i+shift] = (R[i+shift]-coeff*B[i]) % p
        while len(R)>0 and R[len(R)-1]==0:
            R_nouvel=[]
            for j in range(len(R)-1):
                R_nouvel.append(R[j])
            R=R_nouvel
    
    if len(R)==0:
        return [0]
    else:
        return R

# Enfin, on crée un programme disant si un polynôme P est nul #

def est_nul(P):
    for i in range(len(P)):
        if P[i]!=0:
            return False # Si on trouve un élément non nul, le polynôme n'est pas nul
    return True # si toutes les éléments sont nuls, le polynôme est nul
    
# Pour finir, on crée  notre programme disant si le polynôme A est congru au polynôme B modulo le polynôme M dans Z_p #
    
def congru(A, B, M, p):
    diff= soustraction(A, B, p)
    reste = division_reste(diff, M, p)
    return est_nul(reste) # si le polynôme est nul, alors A et B sont congrus donc on retourne True sinon on retourne False

###################################################################################################################
### On crée à présent un programme permettant de savoir si deux mots w1 et w2 sont (u, M)-binomiaux équivalents ###
###################################################################################################################

# Pour ce faire, on doit d'abord savoir calculer une q-déformations de deux mots #

q = sp.Symbol('q')

def qbin(u, v):

    if not v:
        return sp.Integer(1) 

    if not u:
        return sp.Integer(0) 
                           
    u_prime, a = u[:-1], u[-1]   
    v_prime, b = v[:-1], v[-1]

    terme_1 = qbin(u_prime, v)*(q**len(v))

    if a == b:
        terme_2 = qbin(u_prime, v_prime)

    else:
        terme_2 = sp.Integer(0)
        
    return sp.expand(terme_1 + terme_2)

# On crée ensuite un programme qui à partir du polynôme obtenu précédemment, nous donne une liste de coefficients #

def qbinlist(u, v, p):
    coeffs=sp.Poly(qbin(u,v), q).all_coeffs()
    liste_finale=[]
    for c in coeffs[::-1]:
        if p!=0:
            valeur_modulo=c%p
        else:
            valeur_modulo=c
        liste_finale.append(valeur_modulo)
    return liste_finale

# Quand on étudie si deux mots sont (u, M)-binomiaux équivalents, on utilise l'ensemble des facteurs de u
# On crée donc un porgramme donant les facteurs d'un mot u #

def factors(u):
    facs = [] # On définit un ensemble vide dans lequel on va mettre les facteurs de u
    n = len(u)
    for i in range(n):
        for j in range(i, n+1): # Pour chaque élément i on parcourt tous les mots restant dans le mot u.
            f = u[i:j]
            if f not in facs: # On regarde ensuite si le mot est déjà dans l'ensemble des facteurs.
                facs.append(f) # S'il n'y est pas on l'ajoute

# On trie les facteurs dans l'ordre lexicographique, c'est-à-dire selon la longueur puis selon l'ordre des lettres    
    permutation=True
    while permutation==True:
        permutation=False
        compteur=0
        while compteur<len(facs)-1:
            mot1=facs[compteur]
            mot2=facs[compteur+1]
            
            inverser=False
            if len(mot1)>len(mot2): # on trie d'abord selon la longueur
                inverser=True
            elif len(mot1)==len(mot2): # une fois les longueurs les mêmes on fait selon l'ordre des lettres
                fini=False
                k=0
                while k<len(mot1) and fini==False:
                    if mot1[k]>mot2[k]:
                        inverser=True
                        fini=True
                    elif mot1[k]<mot2[k]:
                        fini=True
                    k+=1
            if inverser==True:
                facs[compteur]=mot2
                facs[compteur+1]=mot1
                permutation=True
            compteur+=1
    return facs

# On peut à présent avoir un programme disant si deux mots w1 et w2 sont (u, M)-binomiaux équivalents

def umequiv(u, p, M, w1, w2):
    facs=factors(u)
    facteur=facs[1:len(facs)] # On enlève le mot vide des facteurs
    
    for v in facteur:
        liste1=qbinlist(w1, v, p) # on calcule la liste des coefficients pour w1 et w1 par rapport à v
        liste2=qbinlist(w2, v, p)
        if congru(liste1, liste2, M, p)==False: # si c'est faux pour un facteur, alors ils ne sont pas équivalents
            return "Les deux mots ne sont pas binomiaux équivalents" 
               
    return "Les deux mots sont binomiaux équivalents" # si la boucle s'est terminée, c'est qu'ils sont équivalents

###########################################################################################################################
### On veut à présent une fonction qui nous donne le nombre de classes d'équivalences dans le quotient A^*/sim_{u, M} ###
###########################################################################################################################

# On crée maintenant une fonction qui dans chaque cas étudie la signature d'un mot w #

def signature(u, p, M, w):
    facs=factors(u)
    facteur=facs[1:len(facs)] # On enlève le mot vide
    sig=[] # On crée une liste vide qui sera notre signature
    
    for v in facteur:
        poly=qbinlist(w, v, p)
        poly_mod=division_reste(poly, M, p) # On calcule pour tous les facteurs qbin{w}{v} modulo M et on ajoute la signature à sig
        sig.append(tuple(poly_mod))
    
    return tuple(sig)

# On peut ainsi calculer le nombre de classes d'équivalences en calculant le nombre de signatures distinctes #        

def nombre_classes(A, u, p, M):
    signatures = set()
    words = [""]   # mots de longueur courante
    ancien = -1
    L = 0

    while True:
        new_words = []

        for w in words:
            sig = signature(u, p, M, w) # On calcule la signature du mot w et on ajoute cela à l'ensemble signatures
            signatures.add(sig)

        print("Longueur", L, "→", len(signatures), "classes")

        if len(signatures) == ancien: # S'il n'y a pas de nouvelles signatures, on a atteint une stabilisation et donc le nombre de classes d'équivalences
            print("Stabilisation atteinte à la longueur", L-1)
            break

        ancien = len(signatures)

        for w in words: # on génère les mots suivants
            for a in A:
                new_words.append(w + a)

        words = new_words
        L += 1

    return len(signatures)

# Après connaître le nombre de classes d'équivalences, on veut pouvoir énumérer un représentant par classes d'équivalences #

def representants_classes(A, u, p, M):
    reps = {}
    words = [""]
    prev_count = -1
    L = 0

    while True:
        new_words = []
        
        for w in words: # on ajoute les nouvelles classes
            sig = signature(u, p, M, w)
            if sig not in reps:
                reps[sig] = w

        if len(reps) == prev_count: # on test la stabilisation
            break

        prev_count = len(reps)
        
        for w in words: # on génère les mots de la longueur suivante
            for a in A:
                new_words.append(w + a)

        words = new_words
        L += 1

    return reps

# A partir d'un polynôme, la fonction retourne la somme de chaque coefficient de poly multiplié par p^i #

def poly_to_int(poly, p):
    val = 0
    for i, coeff in enumerate(poly):
        val += coeff * (p**i)
    return val

# A présent, on peut transformer n'importe quelle signature en un nombre entier #

def signature_to_key(sig, p):
    return tuple(poly_to_int(list(poly), p) for poly in sig)

# On peut dès lors afficher les représentants de chaque classes d'équivalences #

def representants_affichage(A, u, p, M):
    reps = representants_classes(A, u, p, M)
    
    # tri selon la clé, reps.item() transforme le dictionnaire en une liste de paires (signature, mot). Ensuite, key=lambda item: extrait la signature item[0] pour chaque item de mon dictionnaire
    # Ensuite, sorted trie toutes les paures (signature, mot) de la plus petite valeur numérique (on a des valeurs numérique grâce à signature_to_key()) à la plus grande
    reps_tris = sorted(reps.items(), key=lambda item: signature_to_key(item[0], p))
    
    for i, (sig, w) in enumerate(reps_tris, start=1):
        print(f"Classe {i} : {sig} → {w}")
    
    
def numero_classe(A, u, p, M, w):
    reps = representants_classes(A, u, p, M)

    reps_tris = sorted(reps.items(), key=lambda item: signature_to_key(item[0], p))
    
    sig_w = signature(u, p, M, w)
    
    for i, (sig, rep) in enumerate(reps_tris, start=1):

        if sig == sig_w:
            return i

    return None
        
###############################################################
### On veut à présent construire la table de multiplication ###
###############################################################        

def table_multiplication(A, u, p, M):
    reps = representants_classes(A, u, p, M)
    signatures = sorted(reps.keys(), key=lambda sig: signature_to_key(sig, p))

    index = {sig: i+1 for i, sig in enumerate(signatures)} # On associe à chaque signature un entier
    
    n = len(signatures)
    table = [[0]*n for _ in range(n)] # On construit la table pour ensuite la remplir
    
    for i, sig1 in enumerate(signatures):
        w1 = reps[sig1]
        
        for j, sig2 in enumerate(signatures):
            w2 = reps[sig2]
            
            w = w1 + w2 # On concatène les deux mots pour calculer la signature du produit

            sig_prod = signature(u, p, M, w)
            
            table[i][j] = index[sig_prod] # On trouve ensuite la classe correspondante et on note son numéro dans la table 
    
    return table

table=table_multiplication(['a', 'b'], 'ab', 3, [1, 1, 1])

# On affiche dès à présent proprement cette table de multiplication #

def afficher_table(table):
    for ligne in table:
        print(" ".join(f"{x:2}" for x in ligne)) # On affiche les chiffres sur au moins deux caractères
        
#################################################################################################################################
### On veut dès à présent avoir une image avec des couleurs de notre table de multiplication pour l'importer dans un document ###
#################################################################################################################################

# On veut importer la table dans LaTeX #

def table_to_latex(table):
    n = len(table)
    
    latex = "\\begin{tabular}{" + "|".join(["c"]*n) + "}\n" # On crée un tableau pour mettre dans LaTeX et on centre chaque colonne
    
    for i in range(n):
        row = " & ".join(str(table[i][j]) for j in range(n)) # On sépare chaque colonne et on ajoute le bon élément dans chaque case
        latex += row + " \\\\\n" # On fait ça pour chaque ligne
    
    latex += "\\end{tabular}"
    
    return latex

with open("table.tex", "w") as f:
    f.write(table_to_latex(table))
    
# On transforme ensuite le tableau otenu en image pour pouvoir ensuite ajouter des couleurs #
    
def table_to_image(table, filename="table.png"):
    n = len(table)
    
    fig, ax = plt.subplots(figsize=(12,12)) # On crée notre image
    ax.axis('off') # On supprime les axes
    
    table_text = [[str(x) for x in row] for row in table] # On transforme chaque élément en texte car matplotlib exige du texte
    
    tab = ax.table(cellText=table_text, loc='center') # On insère dans le tableau le contenu des cellules
    tab.auto_set_font_size(False)
    tab.set_fontsize(6) # On fixe la taille
    
    plt.savefig(filename, bbox_inches='tight') # On sauvegarde l'image en enlevant les marges inutiles
    plt.close()
    
# Pour finir on veut pouvoir mettre des couleurs pour que l'image soit visuelle #
    
def table_coloree(table, filename="table_couleur.png"):
    n = len(table)
    data = np.array(table)

    cmap = plt.get_cmap('hsv', n) # On choisit la palette de couleur

    fig, ax = plt.subplots(figsize=(12,12)) # On crée notre image
    
    ax.imshow(data, cmap=cmap) # On associe à chaque entier une couleur

    ax.set_xticks(range(n))
    # ax.set_xticks([])
    ax.set_xticklabels(range(1, n+1), fontsize=10)
    ax.xaxis.tick_top() # On affiche les entiers de 1 à n sur le haut de l'image pour représenter chaque classe

    ax.set_yticks(range(n))
    # ax.set_yticks([])
    ax.set_yticklabels(range(1, n+1), fontsize=10) # On fait la même chose pour l'axe vertical
    
    ax.set_xticks(np.arange(-0.5, n, 1), minor=True)
    ax.set_yticks(np.arange(-0.5, n, 1), minor=True) # On dessine les différentes cases du tableau
    ax.grid(which="minor", color="black", linewidth=0.3)

    for i in range(n): # On affiche les valeurs dans les différentes cases en faisant deux boucles pour avoir toutes les cases
       for j in range(n):

           val = int(data[i, j])

           ax.text(
               j, i,
               str(val),
               ha='center',
               va='center',
               fontsize=9,
               color='black',
               fontweight='bold'
            )

    plt.savefig(filename, bbox_inches='tight', dpi=300)
    plt.close()
    
#################################################################
### Construction de l'automate minimal à partir d'un automate ###
#################################################################

def construire_automate():

    n = int(input("Nombre d'états : ")) # On demande le nombre n d'états

    states = list(range(1, n+1)) # On note que l'ensemble des états est 1, ..., n

    alphabet = input("Alphabet (séparé par des espaces) : ").split() # On demande les lettres qu'il y a dans l'alphabet

    transitions = {} # Pour demander les transitions de l'automate, on définit d'abord un ensemble vide

    print("\n--- Définition des transitions ---")

    for s in states:

        transitions[s] = {}

        for a in alphabet:

            t = int(input(f"Transition depuis {s} avec {a} : ")) # L'auteur introduit toutes les transitions de l'automate

            transitions[s][a] = t

    initial = int(input("\nÉtat initial : ")) # On demande l'état initial

    finals = list(map(
        int,
        input("États finals (séparés par des espaces) : ").split() # On demande les états finals
    ))

    auto = { # On construit notre automate
        "states": states,
        "alphabet": alphabet,
        "transitions": transitions,
        "initial": initial,
        "finals": finals
    }

    return auto

def automate_minimal():    
    auto=construire_automate()
    states = auto["states"]
    alphabet = auto["alphabet"]
    transitions = auto["transitions"]
    finals = set(auto["finals"])

# On utilise l'algorithme de recherche des états équivalents

    nonfinals = set(states) - finals

    partitions = []

    if finals:
        partitions.append(finals)

    if nonfinals:
        partitions.append(nonfinals)

    stable = False

    while not stable:

        stable = True

        nouvelles_partitions = []

        for bloc in partitions:

            separation = {}

            for s in bloc:

                signature = []

                for a in alphabet:

                    t = transitions[s][a]

                    # On cherche dans quelle partition tombe t
                    for i, P in enumerate(partitions):

                        if t in P:
                            signature.append(i)
                            break

                signature = tuple(signature)

                if signature not in separation:
                    separation[signature] = []

                separation[signature].append(s)

            # On ajoute les sous-blocs
            for sous_bloc in separation.values():
                nouvelles_partitions.append(set(sous_bloc))

            # si on a découpé un bloc
            if len(separation) > 1:
                stable = False

        partitions = nouvelles_partitions

# On construit le quotient

    numero = {}

    for i, bloc in enumerate(partitions, start=1):

        for s in bloc:
            numero[s] = i

    new_transitions = {}

    for i, bloc in enumerate(partitions, start=1):

        representant = next(iter(bloc))

        new_transitions[i] = {}

        for a in alphabet:

            t = transitions[representant][a]

            new_transitions[i][a] = numero[t]

    new_finals = set()

    for i, bloc in enumerate(partitions, start=1):

        if bloc & finals:
            new_finals.add(i)

    new_initial = numero[auto["initial"]]

    return {
        "states": list(range(1, len(partitions)+1)),
        "alphabet": alphabet,
        "transitions": new_transitions,
        "initial": new_initial,
        "finals": list(new_finals),
        "partitions": partitions
    }