Programming Exercise #3

[Tolnaftate2004]

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]

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

For example,

findAllPatterns( n )

or something like

findNumber( n, pattern )

[DrakilorP2P]

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 


[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:

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.

[Tolnaftate2004]

Originally Posted by DrakilorP2P

Assuming that the algorithm should find the number of occurrences of a string in another string.

Nooooooot quite.

Originally Posted by cbkbud

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]

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;
} 


[Tolnaftate2004]

I have updated the guidelines slightly.

[DrakilorP2P]

Originally Posted by Tolnaftate2004

I have updated the guidelines slightly.

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

[Tolnaftate2004]

Originally Posted by DrakilorP2P

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

A solid color does not a pattern make.

[Inverness]

No comment on what I posted?

You've irritated me.

[xXziroXx]

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

[DrakilorP2P]

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 


[Crow]

Originally Posted by cbkbud

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]

Originally Posted by Inverness

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]

Originally Posted by Tolnaftate2004

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;
}