##########################################################
### Le 26/01/2022                                      ###
### MatheX                                             ###
### Licence CC BY-NC-SA 4.0                            ###
### 1 SPE NSI4                                         ###
### Correction DS03:                                   ###
### Recherche dichotomique                             ###
### Codage de texte                                    ###
##########################################################


###############################################################################
#                            Exercice 1: (10 points)                          #
###############################################################################

# 1.1. Décrire ce qu’est un système d’encodage de caractères
#      et donner le nom de deux systèmes d’encodage:
# -----------------------------------------------------------

'''
Un système d'encodage définit une correspondance entre chaque caractère
et son code en valeur numérique (en binaire, hexadécimal ou décimal)

Les principaux systèmes d'encodage:
- ASCII (7 bits): le latin de base (pour l'anglais)
- ISO-8859-1 (8 bits): ASCII + accents (latin 1- supplement)
- UTF-8 (de 1 à 4 octets) tous les caractères du standart unicode
'''
  
      
# 1.2. Ecrire une instruction qui affiche sur une ligne:
#      le caractère "a" , son code en décimal, son code en hexadécimal
#      et son code en binaire.
#      >>> a 97 0x61 0b1100001:
# --------------------------------------------------------------------

print("a", ord("a"), hex(ord("a")), bin(ord("a")))


# 1.3. Implémenter une fonction qui convertit une lettre minuscule en majuscule:
#      >>> assert majuscule( "a" ) == "A":
# ------------------------------------------------------------------------------

def majuscule(c: str) -> str :
    '''convertit un caractère minuscule en majuscule'''
    decalage = ord("A") - ord("a") 
    c_M = chr(ord(c) + decalage)
    return c_M

assert majuscule( "a" ) == "A"


# 1.4. Implémenter une fonction qui renvoie le minimum et le maximum
#      d’une liste de nombres donnée en paramètre.
#      >>> assert minMax( [ 7 , 4 , 2 , 10 , 5 ] ) == [ 2 , 10 ]
# ------------------------------------------------------

def minMax(tab: list) -> list : 
    '''renvoie [min, max] d'une liste de nombre'''
    min = max = tab[0]
    for nb in tab:
        if nb < min:
            min = nb
        elif nb > max:
            max = nb
    return [min, max]

assert minMax( [ 7 , 4 , 2 , 10 , 5 ] ) == [ 2 , 10 ]


# 1.5. Implémenter une fonction qui recherche si une valeur est dans une
#      liste de nombres donnée en paramètre. La liste est non triée:
#      >>> assert recherche( [ 7 , 4 , 2 , 10 , 5 ] , 5 ) == True
#      >>> assert recherche( [ 7 , 4 , 2 , 10 , 5 ] , 1 ) == False 
# ----------------------------------------------------------------------

def recherche(tab: list, valeur: int) -> bool :
    '''renvoie True si valeur est dans liste (non triée), False sinon'''
    for nb in tab:
        if nb == valeur:
            return True
    return False

assert recherche( [ 7 , 4 , 2 , 10 , 5 ] , 5 ) == True
assert recherche( [ 7 , 4 , 2 , 10 , 5 ] , 1 ) == False 
  

# 1.6. Implémenter une fonction qui recherche linéairement si une valeur est
#      dans une liste de nombres données en paramètre. La liste est triée
#      en ordre croissant. Votre implémentation doit en tirer bénéfice.
#      >>> assert recherche( [ 2 , 4 , 5 , 7 , 10 ] , 5 ) == True
#      >>> assert recherche( [ 2 , 4 , 5 , 7 , 10 ] , 1 ) == False
# --------------------------------------------------------------------------

def rechercheT(tab: list, valeur: int) -> bool :
    '''renvoie True si valeur est dans tab (liste triée), False sinon'''
    # vérifie si valeur est bien dans l'intervalle [début tab;fin tab]
    if valeur < tab[0] or valeur >tab[-1]:
        return False
    for nb in tab:
        if nb == valeur:
            return True
        # si on dépasse la valeur cherchée
        elif nb > valeur:
            return False
    return False
    
assert rechercheT( [ 2 , 4 , 5 , 7 , 10 ] , 5 ) == True
assert rechercheT( [ 2 , 4 , 5 , 7 , 10 ] , 1 ) == False
    
def rechercheT2(tab: list, valeur: int) -> bool :
    '''renvoie True si valeur est dans tab (liste triée), False sinon'''
    # vérifie si valeur est bien dans l'intervalle [début tab;fin de tab]
    if valeur < tab[0] or valeur > tab[-1]:
        return False
    i = 0
    # on boucle tant qu'une condition de sortie n'est pas atteinte:
    # valeur trouvée , liste terminée, valeur recherchée dépassée
    while not(tab[i] == valeur or i >= len(tab) or tab[i] > valeur):
        i = i + 1
    # si on est sorti sur la valeur recherchée on renvoie True, False sinon
    return tab[i] == valeur

