Re^2: Turning A Problem Upside Down

[QM]

in reply to Re: Turning A Problem Upside Down
in thread Turning A Problem Upside Down

I realized I didn't need the permutation either, so the outline becomes

A Word Twister solution might be
(1) create a sorted anagram lookup for the dictionary,
(2) join the anagram keys into a string with an appropriate separator,
(3) determine the letter counts in the given letters,
(4) create regex snippet strings for each letter count (e.g., "a{0,3}"),
(5) match the given regex string against the monster dictionary anagram string,
(6) lookup the words from the matched anagrams,
(6) print the resulting words

I've also been toying with this idea more, and realized the previous result was bogus. So I've fixed that and cleaned it up:

eval '(exit $?0)' && eval 'exec perl -w -S $0 ${1+"$@"}'
                  && eval 'exec perl -w -S $0 $argv:q'
                  if 0;

# The above invocation finds perl in the path, wherever it may be

# find words in dictionary containing only letters given
# usage: $0 given_letters word_list_file_name[s]

use strict;
use warnings;

our $min_word_length = 3;
our $given = shift;
our $given_length = length( $given );

#######################################
# read in dictionary, removing invalid words, and creating
warn "Reading in dictionary, creating dictionary anagrams\n";
our %dictionary;
while (<>)
{
    chomp;
    next unless /^[a-z]{$min_word_length,}$/; # word filter
    my $sorted_anagram = join '', sort split '', $_; 
    push @{$dictionary{$sorted_anagram}}, $_;
}

my $anagram_keys = scalar keys %dictionary;
our $dictionary_anagram_string = join "\t", sort keys %dictionary;
warn "\t$anagram_keys anagram keys in dictionary (after filtering)\n";

###############################################3
warn "Creating given regex\n";
# convert given to regex strings of the form "a{0,3}b{0,2}..."
my @given = split '', $given;
my %given_counts;
for my $g (@given)
{
    $given_counts{$g}++;
}
my $given_regex = '';
for my $g (sort keys %given_counts)
{
    $given_regex .= sprintf "%s{0,%d}", $g,$given_counts{$g};
}
#warn "\t\$given_regex =~ m/\\b$given_regex\\b/g\n";

###############################################
# find all matching anagram keys
warn "Matching anagram keys\n";
my @key_match_results = grep {defined($_) and length($_)} $dictionary_
+anagram_string =~ m/\b$given_regex\b/g;
warn "\t", scalar @key_match_results, " matching anagram keys\n";

# lookup words from keys
warn "Looking up matching words\n";
my @words_matched;
for my $k (@key_match_results)
{
    push @words_matched, @{$dictionary{$k}};
}

print +join(' ', sort @words_matched), "\n";
warn "\t", scalar @words_matched, " words matched\n";

exit;

Using the same inputs as before:

> time word_twister2.pl posterboy web2*
Reading in dictionary, creating dictionary anagrams
        195645 anagram keys in dictionary (after filtering)
Creating given regex
Matching anagram keys
        146 matching anagram keys
Looking up matching words
ber bes besoot besot bespot bespy best bet betso bey boo boor boort bo
+ose boost booster boosy boot booter bootery boots
booty bop bor bore boro bort borty bose boser bot bote botryose boy bo
+yer bret brey broo broose brose brosot brosy brot
bye byre epos eros ers espy estop eyot obe obey oboe oer oes ootype op
+e opsy opt orb orby ore ort ory ose osprey oyer oy
ster per pert perty pes peso pest pet peto pob pobs poe poesy poet poe
+try poor poot pore poros porose port porto porty p
ory pose poser posey post postboy poster posy pot potboy pote poter po
+y prest presto prey pro prob probe proo prose pros
o prosy prote proto pry pryse pst pyr pyre pyro reb rebop rep repost r
+epot reps resp respot rest resty ret rob robe robo
t roe roey roost root rooty rope ropes ropy rose roset rosety rosy rot
+ rote roto royet royt rye ryot rype sepoy sept ser
 sero seroot sert set sey sob sober soe soot sooter sooty sop sope sop
+or sorb sore sort sorty sory sot soy spet spoor sp
oot spor spore sport sporty spot spret spry spy spyer step stero stey 
+stob stoep stoop stooper stoory stop stope stoper
store story stre strey strop stroy sty sye syre syrt tepor terp tobe t
+oby toe too toop top tope toper topo tops tor tore
 toro torose torse torso tory tosy toy toyer trey troop trope troy try
+ tryp tye type typer typo tyre tyro yeo yep yer ye
rb yes yeso yest yet yoe yoop yor yore yot yote
        261 words matched
5.770u 0.130s 0:06.04 97.6%     0+0k 0+0io 2769pf+0w

which is considerably faster.