The Resistance – CodinGame solution in Python
Convert every dictionary word to its Morse code and insert those Morse strings into a trie over '.' and '-', storing how many words end at each node. Then compute ways[i], the number of ways to split the message suffix starting at i into words, from the end of the message backwards: walk the trie from position i and, at each node where words end, add count × ways[j]. The answer is ways[0].
The problem
You receive one long Morse sequence of dots and dashes with all spaces removed, so letter and word boundaries are lost. You also get a dictionary of N words. Count how many different sequences of dictionary words, once encoded in Morse and concatenated, produce exactly the given sequence.
The message can be up to about 100,000 symbols, the dictionary up to roughly 100,000 words of at most 20 letters, and the answer can be very large (it fits in a signed 64-bit integer). Enumerating the decodings one by one is hopeless; you must count them.
Approach, step by step
- Encode words, not the messageDecoding the message letter by letter is ambiguous at every step. Instead, translate each dictionary word into Morse once; words become strings of at most 80 symbols that can be matched directly against the message.
- Build a Morse trieInsert each encoded word into a binary trie (one child for '.', one for '-'). At the final node, increment a counter rather than set a flag: two different words can share the same Morse code, and both decodings must be counted.
- Define the DPLet ways[i] be the number of ways to cover message[i:] with words, with ways[len] = 1 for the empty suffix. Fill the array from right to left so that every value you read is already known.
- Walk the trie from each positionFor position i, follow the trie with message[i], message[i+1], and so on, stopping as soon as a child is missing. Every time you land on a node where k words end after consuming j - i symbols, add k × ways[j] to ways[i].
- Output ways[0]The walk from each position is bounded by the trie depth (at most 80), so the whole DP runs in O(len × 80) steps.
Complexity
O(L · W)O(L + total Morse length)L is the message length and W ≤ 80 the longest encoded word; the trie walk from each position usually stops far earlier. The trie holds one node per distinct Morse prefix of the dictionary.
Solution code
Bug fixed in this version: The Python block is broken. The bodies of Node.__init__ and Node.memoize are not indented (IndentationError on load). In Patricia.add, the lines that move to the child and set word = True sit inside the 'if c not in it.sons' branch, so the walk does not advance through existing letters and every newly created node is marked as a word end. Even fixed, the recursion can go about as deep as the message length (around 100,000), well above the recursion limit of 10,000 it sets. A correct iterative Python 3 replacement is provided.
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])
Common mistakes
- Decoding letters firstSplitting the message into letters and then grouping letters into words is correct in principle but explodes combinatorially. Matching whole encoded words removes the intermediate letter layer entirely.
- Ignoring words with identical Morse codesDifferent words can encode to the same Morse string (for example EE and I both give '..'). Storing a boolean end flag counts them once; you need a counter per trie node.
- Deep recursionA top-down memoised recursion can nest once per word boundary, which on a 100,000-symbol message breaks Python's default limit and may crash even after raising it. A bottom-up loop has no such problem.
- Slicing the message for every candidate lengthTesting message[i:i+k] in a dictionary of Morse strings for every k up to 80 copies up to 80 characters each time. The trie walk reads each symbol once and stops early when no word continues.
- 32-bit overflowIn C, C++ or Java the count needs a 64-bit integer (long long / long). With int, the large tests wrap around.
Going further
The key reframing is that letters do not matter at all once the dictionary is encoded: the problem becomes 'count the ways to tile a binary string with a given multiset of binary words', a textbook word-break DP. That also gives you a quick way to test your code: with a one-word dictionary 'E' and a message of n dots, the answer must be 1; with dictionary {E, I} and n dots, the answer follows the Fibonacci sequence (1, 2, 3, 5, 8...), because each position ends either a one-dot or a two-dot word. If your implementation does not reproduce Fibonacci on that toy case, the DP transition or the end counters are wrong.
FAQ
Why is The Resistance rated very hard?
Because the naive decoding has an exponential number of branches and the sizes are large. The difficulty is in finding the right state (position in the message) and an efficient way to match words, not in the code itself.
Can I use a hash map of Morse words instead of a trie?
Yes: group Morse strings by length and test each possible length at each position. It is correct, but slower in Python because of string slicing; the trie version is safer on the largest tests.
Does the answer fit in a 64-bit integer?
The puzzle guarantees it does. Python integers are unbounded anyway; in C, C++ or Java use long long or long for the DP array.