Home > Archive > PERL Beginners > January 2006 > please help find logic error in home-brewed brute force anagram solver/creator script
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
please help find logic error in home-brewed brute force anagram solver/creator script
|
|
| Kenneth A Wolcott 2006-01-10, 4:02 am |
| Hi;
I have enclosed both the perl source and the associated output of a
bruce-force anagram script that I wrote that has a logic error in it
that I can't find.
It does not generate all of the permutations of the letters in the
words specified. Why not?
Secondly, on the matter of efficiency, I could push the results into a
hash, then sort the hash to print out unique permutations. Even better
yet, a better algorithm that wouldn't generate multiple permutations.
And one better yet, usage of an external dictionary lookup to eliminate
the permutations that aren't words. But I need help on the logic error
first :-)
Thanks,
Ken Wolcott
#################
use strict;
my @words = ("NERO", "TOOLED", "MEALS", "DOMAINS", "NERVED", "TRADUCE",
"COUNTS", "SALVAGES", "DIAGNOSE", "AGROUND");
for (my $w=0; $w<@words; $w++) {
print "word=".$words[$w]."\n";
my @letters = split //, $words[$w];
for (my $i=0; $i<=length($words[$w]); $i++) {
for (my $j=0; $j<=length($words[$w]); $j++) {
# next if ($i == $j);
($letters[$i], $letters[$j]) = ($letters[$j], $letters[$i]);
my $new_word = join "", @letters;
print "|".$new_word . "|\n";
}
}
}
#################
#################
word=NERO
|NERO|
|ENRO|
|RNEO|
|ONER|
|NERO|
|NERO|
|NERO|
|NERO|
|NREO|
|NOER|
|ONER|
|NOER|
|NOER|
|NEOR|
|NROE|
|ONRE|
|ORNE|
|ONRE|
|ONRE|
|ONER|
|RNEO|
|RONE|
|ROEN|
|RONE|
|RONE|
word=TOOLED
|TOOLED|
|OTOLED|
|OTOLED|
|LTOOED|
|ETOOLD|
|DTOOLE|
|TOOLED|
|TOOLED|
|TOOLED|
|TOOLED|
|TOOLED|
|TLOOED|
|TEOOLD|
|TDOOLE|
|DTOOLE|
|TDOOLE|
|TDOOLE|
|TODOLE|
|TODOLE|
|TLDOOE|
|TEDOOL|
|DTEOOL|
|DETOOL|
|DTEOOL|
|DTEOOL|
|DTOEOL|
|DTOEOL|
|DTLEOO|
|ETLDOO|
|EDTLOO|
|EDLTOO|
|EDTLOO|
|EDTLOO|
|EDTOLO|
|EDTOLO|
|LDTOEO|
|LETODO|
|LEDTOO|
|LEDOTO|
|LEDTOO|
|LEDTOO|
|LEDTOO|
|OEDTOL|
|OLDTOE|
|OLETOD|
|OLEDTO|
|OLEDOT|
|OLEDTO|
|OLEDTO|
word=MEALS
|MEALS|
|EMALS|
|AMELS|
|LMEAS|
|SMEAL|
|MEALS|
|MEALS|
|MEALS|
|MEALS|
|MAELS|
|MLEAS|
|MSEAL|
|SMEAL|
|MSEAL|
|MSEAL|
|MESAL|
|MASEL|
|MLSEA|
|SMLEA|
|SLMEA|
|SMLEA|
|SMLEA|
|SMELA|
|SMALE|
|LMASE|
|LSMAE|
|LSAME|
|LSMAE|
|LSMAE|
|LSMEA|
|ASMEL|
|ALMES|
|ALSME|
|ALSEM|
|ALSME|
|ALSME|
word=DOMAINS
|DOMAINS|
|ODMAINS|
|MDOAINS|
|ADOMINS|
|IDOMANS|
|NDOMAIS|
|SDOMAIN|
|DOMAINS|
|DOMAINS|
|DOMAINS|
|DOMAINS|
|DMOAINS|
|DAOMINS|
|DIOMANS|
|DNOMAIS|
|DSOMAIN|
|SDOMAIN|
|DSOMAIN|
|DSOMAIN|
|DOSMAIN|
|DMSOAIN|
|DASOMIN|
|DISOMAN|
|DNSOMAI|
|SDNOMAI|
|SNDOMAI|
|SDNOMAI|
|SDNOMAI|
|SDONMAI|
|SDMNOAI|
|SDANOMI|
|SDINOMA|
|NDISOMA|
|NSDIOMA|
|NSIDOMA|
|NSDIOMA|
|NSDIOMA|
|NSDOIMA|
|NSDMIOA|
|NSDAIOM|
|ISDANOM|
|INDASOM|
|INSDAOM|
|INSADOM|
|INSDAOM|
|INSDAOM|
|INSDOAM|
|INSDMAO|
|ANSDMIO|
|AISDMNO|
|AINDMSO|
|AINSDMO|
|AINSMDO|
|AINSDMO|
|AINSDMO|
|AINSDOM|
|MINSDOA|
|MANSDOI|
|MAISDON|
|MAINDOS|
|MAINSDO|
|MAINSOD|
|MAINSDO|
|MAINSDO|
word=NERVED
|NERVED|
|ENRVED|
|RNEVED|
|VNERED|
|ENERVD|
|DNERVE|
|NERVED|
|NERVED|
|NERVED|
|NERVED|
|NREVED|
|NVERED|
|NEERVD|
|NDERVE|
|DNERVE|
|NDERVE|
|NDERVE|
|NEDRVE|
|NRDEVE|
|NVDERE|
|NEDERV|
|DNEERV|
|DENERV|
|DNEERV|
|DNEERV|
|DNEERV|
|DNREEV|
|DNVEER|
|ENVDER|
|EDNVER|
|EDVNER|
|EDNVER|
|EDNVER|
|EDNEVR|
|EDNRVE|
|VDNREE|
|VENRDE|
|VEDNRE|
|VEDRNE|
|VEDNRE|
|VEDNRE|
|VEDNER|
|REDNEV|
|RVDNEE|
|RVENED|
|RVEDNE|
|RVEDEN|
|RVEDNE|
|RVEDNE|
word=TRADUCE
|TRADUCE|
|RTADUCE|
|ATRDUCE|
|DTRAUCE|
|UTRADCE|
|CTRADUE|
|ETRADUC|
|TRADUCE|
|TRADUCE|
|TRADUCE|
|TRADUCE|
|TARDUCE|
|TDRAUCE|
|TURADCE|
|TCRADUE|
|TERADUC|
|ETRADUC|
|TERADUC|
|TERADUC|
|TREADUC|
|TAERDUC|
|TDERAUC|
|TUERADC|
|TCERADU|
|ETCRADU|
|ECTRADU|
|ETCRADU|
|ETCRADU|
|ETRCADU|
|ETACRDU|
|ETDCRAU|
|ETUCRAD|
|CTUERAD|
|CETURAD|
|CEUTRAD|
|CETURAD|
|CETURAD|
|CETRUAD|
|CETAURD|
|CETDURA|
|UETDCRA|
|UCTDERA|
|UCETDRA|
|UCEDTRA|
|UCETDRA|
|UCETDRA|
|UCETRDA|
|UCETADR|
|DCETAUR|
|DUETACR|
|DUCTAER|
|DUCETAR|
|DUCEATR|
|DUCETAR|
|DUCETAR|
|DUCETRA|
|AUCETRD|
|ADCETRU|
|ADUETRC|
|ADUCTRE|
|ADUCETR|
|ADUCERT|
|ADUCETR|
|ADUCETR|
word=COUNTS
|COUNTS|
|OCUNTS|
|UCONTS|
|NCOUTS|
|TCOUNS|
|SCOUNT|
|COUNTS|
|COUNTS|
|COUNTS|
|COUNTS|
|CUONTS|
|CNOUTS|
|CTOUNS|
|CSOUNT|
|SCOUNT|
|CSOUNT|
|CSOUNT|
|COSUNT|
|CUSONT|
|CNSOUT|
|CTSOUN|
|SCTOUN|
|STCOUN|
|SCTOUN|
|SCTOUN|
|SCOTUN|
|SCUTON|
|SCNTOU|
|TCNSOU|
|TSCNOU|
|TSNCOU|
|TSCNOU|
|TSCNOU|
|TSCONU|
|TSCUNO|
|NSCUTO|
|NTCUSO|
|NTSCUO|
|NTSUCO|
|NTSCUO|
|NTSCUO|
|NTSCOU|
|UTSCON|
|UNSCOT|
|UNTCOS|
|UNTSCO|
|UNTSOC|
|UNTSCO|
|UNTSCO|
word=SALVAGES
|SALVAGES|
|ASLVAGES|
|LSAVAGES|
|VSALAGES|
|ASALVGES|
|GSALVAES|
|ESALVAGS|
|SSALVAGE|
|SALVAGES|
|SALVAGES|
|SALVAGES|
|SALVAGES|
|SLAVAGES|
|SVALAGES|
|SAALVGES|
|SGALVAES|
|SEALVAGS|
|SSALVAGE|
|SSALVAGE|
|SSALVAGE|
|SSALVAGE|
|SASLVAGE|
|SLSAVAGE|
|SVSALAGE|
|SASALVGE|
|SGSALVAE|
|SESALVAG|
|SSEALVAG|
|SESALVAG|
|SSEALVAG|
|SSEALVAG|
|SSAELVAG|
|SSLEAVAG|
|SSVEALAG|
|SSAEALVG|
|SSGEALVA|
|ESGSALVA|
|ESSGALVA|
|ESGSALVA|
|ESSGALVA|
|ESSGALVA|
|ESSAGLVA|
|ESSLGAVA|
|ESSVGALA|
|ESSAGALV|
|GSSAEALV|
|GESASALV|
|GESSAALV|
|GESASALV|
|GESSAALV|
|GESSAALV|
|GESSAALV|
|GESSLAAV|
|GESSVAAL|
|AESSVGAL|
|AGSSVEAL|
|AGESVSAL|
|AGESSVAL|
|AGESVSAL|
|AGESSVAL|
|AGESSVAL|
|AGESSAVL|
|AGESSLVA|
|VGESSLAA|
|VAESSLGA|
|VAGSSLEA|
|VAGESLSA|
|VAGESSLA|
|VAGESLSA|
|VAGESSLA|
|VAGESSLA|
|VAGESSAL|
|LAGESSAV|
|LVGESSAA|
|LVAESSAG|
|LVAGSSAE|
|LVAGESAS|
|LVAGESSA|
|LVAGESAS|
|LVAGESSA|
|LVAGESSA|
word=DIAGNOSE
|DIAGNOSE|
|IDAGNOSE|
|ADIGNOSE|
|GDIANOSE|
|NDIAGOSE|
|ODIAGNSE|
|SDIAGNOE|
|EDIAGNOS|
|DIAGNOSE|
|DIAGNOSE|
|DIAGNOSE|
|DIAGNOSE|
|DAIGNOSE|
|DGIANOSE|
|DNIAGOSE|
|DOIAGNSE|
|DSIAGNOE|
|DEIAGNOS|
|EDIAGNOS|
|DEIAGNOS|
|DEIAGNOS|
|DIEAGNOS|
|DAEIGNOS|
|DGEIANOS|
|DNEIAGOS|
|DOEIAGNS|
|DSEIAGNO|
|EDSIAGNO|
|ESDIAGNO|
|EDSIAGNO|
|EDSIAGNO|
|EDISAGNO|
|EDASIGNO|
|EDGSIANO|
|EDNSIAGO|
|EDOSIAGN|
|SDOEIAGN|
|SEDOIAGN|
|SEODIAGN|
|SEDOIAGN|
|SEDOIAGN|
|SEDIOAGN|
|SEDAOIGN|
|SEDGOIAN|
|SEDNOIAG|
|OEDNSIAG|
|OSDNEIAG|
|OSEDNIAG|
|OSENDIAG|
|OSEDNIAG|
|OSEDNIAG|
|OSEDINAG|
|OSEDANIG|
|OSEDGNIA|
|NSEDGOIA|
|NOEDGSIA|
|NOSDGEIA|
|NOSEDGIA|
|NOSEGDIA|
|NOSEDGIA|
|NOSEDGIA|
|NOSEDIGA|
|NOSEDAGI|
|GOSEDANI|
|GNSEDAOI|
|GNOEDASI|
|GNOSDAEI|
|GNOSEDAI|
|GNOSEADI|
|GNOSEDAI|
|GNOSEDAI|
|GNOSEDIA|
|ANOSEDIG|
|AGOSEDIN|
|AGNSEDIO|
|AGNOEDIS|
|AGNOSDIE|
|AGNOSEDI|
|AGNOSEID|
|AGNOSEDI|
|AGNOSEDI|
word=AGROUND
|AGROUND|
|GAROUND|
|RAGOUND|
|OAGRUND|
|UAGROND|
|NAGROUD|
|DAGROUN|
|AGROUND|
|AGROUND|
|AGROUND|
|AGROUND|
|ARGOUND|
|AOGRUND|
|AUGROND|
|ANGROUD|
|ADGROUN|
|DAGROUN|
|ADGROUN|
|ADGROUN|
|AGDROUN|
|ARDGOUN|
|AODGRUN|
|AUDGRON|
|ANDGROU|
|DANGROU|
|DNAGROU|
|DANGROU|
|DANGROU|
|DAGNROU|
|DARNGOU|
|DAONGRU|
|DAUNGRO|
|NAUDGRO|
|NDAUGRO|
|NDUAGRO|
|NDAUGRO|
|NDAUGRO|
|NDAGURO|
|NDARUGO|
|NDAOUGR|
|UDAONGR|
|UNAODGR|
|UNDAOGR|
|UNDOAGR|
|UNDAOGR|
|UNDAOGR|
|UNDAGOR|
|UNDAROG|
|ONDARUG|
|OUDARNG|
|OUNARDG|
|OUNDARG|
|OUNDRAG|
|OUNDARG|
|OUNDARG|
|OUNDAGR|
|RUNDAGO|
|RONDAGU|
|ROUDAGN|
|ROUNAGD|
|ROUNDAG|
|ROUNDGA|
|ROUNDAG|
|ROUNDAG|
#################
Kenneth A. Wolcott
I/S AT Money/Assets - Purchase, Inventory, Contracts, Assets, & Project
QA Load specialist
Ext. 36430
| |
| Peter Cornelius 2006-01-10, 4:02 am |
| Jupiter host has a good point about not reinventing the wheel but it
might still be educational to fix this code. There's an interesting
warning if you run this with '-w':
word=NERO
|NERO|
|ENRO|
|RNEO|
|ONER|
Use of uninitialized value in join or string at ./anagram.pl line 33.
|NERO|
Use of uninitialized value in join or string at ./anagram.pl line 33.
If you take a look at your loop conditions you should be able to
figure out why this is happening. You might use the other version of
the 'for' construct to keep you from hitting this again.
for my $word (@words) {
....
}
-PC
On Dec 30, 2005, at 12:23 PM, Wolcott, Kenneth A wrote:
> Hi;
>
> I have enclosed both the perl source and the associated output of a
> bruce-force anagram script that I wrote that has a logic error in it
> that I can't find.
>
> It does not generate all of the permutations of the letters in the
> words specified. Why not?
>
> Secondly, on the matter of efficiency, I could push the results
> into a
> hash, then sort the hash to print out unique permutations. Even
> better
> yet, a better algorithm that wouldn't generate multiple permutations.
> And one better yet, usage of an external dictionary lookup to
> eliminate
> the permutations that aren't words. But I need help on the logic
> error
> first :-)
>
> Thanks,
> Ken Wolcott
>
> #################
> use strict;
>
> my @words = ("NERO", "TOOLED", "MEALS", "DOMAINS", "NERVED",
> "TRADUCE",
> "COUNTS", "SALVAGES", "DIAGNOSE", "AGROUND");
>
> for (my $w=0; $w<@words; $w++) {
> print "word=".$words[$w]."\n";
> my @letters = split //, $words[$w];
> for (my $i=0; $i<=length($words[$w]); $i++) {
> for (my $j=0; $j<=length($words[$w]); $j++) {
> # next if ($i == $j);
> ($letters[$i], $letters[$j]) = ($letters[$j], $letters[$i]);
> my $new_word = join "", @letters;
> print "|".$new_word . "|\n";
> }
> }
> }
> #################
| |
| Chris Charley 2006-01-10, 4:02 am |
|
----- Original Message -----
From: ""Wolcott, Kenneth A"" <KWOLCOTT@amfam.com>
Newsgroups: perl.beginners
To: <beginners@perl.org>
Sent: Friday, December 30, 2005 3:23 PM
Subject: please help find logic error in home-brewed brute force anagram
solver/creator script
Hi;
I have enclosed both the perl source and the associated output of a
bruce-force anagram script that I wrote that has a logic error in it
that I can't find.
It does not generate all of the permutations of the letters in the
words specified. Why not?
[snip]
And one better yet, usage of an external dictionary lookup to eliminate
the permutations that aren't words. But I need help on the logic error
first :-)
Thanks,
Ken Wolcott
Hello Ken,
The code (and its results below) indeed do check each word against a
dictionary.
Chris
#!/usr/bin/perl
use strict;
use warnings;
my %dict;
while (<> ) {
chomp;
my $key = lc join "", sort split "";
push @{$dict{$key}}, $_;
}
my @words = ("NERO", "TOOLED", "MEALS", "DOMAINS", "NERVED", "TRADUCE",
"COUNTS", "SALVAGES", "DIAGNOSE", "AGROUND");
for (@words) {
my $key = lc join "", sort split "";
if ($dict{$key}) {
print "$_: @{$dict{$key}}\n";
}
else {
print "$_\n";
}
}
__END__
C:\perlp>perl t4.pl \usr\dict\wordnet
NERO: nero reno
TOOLED: looted toledo
MEALS: males meals salem selma
DOMAINS: domains madison
NERVED: denver vender
TRADUCE: traduce
COUNTS: counts tucson
SALVAGES: salvages
DIAGNOSE: diagnose
AGROUND: aground
|
|
|
|
|