# -*- coding: utf-8 -*-
"""
TP5 : Recherche séquentielle

PCSI2 - Albert Schweitzer - Le Raincy
"""

##Q2
#Il y a beaucoup de facons de coder la fonction appartient
def appartient(L:list, e) -> bool:
    '''
    Renvoie True si e est un élément de L et False sinon
    '''
    for element in L:
        if e == element:
            return True
    return False

#Tests
L = [1,2,3,-1,-14]
print(appartient(L, 1) == True)
print(appartient(L, -1) == True)
print(appartient(L, -15) == False)

##Q3
def appartient(L:list, e) -> (bool, int):
    '''
    Renvoie (True, i) si e apparait dans L à l'indice i et (False,-1) sinon
    '''
    for i in range(len(L)):
        if e == L[i]:
            return (True, i)
    return (False, -1)

##Q4
def appartient(L:list, e) -> list:
    '''
    Renvoie la liste des indices d'apparition de e dans L
    '''
    M = []
    for i in range(len(L)):
        if e == L[i]:
            M.append(i)
    return M

#Tests
L = [1,2,-14,-1,-14]
print(appartient(L, 1) == [0])
print(appartient(L, -14) == [2, 4])
print(appartient(L, -15) == [])

##Q5
def maximum(L:list):
    '''
    Renvoie le maximum de L
    '''
    M = L[0]
    for e in L:
        if e > M:
            M = e
    return M

##Q6
def maximum2(L:list) -> int:
    '''
    Renvoie la position de la première
    apparition du maximum de L
    '''
    pos = 0
    for i in range(1, len(L)):
        if L[i] > L[pos]:
            pos = i
    return i

##Q7
def maximum3(L:list) -> int:
    '''
    Renvoie la position de la dernière
    apparition du maximum de L
    '''
    pos = 0
    for i in range(1, len(L)):
        if L[i] >= L[pos]:
            pos = i
    return i

##Q8
def maximum4(L:list):
    '''
    Renvoie le maximum de L et la liste des positions
    d'apparition du maximum de L
    '''
    m = L[0]
    Pos = [0]
    for i in range(1, len(L)):
        if L[i] > m:
            m = L[i]
            Pos = [i]
        elif L[i] == m:
            Pos.append(i)
    return (m, Pos)

##Q9
import random as rd

L = [rd.random() for i in range(10**4)]


##Q10-11
def comptage(L:list) -> dict:
    '''
    Renvoie le dictionnaire qui fait l'inventaire
    des éléments de L
    '''
    d = {}#pour stocker l'inventaire
    for element in L:#on parcourt toute la liste
        if element in d:#si on a déjà trouvé element
            d[element] = d[element] + 1
        else:#sinon, on crée la clé dans d
            d[element] = 1
    return d

##Q12
L = []
print(comptage(L))
L = [0]*10
print(comptage(L))
L = [1,2,3,4,3,2,1]
print(comptage(L))

##Q13
def liste_alea(n:int) -> list:
    '''
    Renvoie une liste de taille n composée d'entiers
    aléatoires entre 0 et 10
    '''
    L = []
    for i in range(n):
        L.append(rd.randint(0, 10))
    return L

##Q15
def deux_max(L:list):
    '''
    Renvoie les deux plus grands éléments de L sauf si tous sont égaux
    '''
    max1 = L[0]
    i = 0
    while i < len(L) and max1 == L[i]:#on cherche un élément différent
        i = i + 1
    if i == len(L):#tous les éléments sont égaux
        return max1
    if L[i] < max1:
        max2 = L[i]
    else:
        max2 = max1
        max1 = L[i]
    while i < len(L):
        if L[i] > max1:
            max2 = max1
            max1 = L[i]
        elif L[i] > max2:
            max2 = L[i]
        i = i + 1
    return max1, max2

##Q16
def plus_longue_sous_liste_croissante(L:list) -> (int, list):
    '''
    Renvoie la longueur de la plus grande sous-liste
    croissante de L et une sous-liste de cette taille
    '''
    M = []#La plus grande ss-liste croissante trouvée
    N = [L[0]]#Pour stocker les ss-listes croissantes successives
    for i in range(len(L)-1):
        if L[i + 1] >= L[i]:#la ss-liste croissante continue
            N.append(L[i+1])
        else:
            if len(N) > len(M):#la sous-liste terminée est plus grande
                M = N[:]#Attention copie !!
            N = [L[i+1]]#on part sur une autre ss-liste
    if len(N) > len(M):
        M = N
    return len(M), M