scripts.py

import os
import numpy as np
import os
import heapq




def methode_coin_nord_ouest(emissions, receptions):
    
    # On travaille sur des copies pour ne pas modifier les listes originales
    s = list(emissions)
    d = list(receptions)
    
    nb_emetteurs = len(s)
    nb_recepteurs = len(d)
    
    allocation = np.zeros((nb_emetteurs, nb_recepteurs))
    
    i = 0  # Index de la Source (Ligne)
    j = 0  # Index du Récepteur (Colonne)
    
    # On continue tant qu'on n'a pas parcouru toutes les emetteurs ou récepteurs
    while i < nb_emetteurs and j < nb_recepteurs :
        
        
        # On regarde combien on peut envoyer (le maximum possible)
        quantite = min(s[i], d[j])
        
        # On remplit la case dans le tableau des allocations
        allocation[i][j] = quantite
        
        # On met à jour les compteurs de stock et de besoin
        s[i] -= quantite
        d[j] -= quantite
        
        # SI l'émetteur vaut 0, on descend à la ligne suivante (Sud)
        if s[i] == 0:
            i += 1
        # SINON (si c'est le récepteur qui est plein), on va à la colonne suivante (Est)
        elif d[j] == 0:
            j += 1
            
            
    return allocation




def preprocess_bad_character(pattern):
    
    bad_char = {}
    
    for i, c in enumerate(pattern):
        bad_char[c] = i
        
    return bad_char


def preprocess_good_suffix(pattern):
    
    m = len(pattern)
    good_suffix = [m] * (m + 1)
    border_pos = [0] * (m + 1)

    i = m
    j = m + 1
    border_pos[i] = j

    while i > 0:
        
        while j <= m and pattern[i - 1] != pattern[j - 1]:
            
            if good_suffix[j] == m:
                
                good_suffix[j] = j - i
                
            j = border_pos[j]
            
        i -= 1
        j -= 1
        border_pos[i] = j

    j = border_pos[0]
    
    for i in range(m + 1):
        
        if good_suffix[i] == m:
            good_suffix[i] = j
            
        if i == j:
            j = border_pos[j]

    return good_suffix


def boyer_moore_full(text, pattern):
    
    n = len(text)
    m = len(pattern)

    if m == 0:
        return []

    bad_char = preprocess_bad_character(pattern)
    good_suffix = preprocess_good_suffix(pattern)

    indices = []
    s = 0

    while s <= n - m:
        j = m - 1

        while j >= 0 and pattern[j] == text[s + j]:
            j -= 1

        if j < 0:
            indices.append(s)
            s += good_suffix[0]
        else:
            bc_shift = j - bad_char.get(text[s + j], -1)
            gs_shift = good_suffix[j + 1]
            s += max(bc_shift, gs_shift)

    return indices




def floyd_steinberg_matrice(matrice_entree : list[list]) -> list[list]:
    
    # On crée une copie pour ne pas modifier la liste d'origine
    # On convertit les valeurs en float pour garder la précision du calcul d'ecart
    matrice = [row[:] for row in matrice_entree]
    
    hauteur = len(matrice)
    largeur = len(matrice[0]) if hauteur > 0 else 0


    for y in range(hauteur):


        for x in range(largeur):

            ancienne_valeur = matrice[y][x]

            nouvelle_valeur = 0 if ancienne_valeur < 128 else 255
            matrice[y][x] = nouvelle_valeur


            # Calcul de l'ecart de diffusion
            # Le blanc est obtenu par (255, 255, 255) et le noir par (0, 0, 0)
            
            ecart = ancienne_valeur - nouvelle_valeur

            # Diffusion de l'ecart selon les coefficients de Floyd-Steinberg
            # Pixel à droite (+1, 0)
            if x + 1 < largeur:
                matrice[y][x + 1] = clamp(matrice[y][x + 1] + ecart * 7/16) # écart "foncé" ajouté

            # Pixel en bas à gauche (-1, +1)
            if x - 1 >= 0 and y + 1 < hauteur:
                matrice[y + 1][x - 1] = clamp(matrice[y + 1][x - 1] + ecart * 3/16) # écart "clair" ajouté

            # Pixel juste en dessous (0, +1)
            if y + 1 < hauteur:
                matrice[y + 1][x] = clamp(matrice[y + 1][x] + ecart * 5/16) # écart "clair" ajouté

            # Pixel en bas à droite (+1, +1)
            if x + 1 < largeur and y + 1 < hauteur:
                matrice[y + 1][x + 1] = clamp(matrice[y + 1][x + 1] + ecart * 1/16) # écart "clair" ajouté
                

    return matrice


def clamp(valeur):
    
    """Garantit que la valeur reste entre 0 et 255 et retourne un entier"""
    return max(0, min(255, int(valeur)))




def dijkstra(graphe : dict, depart : str) -> int :
    
    # Initialisation : distance infinie pour tout le monde, 0 pour le départ
    distances = {noeud: float('inf') for noeud in graphe}
    distances[depart] = 0
    
    # File de priorité : (distance, noeud)
    file_priorite = [(0, depart)]
    
    
    while file_priorite:
        
        # On extrait le nœud avec la plus petite distance actuelle
        dist_actuelle, noeud_actuel = heapq.heappop(file_priorite)

        # Si on a déjà trouvé un chemin plus court pour ce nœud, on ignore
        if dist_actuelle > distances[noeud_actuel]:
            continue


        # On explore les voisins
        for voisin, poids in graphe[noeud_actuel].items():
            
            distance = dist_actuelle + poids

            # Si on trouve un chemin plus court vers le voisin
            if distance < distances[voisin]:
                distances[voisin] = distance
                heapq.heappush(file_priorite, (distance, voisin))
                
                
    return distances




