Graal Forums Programming Exercise #3
 FAQ Members List Calendar Search Today's Posts Mark Forums Read

#1
03-26-2008, 02:44 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
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..
#2
03-26-2008, 02:52 AM
 cbk1994 the fake one Join Date: Mar 2003 Location: San Francisco Posts: 10,718
 Do we need to find every pattern possible, or just ones specified? For example, findAllPatterns( n ) or something like findNumber( n, pattern )
 __________________
#3
03-26-2008, 03:25 AM
 DrakilorP2P Registered User Join Date: Apr 2006 Posts: 755
 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

Last edited by DrakilorP2P; 03-26-2008 at 09:57 AM..
#4
03-26-2008, 05:05 AM
 cbk1994 the fake one Join Date: Mar 2003 Location: San Francisco Posts: 10,718
 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.
 __________________
#5
03-26-2008, 07:34 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by DrakilorP2P Assuming that the algorithm should find the number of occurrences of a string in another string.
Nooooooot quite.

Quote:
 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³)
 __________________ ◕‿‿◕ · 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 :/
#6
03-26-2008, 08:16 AM
 Inverness Incubator Join Date: Aug 2004 Location: Houston, Texas Posts: 3,613
 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;}  ```
 __________________

Last edited by Inverness; 03-26-2008 at 01:28 PM..
#7
03-26-2008, 09:13 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
 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 :/
#8
03-26-2008, 09:59 AM
 DrakilorP2P Registered User Join Date: Apr 2006 Posts: 755
Quote:
 Originally Posted by Tolnaftate2004 I have updated the guidelines slightly.
Why isn't strings of length one considered valid patterns?
#9
03-26-2008, 12:11 PM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by DrakilorP2P 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 :/
#10
03-26-2008, 01:28 PM
 Inverness Incubator Join Date: Aug 2004 Location: Houston, Texas Posts: 3,613
 No comment on what I posted? You've irritated me.
 __________________
#11
03-26-2008, 02:05 PM
 xXziroXx Master of Puppets Join Date: May 2004 Location: Sweden Posts: 5,288
 How about making Programming Exercise #4 something that we normal mortals stand a chance at?
 __________________ Contact Informationemail: [email protected] "A delayed game is eventually good, but a rushed game is forever bad." - Shigeru Miyamoto
#12
03-26-2008, 05:13 PM
 DrakilorP2P Registered User Join Date: Apr 2006 Posts: 755
 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 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  ```
#13
03-26-2008, 05:26 PM
 Crow ǝɔɐɹq ʎןɹnɔ Join Date: Dec 2006 Location: Germany Posts: 5,153
Quote:
 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.
 __________________
#14
03-26-2008, 07:26 PM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 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.
 __________________ ◕‿‿◕ · 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..
#15
03-26-2008, 09:40 PM
 Inverness Incubator Join Date: Aug 2004 Location: Houston, Texas Posts: 3,613
Quote:
 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;}  ```
 __________________

 Tags pattern-matching, programming-exercise