Your task is to write down a sequence of English words that, after possibly moving around the spaces between the words, become their German translations.
As stated, this is pretty easy: for instance, I could write down the single English word SAND which translates to the single German word SAND. Or I could be a tiny bit more ambitious and write down a sequence of words like SAND PARK RADIO, which is similarly unchanged after translating into German.
But suppose we generalised away from just “English and German” and used a pair of languages that share an alphabet but don’t have any words that self-translate like that. Then the problem becomes rather harder because you might have to actually shuffle the spaces around in order to find a solution.
For instance, perhaps the dictionary looks like this:
| Language 1 | Language 2 |
CHEMOUS | MOUS |
MOUS | MOUSTA |
MOUSTACHE | CHE |
TA | CHEMOUS |
Can you come up with a sequence of words in Language 1 that, after possibly moving around the spaces, become their Language 2 translations? Here’s one:
"MOUS TA CHEMOUS MOUS MOUSTACHE"is a sequence of words in Language 1, and if I move the spaces around I can get
"MOUSTA CHEMOUS MOUS MOUSTA CHE"which is exactly the same sequence translated into Language 2.
Although that particular example wasn’t too hard in the end, it turns out that this is a rather hard problem to solve in general. In fact, it’s an instance of the Post Correspondence Problem, which is famously undecidable. That means that it’s impossible to write a program that is capable of taking any translation dictionary you can think of and telling you whether or not a solution exists.
Might still be fun to try, though.
