Programming Exercise #3

[Chompy]

Originally Posted by Horrified

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]

Originally Posted by Tolnaftate2004

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]

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]

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

[Tolnaftate2004]

Originally Posted by Inverness

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]

Originally Posted by Tolnaftate2004

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.

[Programmer]

Originally Posted by cbkbud

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

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

[Tolnaftate2004]

Originally Posted by cbkbud

There are always improvements to be made...

This can be disproved.

[Inverness]

Originally Posted by cbkbud

There are always improvements to be made

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

[cbk1994]

Originally Posted by Inverness

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

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

THE POWER OF THE SUN IN THE CHRIS.

[Tolnaftate2004]

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()?