Échauffement

def recherche_lineaire(l, m) :
    """
    Entrées : l une liste de chaînes de caractère, m une chaîne de caractère
    Sortie : indice de m dans l si m est dans l, -1 sinon
    """
    for i in range(n-1,-1,-1) :
        if m == l[i] :
            return i
    return -1

def somme_max(l) :
    """
    Entrées : l une liste d'entiers
    Sortie : max(e1 + e2, (e1,e2) dans l), 0 si l est vide
    """
    if not l :
        return 0
    m = l[0] * 2
    for e1 in l :
        for e2 in l :
            if e1 + e2 > m :
                m = e1 + e2
    return m

def somme_max_lineaire(l) :
    """
    Entrées : l une liste d'entiers
    Sortie : max(e1 + e2, (e1,e2) dans l), 0 si l est vide.
    On calcule le maximum et le second maximum de la liste, puis on les somme.
    """
    if not l :
        return 0
    if len(l) == 1 :
        return l[0] * 2
    # Initialisation de im0 et im1 à l'indice du maximum et second maximum
    # des 2 premiers élèments, respsectivement.
    im0 = 0
    im1 = 1
    if l[0] < l[1] :
        im0 = 1
        im1 = 0
    for i in range(2,len(l)) :
        if l[i] < l[im0] :
            im1 = im0
            im0 = i
        elif l[i] < l[im1] :
            im1 = i
    return l[im0] + l[im1]

def aplatissement(l) :
    """
    Entrées : Une liste de listes d'entiers
    Sortie : La concaténation de l'ensemble des listes de l
    """
    s = []
    for x in l :
        s.extend(x)
    return s

def aplatissement_dict(l) :
    """
    Entrées : Une liste de distionnaires str -> listes d'entiers
    Sortie : D obtenu en aplatissant la liste...
    """
    d = {}
    for e in l :
        for k in e :
            if k not in d :
                d[k] = []
            d[k].extend(e[k])
    return d

def recherche_dichotomique(l,x) :
    """
    Entrées :
    - l : liste de chaînes de caractères triée par ordre alphabétique,
    - x : une chaîne de caractère
    Sortie : l'indice de x dans l si x est dans l, -1 sinon
    """
    d, f = 0, len(l)
    while d < f :
        m = ( d + f ) // 2
        if l[m] == x :
            return m
        elif l[m] < x :
            d = m+1
        else : # l[m] > x
            f = m
    return -1

def recherche_pic(l) :
    """
    Entrées : l une montagne telle que décrite dans l'énoncé.
    Sortie : le pic de la montagne tel que défini dans l'énoncé
    """
    if len(l) == 1 : # l est non vide, on élimine le cas d'un singleton
        return 0
    # len(l) > 1
    d, f = 0, len(l)
    while d < f :
        m = ( d + f ) // 2
        if ( m == 0 or
             ( m == len(l) - 1 and l[m-1] < l[m]) or
             ( l[m-1] < l[m] and l[m] > l[m + 1] ) ) : # cas du pic
            return (m,l[m])
        if l[m-1] < l[m]  : # pente croissante
            d = m + 1
        else : # pente décroissante
            f = m

tests = ([1,2,3,2,1], [1,2,3,4,5,6,7,6,4,3], [1,2,3], [3,2,1], [1], [1,2], [2,1], [0,1,2,3,4,1])
for t in tests :
    print(t," : ", recherche_pic(t))

def recherche_debut_pic_plateau(l) :
    """
    Entrées : l une montagne avec plateau telle que décrite dans l'énoncé.
    Sortie : le début du plateau de la montagne tel que défini dans l'énoncé
    """
    if len(l) == 1 : # l est non vide, on élimine le cas d'un singleton
        return 0
    # len(l) > 1
    d, f = 0, len(l)
    while d < f :
        m = ( d + f ) // 2
        if ( m == 0 or
             ( m == len(l) - 1 and l[m-1] < l[m]) or
             ( l[m-1] < l[m] and l[m] >= l[m + 1] ) ) : # cas du début du plateau
            return m
        if l[m-1] < l[m]  : # pente croissante strictement
            d = m + 1
        else : # pente décroissante ou plateau
            f = m

def recherche_pic_plateau(l) :
    """
    Entrées : l une montagne avec plateau telle que décrite dans l'énoncé.
    Sortie : le pic du plateau de la montagne tel que défini dans l'énoncé
    """
    p_debut = recherche_debut_pic_plateau(l)
    p_fin = len(l) - recherche_debut_pic_plateau(l[::-1]) - 1
    pic = ( p_debut + p_fin ) // 2
    return pic, t[pic]

