Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re^8: Challenge: 8 Letters, Most Words

by LanX (Canon)
on Oct 05, 2013 at 21:28 UTC ( #1057086=note: print w/ replies, xml ) Need Help??


in reply to Re^7: Challenge: 8 Letters, Most Words
in thread Challenge: 8 Letters, Most Words

isn't the goal to find a clever Perl solution for the whole problem which does it within less than an hour? :)

I have two good ideas but no time to hack them. :(

Cheers Rolf

( addicted to the Perl Programming Language)


Comment on Re^8: Challenge: 8 Letters, Most Words
Replies are listed 'Best First'.
Re^9: Challenge: 8 Letters, Most Words
by Limbic~Region (Chancellor) on Oct 05, 2013 at 22:07 UTC
    LanX,
    Absolutely - but I am not that smart. I was hoping someone would provide a solution that was guaranteed to be correct that didn't require exhaustive searching. So far, all of the heuristic methods have flaws. That isn't to say I am not smart enough to come up with a heuristic solution but I needed to know for certain.

    Cheers - L~R

      hi Limbic~Region

      IMHO all "heuristic" methods must have flows... I'm quite experienced with these kind of problems and people tend to underestimate them (I'm not smart just trained :).

      And shouldn't be to difficult to show this belongs to NP-class.

      Anyway since I was able to calculate all possible 8-letter-combinations within 3 minutes with an non-optimized recursion it should be possible to find an approach to rapidly calculate each covering-number and to choose the maximum.

      Let me explain:

      First of all a good branch-and-bound could avoid useless branches which can't possibly beat the current maximum (my recursion just needs more criteria to bound)

      (this doesn't contradict NP, NP is about run-time and not correctness)

      In order to speed up calculation, one should cache sub-solutions which can be rapidly added.

      Let l be a letter-combination to be checked and L-x all derived combinations by striking x letters and n(l) the number of dictionary-words which can be formed with exactly all letters.

      its easy to see that the covering

      C(l)= n(l)+ sum { C($_) } L-1 - sum { C($_) } L-2

      e.g.  C('abc') = n('abc') + C('ab')+C('ac')+C('bc') - C(a) -C(b)-C(c)

      and with the table from this post

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

      we see C('abc') = 0+3+2+2-(1+1+0) = 5 and indeed the first 5 entries in the table can be constructed out of a,b and c!

      So to calculate the covering of an 8-letter tuple we just need to look up the covering of (at most) 8 7-letter sub-tuples and 28 6-letter sub-tuples and add them.

      Starting with all 1-letter tuples one can successively calculate the covering of all 2-letter tuples and so on.

      -max: 1 26 -max: 2 350 -max: 3 3247 -max: 4 23312 -max: 5 137909 -max: 6 698996 -max: 7 3116882 -max: 8 12461993 sum 16442715

      Holding 16 million hash-entries shouldn't be a problem. A worst case of 591_937_740 (=16442715 *(28+8)) additions neither, which are already 1000 times less operations than in your C program.

      This should be fast enough for 8 letters and I doubt one can do it faster...

      Implementation left as an exercise! :)

      Cheers Rolf

      ( addicted to the Perl Programming Language)

      ) for simplification this table only holds ordered words, extending it to count different permutations of the same letters ("cab" and "abc" => n("abc") =2 ) wouldn't change the math!

      ) and normally one can always construct an edge case where the recursion never bounds.

      ) please note the complexity rises exponentially for more letters, it's still NP!

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (4)
As of 2015-07-28 04:35 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 (252 votes), past polls