The Resistance puzzle discussion

[MrAnderson]

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.

[silvain_louis]

Ah, I understand and actually, I lose a lot of time ...
I'll think about how to take that into account in my tree search (or may be of graph)

[bananaMixer]

I solved this puzzle in Python3 with memoization.

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!

[Nabilion]

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

[JamesPun]

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.

[Kevapo]

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?

[puma17]

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

[xiaohouzi]

A few words on this one. I did a standard recursion with strings matching & memoization to avoid recursion on already-done paths.

[PierreVautherin]

Hello everyone,

just a question on test case 2, correct detection of a word.

Input :
--.-------..
5
GOD
GOOD
MORNING
G
HELLO

Expected : "1"

G is in the input dictionnary, so why isn't it a correct solution ?

Thanks !

Pierre

[nicola1]

Because all the symbols must be used?

[PierreVautherin]

that's a pretty good reason, thx !

[karlgros]

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 ?

[chr-m]

Does this help to make it more clear? https://forum.codingame.com/t/mime-type-puzzle-discussion/36/221

The runtime shouldn't be the problem if your algorithm passes the "Long sequence, large dictionary" IDE test.

[karlgros]

But if it passes the 4th test, why would it fail on the 10th ?

[chr-m]

Yes, the tests are different. That's the whole point.