Coding Solution

Genome Sequencing – solution CodinGame en Python

Difficileshortest common superstringpermutationsstring overlapbrute forceMis à jour le
Réponse courte

On supprime d'abord chaque fragment qui apparaît déjà à l'intérieur d'un autre, puis on essaie toutes les permutations des chaînes restantes (N ≤ 5, donc au plus 120 ordres) en les fusionnant de gauche à droite, à chaque fois en faisant chevaucher le plus long suffixe du résultat courant avec un préfixe de la chaîne suivante. La réponse est la longueur de la plus courte chaîne fusionnée sur tous les ordres, en O(N!·N·L²), instantané à cette taille.

L'énoncé

On reçoit N fragments d'ADN (N au plus 5, chacun d'au plus 10 lettres parmi A, C, G, T). Il faut trouver la longueur de la plus courte séquence qui contient chaque fragment comme sous-chaîne contiguë.

Seule la longueur est affichée, pas la séquence elle-même. C'est le problème de la plus courte super-chaîne commune, NP-difficile en général, mais la taille minuscule de l'entrée rend une recherche exhaustive sur les ordres parfaitement praticable.

La démarche, étape par étape

  1. Retirer les fragments contenusSi un fragment est une sous-chaîne d'un autre (ou un doublon), il n'apporte rien à la réponse. Le supprimer dès le départ est ce qui rend la recherche par permutations correcte de façon prouvable.
  2. Écrire une fusion à chevauchement maximalmerge(a, b) renvoie a si b est déjà contenu dans a ; sinon elle cherche le plus grand k tel que les k dernières lettres de a égalent les k premières de b, et renvoie a + b[k:]. On essaie k de min(len(a), len(b)) jusqu'à 0 et on s'arrête à la première correspondance.
  3. Essayer tous les ordresPour chaque permutation, on replie les fragments avec merge de gauche à droite et on mesure le résultat. Avec N ≤ 5, cela fait au plus 120 ordres et quelques centaines de comparaisons de chaînes chacun.
  4. Garder la longueur minimaleOn affiche la plus petite longueur trouvée. Il n'est jamais nécessaire de stocker les chaînes elles-mêmes, seulement leurs longueurs.

Complexité

TempsO(N! · N · L²)
MémoireO(N · L)

120 permutations, jusqu'à 4 fusions chacune, et chaque fusion compare au plus L préfixes de longueur ≤ L (les chaînes fusionnées restent sous les 50 caractères). Le tout s'exécute en quelques millisecondes.

Code de la solution

Genome Sequencing – Python

from itertools import permutations

def merge(a, b):
    """Shortest string starting with a that contains b."""
    if b in a:
        return a
    for k in range(min(len(a), len(b)), -1, -1):
        if a.endswith(b[:k]):
            return a + b[k:]

n = int(input())
subs = [input() for _ in range(n)]
# drop duplicates and strings already contained in another one
subs = [s for i, s in enumerate(subs)
        if not any(s in t and (s != t or j < i) for j, t in enumerate(subs) if j != i)]

best = None
for order in permutations(subs):
    res = order[0]
    for s in order[1:]:
        res = merge(res, s)
    if best is None or len(res) < best:
        best = len(res)
print(best)

Erreurs fréquentes

Pour aller plus loin

Pourquoi « retirer les chaînes contenues, puis essayer tous les ordres avec chevauchement maximal » est-il exact ? Prenez n'importe quelle super-chaîne la plus courte et regardez où chaque fragment restant y commence. Comme aucun fragment n'en contient un autre, leurs positions de départ sont toutes différentes et leurs positions de fin sont dans le même ordre, donc les fragments apparaissent dans un ordre de gauche à droite bien défini. Entre deux fragments consécutifs dans cet ordre, la chaîne optimale ne peut faire mieux qu'en les faisant se chevaucher au maximum, donc l'optimum est égal à la fusion à chevauchement maximal de cette permutation particulière. Voilà pourquoi le filtre des fragments contenus n'est pas une optimisation mais une condition de correction : sans lui, deux fragments peuvent commencer au même endroit ou l'un peut finir avant le précédent, et l'argument s'effondre, tout comme les solutions naïves.

Questions fréquentes

La force brute est-elle vraiment acceptable pour Genome Sequencing ?

Oui. N vaut au plus 5, donc 120 permutations de chaînes de moins de 10 caractères sont triviales. Les méthodes plus fines (DP sur masques de bits de sous-ensembles) n'ont d'intérêt qu'à partir de N ≈ 15.

Faut-il afficher la séquence elle-même ?

Non, seulement sa longueur. Conserver la chaîne fusionnée n'est que la façon la plus simple de la mesurer.

Et si deux fragments sont identiques ?

On les traite comme un seul. Le filtre des fragments contenus doit garder exactement une copie, sinon les deux sont supprimés comme sous-chaînes l'un de l'autre.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome