Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Re: Challenge: 8 Letters, Most Words

by LanX (Canon)
on Oct 04, 2013 at 17:38 UTC ( #1056904=note: print w/ replies, xml ) Need Help??


in reply to Challenge: 8 Letters, Most Words

(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.

DB<211> join "",sort split //,"electron" => "ceelnort" DB<212> join "",sort split //,"elector" => "ceelort"

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

1 a 1 b 3 a b 2 a c 2 b c 4 a b d

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)

update

Maybe 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... =)


Comment on Re: Challenge: 8 Letters, Most Words
Select or Download Code
Replies are listed 'Best First'.
Re^2: Challenge: 8 Letters, Most Words
by Limbic~Region (Chancellor) on Oct 05, 2013 at 03:31 UTC
    LanX,
    I couldn't convince myself that anything other than an exhaustive brute force solution would guarantee the correct answer. Now that I have done that, I will think about alternatives.

    Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1056904]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (13)
As of 2015-07-30 14:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (271 votes), past polls