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, 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.
 __________________
#7
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..
#8
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 :/
#9
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?
#10
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 :/
#11
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.
 __________________
#12
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..
#13
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;}  ```
 __________________
#14
03-26-2008, 09:49 PM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by Inverness What the hell are you talking about?
This is big O notation, it is how we measure the efficiency of algorithms, without being hardware-specific. The O stands for order, which can take 2 meanings:
1. In mathematics, O(f) is for all terms order f and above. f is usually a function where the parameter is much less than 1 (error terms).
2. In computer science O(f) is the major factor in determining algorithm efficiency. f is a function of n, which is a whole number.

For example, the quicksort algorithm is O(n log n) [for every item to sort, it takes log base 2 of n loops to find its place].
 __________________ ◕‿‿◕ · 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 10:04 PM..
#15
03-27-2008, 10:25 PM
 napo_p2p oh snaps Join Date: Sep 2003 Location: Pismo Beach, California Posts: 2,118
 PHP Code: ``` function findpatterns(str) {  temp.loc = 0;  temp.l = temp.str.length();  temp.results = new[0];    while (temp.loc < temp.l) {    temp.len = 2;    while (temp.len <= (temp.l - temp.loc)) {      temp.seq = temp.str.substring(temp.loc, temp.len);      temp.("count_" @ temp.seq)++;      if (temp.("count_" @ temp.seq) == 2) {        temp.results.add(temp.seq);      }      temp.len++;    }    temp.loc++;  }  for (temp.r: temp.results) {    echo(temp.r @ ": " @ temp.("count_" @ temp.r));  }}  ```
 __________________ Scito hoc super omnia. Haec vita est tua una sola. Dum vita superest, utere maxime quoque puncto, momento, et hora quae habes. Tempus neminem non manet. Noli manere tempus. Carpe Diem Seize the Day.

Last edited by napo_p2p; 03-27-2008 at 10:27 PM.. Reason: .

 Tags pattern-matching, programming-exercise