## EXERCICE 1 ## Classique, à savoir faire

def maximum(L) :
    M = L[0]
    for elt in L :
        if elt > M :
            M = elt
    return M

def compte_occurences(L) :
    maxi = maximum(L)
    M = [0 for _ in range(maxi+1)]
    for elt in L :
        M[elt] += 1
    return M

## EXERCICE 2 ## Première question à savoir faire. La deuxième est hors-programme

def noccur(m,x) :
    compteur = 0
    for lettre in m :
        if lettre == x :  # ou : compteur += (lettre == x)
            compteur += 1
    return compteur

def code(m) :
    '''minuscules latines de codes 97 ('a') -> 122 ('z')'''
    mot_code = ''
    for lettre in m :
        p = noccur(m,lettre)
        pos = (ord(lettre)-97+p)%26+97  # fonction 'ord' hors-programme
        lettre2 = chr(pos)              # fonction 'chr' hors-programme
        mot_code += lettre2
    return mot_code


## EXERCICE 3 ## A savoir faire, à l'exception des tests sur les types

def esperance(L) :
    n = len(L)
    S = 0
    for k in range(n) :
        x,p = L[k]
        S += p*x
    return S

def verif(L) :
    if type(L) != list :
        return False
    for ssliste in L :
        if type(ssliste) != list or len(ssliste) != 2 :
            return False
    dict = {}
    S = 0
    for ssliste in L :
        x,p = ssliste
        if type(x) not in [int,float] :
            return False
        if type(p) not in [int,float] :
            return False
        if p < 0 :
            return False
        dict[x] = 1
        S += p
    if len(dict) != len(L) : # des valeurs xi sont identiques
        return False
    if S != 1 :     # danger : test d'égalité sur des flottants
        return False
    return True

## EXERCICE 4 ## A savoir faire

def parenthesage(m) :
    ouvertes = 0
    fermees = 0
    for lettre in m :
        if lettre == '(' :      # voir remarque exercice 2
            ouvertes += 1
        if lettre == ')' :
            fermees += 1
    return ouvertes == fermees

def bon_ordre(m) :
    ouvertes = 0
    fermees = 0
    for lettre in m :
        ouvertes += (lettre == '(')
        fermees += (lettre == ')')
        if fermees > ouvertes :
            return False
    return ouvertes == fermees


## EXERCICE 5 ## Classique, à savoir faire

def eval(P,z) :
    S = 0
    for k in range(len(P)) :
        S += P[k]*z**k
    return S

def Horner(P,z) :
    d = len(P)-1
    S = 0
    while d > 0 :
        S = (S + P[d])*z
        d -= 1
    return S+P[0]


## EXERCICE 6 ##

def serie1(L) :
    n = len(L)
    s = [1,0]
    premier = L[0]
    en_cours = premier
    ind = 0
    for k in range(1,n) :
        if L[k] == en_cours :
            s[ind] += 1
        elif ind == 1 :
            return s
        else :
            deuxieme = L[k]
            en_cours = deuxieme
            ind = 1
            s[ind] += 1
    return s

## EXERCICE 7 ## à savoir faire

import random as rd

def evolution(N,p) :
    morts = 0
    for _ in range(N) :
        if rd.random() < p :
            morts += 1
    return N-morts

def lifetime(N,p) :
    heure = 0
    while N>0 :
        heure += 1
        N = evolution(N,p)
    return heure

def evolution2(N,p,n) :
    for _ in range(n) :
        morts = 0
        dupliq = 0
        for _ in range(N) :
            if rd.random() < p :
                morts += 1
            else :
                dupliq += 1
        N = N - morts + dupliq
    return N


## EXERCICE 8 ## à savoir faire

def ind_max(L) :
    M = L[0]
    Lind = [0]
    for k in range(len(L)) :
        if L[k] == M :
            Lind.append(k)
        elif L[k] > M :
            M = L[k]
            Lind = [k]
    return Lind

