Graal Forums

Graal Forums (https://forums.graalonline.com/forums/index.php)
-   NPC Scripting (https://forums.graalonline.com/forums/forumdisplay.php?f=8)
-   -   Programming Exercise #3 (https://forums.graalonline.com/forums/showthread.php?t=79189)

Tolnaftate2004 03-26-2008 02:44 AM

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.

cbk1994 03-26-2008 02:52 AM

Do we need to find every pattern possible, or just ones specified?

For example,

findAllPatterns( n )

or something like

findNumber( n, pattern )

DrakilorP2P 03-26-2008 03:25 AM

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



cbk1994 03-26-2008 05:05 AM

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.

Tolnaftate2004 03-26-2008 07:34 AM

Quote:

Originally Posted by DrakilorP2P (Post 1382414)
Assuming that the algorithm should find the number of occurrences of a string in another string.

Nooooooot quite.

Quote:

Originally Posted by cbkbud (Post 1382427)
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)

Inverness 03-26-2008 08:16 AM

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;



Tolnaftate2004 03-26-2008 09:13 AM

I have updated the guidelines slightly.

DrakilorP2P 03-26-2008 09:59 AM

Quote:

Originally Posted by Tolnaftate2004 (Post 1382436)
I have updated the guidelines slightly.

Why isn't strings of length one considered valid patterns?

Tolnaftate2004 03-26-2008 12:11 PM

Quote:

Originally Posted by DrakilorP2P (Post 1382443)
Why isn't strings of length one considered valid patterns?

A solid color does not a pattern make.

Inverness 03-26-2008 01:28 PM

No comment on what I posted?

You've irritated me.

xXziroXx 03-26-2008 02:05 PM

How about making Programming Exercise #4 something that we normal mortals stand a chance at? :whatever:

DrakilorP2P 03-26-2008 05:13 PM

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 


Crow 03-26-2008 05:26 PM

Quote:

Originally Posted by cbkbud (Post 1382427)
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.

Tolnaftate2004 03-26-2008 07:26 PM

Quote:

Originally Posted by Inverness (Post 1382448)
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. ;)

Inverness 03-26-2008 09:40 PM

Quote:

Originally Posted by Tolnaftate2004 (Post 1382481)
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;




All times are GMT +2. The time now is 12:37 PM.

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