Au cours de ses nombreux et longs voyages, le Docteur a rencontré de multiples êtres vivants. Afin d'être toujours prêt, face à un environnement inconnu, il a commencé à programmer le Tardis pour qu'il analyse les séquences ADN environnantes. Pour le moment, il a à disposition une matrice, contenant les noms des bases, comme celle-ci :
Mais la suite l'ennuie, et il vous confie la tâche de terminer le travail.
Il faut maintenant extraire des séquences en se déplaçant dans la matrice (sans passer deux fois par la même base). Les séquences intéressantes sont les plus longues possibles, sachant que chaque base ne peut avoir que deux voisins particuliers dans une séquence :
Apeut être voisin avecTouCTpeut être voisin avecAouGGpeut être voisin avecTouCCpeut être voisin avecAouG
Deux séquences qui passent exactement par les mêmes cases de la grille sont considérées comme identiques, quel que soit l'ordre de parcours des bases dans la séquence.
Dans la matrice précédente, il n'y a pas de séquence plus longue que 11. Par ailleurs, il y a 5 séquences différentes (i.e. des séquences utilisant des cases différentes) ayant cette longueur (le flêchage en rouge est un exemple de chemin parcourant les cases de chaque séquence) :
Pour chacune de ces séquences, on peut attribuer un score : la somme des produits de l'abscisse par l'ordonnée de chaque élément de la matrice utilisée dans la séquence (le coin haut/gauche a pour coordonnées 1, 1).
Par exemple, pour cette séquence :
Le score est : 5x1 + 4x1 + 3x1 + 3x2 + 4x2 + 4x3 + 3x3 + 3x4 + 4x4 + 5x4 + 5x3 = 110
Pour les 5 séquences les plus longues qui précèdent, les 5 scores, du plus petit au plus grand sont :
110, 120, 127, 130, 132
L'objectif est d'analyser la matrice ADN proposée en entrée du problème, de découvrir les séquences ADN les plus longues, de calculer leurs scores et de donner ces scores classés par ordre croissant.
Dans le cas de l'exemple, on validerait le défi en entrant :
110, 120, 127, 130, 132
