Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re^2: Turning A Problem Upside Down

by QM (Vicar)
on Aug 24, 2009 at 21:34 UTC ( #790917=note: print w/ replies, xml ) Need Help??


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.

-QM
--
Quantum Mechanics: The dreams stuff is made of


Comment on Re^2: Turning A Problem Upside Down
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://790917]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (8)
As of 2014-10-02 08:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    What is your favourite meta-syntactic variable name?














    Results (52 votes), past polls