The Resistance – solution CodinGame en Python
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
- 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.
- 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.
- 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.
- 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].
- 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é
O(L · W)O(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
- Décoder d'abord les lettresDécouper le message en lettres puis regrouper les lettres en mots est correct en principe mais explose combinatoirement. Faire correspondre des mots entiers encodés supprime complètement la couche intermédiaire des lettres.
- Ignorer les mots au code morse identiqueDes mots différents peuvent donner la même chaîne morse (par exemple EE et I donnent tous deux '..'). Un drapeau booléen de fin les compte une seule fois ; il faut un compteur par nœud du trie.
- Récursion profondeUne récursion mémoïsée descendante peut s'imbriquer une fois par frontière de mot, ce qui sur un message de 100 000 symboles dépasse la limite par défaut de Python et peut planter même après l'avoir relevée. Une boucle ascendante n'a pas ce problème.
- Trancher le message pour chaque longueur candidateTester message[i:i+k] dans un dictionnaire de chaînes morse pour chaque k jusqu'à 80 copie jusqu'à 80 caractères à chaque fois. La descente dans le trie lit chaque symbole une fois et s'arrête tôt quand aucun mot ne continue.
- Débordement 32 bitsEn C, C++ ou Java, le compte exige un entier 64 bits (long long / long). Avec int, les gros tests bouclent sur eux-mêmes.
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.