Programming Exercise #2

[Kristi]

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

[Novo]

PHP Code:

function anagramsOf( word )
{
  if ( word == "jew" )
    return {"jew", "wej", "wje", "jwe", "ewj", "ejw" };
  else echo("This feature isn't implemented yet.")
} 


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

PHP Code:

function anagramsOf( word )
{
  if ( word == "jew" )
    return {"jew"};
  else echo("This feature isn't implemented yet.")
} 


Still O(1)! I'm good.

[Kristi]

Originally Posted by Novo

PHP Code:

function anagramsOf( word )
{
  if ( word == "jew" )
    return {"jew", "wej", "wje", "jwe", "ewj", "ejw" };
  else echo("This feature isn't implemented yet.")
} 


=D Is O(1)!

those aren't even real words. Fail

[Novo]

Originally Posted by Kristi

those aren't even real words. Fail

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

[Tolnaftate2004]

Originally Posted by Novo

Still O(1)! I'm good.

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...

[Kristi]

Originally Posted by Tolnaftate2004

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

The hard part is getting all of the arrangements in N!...

what does n represent

[Tolnaftate2004]

Originally Posted by Kristi

what does n represent

The length of the word passed.

[Kristi]

Originally Posted by Tolnaftate2004

The length of the word passed.

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

[DustyPorViva]

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

[Tolnaftate2004]

Originally Posted by Kristi

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

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).

[Kristi]

Originally Posted by Tolnaftate2004

Are we given said dictionary?

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

[Dan]

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*

Originally Posted by fowlplay4

Dictionary
Heres my functions , while playing with this script you'll find many funny definitions. LOL

PHP Code:

function Define(word) {
 temp.link = "http://www.onelook.com/?w=" @ word @ "&ls=a";
 echo("Requesting Definition of" SPC word @ ":");
 temp.req = requesturl(temp.link);
 this.catchevent(temp.req,"onReceiveData","onDefine");
}
function onDefine(obj) {
 temp.toks = obj.fulldata.tokenize("\n");
 for(b: temp.toks) {
  if (b == "<LI>") continue;
  if (b.starts("<LI>") > 0) {
   temp.ntoks = b.tokenize(";");
   temp.npos = temp.ntoks[2].pos("(");
   temp.defin = temp.ntoks[2].substring(0,temp.npos);
   if (temp.defin.length() > 1) echo(" - " @ temp.defin);
   temp.msg++;
  }
 }
 if (temp.msg == 0) echo("No Definitions Found!");
} 


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

[Kristi]

Originally Posted by Dan

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

*swings magic wand to gather thread*

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

[napo_p2p]

Originally Posted by Tolnaftate2004

Now I just need some inDictionary(word).

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...

[Tolnaftate2004]

Originally Posted by Kristi

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

Well is this dictionary stored by my choice of method?

[Chompy]

PHP Code:


/* Loops through a given wordlist
    
    First checks if the current word in the wordlist
    contains the letters the checking word does

    then checks the length of the current
    word and the checking word
*/
function findanagram(word) {
  temp.wordlist = getwordlist();
  temp.matches = "";
  for(temp.currentword : wordlist) {
    temp.y = "";
    temp.cword = uppercase(currentword);
    temp.word2 = uppercase(word);
    // Checking 
    for(temp.i = 0; i < cword.length(); i++) {
      if (word2.pos(cword.charat(i)) > -1) y @= "y";
      else y @= "n";
    }
    if (y.pos("n") == -1) { // Checking purposes
      temp.locw = cword.trim().length(); // length of currentword (for loop)
      temp.low = word2.trim().length(); // length of word (params)
      if (locw == low) {// if length of both comparing words are the same
        if (currentword != word) matches @= currentword @", ";
      }
    }
  }
  if (matches.length() > 0) { 
    return matches;
  }
}
// Edit this to return the wordlist used
function getwordlist() {
  temp.list.loadlines("temp/wordlist.txt");
  return list;
} 


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

[Tolnaftate2004]

Originally Posted by Chompy

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

[Kristi]

Originally Posted by Tolnaftate2004

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!

[Tolnaftate2004]

Originally Posted by Kristi

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

[Kristi]

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...

[Tigairius]

Originally Posted by Kristi

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

[Tolnaftate2004]

Originally Posted by Tigairius

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...