Just by looking at the structure of the problem, it appears to be NP-Complete. It has some similarities to MDKP (multi-dimensional knapsacks) but here the capacity is not present but the profit values are multidimensional and they are related to other objects in the bag.

An exact solution will be out of the picture when the data becomes large and i am sure your wife would appreciate some kind of approximation if it can be done in couple of mins rather than the best solution which might take days!!!

Here is my Mathematical formulation and at this point I am not aware of any MINLP (mixed-integer non linear prog solvers).

Let i represent the index (num in your example) and
    j represent the actual word
    c represent all the letters ('A'..'Z')

Let X[i,j] = { 1 if word (i,j) was chosen, 0 otherwise}

The value of each word can be broken into characters/letters

For all (i, j) - 
  # you get the value only if the word is chosen
  V[i,j,c] = number of c's in the word (i,j) * X[i,j]   

For all c
  Let Value(c) = (sum {over all i,j} V[i,j,c])*((sum {over all i,j} V[
+i,j,c])+1)/2  

Optimization problem
===================
Max sum {over c} Value(c)

# You can choose only one word from each index (num)
subject to: sum {over all j} X[i,j] = 1 for all i.
subject to: x[i,j] element of (0,1) for all i, j.
[download]

Here a simple heuristic that i can think of and can be improved a lot -

1. For each index/word pair store the number of repeats of each charac
+ter.
2. INIT: Start with the index/word pair that has the highest value by 
+itself (i.e. assuming the value of other index/words are zero). 
3. Choose the next index/word pair that increases the value the most (
+let's say your init value for 1/alabama, then you move to index = 2 a
+nd look for the best next increase.)
4. Repeat step-3 until you exhaust all indices.
5. Now you have a local optimum based on your starting point. 
6. EXCHANGE: Store the current objective, Go back to index = 1 and pic
+k the second best word in index = 1. Now check if you could improve t
+he previous solution by exchanging index = 2 with something new etc. 
7. You can repeat this exercise for certain number of iterations and t
+hen you stop with the best solution found thus far. 
NOTE that you can also use randomized approach to randomly pick an ele
+ment to exchange and try to improve the solution.
[download]

very interesting problem!

cheers

SK

#!/usr/bin/perl

use strict;
use warnings;

my @text;

while (<DATA>) {
  my ($q, $w) = split;
  push @{ $text[$q-1] }, $w;
}

my @best = calc(\@text);
print "{@best}\n";

sub calc {
  my ($t) = @_;
  my @best = (0);

  iter($t, [(0) x 26], \@best, 0);

  return @best;
}


