Let’s say you’ve got a sequence of 1000 dots and dashes. One possible word ends at position 100, but other words are still possible on the same path (e.g. you’ve parsed out the word HELLO the words HELLO and HELLOWORLD are both in the dictionary). This is a fork; from position 100 you can start a new word (path B) or continue checking to see if HELLOWORLD is possible (path A).
Paths A and B both end somewhere. Let’s say they both end at the same spot, position 150 (e.g. the word WORLD is also in the dictionary). This is what I mean by the path reconverging; paths A and B both lead to new path C at position 150. When you get done parsing path A, you parse path C until you hit an endpoint, then go back to parse path B. Path B ends at the beginning of path C. However, since you already parsed path C once, you don’t need to do it again.
This kind of thing happens a lot in the larger tests, and the paths can split several times before recombining. You can waste a lot of compute cycles parsing out stuff you already did if you don’t take it into account.
I had the same problem as you because in a first version I used a set to store all my Morse words instead of a dictionary counting the number of combination a Morse word represents. Thank you for your message, it helped me a lot!
This was the simplest problem in the very hard category. I used recursion with memoization, but at first I was stucked at the point where many dictionary word can map to the same morse code which failed at dev test4
This has to be the easiest problem in the category.
My core program is about 20 lines long.
However, being a hard problem, it does require some forethought before sitting down and writing the code.
Knowing the nature of CodinGame’s puzzles, I knew from the start that the program has to cater for large datasets. So I had to memorize repeated searches and use dictionaries for string matching.
I was surprised I passed the last validation test but failed validations #6 and #7. #6 was an obvious oversight and could be solved by updating my data structure. It took me some time to resolve #7 and the test case from #alexander_yaremchuk was what I needed to identify the flaw in my logic.
I failed at validation test #8 but succeed at all others… (Even the #alexander_yaremchuk tests cases)
My implementation is fairly straightforward binary tree + memorization with path multiplication.
Do any of you have any idea what type of specificity #8 test has?
A very nice puzzle. I converged pretty quickly towards a TRIE (the first option that came into my mind actually).
I started by implementing a stack-based traversal as I was thinking that recursion would be too slow. Turned out my implementation was way too slow
I used a naive caching and it really didn’t save time.
Switching to a decent cache allowed me to use the simplest recursion and implied DFS, with the DP boosting performance to millisecond range
After all dust settled down, it allowed also for a nifty golfing experience
The validation test cases are nice, and their names mostly imply their content. Nice selection of edge cases.
nice puzzle. If you are stuck on the long test-case, don’t give up hope
Hey I don’t understand : I cover all the tests that are available in the IDE, including “Long sequence, large dictionary”, but I don’t cover the “Long sequence, large dictionary” in the Submitting section test. I’m stuck at 90%, and my 4th test in IDE takes 883 ms. Let say that the algorithm works. Isn’t 883 ms enough ? Is the 4th IDE test different from the 10th one in the submit section ?
Why does that matter? The puzzle is asking how many possible meanings the message can have, given the list of possible words. There’s no minimum or maximum number of times each word might appear in one message; it’s a dictionary.
is it possible for any of the words to have more than 1 index in the original morse code string?
My program just puts value as morseCode.indexOf().
Will it work? Any help will be appreciated
