laziness, impatience, and hubris | |
PerlMonks |
Re: Challenge: 8 Letters, Most Wordsby LanX (Saint) |
on Oct 04, 2013 at 17:38 UTC ( [id://1056904]=note: print w/replies, xml ) | Need Help?? |
(Tsts this Limbic~Region sabotaging our work-life balance again! ;) Some theory: For a minute I thought this can be trivially solved by counting the normalization of all words (<=8) from the dictionary in a hash... e.g.
As next step successively the count from all smaller words had to be added to covering words, e.g striking the "n" from "ceelnort" leads to "ceelort", so $count{ceelnort}+=$count{ceelort} But than I realized that the best covering word from the dictionary is not necessarily the best solution. take this counterexample for 3 out of 4 letters, the number showing the coverage-count
so the word (a,b,d) is the maximum with a count 4, but the set (a,b,c) would cover 5 words!!! (yes this also works with repeated letters) IMHO this problem belongs to the family of Maximum coverage problem and Set_cover_problem, so finding a guarantied best solution shouldn't be trivial w/o brute force. OTOH adapting the sort order of letters might already lead to very good solutions...
Cheers Rolf ( addicted to the Perl Programming Language)
updateMaybe you can use the above count hash to solve the dual problem: "which of the n-8 letters cover the minimum of words" (n including repetition) E.g. "d" is in only one out of 6 words with 4 letters => the remaining 3 letters cover 5 words. "c" is only in 2 remaining words => (a,b) cover a maximum of 3 words and so on. Not sure if this leads to the guarantied best solution, sounds to easy... =)
In Section
Seekers of Perl Wisdom
|
|