Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

Re: literati cheat / finding words from scrambled letters

by gryphon (Abbot)
on Nov 20, 2005 at 22:50 UTC ( #510305=note: print w/replies, xml ) Need Help??

in reply to literati cheat / finding words from scrambled letters

Greetings sulfericacid,

After only a brief bit of thought, two options come to mind: the "top down" and "bottom up" methods (thus named because I can't think of a better name right now). The "top down" approached would be to write a script that:

  1. Accepts the up-to-7-character as input
  2. Rearranges the letters to create a list of all possible combinations
  3. Compares each combination to a dictionary file
  4. Where there's a match, print it

That may not be the fastest script to run, but it would work, and it would be fairly easy to code and very easy to setup (just a single script and a dictionary file). However, the "bottom up" approach would probably be faster to run. In this approach, you do all the work up front:

  1. Write a "setup" script to read a dictionary file
  2. For each word in the file, sort the letters and store the results in a hash of arrays where the key is the sorted letters and the value is an arrayref that you push the original word on to
  3. # Kind of like this... push( @{ $data{ join('', sort split(//, $word)) } }, $word );
  4. Save the monsterous hash somewhere; you could stick it in a simple database, XML file, CSV, or whatever; maybe a BerkleyDB would be a good idea
  5. Then write "search" script that accepts the up-to-7-character as input
  6. Sort the letters and seek that key
  7. Now just print out the array's contents
  8. # Kind of like this... print join("\n", @{ $data{ join('', sort split(//, $input)) } }), "\n" +;

The second option would be more difficult to implement, and it would require some setup time to run, but the "production" version would be faster (I'm guessing) than the "top down" method for two reasons: During a run, the first option has to create and search against every possible combination of letters. For larger inputs (those approaching 7), this could be slow. The second option only has to sort the input and lookup the value; thus it's very fast.

I hope this helps out.

gryphon Development Manager (DSMS)
code('Perl') || die;

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://510305]
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: (5)
As of 2021-03-05 01:48 GMT
Find Nodes?
    Voting Booth?
    My favorite kind of desktop background is:

    Results (108 votes). Check out past polls.