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

``` String: AU, Occurances: 2String: CC, Occurances: 2String: CG, Occurances: 2String: CGT, Occurances: 2String: CGTA, Occurances: 2String: GT, Occurances: 2String: GTA, Occurances: 2String: 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 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.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 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=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 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.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;}  ```

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