Re: Challenge: 8 Letters, Most Words

in reply to Challenge: 8 Letters, Most Words

OK, this uses some fairly naive heuristics to narrow down the search field. I'm sure somebody can do better, though I'd be fairly surprised if anybody came up with an answer that differed from mine by more than 2 letters.

use v5.14;
use Sort::Key::Top 'nkeytopsort';

sub sort_letters {
    my @letters = split '', $_[0];
    join '', sort @letters;
}

sub can_make {
    my ($letters, $word) = @_;
    $word = join '.*', sort split '', $word;
    $letters =~ qr{$word};
}

say "Reading words from dictionary...";
open my $dict, '<', '/usr/share/dict/words';
chomp( my @WORDS = map lc, grep length($_) <= 9, <$dict> );

say "Scoring microcombinations...";
my %SCORE; $SCORE{ sort_letters($_) }++ for @WORDS;
my @GOOD = nkeytopsort { $SCORE{$_} } -40 => keys %SCORE;

say "Generating candidate answers...";
my %CANDIDATES;
for my $x (@GOOD)
{
    for my $y (@GOOD)
    {
        for my $z (@GOOD)
        {
            my $letters = sort_letters substr("$x$y$z", 0, 8);
            $CANDIDATES{$letters}++;
        }
    }
}
my @VERYGOOD = nkeytopsort { $SCORE{$_} } -40 => keys %CANDIDATES;

say "Finding best candidate answer...";
my %RESULTS = map {
    my $letters  = $_;
    my @can_make = grep can_make($letters, $_), @WORDS;
    say "   $letters - ", scalar(@can_make);
    $letters => \@can_make;
} @VERYGOOD;
my ($BEST) = nkeytopsort { scalar @{$RESULTS{$_}} } -1 => @VERYGOOD;

say "BEST: $BEST";
say for sort @{$RESULTS{$BEST}};
[download]

The dictionary used was the standard /usr/share/dict/words supplied with Ubuntu 13.04.

The best set of letters it found was "aeinprst" which could make 426 words. (The list appears to have some duplicates because some words appear in /usr/share/dict/words more than once with different cases.)

use Moops; class Cow :rw { has name => (default => 'Ermintrude') }; say Cow->new->name

Comment on Re: Challenge: 8 Letters, Most Words Select or Download Code

Replies are listed 'Best First'.
Re^2: Challenge: 8 Letters, Most Words by dwhite20899 (Friar) on Oct 04, 2013 at 16:40 UTC
In the right typeface, if "a","n" and "p" can do handstands, you have (another) "e", "u" and "d" available, so it's really more then 426. Let a double for e, and add "h" who can also be "y" and this could get weird. Edit: if "p" makes the costume right, they can also be "b", "d" or "q". As far as I can tell, this doesn't violate the rules above.	[reply]
Re^2: Challenge: 8 Letters, Most Words by Limbic~Region (Chancellor) on Oct 05, 2013 at 04:17 UTC
tobyink, This is a pretty good heuristic solution but as-is, it only gets the second best solution for 2of12inf.txt (aeilprst at 344 instead of aeinprst at 346). Cheers - L~R	[reply]

In Section Seekers of Perl Wisdom