3 ms·
Is the answer even well-defined? Seems like without spaces, there could be strings that decode to multiple possible (possibly nonsense) “sentences.”
by egdod 7y ago
Is the answer even well-defined? Seems like without spaces, there could be strings that decode to multiple possible (possibly nonsense) “sentences.”
- hnkain 7y agoIn particular, E is . and T is -, so you can trivially decode any sequence of dots and dashes to strings containing only E and T.
- pbhjpbhj 7y agoSurely "decoding" means returning the text that was encoded. You can't trivially decode it, you can provide a candidate solution, that's entirely different; the point of sharing this was it's not possible to decode because there's no unique solution. ...---... you can guess it's EEETTTEEE, but the decoding is SOS, that was the plaintext I started with.
- rdlw 7y agoYes, and even a simple string like "...---..." has 200 possible solutions, including "VTTIE", "3NI", and "SMB". Especially for longer inputs, there's no way to guess which one is right.
- Stratoscope 7y agoSOS is an interesting case, because it is a Morse "prosign", which means it is sent as one continuous stream of dits and dahs without any pauses between the letters we use to represent it. In other words, SOS is sent exactly the way you wrote it, as if it were one long character: ...---... It is not sent as three separate letters like this: ... --- ... To indicate this special treatment, prosigns are normally typeset with a bar over the connected letters, something like this: ___ SOS (I used underscores above the letters here; if they render as separate underscores, imagine that they all run together.)
- deleted 7y ago[deleted]
- sethammons 7y agoExactly. Hence the moral of don't give a problem you have not solved yourself. Similar to the reverse a Unicode string from the article.
- saagarjha 7y agoNo, Morse Code is not a prefix code.
- joezydeco 7y agoTelegraph operators could do this in their heads in realtime!
- Someone 7y ago“Prefix code” is sufficient for the problem to be well-defined, but I don’t think it is necessary. For a trivial counterexample, consider an alphabet of .- ..- ...- (And yes, it isn’t uniquely solvable in the case or Morse code, as shown by the counter example A = ET)
- hcs 7y agoThat's a prefix code, they're defined by no code word being a prefix of another (so if you put them in a trie the code words only appear on leaves). A trivial example is the reverse: _. _.. _... Which can be decoded by, at worst, reversing the string first. (Sorry if I've misunderstood your example)
- Someone 7y agoNo, you didn’t.