Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Comment on

( #3333=superdoc: 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.

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


In reply to Re: Challenge: 8 Letters, Most Words by LanX
in thread Challenge: 8 Letters, Most Words by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others exploiting the Monastery: (12)
    As of 2015-07-02 22:09 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 (46 votes), past polls