#!/usr/bin/perl
use strict;
use warnings;

my (
    @words,
    $catcount,
    $bestscore,
    $bestsolution,
);

# collect words and count categories
$catcount= 0;
while (<DATA>) {
    chomp;
    my($cat, $word)= split;
    push(@{$words[--$cat]}, $word);
    $catcount= $cat if $cat>$catcount;
}

# initialise solution
$bestscore= 0;
$bestsolution= '';

find_best_solution($catcount+1, '');

print "\n",$bestsolution;

sub find_best_solution {
    my($cat, $solution)= @_;
    if ($cat > 0) {
        # Still categories to check
        --$cat;
        foreach (@{$words[$cat]}) {
            find_best_solution($cat, $_ . "\n".  $solution);
        }
    }
    else {
        # All categories done
        my $score= score($solution);
        if ($score > $bestscore) {
            print STDERR "\rNew best score: ",$score;
            $bestscore= $score;
            $bestsolution= $solution;
        }
#        else { #decomment if you want to see it work
#            print STDERR " (",$score,")",("\010" x (3+length($score))
+);
#        }
    }
}

# Scoring is done for the concatenation of the words
sub score {
    # Get the words and lowercase them 
    local($_)= lc shift;
    # being paranoid I remove all non-letters
    s/[^a-z]//g;
    my $score= 0;
    while ($_) {
        # get the first character (alternative substr($_,0,1);)
        my $f=chr(ord($_));
        # count that character and remove it
        my $n=s/$f//g;
        # add the score 1+2+3+4..+n= n*(n+1)/2
        $score+= ($n+1)*$n/2;
    }
    return $score;
}

__DATA__
1 alabama
1 arkansas
1 alaska
1 delaware
1 hawaii
1 indiana
1 kansas
1 montana
1 delaware
2 sazerac
2 sangrita
3 radiator
3 gastank
3 engine
3 heater
3 fender
3 wheel
3 detent
3 battery
3 clutch
3 mirror
3 window
4 alloy
4 amalgam
4 vanadium
4 copper
4 steel
5 rutabaga
5 limabean
5 cress
5 carrot
5 sorrel
5 squash
5 cabbage
5 pepper
5 lettuce
5 beet
5 leek
5 celery
5 endive
5 rhubarb
5 parsnip
5 pumpkin
6 azalia
6 camellia
6 dahlia
6 gardenia
6 gentian
6 vervain
6 canna
6 hepatica
6 bluebell
6 anemone
6 oleander
7 lasagna
7 macaroni
7 pastina
7 gnocchi
7 tortelli
7 alfabeto
8 mascagni
8 britten
8 menotti
9 unamas
9 tacotime
9 pizzahut
9 tacobell
9 panago
9 tacomayo
9 edojapan
9 hardees
10 caramel
10 marzipan
10 taiglach
10 taffy
10 brittle
10 fondant
10 toffee
10 dragee
[download]