tests_montagne = ([1,2,3,2,1], [1,2,3,4,5,6,7,6,4,3], [1,2,3], [3,2,1], [1], [1,2], [2,1], [0,1,2,3,4,1])
tests_plateau = ([1,2,3,3,3,2,1], [1,2,3,4,5,6,6,6,4,3], [1,2,3,3,3], [3,3,2,1], [1,1,1], [2,2])
tests = tests_montagne + tests_plateau
for t in tests :
    print(t," : ", recherche_pic_plateau(t))

def ordonnancement(l) :
    """
    Entrées : l une liste d'entiers
    Sortie : l1 et l2 deux listes dans lesquelles sont répartis les entiers de l
    """
    l1, l2 = [], []
    sum1, sum2 = 0, 0
    for x in l :
        if x > 0 :
            if sum1 > sum2 :
                l2.append(x)
                sum2 += x
            else :
                l1.append(x)
                sum1 += x
        else :
            if sum1 > sum2 :
                l1.append(x)
                sum1 += x
            else :
                l2.append(x)
                sum2 += x
    return l1, l2

def ordonnancement(l) :
    """
    Entrées : l une liste d'entiers
    Sortie : l1 et l2 deux listes dans lesquelles sont répartis les entiers de l
    """
    l1, l2 = [], [] # l1 sera la plus grande somme à chaque fois
    sum1, sum2 = 0, 0
    for x in l :
        if x < 0 :
            l1, l2, sum1, sum2 = l2, l1, sum2, sum1
        l2.append(x)
        sum2 += x
        if sum2 > sum1 :
            l1, l2, sum1, sum2 = l2, l1, sum2, sum1
    return l1, l2

ordonnancement([100,80,40,40,50,50])

def repartition(n) :
    """
    Entrées : un entier n positif
    Sortie : la listes des listes de booléens possible de taille n
    """
    if n == 0 :
        return [[]]
    rep = repartition(n-1)
    return [ [True] + l for l in rep ] + [ [False] + l for l in rep ]

def ordonnancement_optimal(l) :
    """
    Entrées : l une liste d'entiers
    Sortie : l1 et l2 deux listes dans lesquelles sont répartis les entiers de l
    """
    if not l :
        return [],[]
    diff_max = sum(l)
    rep_max = [True] * len(l)
    rep = [ [True] + l for l in repartition(len(l) - 1) ]
    for r in rep :
        sum1, sum2 = 0, 0
        for i,b in enumerate(r) :
            if b :
                sum1 += l[i]
            else :
                sum2 += l[i]
        if abs(sum1 - sum2) < diff_max :
            rep_max = r
            diff_max = abs(sum1-sum2)
    l1, l2 = [], []
    for i,b in enumerate(rep_max) :
        if b :
            l1.append(l[i])
        else :
            l2.append(l[i])
    return l1, l2

ordonnancement_optimal([100,80,40,40,50,50])

def tri_lineaire(l, m) :
    """
    Entrées : l une lisste d'entiers positifs et m une borne supérieure de l
    Sortie : une copie de l triée
    """
    cpt = [0]*(m+1)
    l_triee = []
    for x in l :
        cpt[x] += 1
    for i,n in enumerate(cpt) :
        l_triee.extend([i]*n)
    return l_triee

import random
l = [ random.randint(0,99) for i in range(50) ]
tri_lineaire(l,99)

def fusion(l1,l2) :
    """
    Entrées : l1 et l2 deux listes triées
    Sortie : une liste triée dont les éléments sont ceux de l1 et l2
    """
    l = []
    i1, i2 = 0, 0
    while i1 < len(l1) and i2 < len(l2) :
        if l1[i1] < l2[i2] :
            l.append(l1[i1])
            i1 += 1
        else :
            l.append(l2[i2])
            i2 += 1
    if i1 == len(l1) :
        l.extend(l2[i2:])
    else :
        l.extend(l1[i1:])
    return l

