Given a string which was produced by mixing up a string of digits, find the original digits

Question

I encountered the following problem:

Given a string which was produced by mixing up a string of digits (0-9), for example: "otetwonhree" was produced by "onetwothree"~123, find the original digits (without importance of order). in our example we would return "123". Another example: "oneoneeon", we return "111".

My question is, is there necessarily a unique way to interpret such a string? meaning, could there be a string with 2 different correct interpretations? I feel like it is complicated to show that (if we know that there isn't such a string, then the solution is easy, otherwise the problem doesn't really have a solution).

More generally, given some codes $\sigma_1, ..., \sigma_n$ instead of digits, each has a unique fitting string of letters, could we decide if any string which was created similarly as in the original problem, has a unique interpretation? It's easy to find some codes for which the answer would be no, which is why I find this problem also difficult.

I'll mention I haven't studied any computability courses yet so I am mainly looking for an answer rather than a full solution (but feel free to post such if it is of any interest to anyone else), this problem just made me curious. If there is a solution which could be somewhat understood with only basic algorithms background I wouldn't mind that.

Answer 1

The solution to this problem is linear algebra, rather than algorithms. The same apprach works for your example as for the general case.

The letters in the garbled message come from the number of times a code was used. In a forward way: if the code for "7" occurs $x_7$ times we have $2x_7$ e's, and $x_7$ n, s, v each.

For decoding we in reverse try to determine the number $x_i$ of times that code for "i" is present, for each $i=0,1,\dots,9$.

As an example, the total number of e's in the message equals $\#e = x_0+x_1+2x_3+2x_7+x_8+x_9$. The number of f's equals $\#f = x_4+x_5$.

I will not do this for every symbol, but after doing this we get a system of equations from which the numbers $x_0,\dots,x_9$ can be determined (if the system has no dependencies). Note that for some letters we might be lucky, like $\#z = x_0$.