Coding Solution

The Resistance – CodinGame solution in Python

Very harddynamic programmingtrieMorse codestring parsingUpdated
Short answer

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

  1. 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.
  2. 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.
  3. 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.
  4. 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].
  5. 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

TimeO(L · W)
SpaceO(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

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.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome