##TP - Chaînes de caractères

##1.Premières manipulations
"""
Question 1 :
"""
s1="Science"
s2="sans conscience n'est que ruine de l'âme."

"""
Question 2 :
"""
print(s1)  #Accès à la longueur de s1
print(s2)

"""
Question 3 :
"""
print(s2[0]) #Accès à l'élément d'indice 0
print(s2[5]) #Les espaces sont des caractères
#print(s2[41])  #Il n'existe pas de caractère d'indice len(s2)=41

"""
Question 4 :
"""
s=s1+" "+s2
print(s)

"""
Question 5 :
"""
#print(s[0]="A") #Erreur pas d'assignement pour les chaînes de caractères, ce sont des objets non mutables !



##2.Algorithmes fondamentaux
"""
Question 6 :
Fonction present prend en entrée une chaîne de caractères s et un caractère c et renvoie un booléen indiquant si c est dans s.
"""
def present(s,c):
    n=len(s) #longueur de la chaîne
    i=0 #Indice de parcours de s
    while i<n and not(s[i]==c) : #Tant que le parcours n'est pas fini et qu'on n'a pas trouvé c
        i += 1 #On passe à l'indice suivant
    return i<n #Si le parcours n'est pas fini c'est qu'on a trouvé c et inversement

print(present("conscience",'o'))
print(present("conscience",'a'))

"""
Question 7:
Fonction compter prend en entrée une chaîne de caractères s et un caractère c et renvoie le nombre d'occurrences de c dans s.
"""
def compter(s,c):
    n=len(s) #longueur de la chaîne
    cpt=0 #compteur des occurrences de c
    for i in range(n): #On parcourt la chaîne
        if s[i]==c : #Si on trouve c
            cpt += 1 #On incrémente le compteur
    return cpt #On renvoie le compteur

print(compter("conscience",'c'))
print(compter("conscience",'o'))
print(compter("conscience",'a'))

"""
Question 8 :
Fonction verifFacteur prend en entrée un chaîne s, une chaîne f plus petite et un indice i et renvoie un booléen indiquant si f est un facteur de s à l'indice i.
"""
def verifFacteur(s,f,i) :
    assert 0 <= i <= len(s) #i est-il valide ?
    if i + len(f)-1 > len(s)-1: #Si on n'a pas la place d'écrire f en position i
        return False #On renvoie False
    for k in range(len(f)) : #On parcourt le facteur f
        if not f[k]==s[i+k] : #Si la kème lettre de f n'est pas égale à la lettre de s d'indice i+k
            return False #On renvoie False
    return True #On renvoie True

print(verifFacteur(s,"conscience",13))
print(verifFacteur(s,"conscience",12))
print(verifFacteur(s,"conscience",46))

#Deuxième méthode en utilisant le slicing pour extraire le morceau de s à tester.
def verifFacteur(s,f,i):
    return s[i:i+len(f)]==f

print(verifFacteur(s,"conscience",13))
print(verifFacteur(s,"conscience",12))
print(verifFacteur(s,"conscience",46))

"""
Question 9 :
Fonction estFacteur prend en entrée une chaîne de caractère s, une chaîne f plus petite et renvoie un booléen indiquant si f est un facteur de s.
"""
def estFacteur(s,f):
    for i in range(len(s)-len(f)+1): #On teste toutes les positions possibles pour f, on a nécessairement i+len(f)-1<len(s)
        if verifFacteur(s,f,i): #Si f est un facteur en position i
            return True #On renvoie True
    return False #On renvoie False

print(estFacteur(s,"conscience"))
print(estFacteur("bonjour","bon"))
print(estFacteur("bonjour","boj"))
print(estFacteur("bonjour","jour"))
print(estFacteur("bonjour","r"))

