Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

(un)jumbler...

by stevenrh (Beadle)
on Nov 09, 2004 at 17:25 UTC ( [id://406399]=perlquestion: print w/replies, xml ) Need Help??

stevenrh has asked for the wisdom of the Perl Monks concerning the following question:

I am looking to make a script that will scramble/jumble a word, and reference a dictionary file to output proper words...

I am mostly looking for the right module/correct direction to head in for this.

Here's what i hope to accomplish:
take the word from <STDIN>, chomp it, and take each possible combination of letters, compare each combination to a dictionary file, and print it to the screen.

for example, I would like to plug in the word "dude," and get the legit words like "due" and "dud"

thanks :) Update,/b>

Replies are listed 'Best First'.
Re: (un)jumbler...
by ikegami (Patriarch) on Nov 09, 2004 at 17:45 UTC

    The following gives you a sorted list, so it should be easy to check against a sorted dictionary (by doing something like a merge sort). It's also memory efficient since it doesn't keep a list of all the permutations in memory.

    use Algorithm::Loops qw( NextPermute ); my $word = 'tool'; my @list = sort ' ', $word =~ /(.)/g; my $last_word = ''; while (NextPermute(@list)) { my $new_word = join('', @list); $new_word =~ s/ .*//; next if ($new_word eq $last_word); $last_word = $new_word; print($new_word, $/); }

    Output:

      Update: Made to work with /usr/share/dict/words which contains uppercase words.

      Well, I went and wrote the code to check against the dictionary.

      use strict; use warnings; use Algorithm::Loops qw( NextPermute ); sub get_next_dict_word { my ($dict_fh) = @_; for (;;) { local $_ = <$dict_fh>; return $_ unless defined; my $first_letter = substr($_, 0, 1); return $_ if lc($first_letter) eq $first_letter; } } { die("Specify the word as an argument.$/") unless @ARGV; my $word = lc($ARGV[0]); # DICTIONARY MUST BE SORTED, ONE WORD PER LINE. # UPPERCASE WORDS ARE IGNORED. my $dict_fh; open($dict_fh, '<', '/usr/share/dict/words') or die("Can't open dictionary: $!$/"); my $dict_word = <$dict_fh>; chomp($dict_word) if defined $dict_word; my @list = sort ' ', $word =~ /(.)/g; my $last_permute = ''; while (NextPermute(@list)) { my $permute = join('', @list); $permute =~ s/ .*//; next if ($permute eq $last_permute); $last_permute = $permute; while (defined($dict_word) && $dict_word lt $permute) { $dict_word = <$dict_fh>; chomp($dict_word) if defined $dict_word; } if (defined($dict_word) && $permute eq $dict_word) { print("Found $permute$/"); $dict_word = <$dict_fh>; chomp($dict_word) if defined $dict_word; } else { print("Didn't find $permute$/"); } } } dictionary used --------------- apple dud dude dudette due orange output ------ Didn't find d Didn't find dd Didn't find dde Didn't find ddeu Didn't find ddu Didn't find ddue Didn't find de Didn't find ded Didn't find dedu Didn't find deu Didn't find deud Didn't find du Found dud Found dude Found due Didn't find dued Didn't find e Didn't find ed Didn't find edd Didn't find eddu Didn't find edu Didn't find edud Didn't find eu Didn't find eud Didn't find eudd Didn't find u Didn't find ud Didn't find udd Didn't find udde Didn't find ude Didn't find uded Didn't find ue Didn't find ued Didn't find uedd
        Thank you. You have been most helpful!!! I just need to get the module, and depending onhoe successful that goes...I will be returning to thank you One Thousand more times :)
Re: (un)jumbler...
by Anonymous Monk on Nov 09, 2004 at 17:53 UTC
    You can use Math::Combinatorics for this. Something like:
    use Math::Combinatorics; for (`cat /usr/share/dict/words`) { chomp; $real_words{$_}++ } while (<STDIN>) { chomp; my @letters = split //; foreach my $word_len (1 .. @letters) { foreach my $combination (combine($word_len, @letters)) { foreach my $permutation (permute(@$combination)) { my $word = join '', @$permutation; print "$word\n" if $real_words{$word}; } } } }
Re: (un)jumbler...
by bgreenlee (Friar) on Nov 09, 2004 at 17:37 UTC

    You're not trying to cheat at Scrabble, are you? :-)

    This post might get you started: Scrabbler

    -b

      well....ummm, well.....not trying to cheat at scrabble....just Jumble :)
Re: (un)jumbler...
by PreferredUserName (Pilgrim) on Nov 09, 2004 at 22:06 UTC
    BTW, here's an "Official Scrabble Player's Dictionary" file:
    http://www.calvin.edu/~rpruim/scrabble/ospd3.txt

    It should be the same as the paperback books of the same name. As a little joke, it really *isn't* the official Scrabble player's dictionary, since it doesn't have the naughty words:

    http://home.teleport.com/~stevena/scrabble/expurg.html

    There are various other incarnations of the list floating around (search for SOWPODS, e.g.).

Re: (un)jumbler...
by hv (Prior) on Nov 10, 2004 at 14:33 UTC

    I have a crossword helper program 'word' that will let you do this: '-a' specifies anagram and '-u' specifies a subset of the supplied letters, so I'd use it so:

    zen% word -ua dude de dud dude due dued Ed zen%

    The program always constructs a single regexp that matches the things it's searching for, in this case:

    /^(?:(?:([eu])(?!.*\1)|([d])(?!.*\2.*\2))+)\z/oi

    Hugo

Re: (un)jumbler...
by BrowserUk (Patriarch) on Nov 09, 2004 at 17:40 UTC

    Update: Ignore this. It's broken. See ikegami's post below.

    perl -lne"BEGIN{ $x=join'',sort split'',shift }" -e"1+index( $x, join'',sort split'', $_ ) and print" dude words de dude due ed ude

    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
    "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
      What about d, dd, dde, ddeu, ddu, ddue, ded, dedu, deu, du, dud, due, e, edd, eddu, edu, edud, eu, eud, eudd, u, ud, udd, udde, uded, ue, ued and uedd? (One of which is actually a word!)

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://406399]
Approved by bgreenlee
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (4)
As of 2024-03-29 10:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found