Graal Forums Programming Exercise #3
 User Name Remember Me? Password
 FAQ Members List Calendar Search Today's Posts Mark Forums Read

 Thread Tools Search this Thread Display Modes
#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

 Thread Tools Search this Thread Search this Thread: Advanced Search Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General Forums     Graal Main Forum (English)         Hello and Goodbyes         Birthday Forum         Guild Life         Job Forum             Global Scripting Team             Playerworld Administration Team             Forum moderation Team             Graal Kingdoms Team             Graal Zone Team             Wiki Administration Team         Server Maintenance         Discussions en Francais (Français)         Diskussionsforum (Deutsch)     Forum Rules and documentation     Non-Graal-related threads Graal V6 forums     Announcements     Your opinion     Questions about V6     Feature request     Bug Report Gold Servers     Graal Kingdoms         Markets         Kingdoms             Dustari             Forest             Crescent Pirates             Samurai             Zormite Republic         Graal Kingdoms Events         Information             Gods         GK Suggestions         GK Bugs     Zone         Gfx submissions         Information         Zone Suggestions.         Zone Bugs         Zone News         Zone PC PlayerWorlds     PlayerWorlds Main Forum         Playerworld Related Information     Playerworld Staff Openings     Bomy Island Main Forum         Kingdoms Main Forum         Events and Activities         Bugs and Future Improvements             New Races     Classic Main Forum         Classic News         Classic Bugs and suggestions         Hiring for Classic     Delteria Main Forum         Delteria News         Delteria Bugs and suggestions         Hiring for Delteria     Era Main Forum         Era News         Era Bugs and improvements         Hiring for Era         Era Wiki     N-Pulse Main Forum         N-Pulse News         N-Pulse Bugs and suggestions         Hiring for N-Pulse     Unholy Nation Main Forum         Unholy Nation News         Unholy Nation Bugs and improvements         Hiring for Unholy Nation     Valikorlia Main Forum         Valikorlia News         Valikorlia Bugs and suggestions         Hiring for Valikorlia     Zodiac Main Forum         Zodiac News         Zodiac Bugs and suggestions         Hiring for Zodiac Development Forums     Level Design     Graphic Design     Sounds & Music     Gani Construction     Videos     NPC Scripting         New Scripting Engine (GS2)         Old Scripting Engine (GS1)         Code Gallery     Tech Support         Bug Reports (No posting)     Future Improvements Private forums

All times are GMT +2. The time now is 04:45 AM.

 -- Graal Forums - Author on top -- Mobile -- Graal Forums - Old Layout Contact Us - Graal - Archive - Privacy Statement - Top

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.