"""
Question 10 :
Fonction miroir prend en entrée une chaîne s et renvoie une nouvelle chaîne étant la chaîne miroir de s.
"""
def miroir(s):
    n=len(s) #longueur de s
    res=s[n-1] #la chaîne miroir commence par le dernier caractère de s
    for i in range(n-1): #On parcourt s
        res = res + s[n-2-i] #On ajoute le caractère d'indice n-1-(i+1)
    return res #On renvoie la chaîne miroir res

print(miroir("jour"))

#Hors-Programme : Utilisation d'un range décroissant
def miroir(s):
    n=len(s)#longueur de s
    res = "" #chaîne miroir
    for i in range(n-1,-1,-1): #On parcourt s à l'envers
        res += s[i]#On ajoute le caractère i de s
    return res #On renvoie res

print(miroir("jour"))

#Hors-Programme : Utilisation des indices négatifs : de -1 à -len(s)
def miroir(s):
    n=len(s)#longueur de s
    res = "" #chaîne miroir
    for i in range(1,n+1): #On parcourt s
        res += s[-i] #On ajoute le terme d'indice -i
    return res #On renvoie res

print(miroir("jour"))

#Utilisation de +
def miroir(s):
    n=len(s)#longueur de s
    res = s[0] #chaîne miroir
    for i in range(1,n): #On parcourt la chaîne s
        res = s[i] + res #On ajoute le caractère de s d'indice i devant res
    return res #On renvoie res

print(miroir("jour"))



##3.Autres exercices
##Exercice 1 : Pangramme
"""
Question 11 :
"""
from string import ascii_lowercase as alph
#On renomme la variable ascii_lowercase en alph plus court !

print(alph)

pangramme="portez ce vieux whisky au juge blond qui fume" #on stocke le pangramme dans une variable

"""
Fonction estPangramme prend en entrée une chaîne et renvoie un booléen indiquant si il s'agit d'un pangramme.
"""
def estPangramme(s):
    for i in range(26): #On parcourt alph
        if not estFacteur(s,alph[i]): #Si la (i+1)ème lettre de l'alphabet n'est pas un facteur de s,
            return False #ce n'est pas un pangramme
    return True #Sinon s'en est un

print(estPangramme(pangramme))
print(estPangramme("bonjour"))

"""
Question 12 :
Fonction manquePourPangramme prend en entrée un chaîne et renvoie la liste des caractères qu'il manque à la chaîne pour que ce soit un pangramme.
"""
def manquePourPangramme(s):
    manque=[] #liste de caractères manquants
    for i in range(26): #On parcourt l'alphabet
        if not estFacteur(s,alph[i]): #Si la (i+1)ème lettre de l'alphabet n'est pas un facteur de s,
            manque.append(alph[i]) #on ajoute la lettre à manque
    return manque #On renvoie manque

print(manquePourPangramme("bonjour"))
print(manquePourPangramme(pangramme))
"""
Remarque : il est inutile d'utiliser la fonction estPangramme qui effectue exactement les même test que manquePourPangramme. Dans le cas d'une chaîne qui n'est pas un pangramme, on effectuerait donc deux fois les mêmes calculs.
Dans le cas d'une chaîne qui est un pangramme on effectue les mêmes calculs que si on avait utilisé estPangramme.
"""

##Exercice 2 : Cybercafé
"""
Question 13 :
On commence par une fonction present qui prend en entrées une liste l et un élément e et renvoie un booléen indiquant si e est dans l."""
def present(l,e):
    n=len(l) #longueur de l
    i=0 #Indice de parcours de la liste
    while i<n and not(l[i]==e) : #Tant qu'on n'a pas fini le parcours et qu'on n'a pas trouvé e
        i += 1 #On passe à l'indice suivan
    return i<n #Si on n'a pas fini le parcours c'est qu'on a trouvé e et inversement.

print(present(['A','B','C'],'B'))

"""supprime(l,e) renvoie la liste obtenue en supprimant l'unique occurence de e dans la liste l"""
def supprime(l,e):
    n=len(l) #longueur de l
    i=0 #Indice de parcours de la liste
    while i < n : #Tant qu'on n'a pas fini la liste
        if l[i] == e: #Si on a trouvé e
            return l[:i]+l[i+1:] #On renvoie la liste obtenue en supprimant l'élément d'indice i
        i+=1 #Sinon, on passe à l'indice suivant

