Programming Exercise #2
 

Problem: Make an anagram finder.

Say what?!?
An anagram is a word that uses the same letters as another word. For example, santa and satan are anagrams.

The exercise is to propose and/or code the best and most efficient way to find all anagrams for a word. For our purposes, assume you're using an english dictionary.

Go go go

=D Is O(1)! Wait? Do anagrams have to be dictionary words?

Still O(1)! I'm good.

those aren't even real words. Fail

Umm... You crazy? Or you just neglected my improvement, punk?

With any luck, we should be able to get O(N!) [for single-word anagrams], or so, I'm thinking.

edit: Recursion can be used to get the arrangements, working on that...

what does n represent

The length of the word passed.

yes but you also have to find which arrangements are actually words in the dictionary.... fun fun fun

I'm not gonna write it out, but I say just have a script that links to a website that solves anagrams :o

Are we given said dictionary?

edit:

NPC Code:

---

function arrange(letters,first) {

  temp.len = letters.length();

  if (first == 0) first = "";

  if (temp.len > 1) {

    temp.returns.clear();

    temp.htable = {0,0,0,0,0,0,0,0,0,0,0,0,0,

                  0,0,0,0,0,0,0,0,0,0,0,0,0,1};

    for (temp.i=0; temp.i<temp.len; temp.i++) {

      temp.letter = letters.charat(temp.i).tolower();

      temp.hindex = (max(96,min(123,getascii(temp.letter)))-97)%27; // maps characters outside of a-z to htable[26]

      if (temp.htable[temp.hindex] == 0) {

        temp.htable[temp.hindex] = 1;

        temp.pref= first @ temp.letter;

        temp.endings = arrange(letters.substring(0,temp.i) @ letters.substring(temp.i+1),temp.pref);

        temp.returns.addarray(temp.endings);

      }

    }

    return temp.returns;

  }

  else {

    temp.word = first @ letters.tolower();

    if (inDictionary(temp.word))

      return {temp.word};

    else return char(0);

  }

}

---

Now I just need some inDictionary(word).

assumption says theres a dictionary. you cant just return all possible combinations of the letters

I guess we should just load those word combinations generated, with some dictionairy script (it's around here somewhere).

*swings magic wand to gather post*

Perhaps change that into returning 'temp.msg > 0'. Could need some better dictionary maybe.

thats definitely not the most efficient way at all. just getting it done and doing it efficiently are two different things. this is often your faults ;)

Just say that you've made this.wordlist a sorted array of all known words in the english dictionary. Then for inDictionary() do a binary search or something on that list.

Is that cheating? Although, it probably isn't very efficient in terms of the memory needed to hold such a list...

Well is this dictionary stored by my choice of method?

And you need to set maxlooplimit if your wordlist count is higher then the loop limit :o

Edit getwordlist() at the bottom to return the wordlist used. I used a wordlist which I uploaded to temp (if anyone wants to try with that I can rar it and attach, but you might need to edit it (graal doesn't like to loop through 317k words :()) :O

And.. don't hurt me if this isn't a good anagram finder :(

For words longer than 9 unique letters this is "eh, it's 'okay'."

In a perfect world, we could have a dictionary in a sort of hash table:

NPC Code:

---

function anagrams( word )

  sort letters in word;

  calculate hashkey from letters;

  return hashtable[hashkey];

---

TADAA

thats almost what i was looking for!

You want the hash algorithm? I'm thinking a hash table of about 30^26 elements would do the job. :P

I'm guessing this hasn't been touched long enough no one will add to this.
I would have presorted a file of all known words with the letters arranged in alphabetical order, then just saved that and used it until the end of time.
example line from file:
aanst=santa,satan,etc
then when given a word, sort it and look it up (very fast).
now if someone wants to take the best shot coding the sorting of the word file and the look up in gscript...

This isn't exactly how you described it, using a less efficient method, but it works decently fast for what it does.

http://forums.graalonline.com/forums...ad.php?t=81856

From what I can see it's a lot slower (something to the order of number-of-words-in-the-dictionary slower).
edit: I just watched the video and it makes me think that it might be slower than that even...