http://qs321.pair.com?node_id=510305


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
Whitepages.com Development Manager (DSMS)
code('Perl') || die;