Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options

Re^8: Challenge: 8 Letters, Most Words

by LanX (Bishop)
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)

Replies are listed 'Best First'.
Re^9: Challenge: 8 Letters, Most Words
by Limbic~Region (Chancellor) on Oct 05, 2013 at 22:07 UTC
    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?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1057086]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (12)
As of 2018-06-20 07:52 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (116 votes). Check out past polls.