Coding Solution

The Resistance – solution CodinGame en Python

Très difficiledynamic programmingtrieMorse codestring parsingMis à jour le
Réponse courte

On convertit chaque mot du dictionnaire en morse et on insère ces chaînes dans un trie sur '.' et '-', en stockant combien de mots se terminent à chaque nœud. On calcule ensuite ways[i], le nombre de façons de découper le suffixe du message à partir de i en mots, en partant de la fin : depuis la position i on descend dans le trie et, à chaque nœud où des mots se terminent, on ajoute compte × ways[j]. La réponse est ways[0], obtenue en O(L · W) avec W ≤ 80.

L'énoncé

On reçoit une longue séquence morse de points et de tirets dont tous les espaces ont été retirés, si bien que les frontières de lettres et de mots sont perdues. On reçoit aussi un dictionnaire de N mots. Il faut compter combien de suites différentes de mots du dictionnaire, une fois encodées en morse et concaténées, produisent exactement la séquence donnée.

Le message peut atteindre environ 100 000 symboles, le dictionnaire environ 100 000 mots de 20 lettres au plus, et la réponse peut être très grande (elle tient dans un entier signé 64 bits). Énumérer les décodages un par un est sans espoir : il faut les compter.

La démarche, étape par étape

  1. Encoder les mots, pas le messageDécoder le message lettre par lettre est ambigu à chaque pas. On traduit plutôt chaque mot du dictionnaire en morse une seule fois ; les mots deviennent des chaînes de 80 symboles au plus que l'on peut faire correspondre directement au message.
  2. Construire un trie morseOn insère chaque mot encodé dans un trie binaire (un enfant pour '.', un pour '-'). Au nœud final, on incrémente un compteur plutôt que de poser un drapeau : deux mots différents peuvent avoir le même code morse, et les deux décodages doivent être comptés.
  3. Définir la PDSoit ways[i] le nombre de façons de couvrir message[i:] avec des mots, avec ways[len] = 1 pour le suffixe vide. On remplit le tableau de droite à gauche pour que chaque valeur lue soit déjà connue.
  4. Descendre dans le trie depuis chaque positionPour la position i, on suit le trie avec message[i], message[i+1], etc., en s'arrêtant dès qu'un enfant manque. Chaque fois qu'on atteint un nœud où k mots se terminent après avoir consommé j - i symboles, on ajoute k × ways[j] à ways[i].
  5. Afficher ways[0]La descente depuis chaque position est bornée par la profondeur du trie (80 au plus), donc toute la PD tourne en O(len × 80) étapes.

Complexité

TempsO(L · W)
MémoireO(L + total Morse length)

L est la longueur du message et W ≤ 80 le plus long mot encodé ; la descente dans le trie depuis chaque position s'arrête en général bien plus tôt. Le trie contient un nœud par préfixe morse distinct du dictionnaire.

Code de la solution

The Resistance – Python

MORSE = {
    'A': '.-', 'B': '-...', 'C': '-.-.', 'D': '-..', 'E': '.', 'F': '..-.',
    'G': '--.', 'H': '....', 'I': '..', 'J': '.---', 'K': '-.-', 'L': '.-..',
    'M': '--', 'N': '-.', 'O': '---', 'P': '.--.', 'Q': '--.-', 'R': '.-.',
    'S': '...', 'T': '-', 'U': '..-', 'V': '...-', 'W': '.--', 'X': '-..-',
    'Y': '-.--', 'Z': '--..'
}

message = input().strip()
n = int(input())

# Morse trie stored in flat lists: child_dot[node], child_dash[node], ends[node]
child_dot = [-1]
child_dash = [-1]
ends = [0]

for _ in range(n):
    code = ''.join(MORSE[c] for c in input().strip())
    node = 0
    for s in code:
        children = child_dot if s == '.' else child_dash
        if children[node] == -1:
            children[node] = len(ends)
            child_dot.append(-1)
            child_dash.append(-1)
            ends.append(0)
        node = children[node]
    ends[node] += 1  # several words may share the same Morse code

L = len(message)
ways = [0] * (L + 1)
ways[L] = 1

for i in range(L - 1, -1, -1):
    node = 0
    j = i
    total = 0
    while j < L:
        node = child_dot[node] if message[j] == '.' else child_dash[node]
        if node == -1:
            break
        j += 1
        if ends[node]:
            total += ends[node] * ways[j]
    ways[i] = total

print(ways[0])

Erreurs fréquentes

Pour aller plus loin

La reformulation clé est que les lettres ne comptent plus du tout une fois le dictionnaire encodé : le problème devient « compter les façons de paver une chaîne binaire avec un multi-ensemble donné de mots binaires », une PD de découpage en mots tout à fait classique. Cela donne aussi un moyen rapide de tester son code : avec un dictionnaire d'un seul mot « E » et un message de n points, la réponse doit être 1 ; avec le dictionnaire {E, I} et n points, la réponse suit la suite de Fibonacci (1, 2, 3, 5, 8...), car chaque position termine soit un mot d'un point, soit un mot de deux points. Si votre implémentation ne reproduit pas Fibonacci sur ce cas jouet, la transition de la PD ou les compteurs de fin sont faux.

Questions fréquentes

Pourquoi The Resistance est-il classé très difficile ?

Parce que le décodage naïf a un nombre exponentiel de branches et que les tailles sont grandes. La difficulté est de trouver le bon état (la position dans le message) et une façon efficace de faire correspondre les mots, pas dans le code lui-même.

Peut-on utiliser une table de hachage de mots morse au lieu d'un trie ?

Oui : on groupe les chaînes morse par longueur et on teste chaque longueur possible à chaque position. C'est correct, mais plus lent en Python à cause des tranches de chaînes ; la version avec trie est plus sûre sur les plus gros tests.

La réponse tient-elle dans un entier 64 bits ?

Le puzzle le garantit. Les entiers Python sont de toute façon non bornés ; en C, C++ ou Java, utilisez long long ou long pour le tableau de la PD.

Puzzles similaires

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