Indeed it seems possible, and the exponential count of re-arrangements is where this puzzle earns its seat in the Very Hard ranks. Care needs to be taken in order to avoid recalculating expensive operations.
~34 ms in Python3 for the last test case. struggled a lot until i discovered identical sequences could be different words… simple recursion with memoization.
Well, it took me three months and fifteen submits. It got to around 120ms for the last test case in C++ (my solution turned out to be somehow similar to Agade’s).
Throughout the three months, I’ve read through this entire thread multiple times. There were, of course, some discouraging posts up there amidst the ones that were actually helpful.
This puzzle wasn’t entirely easy for me but I’m happy that it wasn’t easy - the process to get to the end was exhilarating.
If you’re stuck, persist; and if you haven’t started the puzzle already, do start and try it out. 
8 Likes
There’s a few posts in this thread with hints. The big one that got me to 100% was saving the outcome at each stop, so if I found myself in the same position again I wouldn’t have to re-parse the path. I left a post in April '16 explaining it.
Does the rust compiler is enable with optimisation ? Because I get a 2200ms for the “Séquence longue, grand dictionnaire” with debug mode on my laptop and I get a 53ms with release mode (enable optimisation when compiling). I also use the same code ported in Kotlin and it succeed on all the tests.
No release mode for puzzles.
1 Like
Ok thank’s for the answer 
In the core of the problem, there is a really simple mathematical solution
I fail at:
- Simple Test
- Dictionnary contains differents words for a same code
- Many possibilities, with small sequence and small dictionnary
- Long sequence, small dictionary
does anyone have an idea on the problem with these test cases.
I’m really stuck and can’t figure out the issue
what tests are you failing? IDE tests or validators (when you submit)?
As for hints, test names seem like relatively good directions to me.
By default, you can suppose that there is no problem with test cases of puzzles solved by thousands of other developers.
the 4 test cases i’m failing are the validator (after submit; all the ide test are passed). lol i’m sure that the test cases are correct i just can’t figure out what’ going on. for the “simple test” all that says is that its simple
for the “dictionnary contains more words for same code” i tested the same situation with the 4th test on the ide.
for the “many possibilities with small sequence” i tested my code with 2 examples given in the posts (look for ‘EEE’) one of them was
…
2
E
EEE
for a result of 19
my problem is that i’m not able to think about any case that makes my program fails
so i finally fixed the issue.
i had a bug not reading the last word in the input dictionary word.
fixed that and got 100%.
Thank you _CG_Thibaud for your help.
1 Like
Could you explain why 19 please ? ( and not 2) 
for this :
…
2
E
EEE
1 Like
The codingame markdown editor (now?) formats any sequence of dots with more than three dots into …
So ..... will become … unless you quote it as code.
I know this is a sad answer, took me some time to realize it as well ;).
Here are two test cases that helped me:
.
2
E
EEE
Answer is 1. Looks super basic but I was passing the 4 IDE tests and failing that.
....----
4
E
EE
T
TT
Answer is 25. With three dots instead of 4 it should be 15.
Good luck!
2 Likes
lol thanks a lot !
I’m really ashamed to write this, but if it can help someone who was able to make the same stupid mistake, it will serve me as a penance.
Working in JAVA, I wrote code with a clear idea what to do and procedure returning number of possible phrases for a line of morse code, that was recursively called was of the type Integer. It should be enough or so I thought, before forgetting about it.
So I passed first 3 cases without problems, but #4 didn’t gave me expected value.
Tumbling code up and down, I could not find what was wrong, as it is usually when it is something stupid like that.
As soon as the type was changed into long, I got things straight.
It took me almost a day (with watching some games on TV) to figure it out.
1 Like
Hi,
Can someone please explain what the goal is?
I say this because I have a working algorithm that checks the encoded message against the powerset of the list containing the morse code encoding of all the words in the dictionary. I assumed this was the goal since the “-.-” test gives as an only possible answer the K ("-.-") and not A (".-") but the “HELLOWORLD” test has an expected answer of 2, one for each combo [HELL+OWORLD, HELLO+WORLD]. So I assumed that the goal was to check for combinations that resulted in the whole encoded message being produced by said combinations, thus making just A not a valid answer for “-.-” since a T ("-") would be missing.
That said, since I check through the powerset of the encoded versions of the words in the dictionary, it is not possible to “skip” a certain combination yet the answers produced are not the expected answers.
P.S. It times out on large big, I’ll optimize later, it fails the “one possible”, “no possible” and “many possible” tests
P.S.2. I get the encoded versions using a function I wrote for uni, which gets the code from a flattened binary tree, I checked, it works.
Thanks for the help.
Thanx for your test but i can’t undertand how it works. I am using Java and I pass the first 5 test when you submit, but I’m afraid I haven’t understood something.
How do you get 19 solutions for this?
…
2
E
EEE
I only see 2.
E (3 times until the end)
EEE.(1 time)
I would apreciate an explanation or a list to know what 19 are.
And again, thanks for the tests
you are right …
the answer is 2
19 is definitely wrong
2 Likes
Great puzzle. At first glance it seemed quite easy to come up with good solution and it really is for the simple tests, small dictionary short word to decode. But when the time comes to solve the very hard tests, really good optimizations are needed. I needed quite some time and lots of thinking to find the right algorithm. At the end storing where each letter begins in the input string helped me for faster finding where each word from the dictionary begins. After that I used a recursion over the dictionary words and count how many words start at a given index of the input word and span to the end of the input string, that way I do not go through the how string every time.