\ Article: 97346 of comp.lang.forth \ Path: tunews.univie.ac.at!aconews-feed.univie.ac.at!newsfeed.wu-wien.ac.at!newsfeed.utanet.at!newsfeed01.chello.at!feed.news.tiscali.de!news.maxwell.syr.edu!postnews1.google.com!not-for-mail \ From: iano@quirkster.com (Ian Osgood) \ Newsgroups: comp.lang.forth \ Subject: Re: Pronounce it [contest] \ Date: 27 Jan 2004 21:00:32 -0800 \ Organization: http://groups.google.com \ Lines: 101 \ Message-ID: <7ec890f8.0401272100.3acbd388@posting.google.com> \ References: <90233230223563@frunobulax.edu> <7ec890f8.0401271204.4f271ce1@posting.google.com> \ NNTP-Posting-Host: 63.105.26.46 \ Content-Type: text/plain; charset=ISO-8859-1 \ Content-Transfer-Encoding: 8bit \ X-Trace: posting.google.com 1075266032 29925 127.0.0.1 (28 Jan 2004 05:00:32 GMT) \ X-Complaints-To: groups-abuse@google.com \ NNTP-Posting-Date: Wed, 28 Jan 2004 05:00:32 +0000 (UTC) \ Xref: tunews.univie.ac.at comp.lang.forth:97346 \ \ iano@quirkster.com (Ian Osgood) wrote in message news:<7ec890f8.0401271204.4f271ce1@posting.google.com>... \ > mhx@iae.nl (Marcel Hendrix) wrote in message news:<90233230223563@frunobulax.edu>... \ > > \ > > The total computation took some 27 hours. (From 07:01:58, January 22, 2004 \ > > to 10:03:58, January 23, 2004). I've put the anagram generator, it's dawg filter \ > > and the complete log for "forth is great" at \ > > http://home.iae.nl/users/mhx/programs.html . \ > > \ > > -marcel \ > \ > You should be able to reduce the search time to a few seconds by using \ > the set of letters to constrain a DAWG traversal, O(number of \ > results), rather than generating every possible permutation and \ > filtering through those anagrams composed entirely of legal words, \ > O(number of permutations). (Time to dig out my old anagramer and \ > translate it into Forth.) \ > \ > Ian \ \ (Written on the bus ride home from work today. :) \ \ ============= anagram.f ================ \ anagram generator, using a Directed Acyclic Word Graph \ uses: ?c>let let>c Let EOW EOB Ind dawg-root dawg@i include dawg.fs include dawg2.fs \ letters + let is the number of each letter in the anagram \ letters is the total count of letters (and spaces) create letters 27 cells allot : more-left? letters @ ; : remove-let ( let -- TF ) cells letters + dup @ dup if 1- swap ! -1 letters +! TRUE else nip ( 0 ) then ; : replace-let ( let -- ) cells letters + 1 swap +! 1 letters +! ; \ optional: each space increases words allowed in the anagram variable max-words : init-phrase ( addr len -- ) letters 27 cells erase 0 max-words ! \ optional bounds do I c@ ?c>let ?dup if replace-let else 1 max-words +! then loop ; variable num-found variable result-len create result 80 chars allot : result+c ( c -- ) result result-len @ + c! 1 result-len +! ; : solve ( block -- ) cell- begin cell+ dup @ Let remove-let if dup @ Let let>c result+c more-left? if dup @ EOW if max-words @ if -1 max-words +! \ optional bl result+c dawg-root recurse -1 result-len +! 1 max-words +! then \ optional then dup @ Ind ?dup if dawg@i recurse then else dup @ EOW if 1 num-found +! cr result result-len @ type then then -1 result-len +! dup @ Let replace-let then dup @ EOB until drop ; : anagrams" ( blah blah" -- ) [char] " parse init-phrase 0 result-len ! 0 num-found ! cr dawg-root solve cr space num-found @ . ." anagrams found" cr ; \ The following generates 67770 anagrams in 65 seconds \ using gforth 0.5.0 on a G4-500. \ load-dawg \ anagrams" forth is great" \ bye \ ============== Ian Osgood ==================