assert rechercheT2( [ 2 , 4 , 5 , 7 , 10 ] , 5 ) == True
assert rechercheT2( [ 2 , 4 , 5 , 7 , 10 ] , 1 ) == False
   


###############################################################################
#                            Exercice 2: ( 5 points)                          #
###############################################################################

# Recopier, compléter (XXX) et commenter (YYY) la fonction de
# recherche dichotomique en annexe:
# -----------------------------------------------------------

def dichotomie(tab: list, x: int) -> bool:
  '''
  Paramètres:
  -----------
    tab (list): tableau trié dans l’ordre croissant
    x (int): nombre entier
  Retour:
  ------  
    Renvoie True si tab contient x et False sinon
  '''
  # vérifie au préalable que la liste contient des éléments
  if list == None or len(tab) == 0 :
    return False
  
  # vérifie si x est bien dans l'intervalle [début tab;fin de tab]
  if (x < tab[0]) or (x > tab[-1]) : # parenthèse inutile
      return False

  debut = 0            # indice de début d'intervalle de recherche
  fin = len(tab) - 1   # indice de fin d'intervalle de recherche
  # boucle tant que l'intervalle contient au moins un élément
  while debut <= fin:
    m = (fin + debut) // 2   # indice du milieu de l'intervalle
    # print(x, tab, tab[m],tab[debut:fin+1]) # pour afficher
    # renvoie True si x est égal au milieu
    if x == tab[m] :  
      return True 
    # prend l'intervalle de droite si x est supérieur au milieu
    if x > tab[m] :
      debut = m + 1
    # prend l'intervalle de gauche sinon (x est inférieur au milieu)
    else :
      fin = m - 1
  return False


assert dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28) == True
assert dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27) == False
assert dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],1) == False
assert dichotomie([], 28) == False



###############################################################################
#                            Exercice 3: ( 5 points)                          #
###############################################################################


# 3.1. Coder votre nom de famille avec le code César avec 
#      une clé  de décalage  égale   à 3 :
# -------------------------------------------------------

'''
M -> P
A -> D
T -> W
H -> K
E -> H
X -> A

MATHEX -> PDWKHA
'''

# 3.2. Implémenter une fonction qui chiffre un texte avec le code César
#      selon une clé  de décalage.
#      On rappelle les fonctions python ord() et chr() qui code et décode
#      respectivement un caractère.
#      >>> assert chiffrementCesar( "A" , 3 ) == "D"
#      >>> assert chiffrementCesar( "NSI" , 2 ) == "PUK"
#      >>> assert chiffrementCesar( "Z" , 2 ) == "B"
# ------------------------------------------------------------------------

def chiffrementCesar(texte: str, decalage: int) -> str :
    '''renvoie le texte chiffré par le code César avec le décalage spécifiée'''
    texte_c = ''
    for car in texte:
        # ord du caractère chiffré
        ord_car_c = ord(car) + decalage
        # gestion du débordement éventuel
        # on le remet dans l'intervalle [ord(A);ord(Z)]
        ord_car_c = ord("A") + (ord_car_c - ord("A")) % 26
        # on retrouve le caractère correspondant
        car_c = chr( ord_car_c)
        # et on le concatène au texte chiffré
        texte_c = texte_c + car_c
    return texte_c


assert chiffrementCesar( "A" , 3 ) == "D"
assert chiffrementCesar( "NSI" , 2 ) == "PUK"
assert chiffrementCesar( "Z" , 2 ) == "B"


# 3.4. Implémenter une fonction qui déchiffre un texte chiffré  avec
#      le code César selon une clé  de décalage:
#      >>> assert dechiffrementCesar( "D" , 3 ) == "A"
#      >>> assert dechiffrementCesar( "PUK" , 2 ) == "NSI"
#      >>> assert dechiffrementCesar( "B" , 2 ) == "Z"
# ------------------------------------------------------------------

def dechiffrementCesar(texte_c: str, decalage: int) -> str :
    '''renvoie le texte déchiffré connaissant le décalage utilisé'''
    texte = ''
    for car_c in texte_c:
        # ord du caractère chiffré
        ord_car = ord(car_c) - decalage
        # gestion du débordement éventuel
        # on le remet dans l'intervalle [ord(A);ord(Z)]
        ord_car = ord("Z") - (ord("Z") - ord_car) % 26
        # on retrouve le caractère correspondant
        car = chr(ord_car)
        # et on le concatène au texte chiffré
        texte = texte + car
    return texte


assert dechiffrementCesar( "D" , 3 ) == "A"
assert dechiffrementCesar( "PUK" , 2 ) == "NSI"
assert dechiffrementCesar( "B" , 2 ) == "Z"
    

###############################################################################
#                            Fin de la correction                             #
###############################################################################