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 03-26-2008, 02:44 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
Programming Exercise #3

In a string of N characters, calculate the frequencies of repeated patterns, e.g., given "AUGCCCGTAUACGTA", one would get CGTA:2, CGT:2, GTA:2, CG:2, GT:2, TA:2, AU:2, CC:2. You do not need to display the information, only get the data in a format from which it can be extracted (hopefully in a pattern that is of order less than the algorithm). You may assume that only the letters A-Z will be used to make the given string.

It may help to review Programming Exercises #1 and #2.

Remember, the goal is to make this as efficient as possible with graal script.
Your algorithm will be ranked first by big-O notation, then by runtime speed.
__________________
◕‿‿◕ · 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; 03-27-2008 at 05:49 AM..
Reply With Quote
  #2  
Old 03-26-2008, 02:52 AM
cbk1994 cbk1994 is offline
the fake one
cbk1994's Avatar
Join Date: Mar 2003
Location: San Francisco
Posts: 10,718
cbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond repute
Send a message via AIM to cbk1994
Do we need to find every pattern possible, or just ones specified?

For example,

findAllPatterns( n )

or something like

findNumber( n, pattern )
__________________
Reply With Quote
  #3  
Old 03-26-2008, 03:25 AM
DrakilorP2P DrakilorP2P is offline
Registered User
DrakilorP2P's Avatar
Join Date: Apr 2006
Posts: 755
DrakilorP2P is just really niceDrakilorP2P is just really nice
Assuming that the algorithm should find the number of occurrences of a string in another string. Which it shouldn't.

PHP Code:
function findFrequencyOfPattern(haystackneedle)
{
  
temp.occurrences 0;
  for (
temp.i=0temp.i<haystack.length() - needle.length() + 1temp.i++) {
    if (
haystack.substring(temp.ineedle.length()) == needletemp.occurrences++;
  }
  return 
temp.occurrences;

PHP Code:
temp.haystack "AUGCCCGTAUACGTA";
temp.needles = {"CGTA""CGT""GTA""CG""GT""TA""AU""CC"};
sendrpgmessage(temp.haystack);
for (
temp.needletemp.needles) {
  
sendrpgmessage(temp.needle ": " findFrequencyOfPattern(temp.haystacktemp.needle));

Outputs:
PHP Code:
AUGCCCGTAUACGTA
CGTA
2
CGT
2
GTA
2
CG
2
GT
2
TA
2
AU
2
CC


Last edited by DrakilorP2P; 03-26-2008 at 09:57 AM..
Reply With Quote
  #4  
Old 03-26-2008, 05:05 AM
cbk1994 cbk1994 is offline
the fake one
cbk1994's Avatar
Join Date: Mar 2003
Location: San Francisco
Posts: 10,718
cbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond repute
Send a message via AIM to cbk1994
Okay, I have mine finished. It takes about 5 seconds to run (go figure!) but it gets the right answer, at least from what I have seen.

PHP Code:
StringAUOccurances2
String
CCOccurances2
String
CGOccurances2
String
CGTOccurances2
String
CGTAOccurances2
String
GTOccurances2
String
GTAOccurances2
String
TAOccurances
This is what it outputs in RC.

The script is very inefficient and slow, but it works ...

NOTE: You will need to change the [] in the format to a percent sign, it won't let me post without giving me a bad request error. Look for this line:
echo( format( "String: []s, Occurances: []s", rc[0], rc[1] ) );

PHP Code:
function onCreated()
{
  
temp.includeSingle false// Include ones that only appear once?
  
  
temp."AUGCCCGTAUACGTA";
  
temp.na stringToArrayList);
    
  
temp.occ = {};
  
  for ( 
temp.na )
  {
    
temp.fr findFrequencyn);
    if ( 
temp.fr == && includeSingle == false )
    {
      continue;
    }
    
occ.add( { rtemp.fr } );
  }
  
  for ( 
temp.rc occ )
  {
    echo( 
format"String: []s, Occurances: []s"rc[0], rc[1] ) );
  }
}
function 
stringToArrayListstr )
{
  
temp.= {};
  for ( 
temp.char 0char str.length(); char ++ )
  {
    for ( 
temp.charlen 2charlen str.length() +  charcharlen ++ )
    {
      
temp.count ++;
      
temp.newText str.substringcharcharlen );
      if ( 
newText != str && p.index( @ newText ) == -)
      {
        
p.addnewText );
      }
      if ( 
count >= 100 )
      {
        
sleep.05 );
        
count 0;
      }
    }
  }
  return 