def get_n2_permutations(liste):
    
    permutations = []

    for i in range(0, len(liste)):
        
        if i > len(liste)-1:
            break
        else:
            if i+1 > len(liste)-1:
                p = (i+1)-(len(liste)-1)
                permutations.append(liste[i:]+liste[:p])
                permutations.append(list(reversed(liste[i:]+liste[:p])))
            else:
                permutations.append(liste[i:i+2])
                permutations.append(list(reversed(liste[i:i+2])))
    
    
    return permutations


def has_list_1_elements_in_common_with_list_2(list_1, list_2):
    
    return True if list_2[1] not in list_1[:len(list_1)-1] and list_1[-1] == list_2[0] else False


def hook1(arg1, arg2):
    
    result = has_list_1_elements_in_common_with_list_2(arg1, arg2)
    return result


def combine_two_by_two(permutations, original_list_length, final_result):
    
    print("permutations : ", permutations)
    
    if len(permutations[0]) == original_list_length :
        
        final_result = permutations
        
        return final_result
    
    result = []
    
    for i in range(0, len(permutations)):
            
        static_elements = permutations[i]
        
        if i == 0 :
            print("Eléments statiques : ", end="")
            print(static_elements, "\n")
            print(permutations)
        
        new_permutations = [static_elements + [permutation[1]] for permutation in permutations if hook1(static_elements, permutation) == True]
        
        if i == 0 : print(new_permutations, "\n")
        
        result += new_permutations
        if i == 0 : print("result : ", result)
        
    
    permutations = result
    final_result = combine_two_by_two(permutations, original_list_length, final_result)
    
    return final_result
    

def get_permutations(liste):
    
    if not any(isinstance(el, list) for el in liste):
        
        liste_to_list = list(set(liste))
        
        permutations = get_n2_permutations(liste_to_list)
        final_result = combine_two_by_two(permutations, len(liste_to_list), [])


        final_result_to_set = set(tuple(el) for el in final_result)
        final_result_to_list = [list(el) for el in final_result_to_set]

        return final_result_to_list
    
    else:
        
        return liste




def tri_fusion(tab):
    
    if len(tab) <= 1:
        
        return tab
    
    mid = len(tab) // 2
    
    gauche = tri_fusion(tab[:mid])
    droite = tri_fusion(tab[mid:])
    
    resultat = []
    i = j = 0
    
    while i < len(gauche) and j < len(droite):
        
        if gauche[i] <= droite[j]:
            
            resultat.append(gauche[i])
            i += 1
            
        else:
            
            resultat.append(droite[j])
            j += 1
            
    resultat.extend(gauche[i:])
    resultat.extend(droite[j:])
    
    return resultat








if __name__ == "__main__" :
    
        
    os.system("clear")


    # --- EXEMPLES UTILISATION ---

    # 3 Emetteurs (ex: Usines avec leurs stocks)
    stocks_emetteurs = [50, 10] 

    # 3 Récepteurs (ex: Magasins avec leurs besoins)
    besoins_recepteurs = [30, 60]

    # Génération du tableau d'allocations
    tableau_final = methode_coin_nord_ouest(stocks_emetteurs, besoins_recepteurs)

    print("Tableau des Allocations (Résultat du Coin Nord-Ouest) :")
    print(tableau_final)
    
    
    
    text = "ABAAABCDABCABCD"
    pattern = "ABCD"

    resultats = boyer_moore_full(text, pattern)

    print("Texte   :", text)
    print("Motif   :", pattern)
    print("Indices :", resultats)
    
    
    
    
    # Matrice 3x3 en niveaux de gris (0-255)
    matrice_ng = [
        [100, 150, 200, 200],
        [50,  128, 255, 100],
        [0,   200, 100, 150]
    ]
    
    resultat = floyd_steinberg_matrice(matrice_ng)
    
    print("Matrice de sortie (0 ou 255) :")
    for ligne in resultat:
        print(ligne)
    
    
    
    
    # Le graphe est un dictionnaire de dictionnaires : {noeud: {voisin: poids}}
    reseau_routier = {
        'Paris': {'Lyon': 400, 'Lille': 220},
        'Lyon': {'Paris': 400, 'Marseille': 300, 'Nice': 450},
        'Lille': {'Paris': 220},
        'Marseille': {'Lyon': 300, 'Nice': 200},
        'Nice': {'Lyon': 450, 'Marseille': 200}
    }

    resultats = dijkstra(reseau_routier, "Paris")

    print("Distances minimales depuis Paris :")
    for ville, dist in resultats.items():
        print(f"Vers {ville} : {dist} km")
    
    
    liste_echantillon1 = [1,2,3,4]

    print(get_permutations(liste_echantillon1))
    
    
    liste_echantillon2 = [5, 2, 9, 1]
    print(tri_fusion(liste_echantillon2))