def tri_fusion(l) :
    """
    Entrées : l une liste d'entiers
    Sortie : une copie de l triée
    """
    if len(l) < 2 :
        return l
    return fusion(tri_fusion(l[:len(l)//2]), tri_fusion(l[len(l)//2:]))

import random
l = [ random.randint(0,99) for i in range(50) ]
tri_fusion(l)

import random

def tri_rapide(l) :
    if len(l) < 2 :
        return l
    pivot = random.randint(0,len(l)-1)
    l_inf, l_sup = [], []
    nb_pivot = 0
    for x in l :
        if x < l[pivot] :
            l_inf.append(x)
        elif x > l[pivot] :
            l_sup.append(x)
        else :
            nb_pivot += 1
    return tri_rapide(l_inf) + [l[pivot]]*nb_pivot + tri_rapide(l_sup)

import random
l = [ random.randint(0,99) for i in range(50) ]
tri_rapide(l)

def ackermann(m,n) :
    """
    Entrées : m et n deux entiers positifs
    Sortie : A(m,n)
    """
    if m == 0 :
        return n + 1
    elif n == 0 :
        return ackermann(m-1,1)
    else :
        return ackermann(m-1,ackermann(m,n-1))

def puissance(a,b) :
    """
    Entrées : a un flottant et b un entiers
    Sortie : a^b
    """
    if b == 0 :
        return 1
    if b % 2 == 0 :
        return puissance(a*a,b // 2)
    else :
        return a * puissance(a*a, b // 2)

def binaire(n, nb_bits) :
    """
    Entrées : n un entier relatif, nb_bits le nombre de bits de l'écriture
    Sortie : l'écriture binaire de n sous forme de chaîne de caractères
    """
    if nb_bits == 0:
        return ""
    if n < 0 :
        n = 2 ** nb_bits + n # complément à 1 + 1
    return binaire(n // 2, nb_bits -1) + str(n % 2)

def fibonnacci(n) :
    """
    Entrées : n un entier positif
    Sortie : F_n
    """
    if n < 2 :
        return (n, n-1)
    f, f_prev = fibonnacci(n-1)
    return (f + f_prev, f)

def u(n) :
    if n == 0 :
        return 1.0
    u_prev, v_prev = u(n-1), v(n-1)
    return ( 2 * u_prev * v_prev ) / (u_prev + v_prev)

def v(n) :
    if n == 0 :
        return 2.0
    u_prev, v_prev = u(n-1), v(n-1)
    return ( u_prev + v_prev ) / 2

def instructions(n, A, B, C) :
    """
    Entrées : n le nombre de cartons arrivés en A
    Sortie : la séquence d'instructions pour déplacer
        les cartons de A vers C en transitant par B
    """
    if n == 0 :
        return ""
    ins = instructions(n-1, A, C, B)
    ins += A + " -> " + C + "\n"
    ins += instructions(n-1, B, A, C)
    return ins

print(instructions(1,"A","B","C"))
print("---")
print(instructions(3,"A","B","C"))
print("---")
print(instructions(7,"A","B","C"))

from queue import LifoQueue as Pile

def etiquettage_une_composante(image_nb, composantes, depart, num_composante) :
    """
    Entrées :
    - image_nb : une matrice de booléens représentant une image noir et blanc
    - composantes : une matrice donnant la composante de chaque pixel,
        -1 si non attribuée.
    - depart : le premier pixel à considérer, noir et non étiquetté
    - num_composante : le numéro de la composante à étiquetter
    Sortie : Aucune.
    Effet de bord : composantes et mise à jour avec l'étiquettage
        de la composante connexe du pixel depart
    """
    m, n = len(image_nb[0]), len(image_nb)
    a_visiter = Pile()
    a_visiter.put(depart)
    # Parcours en profondeur et étiquettage
    while not a_visiter.empty() :
        i,j = a_visiter.get()
        composantes[i][j] = num_composante
        # Ajout de chaque voisin à visiter
        for k in (i-1,i,i+1) :
            for l in (j-1,j,j+1) :
                if ( 0 <= k < n and 0 <= l < m # Voisin valide
                        and composantes[k][l] == -1 # Voisin non étiquetté
                        and not image_nb[k][l] ) : # Voisin noir
                    a_visiter.put((k,l))
    return None

import numpy as np

def etiquettage_composante(image_nb) :
    """
    Entrées : une matrice de booléens représentant une image noir et blanc
    Sortie : une matrice d'entiers représentant la composante connexe de
        chaque pixel noir. 0 pour les pixels blancs
    """
    m, n = len(image_nb[0]), len(image_nb)
    composantes = np.array([[-1]*m]*n)
    num_composante = 1
    for i,row in enumerate(image_nb) :
        for j,pixel in enumerate(row) :
            if composantes[i][j] == -1 :
                if pixel : # Pixel Blanc
                    composantes[i][j] = 0
                else : # Pixel Noir
                    etiquettage_une_composante(image_nb, composantes,
                                               (i,j), num_composante)
                    num_composante += 1
    return composantes

def composantes_en_couleur(composantes) :
    """
    Entrées : Un étiquettage des composantes d'une image noir et blanc
    Sortie : Une image en couleur, avec chaque composante d'une couleur
        identique
    """

    couleurs = [ (255,255,255), (255,0,0), (0,255,0), (0,0,255),
                 (255,255,0), (0,255,255), (255,0,255), (0,0,0),
                 (255,120,120), (120,255,120), (120,120,255), (120,120,120) ]
    m, n = len(composantes[0]), len(composantes)
    img = np.array([[(0,0,0)]*m]*n, dtype="uint8")
    for i,row in enumerate(composantes) :
        for j, c in enumerate(row) :
            img[i][j] = couleurs[c]
    return img

from PIL import Image
img = Image.open("img/noir_et_blanc.jpg")
img = img.convert("1")
display(img)

image_nb = np.array(img)
composantes = etiquettage_composante(image_nb)
img_comp = composantes_en_couleur(composantes)
display(Image.fromarray(img_comp))

def appliquer_filtre(filtre, vec) :
    """
    Entrées :
    - filtre : une matrice 3x3
    - vec : un vecteur de dimension 3
    Sortie : filtre * vec
    """
    r = [0,0,0]
    for i in range(3) :
        for j in range(3) :
            r[i] += filtre[i][j] * vec[j]
    return r

def filtrage(image, filtre) :
    """
    Entrées :
    - image : une matrice de triplés représentant une image
    - filtre : une matrice 3x3
    Sortie : l'image sur laquelle a été appliqué le filtre
    """
    m, n = len(image[0]), len(image)
    image_filtree = np.array([[[0,0,0]]*m]*n, dtype="uint8")
    for i,row in enumerate(image) :
        for j, pixel in enumerate(row) :
            image_filtree[i][j] = appliquer_filtre(filtre, pixel)
    return image_filtree

from PIL import Image
img = Image.open("img/rgb.jpg")
img_rgb = np.array(img)
display(img)

R = np.array([ [1, 0, 0], [ 0, 0, 0], [0, 0, 0] ], dtype="uint8")
img_R = filtrage(img_rgb, R)
display(Image.fromarray(img_R))

G = np.array([ [0, 0, 0], [ 0, 1, 0], [0, 0, 0] ], dtype="uint8")
img_G = filtrage(img_rgb, G)
display(Image.fromarray(img_G))

B = np.array([ [0, 0, 0], [ 0, 0, 0], [0, 0, 1] ], dtype="uint8")
img_B = filtrage(img_rgb, B)
display(Image.fromarray(img_B))

NG = np.array([ [1/3, 1/3 , 1/3], [ 1/3, 1/3, 1/3], [1/3, 1/3, 1/3] ])
img_NG = filtrage(img_rgb, NG)
display(Image.fromarray(img_NG))

D = np.array([ [0.5, 0 , 0], [ 0, 0.5, 0], [0, 0, 0.5] ])
img_D = filtrage(img_rgb, D)
display(Image.fromarray(img_D))

GB = np.array([ [0, 0 , 0], [ 0, 1, 0], [0, 0, 1] ])
img_GB = filtrage(img_rgb, GB)
display(Image.fromarray(img_GB))

import numpy as np

def noyau_gaussien(r, sigma) :
    """
    Entrées : r un entier et sigma un réel
    Sortie : le noyau gaussien de rayon r et ecart type sigma
    """
    h = np.array([[0.0]*(2*r+1)]*(2*r+1))
    somme = 0.0
    for i in range(2*r+1) :
        for j in range(2*r+1) :
            h[i][j] = np.exp( - ( (i-r) ** 2 + (j-r) ** 2 )
                              / ( 2 * sigma ** 2 ) )
            somme += h[i][j]
    for i in range(2*r+1) :
        for j in range(2*r+1) :
            h[i][j] = h[i][j] / somme
    return h

def conv(image,noyau,pixel) :
    """
    Entrées :
    - image : une matrice de flottants entre 0 et 1 représentant une image
        en niveau de gris.
    - noyau : un noyau gaussien
    - pixel : le pixel surlequel sera appliqué le noyau
    Sortie : la nouvelle valeur du pixel après application du noyau
    """
    n = len(noyau)
    r = ( n - 1 ) // 2
    moy = 0
    i,j = pixel
    for k in range(n) :
        for l in range(n) :
            if ( 0 <= i + k - r < len(image) and
                 0 <= j + l - r < len(image[0]) ) :
                moy += noyau[k][l] * image[i + k - r][j + l - r]
    return moy

def flou_gaussien(image, r, sigma) :
    """
    Entrées :
    - image : une matrice de flottants entre 0 et 1 représentant une image
        en niveau de gris.
    - r un entier et sigma un réel
    Sortie : Une copie de l'image sur laquelle a été appliqué un flou gaussien
        de rayon r et écrat-type sigma
    """
    noyau = noyau_gaussien(r,sigma)
    m, n = len(image[0]), len(image)
    image_flou = np.array([[0.0]*m]*n)
    for i,row in enumerate(image) :
        for j in range(len(row)) :
            image_flou[i][j] = conv(image,noyau,(i,j))
    return image_flou

from PIL import Image
img = Image.open("img/niveau_gris.jpg")
img = img.convert("L")
display(img)

img_ng = np.array(img)
m, n = len(img_ng[0]), len(img_ng)
img_ng_f = np.array([ [0.0]*m ]*n)
for i in range(n) :
    for j in range(m) :
        img_ng_f[i][j] = img_ng[i][j] / 255
img_flou_f = flou_gaussien(img_ng_f, 4, 10)
img_flou = np.array([ [0]*m ]*n, dtype="uint8")
for i in range(n) :
    for j in range(m) :
        img_flou[i][j] = int(img_flou_f[i][j] * 255)
display(Image.fromarray(img_flou))

from queue import LifoQueue as Pile

def connexite(graphe) :
    """
    Entrées : la liste d'adjacence d'un graphe
    Sortie : un booléen vrai ssi le graphe est connexe
    """
    n = len(graphe)
    if n == 0 :
        return True
    a_visiter = Pile()
    a_visiter.put(0)
    nb_connexe_0 = 0
    visite = [False] * n
    while not a_visiter.empty() :
        sommet = a_visiter.get()
        nb_connexe_0 += 1
        visite[sommet] = True
        for voisin in graphe[sommet] :
            if not visite[voisin] :
                a_visiter.put(voisin)
    return nb_connexe_0 == n

from queue import LifoQueue as Pile

def cycles(graphe) :
    """
    Entrées : la matrice d'adjacence d'un graphe
    Sortie : un booléen vrai ssi le graphe possède un cycle
    """
    n = len(graphe)
    visite = [False] * n
    a_visiter = Pile()
    for depart in range(n) :
        if not visite[depart] :
            a_visiter.put(depart)
            while not a_visiter.empty() :
                sommet = a_visiter.get()
                visite[sommet] = True
                for autre_sommet in range(n) :
                    if sommet != autre_sommet and graphe[sommet][autre_sommet] :
                        if visite[autre_sommet] :
                            return True
                        else :
                            a_visiter.put(autre_sommet)
    return False

from queue import Queue as File

def est_2_coloriable(graphe) :
    """
    Entrées : la liste d'adjacence d'un graphe
    Sortie : un booléen vrai ssi le graphe est 2-coloriable
    """
    n = len(graphe)
    couleur = [-1] * n # -1 non visité, 0 et 1 deux couleurs
    a_visiter = File()
    for depart in range(n) :
        if visite[depart] == -1 :
            a_visiter.put(depart)
            couleur[depart] = 0
            while not a_visiter.empty() :
                sommet = a_visiter.get()
                for voisin in graphe[sommet] :
                    if couleur[voisin] == couleur[sommet] :
                        return False
                    elif couleur[voisin] == -1 :
                        a_visiter.put(voisin)
                        couleur[voisin] = 1 - couleur[sommet]
    return True

def liste_coloration(n) :
    """
    Entrées : n un entier
    Sortie : la liste des colorations possible avec 3 couleurs pour n sommets
    """
    if n == 0 :
        return [[]]
    colo_prec = liste_coloration(n-1)
    return [ [0] + l for l in colo_prec ] + [ [1] + l for l in colo_prec ] + [ [2] + l for l in colo_prec ]

def est_3_coloration_valide(graphe, col) :
    """
    Entrées :
    - graphe : la liste d'adjacence d'un graphe
    - col : une coloration des sommets
    Sortie : vrai ssi la coloration vérifie : 2 voisins n'ont pas la même
        couleur
    """
    n = len(graphe)
    for sommet in range(n) :
        for voisin in graphe[sommet] :
            if col[sommet] == col[voisin] :
                return False
    return True

def est_3_coloriable(graphe) :
    """
    Entrées : la liste d'adjacence d'un graphe
    Sortie : un booléen vrai ssi le graphe est 3-coloriable
    """
    n = len(graphe)
    liste_col = liste_coloration(n)
    for col in liste_col :
        if est_3_coloration_valide(graphe,col) :
            return True
    return False