Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling

Anagram Solver

by kilinrax (Deacon)
on Jan 08, 2001 at 21:40 UTC ( #50522=snippet: print w/replies, xml ) Need Help??
Description: While trying to solve an evilly cryptic crossword over Christmas, I idly remarked that it would be a whole lot easier to solve if I had my laptop, then i could use "grep '^..b..s..c$' /usr/share/dict/words" instead of one those 'crossword solver' books, and that I could probably write an anagram solver in a line of Perl.
Meeting a certain amount of disbelief, I decided to prove a point ;-P

(disclaimer: employ caution in using the code below with more than nine letters - generating the hash is order N! - it takes ~six minutes on my PII-300 to do a ten-letter word, and can result in treacle-like system loads)
perl -e 'sub c { my $w = shift; if ($#_) { for $i (0..$#_) { my @w = @
+_; &c ($w . splice (@w, $i, 1), @w); } } else { $p{ $w . $_[0] } = q(
+) } }; &c ( q(), split //, $ARGV[0] ); $\ = qq(\n); open D, q(/usr/sh
+are/dict/words); while(<D>) { chomp; s!\s+!!; print if exists $p{$_};
+ }' ___LETTERS___
Replies are listed 'Best First'.
Re (tilly) 1: Anagram Solver
by tilly (Archbishop) on Jan 08, 2001 at 22:11 UTC
    I suggest following the approach I took in Find anagrams of mapping words to a canonical form, rather than mapping words to every possible permutation.
Re: Anagram Solver
by salvadors (Pilgrim) on Jan 08, 2001 at 22:24 UTC

    A much speedier and shorter version would be: perl -e '$\=$/;sub c{join"",sort split//,lc pop}$l=c(pop);for(<>){chop;c(lc$_)eq$l&&print}'</usr/share/dict/words YOUR_WORD


    Update: trimmed another 14 characters...

    Update2: trimmed another 19 ...

      That's pretty tidy, for sure. It will even work on a DOS command line. Maybe you'd be interested in shortening what follows?

      I worked an absurdly long time on it, trying to understand how hashes of arrays work. It borrows heavily from something by jcwren and from the Cookbook:

      perl -e ' use strict; foreach (map {split} map {lc}<>){ push @{ $ARGV[0] {glue => sort split // }}, $_}; foreach (values %{$ARGV[0]}){my %seen=(); my @anagrams= grep{ ! $seen{$_}++ } @$_ ; print join (" " => @anagrams>1 ? @anagrams : next ), $/ }'

      This doesn't filter out non-alpha stuff, but it does eliminate duplicates. It's not quite as flexible as yours, either, but it does take words from STDIN ( - it's too long for in Windows, but it can be shortened - I'd leave in strict, though. There's funny stuff going on here that could cause unpredict- able results if the wrong thing is put on the command-line).

      It will also take a redirect from any file (not just lists).

      So, it could be used as "perl -e '..etc...' < ${pathto}/wirds to find anagram in that dictionary (yeesh). No globbing.

      Or, it can be invoked as "perl -e '..etc..'__Type Words__ followed by CTRL-D to exit.
      I hope it's at least amusing.

      It seems that your trimming will make the code less efficient, as you are now reading the entire word list into memory at once. I would have liked to have seen your original code preserved and the golf versions added as a separate node.

      Anyway, here's 12 more characters taken off (after Update2): perl -le'sub c{join"",sort split//,lc pop}$l=c pop;chop,c(lc)eq$l&&print for<>'

        Here's 12 more characters taken off..


        -l switch to save 6 characters. Must remember that. In fact must learn a lot more of the command line switches.

        I should really have spotted the spurious space at the start, the calling the sub without ()s, the needless $_, and being able to remove the () on the for by moving the for to the end though ...

        That gets the actual 'executable' code down to 69 characters now, which I think is much more in keeping with the original "do it one line" ideal..

        You want it in one line? Does it have to fit in 80 columns? :-) 
           --Larry Wall in <7349@jpl-devvax.JPL.NASA.GOV>


Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: snippet [id://50522]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (2)
As of 2022-05-25 04:28 GMT
Find Nodes?
    Voting Booth?
    Do you prefer to work remotely?

    Results (84 votes). Check out past polls.