Graal Forums - Programming Exercise #3

Page 4 of 4

Show 40 post(s) from this thread on one page

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)

Chompy

04-06-2008 02:35 PM

Quote:

Originally Posted by Horrified (Post 1384481)

Pffft!

PHP Code:

3/0

Dumb noobs.

o.o hmm?

oh, and when is exercise 4 coming? And could 4 have two difficults? One simplier and one harder?

Mark Sir Link

04-11-2008 01:59 PM

Quote:

Originally Posted by Tolnaftate2004 (Post 1382898)

Give us pseudocode, then.

I got it working O(1) but forget sharing with you guys!

the previous is a lie but I'm tempted to make something ridiculous like O(n!) and declare it O(1) and laugh @ noobs who believe it

Tolnaftate2004

04-22-2008 09:53 AM

Okay, well this thread has been dead for sufficiently long time. Here is what I came up with; it takes quadratic time.

PHP Code:


		
			
function onCreated() {
  temp.p = getpatterns("THISISATESTSTRING");
  for (temp.s: temp.p) {
    if (this.(@"h_"@temp.s) >= 2)
      echo(temp.s @ ": "@ this.(@"h_"@temp.s));
    this.(@"h_"@temp.s) = 0; /* clean-up */
  }
}

function getpatterns(s) {
  temp.l = s.length();
  for (temp.i=0; temp.i<temp.l-1; temp.i++) {
    temp.c = s.charat(temp.i);
    for (temp.j=temp.i+1;temp.j<temp.l;temp.j++) {
      temp.c @= s.charat(temp.j);
      this.(@"h_"@temp.c) ++;
      temp.pat.add(temp.c);
    }
  }
  return temp.pat;
}

Perhaps there are still improvements to be made.

Inverness

04-22-2008 10:35 AM

Maybe try doing it in a language that doesn't allow you to dynamically create new variables.

Tolnaftate2004

04-22-2008 06:35 PM

Quote:

Originally Posted by Inverness (Post 1387185)

Maybe try doing it in a language that doesn't allow you to dynamically create new variables.

So I would use a hash, and it would still run in quadratic time. Also, the instructions say we're making this as efficient as possible in graal script.

cbk1994

04-22-2008 10:04 PM

Quote:

Originally Posted by Tolnaftate2004 (Post 1387184)

Okay, well this thread has been dead for sufficiently long time. Here is what I came up with; it takes quadratic time.

PHP Code:


		
			
function onCreated() {

  temp.p = getpatterns("THISISATESTSTRING");

  for (temp.s: temp.p) {

    if (this.(@"h_"@temp.s) >= 2)

      echo(temp.s @ ": "@ this.(@"h_"@temp.s));

    this.(@"h_"@temp.s) = 0; /* clean-up */

  }

}



function getpatterns(s) {

  temp.l = s.length();

  temp.pat.clear();

  for (temp.i=0; temp.i<temp.l-1; temp.i++) {

    temp.c = s.charat(temp.i);

    for (temp.j=temp.i+1;temp.j<temp.l;temp.j++) {

      temp.c @= s.charat(temp.j);

      this.(@"h_"@temp.c) ++;

      temp.pat.add(temp.c);

    }

  }

  return temp.pat;

}

Perhaps there are still improvements to be made.

There are always improvements to be made, unless Stefan makes it, in which case it must be perfect. :rolleyes:

Programmer

04-22-2008 10:28 PM

Quote:

Originally Posted by cbkbud (Post 1387241)

There are always improvements to be made, unless Stefan makes it, in which case it must be perfect. :rolleyes:

Even Stefan makes mistakes. You should see Kingdoms Debug and Zone Debug xD

Tolnaftate2004

04-23-2008 02:12 AM

Quote:

Originally Posted by cbkbud (Post 1387241)

There are always improvements to be made...

This can be disproved.

Inverness

04-23-2008 07:28 AM

Quote:

Originally Posted by cbkbud (Post 1387241)

There are always improvements to be made

Maybe for you, considering your level of skill, but the same does not go for others. :D

cbk1994

04-23-2008 01:08 PM

Quote:

Originally Posted by Inverness (Post 1387335)

Maybe for you, considering your level of skill, but the same does not go for others. :D

Yes, I have so much skill, it cannot be controlled.

THE POWER OF THE SUN IN THE CHRIS.

Tolnaftate2004

04-23-2008 11:56 PM

I think it is feasible to shrink time to ~ aN + O(N log N). How might we go about doing this? How do we get a logarithmic factor in our order? How can this help us speed up our algorithm?

This post points out a pitfall in computing the algorithm efficiency. The questions above and this problem are related. How can we minimize the effects of substring()?

All times are GMT +2. The time now is 03:34 PM.

Page 4 of 4

Show 40 post(s) from this thread on one page