def prem_dern(L,a) :
    Lind = []
    for k in range(len(L)) :
        if L[k] == a :
            Lind.append(k)
    if len(Lind) == 0 :
        return "La valeur n'est pas présente."
    if len(Lind) == 1 :
        return "Une seule occurence en indice : ", Lind[0]
    return Lind[0],Lind[-1]

## EXERCICE 9 ## à savoir faire

def difference(L1,L2) :
    compte = 0
    for i in range(len(L1)) :
        compte += (L1[i] != L2[i])
    return compte

def sschaine(txt,seq) :
    if len(seq) > len(txt) :
        return False
    for i in range(len(txt)-len(seq)+1) :
        if difference(seq,txt[i:i+len(seq)]) == 0 :
            return True
    return False

## EXERCICE 10 ## ... un peu dur

def periode(L,T) :
    if T >= len(L) :
        return True
    for i in range(T) :
        k = 1
        while i+k*T < len(L) :
            if L[i+k*T] != L[i] :
                return False
            k += 1
    return True

def plus_petite_periode(L) :
    T = 1
    while not periode(L,T) :
        T += 1
    return T

## EXERCICE 11 ##

def diff01(L) :
    M = []
    for elt in L :
        if elt != 0 and elt != 1 :
            M.append(elt)
    return M

def diff(L,k) :
    '''avec effet de bord'''
    for i in range(len(L)) :
        if i%k == 0 :
            L[i] = 0
    return L

## EXERCICE 12 ##

def tx_w(L) :
    compte = 0
    for elt in L :
        compte += (elt == -1)
    return compte / len(L)

def est_elu(L,j) :
    suffrages_exprimes = sum(L) - L[0]
    return L[j] / suffrages_exprimes > 0.5

## EXERCICE 13 ##

def compte(L,x) :
    return noccur(L,x)
    # voir exercice 2 : la syntaxe est commune aux listes et chaînes

def binomial(m,N,p) :
    L = []
    for _ in range(m) :
        s = 0
        for _ in range(N) :
            s += (rd.random()<p)
        L.append(s)
    return L

def simuBinomial(m,N,p) :
    Simul = binomial(m,N,p)
    M = [0 for _ in range(N+1)]
    for elt in Simul :
        M[elt] += 1
    return M


## EXERCICE 14 ##

def hypH(L) :
    if type(L) != list :
        return False
    n = len(L)
    for elt in L :
        if type(elt) != int :
            return False
        if elt < 0 or elt >= n :
            return False
    return True


def hypHprime(L) :
    n = len(L)
    for i in range(n) :
        if i not in L :
            return False
    return True     # solution avec dictionnaire : voir exercice 3

## EXERCICE 15 ##

def marche(i,N) :
    position = i
    for _ in range(N) :
        if rd.random() < .5 :
            position += 1
        else :
            position += -1
    return position

def jeu_plateau(n,a,b,i) :
    position = i
    while position not in [0,n] :
        if rd.random() < .5 :
            position += 1
        else :
            position += -1
    if position == 0 :
        return a
    return b

## EXERCICE 16 ## très similaire à l'exercice 1

def verif16(L,a,b) :
    for elt in L :
        if elt < a or elt > b :
            return False
    return True

def denombre(L,a,b) :
    compte = [0 for _ in range(a,b+1)]
    for elt in L :
        compte[elt-a] += 1
    return compte

## EXERCICE 17 ##

def temps(coords) :
    T = []
    for elt in coords :
        T.append(elt[3])
    return T

def plus_haut(coords) :
    i_top = 0
    top = coords[0][2]
    for i in range(len(coords)) :
        if coords[i][2] > top :
            top = coords[i][2]
            i_top = i
    return [coords[i_top][0], coords[i_top][1]]

## EXERCICE 18 ##

def simulDes(N) :
    L = []
    for _ in range(N) :
        if rd.random() < 0.5 :
            L.append(1)
        else :
            L.append(0)
    return L

# alternative : return [int(rd.random()<0.5) for _ in range(N)]

def PPF() :
    L = [int(rd.random()<0.5) for _ in range(3)]
    while [L[-1],L[-2],L[-3]] != [1,1,0] :
        L.append(int(rd.random()<0.5))
    return len(L)

