Graal Forums - Programming Exercise #3

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)

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.

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

For example,

findAllPatterns( n )

or something like

findNumber( n, pattern )

Assuming that the algorithm should find the number of occurrences of a string in another string. Which it shouldn't.

PHP Code:


		
			
function findFrequencyOfPattern(haystack, needle)

{

  temp.occurrences = 0;

  for (temp.i=0; temp.i<haystack.length() - needle.length() + 1; temp.i++) {

    if (haystack.substring(temp.i, needle.length()) == needle) temp.occurrences++;

  }

  return temp.occurrences;

}

PHP Code:


		
			
temp.haystack = "AUGCCCGTAUACGTA";

temp.needles = {"CGTA", "CGT", "GTA", "CG", "GT", "TA", "AU", "CC"};

sendrpgmessage(temp.haystack);

for (temp.needle: temp.needles) {

  sendrpgmessage(temp.needle @ ": " @ findFrequencyOfPattern(temp.haystack, temp.needle));

}

Outputs:

PHP Code:


		
			
AUGCCCGTAUACGTA

CGTA: 2

CGT: 2

GTA: 2

CG: 2

GT: 2

TA: 2

AU: 2

CC: 2

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:


		
			
String: AU, Occurances: 2
String: CC, Occurances: 2
String: CG, Occurances: 2
String: CGT, Occurances: 2
String: CGTA, Occurances: 2
String: GT, Occurances: 2
String: GTA, Occurances: 2
String: TA, Occurances: 2

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.n = "AUGCCCGTAUACGTA";
  temp.na = stringToArrayList( n );
    
  temp.occ = {};
  
  for ( temp.r : na )
  {
    temp.fr = findFrequency( n, r );
    if ( temp.fr == 1 && includeSingle == false )
    {
      continue;
    }
    occ.add( { r, temp.fr } );
  }
  
  for ( temp.rc : occ )
  {
    echo( format( "String: []s, Occurances: []s", rc[0], rc[1] ) );
  }
}
function stringToArrayList( str )
{
  temp.p = {};
  for ( temp.char = 0; char < str.length(); char ++ )
  {
    for ( temp.charlen = 2; charlen < str.length() +  1 - char; charlen ++ )
    {
      temp.count ++;
      temp.newText = str.substring( char, charlen );
      if ( newText != str && p.index( @ newText ) == -1 )
      {
        p.add( newText );
      }
      if ( count >= 100 )
      {
        sleep( .05 );
        count = 0;
      }
    }
  }
  return p;
}
function findFrequency( str, phrase )
{
  temp.o = 0;
  for ( temp.char = 0; char < str.length(); char ++ )
  {
    for ( temp.charlen = 1; charlen < str.length() +  1 - char; charlen ++ )
    {
      temp.count ++;
      temp.newText = str.substring( char, charlen );
      if ( newText != str )
      {
        if ( newText == phrase )
        {
          o ++;
        }
      }
      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.

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³)

PHP Code:


		
			
function findpatterns(str) {
  temp.outc = {};
  temp.out = {};
  temp.sub = "";
  temp.p = 0;
  temp.i = 0;
  temp.e = 0;

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

I have updated the guidelines slightly.

Quote:

Originally Posted by Tolnaftate2004 (Post 1382436)

I have updated the guidelines slightly.

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

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.

No comment on what I posted?

You've irritated me.

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

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=2; temp.length<temp.theString.length(); temp.length++) {

    for (temp.position=0; temp.position<temp.theString.length() - temp.length + 1; temp.position++) {

      temp.pattern = temp.theString.substring(temp.position, temp.length);

      temp.("pattern_" @ temp.pattern)++;

      

      //Makes iteration through the variables much easier.

      if (temp.("pattern_" @ temp.pattern) == 1) temp.patterns.add(temp.pattern);

    }

  }

  

  //Output

  temp.output = {};

  for (temp.pattern: temp.patterns) {

    if (temp.("pattern_" @ temp.pattern) > 1) {

      temp.output.add({temp.pattern, temp.("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

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.

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. ;)

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.i = 2; temp.i < temp.str.length(); temp.i ++) {
    for (temp.e = 0; temp.e < temp.str.length(); temp.e ++) {
      if (temp.e + temp.i > temp.str.length() - 1) {
        continue;
      }
      temp.sub = temp.str.substring(temp.e, temp.i);
      temp.p = 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;
}