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, 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
  #7  
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
  #8  
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
  #9  
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
  #10  
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
  #11  
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
  #12  
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
  #13  
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
  #14  
Old 03-26-2008, 09:49 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
What the hell are you talking about?
This is big O notation, it is how we measure the efficiency of algorithms, without being hardware-specific. The O stands for order, which can take 2 meanings:
  1. In mathematics, O(f) is for all terms order f and above. f is usually a function where the parameter is much less than 1 (error terms).
  2. In computer science O(f) is the major factor in determining algorithm efficiency. f is a function of n, which is a whole number.

For example, the quicksort algorithm is O(n log n) [for every item to sort, it takes log base 2 of n loops to find its place].
__________________
◕‿‿◕ · 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 10:04 PM..
Reply With Quote
  #15  
Old 03-27-2008, 10:25 PM
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
PHP Code:
function findpatterns(str) {
  
temp.loc 0;
  
temp.temp.str.length();
  
temp.results = new[0];
  
  while (
temp.loc temp.l) {
    
temp.len 2;
    while (
temp.len <= (temp.temp.loc)) {
      
temp.seq temp.str.substring(temp.loctemp.len);
      
temp.("count_" temp.seq)++;
      if (
temp.("count_" temp.seq) == 2) {
        
temp.results.add(temp.seq);
      }
      
temp.len++;
    }
    
temp.loc++;
  }

  for (
temp.rtemp.results) {
    echo(
temp.": " temp.("count_" temp.r));
  }

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

Last edited by napo_p2p; 03-27-2008 at 10:27 PM.. Reason: .
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 03:55 PM.


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