Pretty fun to solve, but the only reason this is a “Very Hard” problem is that the test cases suck 
Based on other replies, it looks like it’s easy to come up with a solution that works for most of the tests, but fails on the last one that’s WAY too big to work through manually to figure out what’s wrong. I’d recommend inserting another test case there to highlight what seems to be a very common error.
Continuing the discussion from The Resistance puzzle discussion:
Hi.
It was fun and instructive, I learnt the concept of memoizaiton (although I had used it before without knowing the name).
Just tere was something a little frustrating with the test cases.
My code had a mistake, when it found a matching word, it didn’t continue trying other words in the same level.
The frustrating thing is that this code passed all the testing tests, but it failed some of the validations tests. Therefore, it was hard to find the mistake, but I could do with the validation tests title.
This was the wrong code:
if (message.startsWith(w, start)) {
if (w.length == message.length - start) return 1; // WE SHOULD TRY THE REST OF WORDS!!!
levelCombinations += tryWords(message, words, combinations.concat([i]), start + w.length);
}
And this is the correct one:
if (message.startsWith(w, start)) {
if (w.length == message.length - start) levelCombinations++;
else levelCombinations += tryWords(message, words, combinations.concat([i]), start + w.length);
}
So, I think it will fail when there are several words that can match with the end of the string.
I think that if you have the time such test could be included.
Many thanks.
Hello
My solution gets 140737488355328 with @SinOfWrath 's example.
What I do at the beginning is store in the dictionary only the morse code of each word in the input, so when we reach to a root case where L[p:] == word-code, the number of possible solutions increases by R(word-code), being R(word-code) the number of times a word with the same morse code as word-code was declared while reading the dictionary input.
Hello everyone,
Looking into adding new IDE test cases for the puzzle, I think @SinOfWrath 's suggestions are great, I’m trying to see if it’s possible to improve them slightly.
The tests are as follow:
Big result (integer overflow gotcha):
Input:
..............................................
2
E
I
Expected output:
2971215073
This is basically the same as the original, but with dots and only 47 of them. I reduced the number of dots it to 47 so that the result is the 47th Fibonacci number, which is the first greater than the maximum positive value of a 32-bit signed integer (usual default when declaring variables as ‘int’). The hope is that this can ensure that the result, in the case where the count uses 32 bit signed integers, overflows once at the end and becomes negative, which I hope will be enough to point out the issue in the code.
The fact that it uses dots with I and E changes nothing in the end.
Ambiguous words (“words with the same morse code representation” gotcha)
Input:
-.-..---.-..---.-..--
5
CAT
KIM
TEXT
TREM
CEM
Expected output:
125
Same idea as for the second proposition, here, all words in the list are encoded as -.-..--, which is repeated 3 times in the input morse code. I am not sure about keeping the CEM and TREM words, as having the 3 others would already be enough. If these words are removed, the answer would become 27.
I am looking for feedback on these, so please tell me what you think about these test cases, whether you like them or not, and if not, why.
1 Like
Regarding the ambiguous words test case. If you reduce the number of words to only 3, the result is 3^3 and based on my experience people get easily mistaken whether that’s lengthoptions or optionslength. Most people also tend to make a quick judgement call and code it immediately. Now that can cause some extra debugging for sure. I do realise that if you do it dynamically it should not be a problem though.
Also @Thetos, do you actually know someone who can add these test cases?
@SinOfWrath I’m not sure I understand what you are trying to say regarding the number of options, is it that you think keeping 5 options is better if there is 3 repeats ? or more generally, just not doing number of repeats == number of options ?
And yes, I do know people who can add these, such as myself :).
After all, I am currently an intern at CG. (Maybe I should have said that in the original post).
1 Like
@Thetos, first of all congrats on the intern job!
Second, I saw this is your first post and I thought you assumed we can edit this puzzle like we can with community contributions (after a certain level), hence my confusion. But you are an insider now. 
And I do think number of repeats == number of options is making it harder, so 5 options, 3 repeats is better. The solution is both small and simple either way.
Lastly, and this is just me who has bad eyesight, I can count .s much harder than I can count -s, that’s why I suggested dashes but that it is really not a big deal. Have some fun naming the test cases.
I personally think that counting . is easier than counting -. maybe a good compromise would be to use C (-.-.) and N (-.) instead?
Now I’ll go have fun naming the test cases.
Oh and thanks for the congratulations, though I’m nearing the end of my internship (been here since september) 
The new tests “Many possibilities” and “Same encoding for different words” have been added.
Have fun solving the puzzle, it should be easier to debug now 
1 Like
Hi! The last test is not passing for me, too slow as well. For now I’m making a BFS of all indices that I’m reaching, and when the indice == string length, then I increment my “win counter” …
I’m memoizing the children for a sub sequence.
But it takes 8 minutes for the sixth test, compare to almost only 5ms for the rest.
So I checked the forum, and everybody is talking about trie algorithm. I’ve never used it, and I can’t understand how I could use it to solve this problem.
Can someone give me a hint to help me think about a solution using trie?
Thanks!
A trie is a type of data structure. You may read more about it here: https://en.wikipedia.org/wiki/Trie
It is more efficient than some other data structures or search algorithms.
You may also search further to understand it more.
1 Like
Yep sorry, I meant trie data structure, not trie algorithm.
I’ll play with it and figure out a way to use it to solve this puzzle.
Thanks for your reply.
1 Like
it’s quite frustrating, I’m stuck at 70% in PHP without the possibility of passing long sequences…
I rewrote my code 4 times but nothing works…
I don’t see how to do better.
Seeing that there are dozens of published solutions in PHP, I think it is doable. Maybe some of the discussion above will inspire you? Or maybe take a break and come back to the puzzle later with a fresh mind.
Continuing the discussion from The Resistance puzzle discussion:
Could someone explain why is this marked as “very hard”?
I’m used to other “very hard” problems being highly abstract and taking me several hours and some amount of confusion to properly solved, this took no longer than a clash of code. Is memoization actually that little-known of a strategy? Or is there some other reason? Even that alone seems like it shouldn’t put it above hard if it is classified as an obscure strategy.
Hello,
I’m just wondering why in the third test (Simple message) i’m right when the output is 2 (solution : “HELL” and “HELLO”) and i’m wrong with the second test (Correction detection of a word) when the output is 2 (solution : “G” and “GOOD”) knowing that the expected output is 1 in this second test
Test case 2
GOOD = --.-------… (which is the input sequence to decode)
G = --. (which is not the input sequence to decode)
Test case 3: the expected output is 2 because the decoded phrases may be “HELLO WORLD” and “HELL OWORLD”, not “HELL” and “HELLO”.
Hello, I was stuck at 70% too in PHP yesterday, using a simple queue, but today I made a recursive function with memoization, and all the IDE tests are now below 0.4ms, except one who take an average 38ms. Got 100% in submission. My dictionnary is build with morse pattern of the word as key, and number of words for this pattern as value, if it can help. That fit in about 25 lines of (dirty) code.
Computation time limit is not part of the constraints. But it makes tests fail.
Do you mean bit as the “.” and “-”?