Problems? Is your data what you think it is? 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

Replies are listed 'Best First'.
Re^8: Challenge: 8 Letters, Most Words
by LanX (Bishop) 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)

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!

Create A New User
Node Status?
node history
Node Type: note [id://1057084]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (7)
As of 2017-11-24 01:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In order to be able to say "I know Perl", you must have:

Results (343 votes). Check out past polls.

Notices?