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?