###########################################
###########################################
########## TP 11 : Algorithmique ##########
###########################################
###########################################

## Importations
import numpy as np

## II-A : Maximum d'une liste

def maxi(L) :
    if len(L) == 0 :
        return 'liste vide'
    else :
        M = L[0]
        for elt in L :
            if elt > M :
                M = elt
        return M

## II-B : Occurences du maximum

def pos_max(L) :
    if len(L) == 0 :
        return 'liste vide'
    else :
        M = maxi(L)
        Pos = []
        for i in range(len(L)) :
            if L[i] == M :
                Pos.append(i)
        return Pos

## II-C : second maximum

def maxi2(L) :
    '''second maximum strictement plus petit que le maximum'''
    if len(L) < 2 :
        return 'liste trop petite'
    M = maxi(L)
    L2 = []
    for elt in L :
        if elt < M :
            L2.append(elt)
    if len(L2) == 0 :
        return 'liste constante'
    else :
        return maxi(L2)

def maxi3(L) :
    '''avant-dernière valeur de la liste triee par ordre croissant'''
    if len(L) < 2 :
        return 'liste trop petite'
    else :
        M = L.copy()
        M.sort()
        return M[-2]

## II-D : monotonie d'une liste

def est_Croissant(L) :
    if len(L) < 2 :
        return -1
    for i in range(len(L)-1) :
        if L[i] > L[i+1] :
            return i
    return -1

def est_Decroissant(L) :
    if len(L) < 2 :
        return -1
    for i in range(len(L)-1) :
        if L[i] < L[i+1] :
            return i
    return -1

def monot(L) :
    c = est_Croissant(L)
    d = est_Decroissant(L)
    if c == -1 or d == -1 :
        return True
    else :
        return max(c,d)

## II-E/F : liste sans répétition

# solution avec dictionnaire

def sans_rep(L) :
    dico = {} # alternative : dico = dict()
    for elt in L :
        if elt in dico :
            dico[elt] += 1
        else :
            dico[elt] = 1
    return [cle for cle in dico]

def multiplicite(L) :
    dico = {}
    for elt in L :
        if elt in dico :
            dico[elt] += 1
        else :
            dico[elt] = 1
    return dico

# solution sans dictionnaire

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

def position(L,elt) :
    for i in range(len(L)) :
        if L[i] == elt :
            return i
    return 'absent'

def multiplicite2(L) :
    L1 = []
    M = []
    for elt in L :
        if not (elt in L1) :
            L1.append(elt)
            M.append(0)
        i = position(L1,elt)
        M[i] += 1
    return (L1,M)

## II-G : Tri à bulles
# cf TP 08

## II-H : liste d'adjacence d'un graphe
# cf TP 09

## III-A : n-ème chiffre

# solution avec opérateurs // et %
def chiffre(M,n) :
    l = np.log10(M)
    p = int(l)+1
    if n > p :
        return 'entier trop petit'
    r = p-n
    M2 = M - M % (10**r)
    M2 = M2 // (10**r)
    return M2%10

#solution par manipulation de chaînes
def chiffre2(M,n) :
    nombre = str(M)
    if n > len(nombre) :
        return 'entier trop petit'
    return int(nombre[n-1])

## III-B : nombres poisseux

def est_poisseux(k) :
    s = str(k)
    for i in range(len(s)-1) :
        if s[i]+s[i+1] == '13' :
            return True
    return False

def poisseux(n) :
    L = []
    for k in range(n+1) :
        if est_poisseux(k) :
            L.append(k)
    return L

## III-C : égalité de chaînes

def sont_egales(c1,c2) :
    return c1 == c2

## III-D : Occurences d'une sous-chaîne

def nb_occ(c1,c2) :
    n1 = len(c1)
    n2 = len(c2)
    compteur = 0
    for k in range(n2-n1+1) :
        if c1 == c2[k:k+n1] :
            compteur += 1
    return compteur

## III-E : génération de chaînes

def lexique(Alphabet,n) :
    if n==0 :
        return ['']
    L = lexique(Alphabet, n-1)
    L2 = []
    for mot in L :
        for lettre in Alphabet :
            L2.append(mot+lettre)
    return L2

## III-F : série dans un mot

def serie(mot,i) :
    k = i+1
    while k < len(mot) and mot[k] == '1' :
        k += 1
    return k-i

## III-G : liste des séries

def Lseries(mot) :
    I, L = [], []
    for i in range(len(mot)) :
        if mot[i] == '1' :
            I.append(i)
            L.append(serie(mot,i))
    return I,L

## III-H : plus longue série

def longest_serie(mot) :
    I,L = Lseries(mot)
    P = pos_max(L)
    J = [I[k] for k in P]
    return max(L),J