Chris Miller
Programmer
Based on a file that contains 194,000 English words, Mike Lewis mentioned in thread1551-1811770
I mentioned a spin off question to his question about all words in the graph
[pre]L - A - R
| x | x |
C - O - I
| x | x |
T - A - F
[/pre]
What letters in which arrangement allow to build the most words?
I think the sheer number of 26^9 combinations (as letters can occur more than once and their position matters) cannot easily be brute forced.
So I thought of a milder problem of which 9 letter word inn the dictionary yields most words. There still is the issue of needing to test all paths in all the different ways the graph nodes can be populated.
So I thought I at least probe by choosing random paths of length 9 and random 9 letter words from the dictionary.
There are 784 full-length paths and there are 28608 9-letter-words, which may be reduced by palindromes and removing mirrored or rotated paths, but even without such optimizations means analysis of a magnitude of 10 million problems of that type. Could be tested in about 8 hours. Lets say within a day, when assuming 27 ms for a single problem setting is the average.
It could be fun to output the best solution found so far on the way. It will not include situations where no 9-letter word is found, but there might be more shorter words worth doing without the 9-letter-word category. Another idea is combining the letters of all 4 and 5 letter words to have statistics on which letter composition is most used. You can of course get an orientation from letter frequency analysis, but the number of repeated letters and letter combinations can shift this a bit. Many vowels are good, I guess repeated Es would work better but surely the optimum isn't all vowels.
Chriss
I mentioned a spin off question to his question about all words in the graph
[pre]L - A - R
| x | x |
C - O - I
| x | x |
T - A - F
[/pre]
What letters in which arrangement allow to build the most words?
I think the sheer number of 26^9 combinations (as letters can occur more than once and their position matters) cannot easily be brute forced.
So I thought of a milder problem of which 9 letter word inn the dictionary yields most words. There still is the issue of needing to test all paths in all the different ways the graph nodes can be populated.
So I thought I at least probe by choosing random paths of length 9 and random 9 letter words from the dictionary.
There are 784 full-length paths and there are 28608 9-letter-words, which may be reduced by palindromes and removing mirrored or rotated paths, but even without such optimizations means analysis of a magnitude of 10 million problems of that type. Could be tested in about 8 hours. Lets say within a day, when assuming 27 ms for a single problem setting is the average.
It could be fun to output the best solution found so far on the way. It will not include situations where no 9-letter word is found, but there might be more shorter words worth doing without the 9-letter-word category. Another idea is combining the letters of all 4 and 5 letter words to have statistics on which letter composition is most used. You can of course get an orientation from letter frequency analysis, but the number of repeated letters and letter combinations can shift this a bit. Many vowels are good, I guess repeated Es would work better but surely the optimum isn't all vowels.
Chriss