#L'algorithme termine car e est supposé appartenir à la liste l.
print(supprime(['A','B','C'],'B'))

"""
nbClientsSansOrdis(n,s) renvoie le nombre de clients ayant du attendre un ordinateur dans le cybercafé de n ordinateurs suivant les entrées-sorties s.
"""
def nbClientsSansOrdis(n,s):
    clients = []  #Liste des clients du cybercafé
    clientsenattente = [] #Liste des clients en attente
    occupe = 0 #Nombre d'ordinateurs occupés
    cpt = 0 #Nombre de clients ayant dû attendre
    for i in range(len(s)):
        #On teste si le client arrête d'utiliser un ordi
        if present(clients,s[i]):
            occupe -=1 #On libère un ordi
            clients = supprime(clients,s[i]) #On supprime le client de la liste des clients actuels du cybercafé

            #Si un client attend, il récupère un ordi
            if clientsenattente != [] :
                occupe += 1 #On occupe un ordi
                clients.append(clientsenattente[0]) #Mise à jour de la liste des clients du cybercafé
                clientsenattente = supprime(clientsenattente,clientsenattente[0]) #Mise à jour de la liste des clients en attente

        #On teste si c'est un client qui en a marre d'attendre
        elif present(clientsenattente,s[i]):
            clientsenattente = supprime(clientsenattente,s[i]) #Mise à jour de la liste des clients en attente

        #Si il entre, on teste si il reste un ordi
        elif occupe < n:
            clients.append(s[i]) #Mise à jour de la liste des clients du cybercafé
            occupe += 1 #On occupe un nouvel ordi

        else: #Ou si les ordis sont tous occupés
            clientsenattente.append(s[i]) #Mise à jour de la liste des clients en attente
            cpt +=1 #Et du compteur correspondant
    return cpt

test1 = "ABCDDCEFFEBGAG"
print(nbClientsSansOrdis(3,test1))

test2 = "ABCDDCBEFFEGAG"
print(nbClientsSansOrdis(2,test2))

"""
Question 14 : nbClientsSansOrdisbis(n,s) renvoie le nombre de clients ayant du attendre un ordinateur dans le cybercafé de n ordinateurs suivant les entrées-sorties s ainsi que la liste de ces clients.
"""
def nbClientsSansOrdisbis(n,s):
    clients = [] #Liste des clients du cybercafé
    clientsenattente = [] #Liste des clients en attente
    pascontents = [] #Liste des clients ayant été un jour mis en attente
    occupe = 0 #Nombre d'ordinateurs occupés
    cpt = 0 #Nombre de clients ayant dû attendre
    for i in range(len(s)):
        #On teste si le client arrête d'utiliser un ordi
        if present(clients,s[i]):
            occupe -=1 #On libère un ordi
            clients = supprime(clients,s[i]) #On supprime le client de la liste des clients actuels du cybercafé

            #Si un client attend, il récupère un ordi
            if clientsenattente != [] :
                occupe += 1 #On occupe un ordi
                clients.append(clientsenattente[0]) #Mise à jour de la liste des clients du cybercafé
                clientsenattente = supprime(clientsenattente,clientsenattente[0]) #Mise à jour de la liste des clients en attente

        #On teste si c'est un client qui en a marre d'attendre
        elif present(clientsenattente,s[i]):
            clientsenattente = supprime(clientsenattente,s[i]) #Mise à jour de la liste des clients en attente

        #Si il entre, on teste si il reste un ordi
        elif occupe < n:
            clients.append(s[i]) #Mise à jour de la liste des clients du cybercafé
            occupe += 1 #On occupe un nouvel ordi

        else: #Ou si les ordis sont tous occupés
            pascontents.append(s[i]) #Mise à jour de la liste des clients ayant un jour été mis en attente
            clientsenattente.append(s[i]) #Mise à jour de la liste des clients en attente
            cpt +=1 #Et du compteur correspondant
    return (cpt, pascontents)

