c0d1ngup 2024 : Défis les plus résolus

Voici les deux défis les plus résolus lors de c0d1ngUP 2024 : Analyse de séquences 1/2 et Méli mélo d’adresses.

Analyse de séquences 1/2

Il est courant pour Mulder et Scully (surtout pour Scully) de devoir classer d’anciens dossiers, et ces dossiers contiennent souvent des relevés de séquences d’acides nucléiques afin de détecter d’éventuelles mutations ou la présence de gènes extraterrestres.

Les relevés auxquels Scully s’intéresse proviennent d’ARN, décrit par une séquence des 4 bases nucléiques : A, C, G ou U (Adénine, Cytosine, Guanine, Uracile). Les séquences d’acides nucléiques sont parfois décrites à l’aide d’autres symboles, comme R (signifie A ou G), Y (signifie C ou U), B (signifie C, G ou U).

Voici la liste complète des symboles :

La séquence ACDMR signifie donc :

• Le premier acide nucléique est forcément A
• Le second acide nucléique est forcément C
• Le troisième acide nucléique est A, G ou U
• Le quatrième acide nucléique est A ou C
• Le cinquième est A ou G

Il y a donc 12 séquences possibles qui correspondent à la description ACDMR : ACAAA, ACAAG, ACACA, ACACG, ACGAA, ACGAG, ACGCA, ACGCG, ACUAA, ACUAG, ACUCA, ACUCG

Étant donnée une séquence décrivant une séquence ARN avec certaines des 15 lettres du tableau précédent, Scully souhaite classer les dossiers en fonction du nombre de séquences ARN qui correspondent à cette description, ce qui lui permettra de répertorier d’une nouvelle manière les différents relevés trouvés dans les affaires non classées.

Cependant, la plupart des séquences sont assez longues, et le nombre correspondant est souvent très grand. Scully décide donc de ne conserver que les 5 derniers chiffres pour le classement.

La séquence BBBBDDDDHHHH correspond à 531441 séquences différentes. Elle sera donc classée à 31441.

Aidez Scully en lui développant un système qui fait le travail demandé. Par exemple, pour la séquence BBBBDDDDHHHH, le système doit répondre : 31441.

Validez le défi en donnant la réponse de votre système à la séquence donnée en entrée du problème (rappel : on n’utilise que les 5 derniers chiffres pour le classement des dossiers).

La séquence d’entrée à traiter est :

GCRNKMDUHBVGNSMRNCWNKDMANNVVYVCYKCGKHSAAUNGUNNAMGRUUCNAGKWSKSKGHKRAGDNABCVUGCMARBKACNKNNDSURCYVDBNSA 

Méli mélo d’adresses

Mulder et Scully partent enquêter en France après avoir été mis sur la piste d’un camion qui transporte une marchandise… inhabituelle.

La marchandise doit être transférée dans un autre moyen de transport quelque part, mais ils ignorent où pour le moment.

Une première enquête leur a permis de sélectionner plus de 200 adresses potentielles pour le transfert. Le fichier des adresses est téléchargeable ici.

Pour communiquer, l’organisme qui semble être à l’origine de l’opération utilise une méthode inhabituelle et ancienne, inspirée de lettres écrites par Newton lui-même. Il ne s’agit pas d’une méthode de chiffrement, mais plutôt d’une sorte de calcul d’empreinte, réalisable manuellement.

Ce calcul, qu’on applique à une chaîne de caractères consiste à regarder le nombre d’apparitions de chaque lettre et de donner, dans l’ordre alphabétique, chaque lettre qui apparaît, précédée du nombre d’occurrences.

Par exemple, pour calculer l’empreinte de bonjour :

• on compte chaque lettre : 1 b, 2 o, 1 n, 1 j, 1 u et 1 r
• puis on donne la liste des lettre qui apparaissent, dans l’ordre alphabétique, chaque lettre étant précédée par le nombre d’apparitions : 1b1j1n2o1r1u

Autre exemple, la verite est ailleurs donnera : 2a4e2i3l2r2s2t1u1v

Les caractères autres que les lettres sont simplement ignorés.

Du lieu où sera effectué le transfert de la marchandise, Mulder ne connaît que l’empreinte, donnée en entrée du problème.

Retrouvez l’adresse recherchée et fournissez la pour valider le défi.

L’entrée du problème à traiter est :

 1a1c1d4e1i1m1n2r3s1t1u 

Alors ? Vous en pensez quoi ?

Seriez-vous parvenu.e à résoudre ces deux problèmes ?