Unfortunately you have failed this regular programming challenge.

:)

Solve it and let me know :).

On the surface it feels relatively easy. Until you realize you can't tell one letter from another.

Is it "D" or is it "T" followed by the start of the next letter? "D" is equal to "TEE". But it could be "NE" also. One letter in and we are exploding. This is not counting nonsensical combinations like this being the start of "NL", but if that is a word boundary, then maybe it is ok.

Yeah, ok, though I'm not sure what that will prove. As I said, it's really just a case of writing a backtracking recursive thing. Here it is in prolog:

    letter(a, X) :- string_to_list("._", X).
    letter(b, X) :- string_to_list("_...", X).
    /* rest ommitted for brevity */
    letter(z, X) :- string_to_list("__..", X).

    morse([], []).
    morse(Morse, [Letter|Rest]) :-
        letter(Letter, Head),
        append(Head, Tail, Morse),
        morse(Tail, Rest).

Prolog is obviously excellent for this kind of thing since the backtracking comes built in, but it's not massively more complicated in other languages.

For "_.._", it gives you the following answers (I added some line-breaks):

    ?- string_to_list("_.._", L), 
       findall(English, morse(L, English), Answers).
    L = [95, 46, 46, 95],
    Answers = [[d, t],
         [n, a],
         [n, e, t],
         [t, e, a],
         [t, e, e, t],
         [t, i, t],
         [t, u],
         [x]].

I wasn't saying that it's not a good little problem. It's a lovely little problem, which you solve with recursive back-tracking! I wouldn't say it's a "trick question" though, it's just a regular programming challenge.

EDIT: Oh, I see what you're saying, do you mean "It's a trick question because there isn't necessarily just one answer"?

If so, then I misunderstood, I figured the challenge was "find all valid interpretations" of a certain morse code string. The fact that there could be more than one seemed fairly obvious to me.

"obviously" you should do this and the rank results under a language model (mainly joking)

edit: oooh and use beam search to limit the output size/time

My gut feeling is that you can solve this with dynamic programming faster than this.

There will be lots of ways to split any given prefix into letters. But all of them leave the same suffix. You don't need to repeat the analysis of the suffix.

You could avoid repeating the analysis by memoising the result. But when you're memoising results from leaves of a search tree, that's a hint that you're close to a dynamic programming approach.

It depends a little bit on what the acceptable answer is. If it's "stream/generate a list of possible strings", then the length of that list is probably O(2^n), so the fact that my recursive descent thing is exponential doesn't actually matter that much asymptotically. If you memoized it, the memo structure caching the suffixes would become massive and you'd spend just almost as much time looping the results from it as you would just walking down the tree, so you might as well save yourself the memory and just walk down the tree. Like, the length of the cached answer is more or less the same as the runtime of just doing the recursion, so you're not actually saving much of anything by memoization, and you're wasting a whole lot of memory.

I guess you could instead return some kind of fancy "prefix DAG" containing all possible strings, and that would be faster. But then you're just making the caller walk that tree instead of you doing it yourself, so you're really just shuffling the runtime around, not really saving much.

However, if the answer is "count the solutions", then yeah, memoizing would speed it up MASSIVELY. That's a good little Project Euler style problem, actually (though not a terribly tricky one), because you could make the input large enough that naive recursive descent wouldn't work. I haven't quite thought through what going full-on DP and turning the recursion upside down would do, but I assume it would work just fine.

But given that the number of possible solutions is a massive O(2^n) (probably, anyway), that puts a floor on the runtime you can't algorithm your way out of. Might as well go with the cheap recursive descent. I think, anyway :)

No if you're just counting you can definitely do it faster than 2^n time. I believe you can do it in linear.

That looks like an O(fuckit!) problem.

I've literally called such problems I've received in interviews O(shitty) or O(don't do that).