print(nbClientsSansOrdisbis(3,test1))
print(nbClientsSansOrdisbis(2,test2))



##Exercice 4 : Mot de passe
"""
Question 15 :
"""
#On a déjà alph variable contenant toutes les lettres de l'alphabet minuscule

"""
contientMin(s) renvoie un booléen indiquant si s est contient une lettre minuscule"""
def contientMin(s):
    for i in range(26): #On parcourt l'alphabet
        if estFacteur(s,alph[i]):
            return True #On renvoie vrai si on trouve un minuscule
    return False

print(contientMin("BONJOUR"))
print(contientMin(pangramme))


#Chaîne contenant toutes les lettres de l'alphabet majuscule
from string import ascii_uppercase as ALPH
print(ALPH)

"""contientMaj(s) renvoie un booléen indiquant si s est contient une lettre majuscule"""
def contientMaj(s):
    for i in range(26): #On parcourt l'alphabet
        if estFacteur(s,ALPH[i]):
            return True #On renvoie vrai si on trouve une majuscule
    return False

print(contientMaj("Bonjour"))
print(contientMaj(pangramme))


#Chaîne contenant tous les chiffres
chiffres = "0123456789"
print(chiffres)

"""contientChiffres(s) renvoie un booléen indiquant si s contient un chiffre"""
def contientChiffres(s):
    for i in range(10): #On parcourt la chaîne des chiffres
        if estFacteur(s,chiffres[i]):
            return True #On renvoie vrai si on trouve un chiffre
    return False

print(contientChiffres(chiffres))
print(contientChiffres("129"))



#Chaîne contenant les caractères spéciaux
speciaux="!\"#$%&'()*+,-./:;<=>@[\\]^_{|}~"
print(speciaux)

"""contientSpeciaux(s) renvoie un booléen indiquant si s contient un caractère de la chaîne spéciaux"""
def contientSpeciaux(s):
    for i in range(len(speciaux)): #On parcourt la chaîne des caractères spéciaux
        if estFacteur(s,speciaux[i]):
            return True #On renvoie vrai si on trouve un caractère spécial
    return False

print(contientSpeciaux(speciaux))
print(contientSpeciaux("(!)"))


"""
motDePasseSecure(s) renvoie un booléen indiquant si le mot de passe s satisfait les 4 conditions ci-dessus.
"""
def motDePasseSecure(s):
    return contientMin(s) and contientMaj(s) and contientChiffres(chiffres) and contientSpeciaux(speciaux)

"""
Question 16 : extractionMotsDePasse(ch,k) renvoie la liste des mots de passe de taille k contenus dans ch.
"""
def extractionMotsDePasse(ch,k):
    liste_mdp = [] #Liste des mots de passe
    for i in range(len(ch)-k): #On parcourt les sous-chaînes de taille k
        mdp = ch[i:i+k+1] #Sous-chaîne de taille k
        if motDePasseSecure(mdp): #Si c'est un potentiel mot de passe
            liste_mdp.append(mdp) #On l'ajoute à la liste résultat
    return liste_mdp

print(extractionMotsDePasse("Ba(5mH]",4))



##Exercice 5 : Plus petit préfixe
"""Question 17:
prefixe(s1,s2)renvoie le plus court préfixe de s1 non préfixe de s2."""
def prefixe(s1,s2):
    n1=len(s1) #longueur de s1
    n2=len(s2) #longueur de s2
    i=0 #Indice de parcours
    while i<n1 and i<n2 and s1[i]==s2[i]: #Tant qu'on n'a pas fini s1 et s2 et qu'il y a égalité
        i +=1 #On passe au caractère suivant
    return s1[:i+1] #On renvoie le premier préfixe non commun

