Vous êtes étudiant à l'université de Zeitre, située dans la région administrative spéciale du même nom. Vous espérez un jour intégrer la Brigade Informatchique de la région, une équipe d'élite composée de programmeurs chargés d'enquêter et de résoudre les problèmes liés à l'informatique.

Heureusement pour vous, le groupe de travail accepte des stagiaires ce semestre, et vous allez donc effectuer plusieurs missions de formation destinées à vous enseigner les bases du métier.

Il y a une heure, vous avez reçu un appel du directeur de votre équipe, le Directeur Icon, qui vous a donné les détails de votre première mission.

« La ligne de métro automatisée de la région ne fonctionne plus ! Vous devez vous rendre immédiatement à la station centrale, où vous trouverez l'ordinateur central du métro. Je suis sûr que, grâce à vos compétences en OCaml et à votre fidèle manuel, vous rétablirez la circulation du métro en un rien de temps ! »

Vous venez d'arriver à la station de métro et après avoir localisé l'ordinateur central, vous êtes accueilli par le texte suivant qui clignote sur son écran :

"YWFKKNHENSYJWWTRUZEFEWFNXTSEIEZSEGFLFLJETZGQNJECE,JZNQQJBEWJIJRFWWJWEXAXYJRD"

Quel désastre ! En recherchant le modèle du serveur central dans votre manuel, vous découvrez que le tampon de sortie responsable de l'impression des chaînes de caractères est susceptible de subir des décalages aléatoires. Autre détail important : la sortie de la machine est du texte français encodé dans un sous-ensemble de l'ASCII. L'alphabet ne comprend que des lettres majuscules, les caractères virgule, point, et underscore: "ABCDEFGHIJKLMNOPQRSTUVWXYZ,._".

• Exercice 1 : Écrivez une fonction qui prend en entrée une chaîne de caractères et génère tous les décalages possibles, caractère par caractère, d'un nombre fixe dans l'alphabet. Par exemple, le décalage de « ABC » de 1 donne « BCD », tandis que le décalage de 2 donne « CDE ». Utilisez cette fonction pour déchiffrer le texte ci-dessus. Les modules standard List, Char, String, Buffer peuvent être utiles à cet effet.

Après avoir déchiffré avec succès le texte ci-dessus, vous lancez l'impression du diagnostic, pour être accueilli par le message suivant :

"FNCLPTUYKHBJPEETWWUCB,GZKQNJ.ERFVNGSVJTDRWQLTJUXKTPDGSBFVYGSVJ AJPECYVJPYGDGSBFVYGSVJAJPECYVJPYGDVJTRKSGDVWCKKHBNPYGWTTOUWEGSBW CNUTPEFZPEDFIFIJBTWGNNGECENFBXVFVNQSBHCYJJFWCQBXCNPYBXKSGIA"

Vous essayez d'appliquer la routine ci-dessus à ce texte, mais rien ne semble fonctionner ! Vous consultez à nouveau le manuel et vous vous rendez compte que les décalages peuvent varier d'un caractère à l'autre !

Heureusement, le manuel indique que la taille du tampon d'impression du mainframe est de 3, donc les seuls décalages à prendre en compte sont les suivants :

1) Chaque caractère est décalé d'un nombre fixe de places i. Compte tenu de ce qui précède, vous savez déjà que ce n'est pas le cas !

2) Les caractères avec un indice pair sont décalés de i et ceux avec un indice impair sont décalés de j places.

3) Les caractères avec un indice \(0 \mod 3, 1 \mod 3\) et \(2 \mod 3\) sont décalés respectivement de i,j,k.

• Exercice 2 : Écrivez des fonctions qui prennent en entrée une chaîne de caractères et génèrent tous les décalages possibles décrits aux points 2) et 3) ci-dessus.

Cela représente encore beaucoup de texte à parcourir manuellement ! Pour déterminer quels décalages sont susceptibles d'être corrects, vous élaborez la stratégie suivante : étant donné que le texte est en français, la distribution des caractères devrait être approximativement la suivante (du plus fréquent au moins fréquent) : « e, a, i, s, n, r, t, o,... ».

• Exercice 3 : Écrivez une fonction qui prend en entrée une chaîne de caractères et génère une liste de paires, (l,f) où l est une lettre qui apparaît dans la chaîne et f est sa fréquence (nombre d'occurrences). Utilisez cette fonction pour classer les textes déchiffrés possibles et déterminer le message original.

Maintenant que vous avez enfin trouvé la cause de l'interruption, vous informez les techniciens afin qu'ils interviennent. Il ne reste plus qu'une dernière chose à faire : redémarrer le système. Vous essayez la séquence d'échappement qui redémarre le serveur, et juste avant qu'il ne s'éteigne, vous voyez le texte suivant s'afficher à l'écran :

"DTWHVJCFFYGEWWEYCXCCWUGYHTEGC,HBFUTJWGEGC,HBODKESGZUBODKESGZUBIDXJCOTQBJVRWLVEVGSCXFCLJCRJXZEO GEVGSWKWCLJCRJXZEOGEVGSWKWCOTQBJVRWLVEVGSCXFBKQCPACCEDWHXPEGQZWGEOCAGGXVWXCLJCRJXZEOGEVGSWKWCL JCRJXZEOGEVGSWKWCLJCRJXZEOGEVGSWKWCLFLBUHWWBDTQLTXTEPGXVKJXTXCLJCUZLUEXPERTILPFWGZUBMDNEQGZIBHHPYVA"

Vous vous demandez ce que tout cela signifiait...

• Exercice 4 : Déterminez la dernière impression !