def temps_PPF(N) :
    s = 0
    for _ in range(N) :
        s += PPF()
    return s/N

## EXERCICE 19 ##

def s19(n) :
    somme = 0
    for k in range(1,n) :
        if n%k == 0 :
            somme += k
    return somme

def prop_parfait(N) :
    compte = 0
    for n in range(1,N+1) :
        if s(n) == n :
            compte += 1
    return compte/N

def kieme_parfait(k) :
    '''temps de calcul important des que k > 4'''
    L = []
    n = 1
    while len(L) < k :
        if s(n) == n :
            L.append(n)
        n += 1
    return L[-1]

## EXERCICE 20 ##

def sans_rep(L) :
    M = []
    for elt in L :
        if elt not in M :
            M.append(elt)
    return M

# version avec dictionnaire

def sans_rep_dico(L) :
    d = {}
    for elt in L :
        d[elt] = 1
    M = [cle for cle in d.keys()]
    return M

def list_oc(L) :
    d = {}
    for elt in L :
        if elt in d :
            d[elt] += 1
        else :
            d[elt] = 1
    M, O = [], []
    for cle,valeur in d.items() :
        M.append(cle)
        O.append(valeur)
    return M,O

## EXERCICE 21 ##

import numpy as np

def indice21(s,Lc) :
    for k in range(len(Lc)-len(s)+1):
        mot = ''
        for i in range(k,k+len(s)) :
            mot += Lc[i]
        if mot == s :
            return k
    return -1

def elt(M,i,j,v) :
    (x,y) = v
    L = []
    n,p = np.shape(M)
    while 0<= i < n and 0<= j < p :
        L.append(M[i,j])
        i += x
        j += y
    return L

## EXERCICE 22 : identique exo 7 ##

## EXERCICE 23 ##

def f23(L,n,p) :
    L2 = []
    for elt in L :
        a,b = elt
        if 0<= a < n and 0<= b < p :
            L2.append(elt)
    return L2

def voisins(M,i,j) :
    L = []
    for di in [-1,0,1] :
        for dj in [-1,0,1] :
            L.append((i+di,j+dj))
    n,p = np.shape(M)
    L2 = f23(L,n,p)
    return [M[elt] for elt in L2]

## EXERCICE 24 ##

def somme24(L,i,j) :
    s = 0
    for k in range(i,j) :
        s += L[k]
    return s

def L_sous(L,k) :
    i0=0
    M = somme24(L,0,k)
    for i in range(1,len(L)-k+1) :
        s = somme24(L,i,i+k)
        if s > M :
            M = s
            i0 = i
    return L[i0:i0+k]

## EXERCICE 25 ##

def prochain(A,dir) :
    x,y = A
    dx,dy = dir
    return x+dx,y+dy

def chemin(mot) :
    A = (0,0)
    L = [A]
    for dir in mot :
        A = prochain(A,dir)
        L.append(A)
    return L

def contour(mot) :
    trace = chemin(mot)
    for i in range(1,len(trace)):
        if trace[i] == (0,0) :
            if i == len(trace)-1 :
                return True
            else : return False
    return False

## EXERCICE 26 ##

def LongCr1(L) :
    l = 1
    i = 0
    while i+1<len(L) and L[i+1] >= L[i] :
        l += 1
        i += 1
    return l

def longCr(L) :
    M = []
    L2 = L.copy()
    while len(L2) > 0 :
        l = LongCr1(L2)
        M.append(l)
        L2 = L2[l:]
    return M

def longCr2(L) :
    M = []
    LL = []
    L2 = L.copy()
    while len(L2) > 0 :
        l = LongCr1(L2)
        M.append(l)
        LL.append(L2[:l])
        L2 = L2[l:]
    return M,LL

## EXERCICE 27 ##

def voyelles(S) :
    V = ['a','e','i','o','u','y']
    for lettre in S :
        if lettre in V :
            return True
    return False

def test27(S,P) :
    for lettre in S :
        if P(lettre) :
            return True
    return False