print(prefixe('AND','BONFIRE'))
print(prefixe('BONEFIRE','BOOL'))


liste_mots = ['CHAR','AND','BOOL','CASE','CATCH','BONFIRE']

print(prefixe(liste_mots[0],liste_mots[1]))

"""
plusCourtPrefixe(l) renvoie la liste des plus court préfixes de chacun des mots qui ne soient préfixes d'aucun autre mot de la liste.
"""
def plusCourtPrefixe(l):
    listepref = ["" for i in range(len(l))] #Liste des préfixes
    for i in range(len(l)): #On parcourt la liste de mots : s1
        for j in range(len(l)): #On parcourt la liste de mots : s2
            if j!= i : #On s'assure qu'on a deux mots différents
                pref = prefixe(l[i],l[j]) #premier préfixe non commun
                if len(pref)>len(listepref[i]): #Si c'est un préfixe plus long que celui déjà enregistré, on le sauvegarde
                    listepref[i] = pref
    return listepref

print(plusCourtPrefixe(liste_mots))


#On donne une deuxième version du programme qui commence par trier la liste dans l'ordre alphabétique.
"""tri(l) renvoie la liste de chaînes de caractères l triée dans l'ordre alphabétique. On effectue un tri Bulle"""
def tri(l):
    n = len(l) #Longueur de la liste
    cpt = 1 #Compteur de permutations
    while cpt >0 : #Tant qu'on a permuté deux éléments
        cpt =0 #On remet le compteur à 0
        for i in range(n-1): #On parcourt la liste
            if l[i]>l[i+1] : #Si les termes i et i+1 ne sont pas bien ordonnés
                l[i],l[i+1] = l[i+1],l[i] #On les permutent
                cpt += 1 #et on incrémente le compteur de permutations
    return l

"""
plusCourtPrefixe2(l) renvoie la liste des plus court préfixes de chacun des mots qui ne soient préfixes d'aucun autre mot de la liste.
"""
def plusCourtPrefixe2(l):
    listepref = [] #Liste des préfixes
    liste = tri(l[:]) #Liste l triée (on effectue une copie de l)
    if liste[0][0]==liste[1][0] : #Si les deux premières chaînes commencent par la même lettre
        listepref.append(prefixe(liste[0],liste[1])) #On ajoute à la liste des préfixes, le plus petit préfixe non commun
    else : #Sinon, le plus court préfixe est constitué de la première lettre de la première chaîne
         listepref.append(liste[0][0])
    for i in range(1,len(l)-1): #On parcourt le reste de la liste
        if liste[i][0]==liste[i-1][0] and liste[i][0]==liste[i+1][0] : #Si la ième chaîne a la même première lettre que la précédente et la suivante
            #On calcule les deux plus courts préfixes non communs
            pref1 = prefixe(liste[i],liste[i+1])
            pref2 = prefixe(liste[i],liste[i-1])
            #On garde le plus long des deux, non communs aux trois chaînes
            if len(pref1)>len(pref2) :
                listepref.append(pref1)
            else :
                listepref.append(pref2)
        elif liste[i][0]==liste[i+1][0] : #Si la ième chaîne a la même première lettre que le mot suivant, on calcul le préfixe le plus court non commun à ces deux chaînes
            listepref.append(prefixe(liste[i],liste[i+1]))
        elif liste[i][0]==liste[i-1][0] : #Sinon si la ième chaîne a la même première lettre que le mot précédent, on calcul le préfixe le plus court non commun à ces deux chaînes
            listepref.append(prefixe(liste[i],liste[i-1]))
        else : #Sinon, le plus court préfixe est constitué de la première lettre de la première chaîne
            listepref.append(liste[i][0])
    if liste[len(l)-1][0]==liste[len(l)-2][0]:
        listepref.append(prefixe(liste[len(l)-1],liste[len(l)-2]))
    else :
        listepref.append(liste[len(l)-1][0])
    return listepref

print(plusCourtPrefixe2(liste_mots))