Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: Challenge: 8 Letters, Most Words

by LanX (Chancellor)
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... =)

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?
[choroba]: I often can't log in to pause. But after it fails for the first time, everything works for the second time.
[cavac]: Ok, thanks for the information
[choroba]: Yes, tried now. Login didn't show the login window at all, timed out, but worked for the second time instantly.
[choroba]: Trying the daemon log...
[choroba]: It seems very slow. But the internet is weird here in Vietnam...
[choroba]: again, stopping it and trying for the second time fixed the problem

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (15)
As of 2017-02-22 09:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Before electricity was invented, what was the Electric Eel called?






    Results (325 votes). Check out past polls.