def test27bis(LS,LP) :
    for mot in LS :
        for lettre in mot :
            for fonct in LP :
                if fonct(lettre) :
                    return True
    return False

## EXERCICE 28 ##

def extrema(L) :
    m,M = L[0],L[0]
    for elt in L :
        if elt > M :
            M = elt
        if elt < m :
            m = elt
    return m,M

def occurences28(L) :
    m,M = extrema(L)
    Occ = [0 for _ in range(M-m+1)]
    for elt in L :
        Occ[elt-m] += 1
    return Occ

## EXERCICE 29 ##

def somme29(A,P) :
    s = 0
    n = len(A)
    for i in range(n) :
        if P[i] :
            s += A[i]
    return s

def suivant29(P) :
    i = 0
    while i < len(P) :
        if P[i] :
            P[i] = False
        else :
            P[i] = True
            return True
        i += 1
    return False

def listeP(n) :
    P = [False for _ in range(n)]
    P2 = P.copy()
    LP = [P2]
    for _ in range(2**n-1) :
        suivant29(P)
        P2 = P.copy()
        LP.append(P2)
    return LP

## EXERCICE 30 ##

def brin(n) :
    N = ['A','T','C','G']
    b = ''
    for _ in range(n) :
        nucleotide = rd.choice(N)
        b += nucleotide
    return b

def brin_complementaire(b) :
    b2 = ''
    for nucleotide in b :
        if nucleotide == 'A' : b2 += 'T'
        if nucleotide == 'T' : b2 += 'A'
        if nucleotide == 'C' : b2 += 'G'
        if nucleotide == 'G' : b2 += 'C'
    return b2

def freq_nucl(b) :
    fA, fT, fC, fG = 0,0,0,0
    n = len(b)
    for nucleotide in b :
        if nucleotide == 'A' : fA += 1
        if nucleotide == 'T' : fT += 1
        if nucleotide == 'C' : fC += 1
        if nucleotide == 'G' : fG += 1
    return fA/n,fT/n, fC/n, fG/n

def brin_prob(n,p) :
    N1 = ['A','T']
    N2 = ['C','G']
    b = ''
    for _ in range(n) :
        if rd.random() < 2*p :
            nucleotide = rd.choice(N1)
        else :
            nucleotide = rd.choice(N2)
        b += nucleotide
    return b

## EXERCICE 31 ##

def geom(p) :
    rg = 1
    while rd.random() > p :
        rg += 1
    return rg

def que_des_6(N) :
    return max([geom(1/6) for _ in range(N)])

## EXERCICE 32 ##

def grille(n,p) :
    G = np.eye(n)
    for i in range(n) :
        for j in range(n) :
            G[i,j] = geom(p)
    return G

def deplacements(G) :
    n,n = np.shape(G)
    i,j = 0,0
    D = []
    while (i,j) != (n-1,n-1) :
        if j+1 >= n or G[i,j+1] > G[i,j] :
            i += 1
            if i > n-1 :
                return False
            D.append('b')
        else :
            j += 1
            D.append('d')
    return D

## EXERCICE 33 ##

def permut(n) :
    L = [k for k in range(n)]
    P = []
    for _ in range(n) :
        i = rd.randint(0,len(L)-1)
        P.append(L.pop(i))
    return P

def est_un_derangement(Perm) :
    for k in range(len(Perm)) :
        if Perm[k] == k :
            return False
    return True

## EXERCICE 34 ##

def tri_bulle(L) :
    for i in range(1,len(L)) :
        k = i
        while k>0 and L[k] < L[k-1] :
            L[k],L[k-1] = L[k-1],L[k]
            k = k-1
        print(L)
    return L

def valeurs_et_occ(L) :
    dico = {}
    for elt in L :
        if elt in dico :
            dico[elt] += 1
        else :
            dico[elt] = 1
    valeurs = [cle for cle in dico]
    occ = [dico[cle] for cle in dico]
    return valeurs,occ

## EXERCICE 35 ##

