Continuing the discussion from The Resistance puzzle discussion:
Finished!
4 Tests Cases is not enough… The 4° is too difficult after passing test 1,2,3.
Here is some useful test Cases (with good number of . Thanks @AY1111 and @ bougadabou)
.........
2
E
EEE
solution 19
-…–.-.-…–.-.
3
BAC
BANN
DUC
solution 9
....----
4
E
EE
T
TT
solution 25
Nice puzzle, but indeed easier than other Very Hard puzzles. I agree that having more testcases would have been nice, especially one small case to show that two words can have the same representation. I would have been stuck for a long time if I hadn’t read a message in the discussion mentioning that fact! But since this puzzle is old now, I guess it won’t be modified ^^
Wow thank you for this puzzle ! I learn a new algorithm, almost a new way of thinking now 
I started with classic hash tables with morse words as keys and using recursion but my code was way too slow…
Then I learned about Trie and finally managed to implement it. It’s amazing !
It took me too much time, to realize that in python:
string[position:].startswith(short_string)
takes 10x more time then:
string.startswith(short_string, position)
Probably, you are smarter then I am, right? 
The first one creates a new string, that’s why.
In general, slicing must be avoided when dealing with big strings or if your slicing is nested in your main iteration in a script where performance matters.
For example checking for palindrome with s==s[::-1] is ok for Code Golf with small strings but it’s a terrible idea in an optimisation problem.
Quick question, I’m getting a timeout, which I was kind of expecting, but when I tried to fprintf(stderr) the input to try to see how slow it is (in my PC) the output is cropped, and I tried adding sleeps, dividing in smaller lines and stuff like that but with no luck, anyone knows how to check the actual inputs or if there is any way to disable it being cropped?
EDIT: never mind, didn’t know the input was in the IDE itself! Found it!!
If you timeout here it’s probably that you recalculate several times the same thing.
The key is to store somehow the results that you might need again later.
Hi Pardouin, yeah, I didn’t even start to optimize it, but with just “timeout” I didn’t know where to begin thinking about it.
After looking more I found in the “Test Cases” pane that it was a three-line-button with details about the inputs/expected results, I copied them from there and ran it locally.
With more visibility I ended up optimizing it to something around 10 ms on my machine, and finished the puzzle at 100%.
Thanks for answering though!
Hello,
It’s my first attempt on a very hard problem, and I have a few remarks like many already mentioned. This problem is supposedly hard but it’s just a case of fake difficulty (https://tvtropes.org/pmwiki/pmwiki.php/Main/FakeDifficulty).
Fake difficulty because of the lack of test cases and the slightly misleading phrasing. I am only at 40% and I still have no idea why I can succeed advanced validators but fail “Simple Test”… feels really bad.
Also feels really bad that the additional test cases wrote here get messed up by the website (triple dots “…” and double dashes “–”). Some editing or even putting a clean first post will help. But the fix is to give intermediate test cases. The rules are just not clear enough.
Anyway, and now my own tip. I am only at 40%, and I was probably going to look for something more interesting to try. But I told myself that I should try optimizing a little bit to see if anything happens.
Then I saw the final message come up by logging the path so far taken by the search. That helped me understand what the problem is really about. It has nothing to do with morse code decoding.
In fact, the real problem is to determine how many small boxes (words of the dictionary) you can put in a larger box (the whole message), and how many combinations there are. See, how I stated the problem in a single phrase ?
That’s why I feel like I had to write about it. The problem is interesting but the design doesn’t feel right. In case what I wrote is confusing to you, let’s just say I started coding letter by letter and branching as necessary, thinking it was a morse problem. But actually it is not.
Edit: I almost forgot. I am very familiar with alpha-beta pruning with memoization because I write chess engines. In this problem I tried very simple idea. From the dictionary, list all letter pairs that can occur. Any time, you see a letter pair in the message that can not occur, you get a cutoff. Sad truth is you get many cutoff on the HELLOWORLD test case, which looks promising. But you get zero cutoff on the hardest case before timing out, which is just unbelievable!!! The whole problem just feels wrongly designed to me.
use longs instead of ints.
Solved it with basic dynamic programming optimized with memoization and a bit of precomputing.
It would be good to have more test cases before the last one as it’s far too big to debug.
I used tries, as others did.
Some have mentioned that memoization was not necessary; but the way I did it, after the trie was built (based on all the words in the dictionary), I stepped through the message exactly once. For each bit in the message, I checked whether the current node in the trie had a branch for that bit. If it did, and if the next node had leaves in the trie, I multiplied the number of leaves by the previous leaves and spawned a new “thread” starting from the base of the trie on the next bit. Well, actually, for each bit, I totalled the number of leaves occurring from all the relevant nodes, and created one new search thread with that number. And if the node represented in that thread had a NULL pointer for that branch, I took the thread out of the list.
When I reached the last bit, instead of starting a new thread with that total number of leaves, I simply printed it.
I didn’t run out of time trying to spawn new threads each time I found trie leaves, but I ran out of space, no matter how I did it. So, keeping track of all the leaves at a certain node of the trie AND summing them all up for each bit before spawning a new thread were forms of memoization - I kept track of how many words ended on that bit, rather than checking each one.
I used C! I had two structs, one for the nodes of the trie and one for the search threads.
I used linked lists for both, to make it easy to insert and delete. There was no disadvantage to using a linked list for the search threads because I had to step through each one anyway for each bit in the message.
That was fun!
thanks for the clue. I had the same issue, all tests passed except that one. I just updated my code to use long to store the number of solutions instead of int.
I’m yet another person here suggesting yes, this really does need more test cases. The description gives a simple example where the code is interpreted as several different words of the same length, but the test cases don’t check that until the final super massively huge test, which leaves us scratching our heads as to what went wrong. Just add a test case based on the same example in the description.
Finally got it. Thanks for the tip, @ze1! Very challenging.
Many coders have asked for more test cases here, but I think what would be more helpful is test cases that correspond to every validator. There are 10 validators, but only 4 test cases. It looks, too, like several of the validators present exactly the kind of test case input that people are asking for, e.g., small sequence, small dictionary, multiple dictionary words represented by the same Morse sequence.
I haven’t solved the puzzle. Would some of you suggest a few test cases that I can add to the IDE?
Thanks for this 
. It’s nice to read something more close to home once in a while instead of the constant stream of “Oh it’s easy and I did it in a nanosecond”-posts.
Based on the two most common mistakes people make, two relatively simple example can help. First of all, as the constraints suggest, the result is less than 2^63 so it should be stored in a long type. (With that said after reading the constraint I immediately declared int result = 0). Now the problem is that the last case overflows int but completely un-debuggable. A more simple one which trivial to solve by hand and overflows can make that easier.
Decoding like Fibonacci
Input:
------------------------------------------------
2
T
M
Output: 7778742049
Note: log2(7778742049) ~ 32.85
In case formatting breaks, that’s 50 of -. It is super easy to see that with one symbol only and the Morse code of length 1 and 2 of that symbol as words, the result is a Fibonnaci number. You can also give that clue in the test name. This way one can simply look up the Fibonnacci sequence’s ~50th member and see that it’s not the same and hopefully realise the overflow problem.
The other problem is that people forget about that multiple keywords can have the same code. I made that too but it’s easy to debug if you add the example from the description as a test case. Even better if you double the
Input:
-....--.-.-....--.-.
3
BAC
BANN
DUTETE
Output: 9
Here the trick is that all 3 keywords translate to -....--.-. which is double in the input, hence the result is 9.
If you are happy with the suggestions, it should be easy to modify them a bit to be different (the second can use common English words for example) or I can edit this and remove the answer.
Also, this might be an excellent chance to add — if exists — a double meaning sentence as an easter egg. In my native language in the middle ages there was a letter sent without punctation that roughly said:
“The queen kill not be afraid”. This can be understood as “The queen not be killed, be afraid” and “Kill the queen, do not be afraid”. Unfortunately it doesn’t work in English but maybe something similar exists and it would make a fun reference.
I just finished this puzzle and it seems like I took a substantially different approach than anyone else I see commenting.
I’m wondering if somebody than understands this puzzle better than me could comment on the computational complexity of my approach compared to what others’ have done? Is mine better? Is mine worse? Am I just doing the same thing as others with more steps?
I computed a finite state machine for parsing the morse code as a function of the word dictionary, then ran the morse string through my state machine. (Similar to regex compilation)
I forked the state whenever multiple moves were possible along the machine (i.e. a word ended, but more characters might still complete a longer word). I also forked the state whenever a state resulted in multiple local interpretations (ex: “ET” or “A”). I merged the state whenever multiple forks collided on the same state (different strings terminated at the same character). I kept track of how many machines had been merged together as I went.
At the end of the string, all valid interpretations would collide on the starting state of the machine, and I could count how many machines had been merged together on that state, which gave the number of valid interpretations.
If you merge the forks that collide into the same state, I’d say it’s equivalent to memoization (what most people used for this problem).
The purpose is the same : don’t launch the same exploration twice.