p;
}
function 
findFrequencystrphrase )
{
  
temp.0;
  for ( 
temp.char 0char str.length(); char ++ )
  {
    for ( 
temp.charlen 1charlen str.length() +  charcharlen ++ )
    {
      
temp.count ++;
      
temp.newText str.substringcharcharlen );
      if ( 
newText != str )
      {
        if ( 
newText == phrase )
        {
          
++;
        }
      }
      if ( 
count >= 100 )
      {
        
sleep.05 );
        
count 0;
      }
    }
  }
  return 
o;

This looks for all possible combinations, then finds how often they occur.

Also, if a mod wants to delete my last post in this thread they can, it won't let me edit it or delete it anymore for some reason, gives a Bad Request error.
__________________
Reply With Quote
  #5  
Old 03-26-2008, 07:34 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 DrakilorP2P View Post
Assuming that the algorithm should find the number of occurrences of a string in another string.
Nooooooot quite.

Quote:
Originally Posted by cbkbud View Post
Okay, I have mine finished. It takes about 5 seconds to run (go figure!) but it gets the right answer, at least from what I have seen.
This is closer (), but no doubt we can do better. ~O(n³)
__________________
◕‿‿◕ · 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
  #6  
Old 03-26-2008, 08:16 AM
Inverness Inverness is offline
Incubator
Inverness's Avatar
Join Date: Aug 2004
Location: Houston, Texas
Posts: 3,613
Inverness is a jewel in the roughInverness is a jewel in the rough
PHP Code:
function findpatterns(str) {
  
temp.outc = {};
  
temp.out = {};
  
temp.sub "";
  
temp.0;
  
temp.0;
  
temp.0;

  for (
2str.length(); ++) {
    for (
0str.length(); ++) {
      if (
str.length() - 1) {
        continue;
      }
      
sub str.substring(ei);
      
str.positions(sub);
      if (
p.size() > 1) {
        if (
outc.index(sub) < 0) {
          
outc.add(sub);
          
out.add({subp.size()});
        }
      }
    }
  }
  return 
out;

__________________

Last edited by Inverness; 03-26-2008 at 01:28 PM..
Reply With Quote
  #7  
Old 03-26-2008, 09:13 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
I have updated the guidelines slightly.
__________________
◕‿‿◕ · 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 03-26-2008, 09:59 AM
DrakilorP2P DrakilorP2P is offline
Registered User
DrakilorP2P's Avatar
Join Date: Apr 2006
Posts: 755
DrakilorP2P is just really niceDrakilorP2P is just really nice
Quote:
Originally Posted by Tolnaftate2004 View Post
I have updated the guidelines slightly.
Why isn't strings of length one considered valid patterns?
Reply With Quote
  #9  
Old 03-26-2008, 12:11 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 DrakilorP2P View Post
Why isn't strings of length one considered valid patterns?
A solid color does not a pattern make.
__________________
◕‿‿◕ · 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
  #10  
Old 03-26-2008, 01:28 PM
Inverness Inverness is offline
Incubator
Inverness's Avatar
Join Date: Aug 2004
Location: Houston, Texas
Posts: 3,613
Inverness is a jewel in the roughInverness is a jewel in the rough
No comment on what I posted?

You've irritated me.
__________________
Reply With Quote
  #11  
Old 03-26-2008, 02:05 PM
xXziroXx xXziroXx is offline
Master of Puppets
xXziroXx's Avatar
Join Date: May 2004
Location: Sweden
Posts: 5,288
xXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant future
Send a message via AIM to xXziroXx Send a message via MSN to xXziroXx
How about making Programming Exercise #4 something that we normal mortals stand a chance at?
__________________

"A delayed game is eventually good, but a rushed game is forever bad." - Shigeru Miyamoto
Reply With Quote
  #12  
Old 03-26-2008, 05:13 PM
DrakilorP2P DrakilorP2P is offline
Registered User
DrakilorP2P's Avatar
Join Date: Apr 2006
Posts: 755
DrakilorP2P is just really niceDrakilorP2P is just really nice
Not much to comment. The code and output dump should speak for themselves.
PHP Code:
function findPatterns(theString)
{
  
sendrpgmessage("String: \"" theString "\"");
  
sendrpgmessage("Init at approximately " timevar2);
  
temp.oldTime timevar2;
  
  
temp.patterns = {};
  for (
temp.length=2temp.length<temp.theString.length(); temp.length++) {
    for (
temp.position=0temp.position<temp.theString.length() - temp.length 1temp.position++) {
      
temp.pattern temp.theString.substring(temp.positiontemp.length);
      
temp.("pattern_" temp.pattern)++;
      
      
//Makes iteration through the variables much easier.
      
if (temp.("pattern_" temp.pattern) == 1temp.patterns.add(temp.pattern);
    }
  }
  
  
//Output
  
temp.output = {};
  for (
temp.patterntemp.patterns) {
    if (
temp.("pattern_" temp.pattern) > 1) {
      
temp.output.add({temp.patterntemp.("pattern_" temp.pattern)});
      
sendrpgmessage(temp.pattern ": " temp.("pattern_" temp.pattern));
    }
  }
  
  
temp.deltaTime timevar2 temp.oldTime;
  
sendrpgmessage("Finished at " timevar2 "\nDelta time is " temp.deltaTime);
  
  return 
temp.output;

PHP Code:
String"AUGCCCGTAUACGTA"
Init at approximately 1206544145.230022907
AU
2
CC
2
CG
2
GT
2
TA
2
CGT
2
GTA
2
CGTA
2
Finished at 1206544145.231662034
Delta time is 0.001600027 
Reply With Quote
  #13  
Old 03-26-2008, 05:26 PM
Crow Crow is offline
ǝɔɐɹq ʎןɹnɔ
Crow's Avatar
Join Date: Dec 2006
Location: Germany
Posts: 5,153
Crow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond repute
Quote:
Originally Posted by cbkbud View Post
NOTE: You will need to change the [] in the format to a percent sign, it won't let me post without giving me a bad request error. Look for this line:
echo( format( "String: []s, Occurances: []s", rc[0], rc[1] ) );
Tiny tip: If you post a "normal" post without any % signs, you can just edit it with quick edit afterwards and add them. Won't give an error.
__________________
Reply With Quote
  #14  
Old 03-26-2008, 07:26 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 Inverness View Post
No comment on what I posted?

You've irritated me.
Yours is still O(n³).

e: The new standard set by DrakilorP2P, O(n²)
@Ziro: Will keep that in mind.
__________________
◕‿‿◕ · 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; 03-26-2008 at 07:57 PM..
Reply With Quote
  #15  
Old 03-26-2008, 09:40 PM
Inverness Inverness is offline
Incubator
Inverness's Avatar
Join Date: Aug 2004
Location: Houston, Texas
Posts: 3,613
Inverness is a jewel in the roughInverness is a jewel in the rough
Quote:
Originally Posted by Tolnaftate2004 View Post
Yours is still O(n³).

e: The new standard set by DrakilorP2P, O(n²)
What the hell are you talking about?

Increased speed of script:
PHP Code:
function findpatterns(str) {
  
temp.time timevar2;
  
temp.outc = {};
  
temp.out = {};
  for (
temp.2temp.temp.str.length(); temp.++) {
    for (
temp.0temp.temp.str.length(); temp.++) {
      if (
temp.temp.temp.str.length() - 1) {
        continue;
      }
      
temp.sub temp.str.substring(temp.etemp.i);
      
temp.temp.str.positions(temp.sub);
      if (
temp.p.size() > 1) {
        if (
temp.outc.index(temp.sub) < 0) {
          
temp.outc.add(temp.sub);
          
temp.out.add(temp.sub ":" temp.p.size());
        }
      }
    }
  }
  echo(
"Time: " timevar2 temp.time);
  return 
temp.out;

__________________
Reply With Quote
Reply

Tags
pattern-matching, 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 07:47 PM.


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