def el_commun(L1,L2) :
    for elt1 in L1 :
        if elt1 in L2 :
            return True
    return False

def liste_commun(L1,L2) :
    COM = []
    for elt1 in L1 :
        if elt1 in L2 :
            if elt1 not in COM :
                COM.append(elt1)
    return COM

## EXERCICE 36 ##

def test_arithmetique(L) :
    r = L[1] - L[0]
    for i in range(1,len(L)-1) :
        if L[i+1] - L[i] != r :
            return False
    return True

def test_geometrique(L) :
    # traitement si l'un des 2 premiers termes est nul
    if L[0]*L[1] == 0 :
        for i in range(1,len(L)) :
            if L[i] != 0 :
                return False
        return True
    # cas général
    q = L[1] / L[0]
    for i in range(1,len(L)-1) :
        if L[i+1] / L[i] != q :
            return False
    return True

## EXERCICE 37 ##

def Maxi37(tab) :
    M = tab[0]
    for elt in tab :
        if elt > M :
            M = elt
    return M

def occur37(tab) :
    M = Maxi37(tab)
    Oc = [0 for _ in range(M+1)]
    for elt in tab :
        Oc[elt] += 1
    return Oc

## EXERCICE 38 ##

def test38(ADN) :
    bases = ['A','T','C','G']
    for lettre in ADN :
        if lettre not in bases :
            return False
    return True

def mut(ADN) :
    M = ''
    for lettre in ADN :
        if lettre == 'T' :
            lettre = 'U'
        M = M + lettre
    return M

def test_gene(ARN) :
    if len(ARN) < 4 :
        return False
    start = ['AUG','GUG','UUG']
    stop = ['UAA','UAG','UGA']
    deb = ARN[:3]
    n = len(ARN)
    fin = ARN[n-3:n]
    return (deb in start) and (fin in stop)

## EXERCICE 39 ##

def Maxi2(L) :
    M1 = L[0]
    M2 = False
    for elt in L :
        if elt > M1 :
            M2 = M1
            M1 = elt
        elif elt < M1 and M2 == False :
            M2 = elt
        elif M2 < elt < M1 :
            M2 = elt
    return M2

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


## EXERCICE 40 ##

def liste_multi(n) :
    LM = []
    for i in range(1,n+1) :
        LM += [i for _ in range(i)]
    return LM

def tirage_2eme_urne() :
    boule = rd.randint(1,5)
    U = liste_multi(boule)
    return rd.choice(U)

def proba40(N) :
    S = 0
    for _ in range(N) :
        S += (tirage_2eme_urne()==1)
    return S/N

# calcul avec FPT : p = 1/3

## EXERCICE 41 ##

def entre(L) :
    n = len(L)
    for elt in L :
        if elt < 0 or elt > n :
            return False
    return True

def recherche(x,L) :
    Lind = []
    for i in range(len(L)) :
        if L[i] == x :
            Lind.append(i)
    return Lind

## EXERCICE 42 ##

import matplotlib.pyplot as plt

def distance(A,B) :
    x1,y1 = A
    x2,y2 = B
    return ((x1-x2)**2+(y1-y2)**2)**.5

def point_moyen(Nuage) :
    Xmoy, Ymoy = 0,0
    n = len(Nuage)
    for point in Nuage :
        x,y = point
        Xmoy += x
        Ymoy += y
    return [Xmoy/n, Ymoy/n]

def plus_proche_G(Nuage) :
    G = point_moyen(Nuage)
    D = distance(G,Nuage[0])
    i0 = 0
    for i in range(len(Nuage)) :
        di = distance(G,Nuage[i])
        if di < D :
            D = di
            i0 = i
    return Nuage[i0]

def representation(Nuage) :
    G = point_moyen(Nuage)
    PPG = plus_proche_G(Nuage)
    X,Y = [], []
    for point in Nuage :
        x,y = point
        X.append(x)
        Y.append(y)
    plt.plot(X,Y,'.')
    plt.plot([G[0]],[G[1]],'x')
    plt.plot([PPG[0]],[PPG[1]],'o')
    plt.show()