L'objet ci-dessous est un automate. Il possède plusieurs états, symbolisés par des cercles, dont un état initial symbolisé par deux cercles concentriques. Il permet de transformer une séquence de lettres 'a' et 'b' en séquence de chiffres 0 et 1.
Pour opérer cette transformation, on va «lire» la séquence de 'a' et 'b' tout en suivant un chemin dans l'automate. Supposons qu'on veuille transformer la séquence aabab. On part de l'état initial, numéroté 0.
Il y a deux flèches qui sortent de l'état 0 : une est étiquetée par un a et l'autre par un b. Puisque la première lettre de la séquence à transformer aabab est un a, on suit l'arête étiquetée par a. On atteint l'état 2. On continue avec la deuxième lettre a, qui nous emmène sur l'état 1. Puis avec la troisième lettre b qui nous amène sur l'état 2... Lire la séquence aabab correspond donc au chemin qui parcourt les noeux suivants sur graphe : [0, 2, 1, 2, 1, 2].
La deuxième étape consiste à parcourir ce chemin, et à chaque fois qu'on emprunte une arête, à noter le chiffre (0 ou 1) dans les parenthèses. Le chemin le long de noeuds [0, 2, 1, 2, 1, 2] correspond ainsi à la séquence de chiffres : [0, 1, 0, 1, 0].
Ainsi, nous venons de voir comment transformer la séquence de lettres aabab en séquence de chiffre binaires [0, 1, 0, 1, 0]. Cela constitue la première étape du chiffrement.
La seconde étape consiste à grouper cette séquence de 0 et 1 par parquet de 5 bits. Par exemple, si le chemin correspond à la séquence de 15 bits (0,0,1,1,0,0,1,0,0,1,1,1,0,0,0), alors les groupes de 5 bits sont 00110 puis 01001 puis 11000. Chaque groupe de 5 bits correspond, en base 10 à un nombre entre 0 et 31. Dans notre exemple : 6 puis 9 puis 24.
Maintenant, que nous disposons d'une liste de nombres entre 0 et 31, nous associons un caractère à chaque nombre en utilisant une table : 0 pour l'espace, 1 pour le A,... 26 pour le Z, et le caractère souligné pour les nombres 27 à 31.
Dans notre exemple, les 3 nombres 6, 9 et 24 correspondent ainsi aux lettres FIX.
DéfiL'entrée de ce problème est une séquence de a et de b. Vous devez la déchiffrer pour obtenir le mot de passe qui permet de valider ce défi.
L'entrée du problème comporte des espaces pour améliorer la lisibilité. Toutefois, la séquence de 'a' et de 'b' est normalement ininterrompue.
Testez votre codeAu cryptogramme ababbbbaabbaabaaaaaa correpond le message ALGO