Algorithmes Classiques

def euclide(a, b) :
    while a != b :
        if a >= b :
            a = a - b
        else :
            b = b - a
    return a

def premier(n) :
    p = True
    d = 2
    while d * d <= n :
        if n % d == 0 :
            p = False
        d = d + 1
    return p

def fibonacci(n) :
    if n == 0 :
        return 0
    f_prev, f = 0, 1
    for rang in range(1,n) :
        f_prev, f = f, f + f_prev
    return f

def syracuse(s0) :
    # Rang 0
    s = s0
    rang = 0
    # Calcul du rang suivant dans s, jusqu'à ce que s == 1
    while s != 1 :
        rang = rang + 1
        if s % 2 == 0 :
            s = s // 2
        else :
            s = 3 * s + 1
    return rang

def somme_liste(l) :
    somme = 0
    for x in l  :
        somme = somme + x
    return somme

def imax(l) :
    if len(l) == 0 :
        return -1
    i_max = 0
    maxi = l[0]
    for i in range(len(l)) :
        if l[i] > maxi :
            maxi = l[i]
            i_max = i
    return i_max

def moyenne(l) :
    somme = 0
    for x in l :
        somme = somme + x
    return somme / len(l)

def recherche_lineaire(l, x) :
    i_x = -1
    i = 0
    n = len(l)
    while i < n and i_x == -1 :
        if l[i] == x :
            i_x = i
        i = i + 1
    return i_x

def recherche_lineaire(l, x) :
    for i in range(len(l)) :
        if l[i] == x :
            return i
    return -1

def compter(l, x) :
    c = 0
    for e in l :
        if e == x :
            c = c + 1
    return c

def deuxieme_minimum(l) :
    if l[0] < l[1] :
        m = l[0]
        second_m = l[1]
    else :
        m = l[1]
        second_m = l[0]
    for x in l[2:] :
        if x < m :
            second_m = m
            m = x
        elif x < second_m :
            second_m = x
    return second_m

def rechercher(s,w) :
    for i in range(0,len(s)-len(w)+1) :
        j = 0
        while j < len(w) and w[j] == s[i+j] :
            j += 1
        if j == len(w) :
            return i
    return -1

def matrice(n,m) :
    M = []
    for i in range(n) :
        L = [ None ] * m
        M.append(L)
    return M

def matrice(n,m) :
    return [ [ None ] * m for i in range(n) ]

def copie(M) :
    M_copie = []
    for L in M : # Pour chaque ligne de M
        L_copie = []
        for x in L : # Pour chaque élément de la ligne
            L_copie.append(x)
        M_copie.append(L_copie)
    return M_copie

def copie(M) :
    return [ [ x for x in L ] for L in M ]

def rendu(L,m) :
    R = []
    reste = m
    i = len(L)-1 # i représente le plus gros billet éventuellement utilisable.
    while reste > 0 :
        if L[i] <= reste : # si on peux utiliser le plus gros billet, on l'utilise
            R.append(L[i])
            reste = reste - L[i]
        else : # sinon on considère le billet d'en dessous.
            i = i-1
    return R

def exponentiation_rapide(a,b) :
    r = 1
    u = a
    v = b
    while v > 0 :
        if v % 2 == 1 :
            r = r * u
        u = u * u
        v = v // 2
    return r

def recherche_dichotomique_zero(a,b,e,f) :
    debut = a
    fin = b
    while fin - debut > e :
        milieu = (debut + fin ) / 2
        if f(milieu) == 0 :
            return milieu
        elif f(milieu) * f(debut) > 0 :
            debut = milieu
        else :
            fin = milieu
    return debut

def recherche_dichotomique(L,x) :
    debut = 0
    fin = len(L)
    while fin - debut > 0 :
        milieu = (debut + fin) // 2
        if L[milieu] == x :
            return milieu
        elif L[milieu] < x :
            debut = milieu
        else :
            fin = milieu
    return -1

def maximum_rec(L, i) :
    if i == 0 :
        return -float('inf')
    b = maximum(L,i-1)
    if L[i-1] < b :
        return b
    return L[i-1]

def maximum(L) :
    return maximum_rec(L, len(L))

def somme_rec(L, i) :
    if i == 0 :
        return 0
    return L[i-1] + somme(L, i-1)

def somme(L) :
    return somme_rec(L,len(L))

