E09 - Décryptage

Le problème

Décryptage

Proposition 1

🐍 Script Python

def trouve_decalage(texte: str, texte_origine: str):
    """
    Renvoie le decalage de la chaine et la chaine dechiffrer

    >>> trouve_decalage('abcz', 'abcd')
    (25, 'bcda')
    """
    texte_trier = sorted(texte_origine)
    for i in range(27):
        texte_dechiffré = déchiffre(texte, i)
        texte_dechiffré_trier = sorted(texte_dechiffré)
        if texte_trier == texte_dechiffré_trier:
            return i, texte_dechiffré

def déchiffre(texte: str, decalage: int) -> str:
    """
    Renvoie le texte en ajoutant à l'indice de chaque lettres le decalage

    >>> déchiffre('abcd', 25)
    'bcde'
    """
    message_déchiffré = ""
    for lettre in texte:
        message_déchiffré += déchiffrage_lettre(lettre, decalage)
    return message_déchiffré


def déchiffrage_lettre(lettre: str, decalage: int) -> str:
    """
    Renvoie la lettre à l'indice de la lettre - decalage

    >>> déchiffrage_lettre('a', 3)
    'x'
    """
    indice = ord(lettre) - ord('a') - decalage
    return chr(ord('a') + indice % 26)

def trouve_rotation(texte: str, texte_dechiffré: str) -> int:
    """
    Trouve la rotation du texte

    >>> trouve_rotation('abcz', 'zabc')
    1
    """
    rotation = 1
    while True:
        dernier = texte_dechiffré[-1]
        nouveau = dernier + texte_dechiffré[:-1]
        if nouveau == texte:
            return len(texte) - rotation
        else:
            texte_dechiffré = nouveau
            rotation += 1

import doctest
doctest.testmod()

# Entrées
nb_caractere = int(input())
chaine_original = input()
chaine_chiffré = input()

décalage, chaine_déchiffré = trouve_decalage(chaine_chiffré, chaine_original)
rotation = trouve_rotation(chaine_original, chaine_déchiffré)

print(rotation, décalage)

• Je ne suis pas d'accord avec la fonction `trouve_décalage_ ; la méthode de tri pourrait échouer !!! Tu as eu de la chance. Il pourrait y avoir plusieurs décalages avec la même chaine triée !!!

• Une bonne solution simple, ici, est de faire une force brute sur tous les couples (rotation, décalage) et renvoyer le couple valide.

Corrigé du professeur

🐍 Script Python

"""
author: Franck CHAMBON
problem: https://prologin.org/train/2004/semifinal/decryptage
"""

def rotation(lettre: str, increment: int):
    """Renvoie la lettre minuscule avec une rotation
    d'un certain `increment` dans l'alphabet,

    >>> rotation('a', 2)
    'c'

    """
    assert 'a' <= lettre <= 'z', f"Caractère invalide : {lettre}"
    indice = ord(lettre) - ord('a')
    indice = (indice + increment) % 26  # le chiffrement est ici
    return chr(ord('a') + indice)

def chiffrement(texte: str, increment: int) -> str:
    """Renvoie le texte où chaque lettre est chiffrée avec
    l'incrément donné.
    """
    return "".join(rotation(lettre, increment) for lettre in texte)

def donne_methode(longueur, texte_1, texte_2):
    """Renvoie le décalage et l'incrément afin de
    transformer texte_1 en texte_2.

    >>> donne_methode(4, "abcd", "hefg")
    (1, 4)

    """
    # méthode force brute ; on teste tous les cas jusqu'au bon !
    for decalage in range(longueur):
        texte_decale = texte_1[longueur - decalage:] + texte_1[:longueur - decalage]
        for increment in range(26):
            if chiffrement(texte_decale, increment) == texte_2:
                return decalage, increment

# Tests
import doctest
doctest.testmod()

# Entrée
longueur = int(input())
texte_1 = input()
texte_2 = input()
assert longueur == len(texte_1) == len(texte_2),\
    f"Problème {longueur}, {len(texte_1)}, {len(texte_2)}"

# Sortie
decalage, increment = donne_methode(longueur, texte_1, texte_2)
print(decalage, increment)