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?