def exp(a,b) :
    if b == 0 :
        return 1
    elif b % 2 == 0 :
        return exp(a * a , b // 2)
    else :
        return a * exp( a * a, b // 2)

def recherche_dichotomique_rec(L,x,d,f) :
    if d == f :
        return -1
    m = (d+f) // 2
    if L[m] == x :
        return m
    elif L[m] > x :
        return recherche_dichotomique(L,x,m,f)
    return recherche_dichotomique(L,x,m+1,f)

def recherche_dichotomique(L,x) :
    return recherche_dichotomique(L,x,0,len(L))

def fusion(l1 : list[int], l2 : list[int]) -> list[int] :
    """
    Entrées : deux listes d'entiers triés.
    Sortie: une liste triée contenant les éléments des deux listes en entrée.
    Complexité : O(len(l1)+len(l2))
    """

def tri_fusion_rec(l,d,f) :
    if f-d < 2 :
        return l[d:f]
    m = (d+f)//2
    l1 = tri_fusion(l,d,m)
    l2 = tri_fusion(l,m,f)
    return fusion(l1,l2)

def tri_fusion(l) :
    return tri_fusion_rec(l,0,len(l))

def degre(g) :
    deg = [ len(g[s]) for s in g ]
    for s in g :
        for v in g[s] :
            deg[v] += 1
    return deg

from collections import deque

# Utilisation d'une file : fifo pour avoir la bonne complexité.

def parcours_largeur(g, source) :
    n = len(g)
    marquage = [False] * n
    fifo = deque()
    fifo.append(source)
    marquage[source] = True
    while len(deque) > 0 :
        s = fifo.popleft()
        # Traiter s ...
        for v in g[s] :
            if not marquage[v] :
                fifo.append(v)
                marquage[v] = True
    return # Quelque chose peut-être

# Utilisation d'une pile : lifo pour avoir la bonne complexité.
def parcours_profondeur(g, source) :
    n = len(g)
    marquage = [False] * n
    lifo = []
    lifo.append(source)
    while len(deque) > 0 :
        s = lifo.pop()
        if not marquage[s] :
            marquage[s] = True
            # Traiter s ...
            for v in g[s] :
                if not marquage[v] :
                    lifo.append(v)
    return # Quelque chose peut-être

def parcours_profondeur(g, source, marquage) :
    marquage[source] = True
    # Traitement de source
    for v in g[source] :
        if marquage[v] != True :
            parcours_profondeur(g, v, marquage)
            # ou ; r = parcours_profondeur(g, v, marquage)
    return # Quelque chose peut-être

def parcours(g, source, marquage) :
    marquage[source] = True
    for v in g[source] :
        if marquage[v] != True :
            parcours_profondeur(g, v, marquage)
    return

def connexite(g) :
    if len(g) == 0 :
        return True
    source = g[0]
    marquage = [False]*len(g)
    parcours(g,source,marquage)
    for m in marquage :
        if not m :
            return False
    return True

def dijkstra(g,source) :
    n = len(g)
    # Structures
    distances = [float(inf)]*n
    parents = [None]*n
    file_prio = creer()
    # Initialisation
    distances[source] = 0
    ajoute(file_prio, source, 0)
    # Algorithme
    while not est_vide(file_prio) :
        # On récupère le sommet non visité à distance minimale
        s = enleve_min(file_prio)
        # On relache tous les voisins
        for voisin, poids in g[s] :
            distance_par_s = distances[s] + poids
            if distance_par_s < distances[voisins] :
                distances[voisins] = distance_par_s
                parents[voisin] = s
                ajoute(file_prio, voisin, distances[voisins])
    return distances, parents

def creer() : # $\O(1)$
    return {}

def est_vide(file_prio) : # $\O(1)$
    return len(file_prio) == 0

def ajoute(file_prio, x, prio) : # $\O(1)$
    file_prio[x] = prio

def enleve_min(file_prio) : # $\O(\symtt{len(file_prio)})$
    min_key, min_prio = None, float('inf')
    for x, prio in file_prio.items() :
        if prio < min_prio :
            min_key, min_prio = x, prio
    del file_prio[min_key]
    return min_key

def astar(g, heuristique, source, destination) :
    n = len(g)
    # Structures
    distances = [float(inf)]*n
    parents = [None]*n
    file_prio = creer()
    # Initialisation
    distances[source] = 0
    ajoute(file_prio, source, 0)
    # Algorithme
    while not est_vide(file_prio) :
        # On récupère le sommet non visité à distance minimale
        s = enleve_min(file_prio)
        # ***** Une différence est ici *****
        if s == destination :
            break
        # On relache tous les voisins
        for voisin, poids in g[s] :
            distance_par_s = distances[s] + poids
            if distance_par_s < distances[voisins] :
                distances[voisins] = distance_par_s
                parents[voisin] = s
                ajoute(file_prio, voisin,
                       # ***** Une autre différence est ici *****
                       distances[voisins]+h(g,source,destination,voisin))
    return distances, parents

def nb_occ(s) :
    d = {}
    for c in s :
        if c not in d :
            d[c] = 0
        d[c] += 1
    return d

def ordo_memo(L,i,delta,memo) :
    if i == 0 :
        memo[(i,delta)] = delta
        return
    delta_1 = delta + L[i-1]
    delta_2 = abs(delta - L[i-1])
    if (i-1, delta_1) not in memo :
        ordo_memo(L,i-1,delta_1,memo)
    if (i-1, delta_2) not in memo :
        ordo_memo(L,i-1,delta_2,memo)
    memo[(i,delta)] = min(memo[(i-1,delta_1)], memo[(i-1,delta_2)])
    return

def ordo(L) :
    memo = {}
    ordo_memo(L,len(L),0,memo)
    return memo[(len(L),0)]

def fw(g) :
    n = len(g) :
    m_new = [ [ x for x in line ] for line in g ]
    for k in range(1,n+1) :
        m_prev = m_new
        m_new = [ [ float("inf") for x in line ] for line in g ]
        for i in range(n) :
            for j in range(n) :
                m_new[i][j] = min(m_prev[i][j], m_prev[i][k] + m_prev[k][j])
    return m_new

def lev_memo(s1,s2,i,j,memo) :
    if i == 0 :
        memo[(i,j)] = j
        return
    elif j == 0 :
        memo[(i,j)] = i
        return
    elif s1[i-1] == s2[j-1] :
        if (i-1,j) not in memo :
            lev_memo(s1,s2,i-1,j,memo)
        if (i,j-1) not in memo :
            lev_memo(s1,s2,i,j-1,memo)
        if (i-1,j-1) not in memo :
            lev_memo(s1,s2,i-1,j-1,memo)
        memo[(i,j)] = 1 + min(memo[(i-1,j)], memo[(i,j-1)], memo[(i-1,j-1)])
        return
    else :
        if (i-1,j-1) not in memo :
            lev_memo(s1,s2,i-1,j-1,memo)
        memo[(i,j)] = 1 + memo[(i-1,j-1)]
        return

def lev(s1,s2) :
    memo = {}
    lev_memo(s1,s2,len(s1),len(s2),memo)
    return memo[(len(s1), len(s2))]

def hk_memo(g,E,i,j,memo) :
    vide = True
    for s_in_E in E :
        if s_in_E :
            vide = False
    if vide :
        memo[(E,i,j)] = g[i][j]
        return
    m = float("inf")
    for s in range(len(E)) :
        if E[s] :
            E_sans_s = E[:i] + (False,) + E[i+1:]
            if (E_sans_s,s,j) not in memo :
                hk_memo(g,E_sans_s,s,j,memo)
            val = g[i][s] + memo[(E_sans_s,s,j)]
            if val < m :
                m = val
    memo[(E,i,j)] = m
    return

def hk(g,i,j) :
    memo = {}
    S = (True,) * len(g)
    S = S[:i] + (False,) + S[i+1:]
    S = S[:j] + (False,) + S[j+1:]
    # ou S = tuple( [ x != i and x != j for x in range(len(g)) ] )
    hk_memo(g,S_sans_ij,i,j,memo)
    return memo[(len(s1), len(s2))]

def kvoisins(e,d,k,x) :
    pp = kplusproches(e,d,k,x)
    return majo(pp,e,d,k)

def kplusproches(e,d,k,x) :
    L = []
    for data in e.keys() :
        if len(L) < k :
            L.append(data)
        elif d(data,x) < d(data,L[k-1]) :
            L.pop()
            L.append(data)
        j = k-1
        while j > 0 and L[j] < L[j-1] :
            L[j], L[j-1] = L[j-1], L[j]
            j += 1
    return L

def majo(pp,e,d,k) :
    etiquettes = {}
    for data in pp :
        if e[data] not in etiquettes :
            e[data] = 1
        else :
            e[data] += 1
    e_max = None
    m = -1
    for et in etiquettes :
        if etiquettes[et] > m :
            e_max = et
            m = etiquettes[et]
    return e_max

from random import sample
def kmoyenne(e,d,k,moyenne) :
    centroides = sample(e,k)
    old_centroides = None
    while old_centroides != centroides :
        categories = [ [] for i in range(k) ]
        for data in e :
            centroide_plus_proche = 0
            min_distance = d(data, centroides[0])
            for i in range(1,k) :
                distance = d(centroide[i], data)
                if distance < min_distance :
                    centroide_plus_proche = i
                    min_distance = distance
            categories[centroide_plus_proche].append(data)
            old_centroides = centroides
            centroides = [ moyenne(cat[i]) for i in range(k) ]
    return categories

def distance(x,y) :
    d = 0
    for i in range(len(x)) :
        d += (x[i]-y[i])**2
    return d ** 0.5

def moyenne(e) :
    m = [0.0] * len(e[0])
    for x in e :
        for i in range(len(x)) :
            m[i] += x[i]
    return [ x / len(m) for x in m ]

def transpose(g) :
    tg = [ [] for s in g ]
    for s in g :
        for v in g[s] :
            tg[v].append(s)
    return tg

def attracteurs(g,v,joueur) :
    tg = transpose(g)
    marquage = [ len(tg[s]) for s in tg ]
    a = [ False for i in range(len(tg)) ]
    for s in v :
        parcours(tg,s,a,marquage, joueur)
    return a

def parcours_dfs(g,s,a,marquage, joueur) :
    if a[s] :
        return
    a[s] = True
    for v in g[s] :
        if not a[v] :
            marquage[v] -= 1
            j,_ = v
            if j = joueur or marquave[v] == 0:
                parcours_dfs(v)

def minmax(a, r, h, j) :
    if len(a[r]) == 0 :
        return h(r), None
    L = []
    for v in a[r] :
        L.append((minmax(a,v,h,1-j), v))
    if i == 0 :
        return max(L)
    return min(L)