sub iter {
  my ($t, $tmp, $best, $i) = @_;

  if ($i == @$t) {
    my $s = 0;
    $s += $_ * ($_+1) / 2 for @$tmp[0..25];
    @$best = ($s, @$tmp[26..$#$tmp]) if $s > $best->[0];
    return;
  }

  for (@{ $t->[$i] }) {
    $tmp->[ord($_) - ord('a')]++ for split //;
    push @$tmp, $_;
    iter($t, $tmp, $best, $i+1);
    pop @$tmp;                  
    $tmp->[ord($_) - ord('a')]-- for split //;
  }               
}
[download]

• The important thing to note about the game is that you only get one word per category, for a total of 10 words (in this case where you have 10 categories).
• sk is right in that this seems to be related to the knapsack and that the perfect solution is probably NP-complete.
• It's immediately clear that optimizing for a single letter is more likely to generate a better score than any other optimization. If you think about it, you're attempting to fill an 8x10 grid with items that have value based on how often that specific item has appeared. (however the items are chosen). Each of the 80 spots must be maximized, so if you can get another G in there, that's worth losing 5 F's (assuming you were optimizing for G and have at least 15-20 more of them than F's).
• When optimizing for a letter, you have to consider all words in a category that have the maximum number of that letter.
• You can skip all letters that don't have a word in each category with a minimum number of that letter. For the sample you gave, that minimum appears to be 2.

This uses your calculate_score() function slightly modified to not change its arguments. I also come up with your 474 list, but in about 0.1 seconds on a PIII-700 with 768M of RAM using the larger dataset you provided. With the full dataset (all 50 states, etc), the prunings I used will remove the best possible score, but I'll get close.

Sounds like a simple memory leak. The most likely culprit would be the XS-happy List::Util, IMO. Simply removing List::Util (and Timer::HiRes for obscure reasons) and running your code shows very little and flat memory usage. It would take 11 hours to run, but it doesn't leak for me.

My first attempt was brute force, unremarkable, found the 474 after processing 95% of the combinations and took just under 8 hours to run.

My second finds the 474 in 0.15 seconds.

P:\test>499358-2
460 : [ alabama sangrita radiator amalgam rutabaga camellia lasagna ma
+scagni tacomayo marzipan ]
472 : [ alabama sangrita radiator amalgam rutabaga azalia lasagna masc
+agni tacomayo marzipan ]
474 : [ alabama sangrita radiator amalgam rutabaga azalia lasagna masc
+agni tacomayo taiglach ]
Elapsed: 0.015 seconds.
[download]

See comments for the strategy used.

#! perl -slw
use strict;
use Time::HiRes qw[ time ];

my $start = time;

my @lookup = map{ ($_+1) * $_ /2 } 0 .. 80;
sub calcScore {
    my( %chars, $score );
    $chars{ $_ }++ for map{ split'' } @{ $_[0] };
    $score += $lookup[ $_ ] for values %chars;
    return $score;
}

my @cats = map{ [ split ' ' ] } <DATA>;
close DATA;

## Sort the words in each category by their individual scores (descend
+ing)
my %wordScores;
@{ $cats[ $_ ] } = sort{
    ( $wordScores{ $b } ||= calcScore [$b] )
    <=>
    ( $wordScores{ $a } ||= calcScore [$a] )
} @{ $cats[ $_ ] } for 0 .. $#cats;

## form our guess from the highest scoring words in each category
my @guess = map{ $cats[ $_ ][ 0 ] } 0 .. $#cats;
my $best = calcScore \@guess;

## Loop over the categories swaping the other words in that cateory 
## for the guessed word. If we get a better score, start again.
LOOP:
for my $iCat ( 0 .. $#cats ) {
    my $cat = $cats[ $iCat ];
    for my $iWord ( 1 .. $#$cat ) {
        my $test = calcScore [ 
            @guess[ 0 .. $iCat -1 ], 
            $cat->[ $iWord ], 
            @guess[ $iCat+1 .. $#guess ] 
        ];
        if( $test > $best ) {
            $best = $test;
            $guess[ $iCat ] = $cat->[ $iWord ];
            print "$best : [ @guess ]";
            redo LOOP;
        }
    }
}
printf "Elapsed: %.3f seconds.\n", time - $start;

__DATA__
alabama arkansas alaska delaware hawaii indiana kansas montana delawar
+e
sazerac sangrita
radiator gastank engine heater fender wheel detent battery clutch mirr
+or window
alloy amalgam vanadium copper steel
rutabaga limabean cress carrot sorrel squash cabbage pepper lettuce be
+et leek celery endive rhubarb parsnip pumpkin
azalia camellia dahlia gardenia gentian vervain canna hepatica bluebel
+l anemone oleander
lasagna macaroni pastina gnocchi tortelli alfabeto
mascagni britten menotti
unamas tacotime pizzahut tacobell panago tacomayo edojapan hardees
caramel marzipan taiglach taffy brittle fondant toffee dragee
[download]

BrowserUk,
I really like this heuristic approach. Take a best guess and then see if it can be refined to get a better score. I am thinking about posting a "Challenge: Letter Power Revisited" thread so I have been considering how to generate puzzles at random. I was able to find an example where your solution does not provide the best solution in just 3 tries:
Read more... (3 kB)

My heuristic solution is very similar to yours. Rather than picking the best individual score from each group, I calculate the letter frequency across all words. Then I select the word from each group that has the highest score based on that frequency analysis. I have also modified the refinement loop to limit the number of loops to handle the edge case where picking the best individual scores is the worst thing to do.

LOOP:
for (1 .. $max_loops) {
    # your refinement loop
        if ($better) {
            # update best
            next LOOP;
        }
    # end of your refinement loop
    last;
}
[download]

This way you pick a "good enough" score in a reasonable time frame no matter what.

I am now going to try and figure out if I can do a smart exhaustive search to guarantee best solution in a reasonable runtime (less than 2 hours). If I can, I will post a new thread comparing naive brute force, optimized brute force, heuristic, optimized heuristic.

Cheers - L~R

It can be show that a better solution exists (not necessarily best):

438 : [ eyesore sleekest steepen spindles baseless rockiest refiners sheered tethers exhausts ]

Yep! That's the problem with heuristic solutions. Unless you also run a full brute force on the same data, you can never be sure that you haven't found some local maxima.

On the dataset above, your 438 is better that my 434, but neither are as good as:

441 : [ rendered spindles squires tethers rockiest 
        eyesore sheered sleekest steepen refiners ]
[download]

But even using all 4 cpus flat out, my brute force solution can just about manage 1/2 a million combinations/minute. Given there are 7.75e9 combinations to try, I'm projecting over 10 days to verify the heuristic for that one dataset. That's too much for that sake of an intellectual challenge with no useful purpose.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Given a list of flowers, the algorithm to find which scores highest in your game should be something like:

sub calculate_score {
    my $word         = shift();
    my $score        = 0;
    my %letter_value = ();
    my @letters      = split( '', $word );
    foreach ( @letters ) {
        if ( defined( $letter_value{$_} ) ) {
           $letter_value{$_} = $letter_value{$_} * 2;
           $score += $letter_value{$_};
         } else {
           $score += 1;
           $letter_value{$_} = 1;
        }
    }
    return $score;
}
[download]

Which assumes that each letter is worth 1 the first time you use it, 2 the second time, 4 the third and so on. it gives me a score of 18 for "alabama" and a score of 47 for "lillipilli".

But as I say, I don't know how you get your lists of words in the first place.

That's easy - if I understood it correct.

Simply take all combinations of words (recursive task) and calculate the score. Just store the best score and the best solution found so far.

Here is my implementation.

s$$([},&%#}/&/]+}%&{})*;#$&&s&&$^X.($'^"%]=\&(|?*{%.+=%;.#_}\&"^"-+%*)
+.}%:##%}={~=~:.")&e&&s""`$''`"e
[download]

Required Parameters:

• Number of categories (default = 10)
• Maximum length of word (default = 8)
• Minimum number of words that can fit a category (default=2)
• Maximum number of words that can fit a category (default=15)

My approach would be to use a dictionary file to randomly select words to fit a category per the parameters above. It will be possible for the same word to fit multiple categories though the solution chosen may only use that word once. In this way, I can reproduce puzzles at will. I assume every letter in all words across the solution counts for points?

Please let me know if I have this all correct. If I don't, please clarify. When I am finished I will post a "Challenge: Letter Power Revisited" post since this thread is three and a half years old.

The part of the original puzzle that made it difficult for me to envision a computer solution to was where they give arbitrary topics. For example, "US States". Obviously, this has 51 possible answers (ok, really 50 - I'm including Canada :-P), a subset of which would be valid depending on the maximum length of the word. Programmatically solving that would be a challenge unto itself. Now, if you're going to generate categories yourself, you could define it to be solvable.

In the original post, my wife had looked for answers in each category trying to maximise the count of 'a's, thinking that would get the best possible score. We don't know if 'e' would have been a better choice, since we didn't try to optimise that. However, a more general application could possibly handle many more answers by having categories with all possible answers in some sort of database. For example, if there is an on-line crossword dictionary, crossword clues make great categories, which is fitting since the original problem came from a puzzle book including crosswords, and then querying from said dictionary should be a relatively solvable problem. Of course, this blows "maximum words in a category" out of the water :-) Then again, even a crossword dictionary won't have every possible answer - just ones used in crosswords. I wouldn't expect a category of "historical English Monarch" to have every monarch ever in the dictionary...

Your assumption about points is correct. Every letter in all words counts.

Of course, you're free to define your own puzzle that is loosely based on the above. You could define your own categories as groups of words in each category (having overlapping words where they can only be used in one category does make it more interesting). Or, for example, you could try varying the score for each letter, especially since a computer is doing the addition anyway. For example, what happens if each letter counts for double the previous? How about each letter counts for its position in the Fibonacci sequence? Maybe each letter gets its own fibonacci sequence, and the last number for each letter counts (e.g., if there are 2 a's and 3 b's, the a's get 1 point as the second number in the sequence, and the b's get 2 points as the third number in the sequence)? Do these variations really make for any difference in tactic? I doubt it, but that'd be like a premature optimisation that'd need benchmarking :-)

Tanktalus,
I agree that writing a program to find words that fit a category is a bigger challenge all unto itself. That's why I took your approach of assuming the words that fit were already known. My categories will just be cat 1 .. N. I just want variation to test the robustness of any possible solution. Using an existing database is also a possible approach but goes beyond the scope of what I am intending to do.

Regarding the "maximum words in a category". That is a configurable parameter that I envision being used to bound a given puzzle so that an implementation has a realistic chance of solving for the "best" combination of words. On the other hand, if you are going to go with a heuristic approach then it may not matter - but being configurable allows the user to make that decision.

Regarding making variations on the rules for the purposes of exploration - sure, but I wanted to make sure I had the basic idea since your original post left me more than a little confused. Now that I know I am on the right track I can think about it further. Thanks!

Cheers - L~R

1. Varaible ammnt of "catagories."
2. Assumed a catagory is a set of random words.
3. 10 "answers"
4. 8 letters per "answer"

The categories are presented. You need to come up with a word that is in the category that will help maximise your points. No word is allowed to be more than 8 letters.

I did not include coming up with the word possibilities because that is a completely different problem which I'm not interested in solving in perl. (Maybe someone else is...)

Example (which I'm making up now, with out seeing the original puzzle - my wife didn't show it to me):

1. US State
2. Car part
3. Type of precipitation
4. Member of NATO
5. Olympic Games site
6. In the kitchen
Note that this is not the game that the words in my list are for, it's just the idea. Each category gets one answer, you need to see how high of a score you can get. An example answer is in the back of the book with a crazy-high total.

One way to solve it is to come up with a list of answers for each category, and then see what combination of these answers gives the highest score, which is what we were doing here. My wife came up with the answers in my OP, and then I set about getting the computer to find the best option.

In her game, there were ten categories. Not all games have the same number of categories.

I agree. I don't understand the description at all. I'd especially like to know what 8 letters per answer means.