Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re^7: Challenge: 8 Letters, Most Words

by Limbic~Region (Chancellor)
on Oct 05, 2013 at 21:08 UTC ( #1057084=note: print w/ replies, xml ) Need Help??


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

LanX,
The C code I wrote to calculate it is below. It finished nearly instantly. I was trying to determine how to write the rest of the code (could it fit in memory).

#include <stdio.h> // Program to count how many 8 character combinations are necessary fo +r brute force // Constants to remove magic numbers #define Z 25 int main (void) { static const short int max[26] = {4, 3, 3, 4, 4, 4, 4, 3, 3, 2, 3, + 4, 3, 4, 4, 3, 1, 4, 5, 3, 4, 2, 3, 2, 3, 4}; // from STDERR of filt +er.pl short int have[26] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; int combo = 0; int i, j, k, l, m, n, o, p; for (i = 0; i <= Z; i++) { if (++have[i] > max[i]) { --have[i]; continue; } for (j = i; j <= Z; j++) { if (++have[j] > max[j]) { --have[j]; continue; } for (k = j; k <= Z; k++) { if (++have[k] > max[k]) { --have[k]; continue; } for (l = k; l <= Z; l++) { if (++have[l] > max[l]) { --have[l]; continue; } for (m = l; m <= Z; m++) { if (++have[m] > max[m]) { --have[m]; continue; } for (n = m; n <= Z; n++) { if (++have[n] > max[n]) { --have[n]; continue; } for (o = n; o <= Z; o++) { if (++have[o] > max[o]) { --have[o]; continue; } for (p = o; p <= Z; p++) { if (++have[p] > max[p]) { --have[p]; continue; } ++combo; --have[p]; } --have[o]; } --have[n]; } --have[m]; } --have[l]; } --have[k]; } --have[j]; } --have[i]; } printf("%i\n", combo); return 0; }
It also ended up being part of my final solution since I realized it was unnecessary to keep them in memory using a high water mark algorithm.

Cheers - L~R


Comment on Re^7: Challenge: 8 Letters, Most Words
Download Code
Re^8: Challenge: 8 Letters, Most Words
by LanX (Canon) on Oct 05, 2013 at 21:28 UTC
    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)

      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://1057084]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (7)
As of 2015-07-06 08:08 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 (70 votes), past polls