Graal Forums  

Go Back   Graal Forums > Development Forums > NPC Scripting
FAQ Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
Thread Tools Search this Thread Display Modes
  #1  
Old 01-14-2008, 11:38 PM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
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
__________________
Reply With Quote
  #2  
Old 01-15-2008, 02:08 AM
Novo Novo is offline
[TServerDeveloper]
Join Date: Jun 2006
Posts: 448
Novo will become famous soon enough
PHP Code:
function anagramsOfword )
{
  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 anagramsOfword )
{
  if ( 
word == "jew" )
    return {
"jew"};
  else echo(
"This feature isn't implemented yet.")

Still O(1)! I'm good.
Reply With Quote
  #3  
Old 01-15-2008, 02:09 AM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
Quote:
Originally Posted by Novo View Post
PHP Code:
function anagramsOfword )
{
  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
__________________
Reply With Quote
  #4  
Old 01-15-2008, 02:23 AM
Novo Novo is offline
[TServerDeveloper]
Join Date: Jun 2006
Posts: 448
Novo will become famous soon enough
Quote:
Originally Posted by Kristi View Post
those aren't even real words. Fail
Umm... You crazy? Or you just neglected my improvement, punk?
Reply With Quote
  #5  
Old 01-15-2008, 04:02 AM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Novo View Post
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...
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/

Last edited by Tolnaftate2004; 01-15-2008 at 04:43 AM..
Reply With Quote
  #6  
Old 01-15-2008, 04:23 AM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
Quote:
Originally Posted by Tolnaftate2004 View Post
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
__________________
Reply With Quote
  #7  
Old 01-15-2008, 04:36 AM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Kristi View Post
what does n represent
The length of the word passed.
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
Reply With Quote
  #8  
Old 01-15-2008, 05:31 AM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
Quote:
Originally Posted by Tolnaftate2004 View Post
The length of the word passed.
yes but you also have to find which arrangements are actually words in the dictionary.... fun fun fun
__________________
Reply With Quote
  #9  
Old 01-15-2008, 05:57 AM
DustyPorViva DustyPorViva is offline
Will work for food. Maybe
DustyPorViva's Avatar
Join Date: Sep 2003
Location: Maryland, USA
Posts: 9,589
DustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond reputeDustyPorViva has a reputation beyond repute
Send a message via AIM to DustyPorViva Send a message via MSN to DustyPorViva
I'm not gonna write it out, but I say just have a script that links to a website that solves anagrams :o
Reply With Quote
  #10  
Old 01-15-2008, 06:10 AM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Kristi View Post
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).
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/

Last edited by Tolnaftate2004; 01-15-2008 at 09:03 AM..
Reply With Quote
  #11  
Old 01-15-2008, 08:07 AM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
Quote:
Originally Posted by Tolnaftate2004 View Post
Are we given said dictionary?
assumption says theres a dictionary. you cant just return all possible combinations of the letters
__________________
Reply With Quote
  #12  
Old 01-15-2008, 08:44 AM
Dan Dan is offline
Daniel
Join Date: Oct 2007
Posts: 383
Dan is an unknown quantity at this point
Send a message via MSN to 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*

Quote:
Originally Posted by fowlplay4 View Post
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(
btemp.toks) {
  if (
== "<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.
__________________
Reply With Quote
  #13  
Old 01-15-2008, 08:47 AM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
Quote:
Originally Posted by Dan View Post
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
__________________
Reply With Quote
  #14  
Old 01-15-2008, 09:14 AM
napo_p2p napo_p2p is offline
oh snaps
napo_p2p's Avatar
Join Date: Sep 2003
Location: Pismo Beach, California
Posts: 2,118
napo_p2p has a spectacular aura aboutnapo_p2p has a spectacular aura about
Send a message via AIM to napo_p2p Send a message via MSN to napo_p2p
Quote:
Originally Posted by Tolnaftate2004 View Post
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...
__________________
Scito hoc super omnia.
Haec vita est tua una sola.
Dum vita superest, utere maxime quoque puncto, momento, et hora quae habes.
Tempus neminem non manet.
Noli manere tempus.
Carpe Diem

Seize the Day.
Reply With Quote
  #15  
Old 01-15-2008, 06:01 PM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Kristi View Post
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?
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
Reply With Quote
Reply

Tags
anagrams, programming-exercise

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 03:32 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.