Longest Shortest Path
A shortest path connects two words, for example "dos" and "lnx", with the shortest possible list of words which differ only in one letter, for example "dog"-"log"-"lug"-"lux". Surely it must be only coincidental that dos is close to dog and lnx close to lux, which among other meanings is Latin for light.
Given a vocabulary of N words it relatively easy to construct an efficient program which computes the shortest path between any two words. But what is the best algorithm for finding the longest shortest path? One could use the Floyd-Warshall algorithm which takes O(N^3) time, or Johnson's algorithm which takes O(N^2 log N) time. Given N is perhaps a few thousand, these algorithms are already palatable in modern computers.
The actual findings depend of course heavily on the given vocabularies, but below are some results using chosen-length subsets of an old /usr/dict/words for English words: Perhaps it is only because of my skeptical tendencies, but for some reason "chi", the circulating life energy in Chinese philosophy, and "ass" come up when searching the longest shortest path in words of three letters. The intervening words are "phi"-"poi"-"pow"-"row"-"roe"-"rye"-"aye"-"are"-"ark"-"ask". Similarly suspiciously the search in five letter long words produced "toxin" and "quack" with a whopping 44 words in between them. Only the four letter words seemed to refer to something less quacky: "zeta"-"unit" or "lava"-"chum" with 15 intervening words.
Given a vocabulary of N words it relatively easy to construct an efficient program which computes the shortest path between any two words. But what is the best algorithm for finding the longest shortest path? One could use the Floyd-Warshall algorithm which takes O(N^3) time, or Johnson's algorithm which takes O(N^2 log N) time. Given N is perhaps a few thousand, these algorithms are already palatable in modern computers.
The actual findings depend of course heavily on the given vocabularies, but below are some results using chosen-length subsets of an old /usr/dict/words for English words: Perhaps it is only because of my skeptical tendencies, but for some reason "chi", the circulating life energy in Chinese philosophy, and "ass" come up when searching the longest shortest path in words of three letters. The intervening words are "phi"-"poi"-"pow"-"row"-"roe"-"rye"-"aye"-"are"-"ark"-"ask". Similarly suspiciously the search in five letter long words produced "toxin" and "quack" with a whopping 44 words in between them. Only the four letter words seemed to refer to something less quacky: "zeta"-"unit" or "lava"-"chum" with 15 intervening words.
posted by cessu at 12:27 AM
1 Comments:
Cool! My 5-yr-old had a puzzle similar to these, and I then wondered what the 'most difficult' one would be. I was then led to consider constructing the graph of four-letter words which you describe, and finding the 'longest shortest path' in it, again, as you describe. Google led me to your blog entry as the first hit for 'longest shortest path', and you have addressed my exact question. On the one hand, then, I now know the answer to my original question, but on the other hand, somebody beat me to asking and answering it! Good stuff.
Post a Comment
<< Home