Message de l'espace

Mulder a eu accès a des enregistrements de radiotélescope, visant à découvrir une intelligence extraterrestre.

Le flux de données enregistré est composé de plusieurs séquences de 15 caractères :

MYNBIQPMZJPLSGQ
EJEYDTZIRWZTEJD
XCVKPRDLNKTUGRP
OQIBZRACXMWZVUZ
TPKHXKWCGSHHZEZ
ROCCKQPDJRJWDRK
RGZTRSJOCTZMKSH
JFGFBTVIPCCVYEE
...

Pour chaque séquence, on s'intéresse à la propriété suivante :

La séquence ne contient aucun bloc de 4 lettres successives contenant une lettre en double.

Pour des séquences de 15 caractères (pris parmi les 26 lettres de l'alphabet), cette propriété est vraie environ 20.4 % du temps.

Si une séquence a cette propriété, on la qualifie de séquence rare. Dans l'exemple qui précède, les séquences rares sont les séquences 1, 3, et 7. La séquence 2, par exemple, n'est pas une séquence rare, car elle contient le bloc de 4 lettres EJEY qui a une lettre en double. De même la séquence 5 contient le bloc de 4 lettres KHXK qui contient 2 fois la lettre K...

Le flux de données provenant de l'espace est enregistré régulièrement. On dispose donc d'un grand nombre de séquences de 15 caractères.

On cherche à détecter quelque chose d'anormal dans les séquences. Plus précisément, un (petit ?) calcul de probabilités indique que pour un enregistrement de 1000 séquences, on peut s'attendre en moyenne à observer environ 204 séquences rares. Parfois ce sera moins, et parfois ce sera plus. Si on s'écarte trop de la valeur 204, on estime que l'enregistrement de 1000 séquences n'est pas un bloc naturel et qu'il contient les signes d'une intervention intelligente extra-terrestre. Plus précisément, si dans l'enregistrement de 1000 séquences, il y a strictement moins de 172 séquences rares ou strictement plus de 235 séquences rares, alors l'enregistrement est suspect.

Vous disposez d'une archive (zip) contenant 500 enregistrements de 1000 séquences. Les fichiers de l'archive ont pour noms : enregXXX.txt avec XXX qui vaut un numéro entre 1 et 500.

Repérez les enregistrements suspects (au sens précédemment défini) et validez le défi en donnant leurs numéros, par ordre croissant. Par exemple, si vous estimez que les enregistrements suspects sont les fichiers enreg023.txt, enreg224.txt et enreg123.txt, vous pourrez valider le défi en indiquant 23, 123, 224.