Graal Forums - Programming Exercise #1

Page 2 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 #1 (https://forums.graalonline.com/forums/showthread.php?t=77627)

Inverness

11-20-2007 01:52 AM

Quote:

Originally Posted by Skyld (Post 1359404)

PHP Code:


		
			
temp.list = new [0];

Quote:

Originally Posted by Graal v5.006 Info

You can now create empty arrays simplier by doing "var = {};" (it was displaying a syntax error before)

...

Twinny

11-20-2007 02:33 AM

Quote:

Originally Posted by Googi (Post 1359418)

I'm pretty seriously fourth or fifth rate at scripting.

Where did this rank come from?

Googi

11-20-2007 03:09 AM

Quote:

Originally Posted by Twinny (Post 1359427)

Where did this rank come from?

I think it should be pretty clear that I'm just using "fourth or fifth" as a synonym for "low" rather than an accurate expression of tier rank.

zokemon

11-20-2007 05:25 AM

Quote:

Originally Posted by Skyld (Post 1359404)

PHP Code:


		
			
temp.list = new [0];

PHP Code:


		
			
temp.list = {};

Support for that was recently added my Stefan. I use it as it is a few characters shorter and in all honesty, it really doesn't matter :).

Quote:

Originally Posted by Kristi (Post 1359416)

Zero, that is incredibly inefficient. We want something better then the naive algorithm

Well you made it in your example that they have to be in order of the first array so that was the only real algorithm that would really work. So far, I haven't seen anything better in this thread that actually works.

xAndrewx

11-20-2007 07:52 AM

Quote:

Originally Posted by Googi (Post 1359241)

PHP Code:


		
			
  if (temp.array1.size > 2 || temp.array2.size > 2) {

PHP Code:


		
			
for (temp.i = 0; temp.i < temp.array1.size - 3; temp.i++) {

wouldn't work at all

Tolnaftate2004

11-20-2007 08:05 AM

PHP Code:


		
			
function S3(arrA,arrB) {
  temp.intersect.clear();
  temp.sets.clear();
  if (arrA.size() > arrB.size()) temp.c = {arrB,arrA};
  else                           temp.c = {arrA,arrB};

  for (elmt: temp.c[0]) {
    if (elmt in temp.c[1])
      temp.intersect.add(elmt);
  }

  temp.len = temp.intersect.size();
  for (temp.i=0; temp.i<temp.len-2; temp.i++) {
    for (temp.j=temp.i+1; temp.j<temp.len-1; temp.j++) {
      for (temp.k=temp.j+1; temp.k< temp.len; temp.k++) {
        temp.sets.add({temp.intersect[temp.i],temp.intersect[temp.j],temp.intersect[temp.k]});
      }
    }
  }
  return temp.sets;
}

This has O(N+N!/((N-3)!*3!)), N ≤ min{a.size(),b.size()}.

Kristi

11-20-2007 11:46 AM

Quote:

Originally Posted by Tolnaftate2004 (Post 1359457)

PHP Code:


		
			
function S3(arrA,arrB) {
  temp.intersect.clear();
  temp.sets.clear();
  if (arrA.size() > arrB.size()) temp.c = {arrB,arrA};
  else                           temp.c = {arrA,arrB};

  for (elmt: temp.c[0]) {
    if (elmt in temp.c[0])
      temp.intersect.add(elmt);
  }

  temp.len = temp.intersect.size();
  for (temp.i=0; temp.i<temp.len-2; temp.i++) {
    for (temp.j=temp.i+1; temp.j<temp.len-1; temp.j++) {
      for (temp.k=temp.j+1; temp.k< temp.len; temp.k++) {
        temp.sets.add({temp.intersect[temp.i],temp.intersect[temp.j],temp.intersect[temp.k]});
      }
    }
  }
  return temp.sets;
}

This has O(N+N!/((N-3)!*3!)), N ≤ min{a.size(),b.size()}.

^_^ this is an open discussion. Please explain why this is better then the naive algorithm
Also, in your big O, did you include the search time for the "in" operator in your intersect portion? I can see a few ways to optimize that.

Tolnaftate2004

11-20-2007 10:42 PM

Quote:

Originally Posted by Kristi (Post 1359465)

Also, in your big O, did you include the search time for the "in" operator in your intersect portion? I can see a few ways to optimize that.

A good point: O(N1*N2 + N!/((N-3)!*3!))

I had originally intended to do something along these lines:

PHP Code:


		
			
  for (elmt: temp.c[0]) {
    if (elmt in temp.c[1])
      temp.intersect.add(elmt);
  }

becomes

PHP Code:


		
			
  while (temp.c[0].size()) {
    temp.elmt = temp.c[0][0];
    if (temp.elmt in temp.c[1]) {
      temp.intersect.add(temp.elmt);
      temp.c[0].remove(elmt);
      temp.c[1].remove(elmt);
    } else temp.c[0].delete(0);
  }

Still O(N1*N2), but often less.
It just slipped my mind. Silly me.
Also, first thing should be if (arrA.size() > 2 && arrB.size() > 2)...

As for the naive algorithm, It has O(N2^3*N1!/((N1-3)!*3!)) (?), I think.

Googi

11-21-2007 12:41 AM

Quote:

Originally Posted by xAndrewx (Post 1359455)

wouldn't work at all

Those are syntax errors, they mean that the script wouldn't work if actually used, they don't mean that the method I'm trying to use is nonsensical.

Novo	11-21-2007 02:52 AM

PHP Code:


		
			
function getSets()
{
  return {{2,3,5}, {2,3,6}, {2,3,10}, {2,5,6}, {2,5,10}, {2,6,10}, {3,5,6}, {3,5,10}, {3,6,10}, {5,6,10}};
}

I win.

Tolnaftate2004

11-21-2007 02:53 AM

Quote:

Originally Posted by Novo (Post 1359607)

PHP Code:


		
			
function getSets()
{
  return {{2,3,5} {2,3,6} {2,3,10} {2,5,6} {2,5,10} {2,6,10} {3,5,6} {3,5,10} {3,6,10} {5,6,10}};
}

I win.

Not quite. :P
e: nice ninja edit.

Crono

11-21-2007 03:14 AM

Using my leet skillz I have created the ultimate:

PHP Code:


		
			
//Returns array containing sets of 3 numbers both arrays have ing common

function ex1(arr1, arr2) {

  temp.result = {};

  temp.pos = 0;

  while (temp.pos < temp.arr1.size() - 2) {  //Make sure there's 3 elements left

    temp.check = {temp.arr1[temp.pos], temp.arr1[temp.pos + 1], temp.arr1[temp.pos + 2]};

    if (temp.result.pos(temp.check) < 0 && searchArr(temp.arr2, temp.check)) {

      temp.result.add(temp.check); 

      temp.pos += 3;  //Set is found, jump over whole set

    }

    else {

      temp.pos++;  //Set not found, go to next number

    }

  }

  return temp.result;

}



function ArrayComp(array1,array2) {

  if (temp.array1.size > 2 || temp.array2.size > 2) {

    temp.checkarray = temp.array2;

    temp.checkarray.delete(temp.array2.size - 1);

    temp.checkarray.delete(temp.array2.size - 2);

    temp.failarray = new [0];

    for (temp.i = 0; temp.i < temp.array1.size - 3; temp.i++) {

      if (temp.failarray.index(temp.array1[temp.i]) == -1) {

        temp.var = temp.checkarray.index(temp.array1[temp.i]);

        if (temp.var == -1) {

          temp.failarray.add(temp.array1[temp.i]);

        }

        else {

          temp.dupecheck = temp.checkarray;

          while (temp.var != -1) {

            if (temp.array1[temp.i + 1] == temp.array2[temp.var + 1]) {

              if (temp.array1[temp.i + 2] == temp.array2[temp.var + 2]) {

                temp.returnvar++;

              }

            }

            temp.dupecheck.replace(temp.var,"x");

            temp.var = temp.dupecheck.index(temp.array1[temp.i]);

          }

        }

      }

    }

  }

  return temp.returnvar;

}  



function ex1(a1, a2) {

  temp.out = {};

  temp.i = 0;

  temp.sub = 0;



  for (temp.i = 0; i < a.size() - 2; i++) {

    if (!(a[i] in b)) continue;

    for (temp.j = i + 1; j < a.size() - 1; j++) {

      if (!(a[j] in b)) continue;

      for (temp.k = j + 1; k < a.size(); k++) {

        if (a[k] in b) list.add({a[i], a[j], a[k]});



function S3(arrA,arrB) {

  temp.intersect.clear();

  temp.sets.clear();

  if (arrA.size() > arrB.size()) temp.c = {arrB,arrA};

  else                           temp.c = {arrA,arrB};



function getSets()

{

  return {{2,3,5}, {2,3,6}, {2,3,10}, {2,5,6}, {2,5,10}, {2,6,10}, {3,5,6}, {3,5,10}, {3,6,10}, {5,6,10}};

}

i SO did not copy paste bits from everyone else's scripts

coreys

11-21-2007 04:22 AM

Rather long, don't you think? XD
But I don't even have the competence to try. :(

Kristi

11-29-2007 08:47 AM

Quote:

Originally Posted by Tolnaftate2004 (Post 1359534)

A good point: O(N1*N2 + N!/((N-3)!*3!))

I had originally intended to do something along these lines:

PHP Code:


		
			
  for (elmt: temp.c[0]) {
    if (elmt in temp.c[1])
      temp.intersect.add(elmt);
  }

becomes

PHP Code:


		
			
  while (temp.c[0].size()) {
    temp.elmt = temp.c[0][0];
    if (temp.elmt in temp.c[1]) {
      temp.intersect.add(temp.elmt);
      temp.c[0].remove(elmt);
      temp.c[1].remove(elmt);
    } else temp.c[0].delete(0);
  }

Deleting elements from the array and etc is actually going to make it take longer to process.

Anyway, hashes would optimize finding the intersect, but graal has no support for it. However, we can dynamically name variables, so we can emulate it well enough for this situation.

code snippet:

PHP Code:


		
			
for(e: temp.array1)
   temp.b.("v"@e) = true;

for(e: temp.array2)
   if(temp.b.("v"@e))
     temp.intersect.add(e);

with larger datasets, this gets exponentially faster. with 5000-10000 element arrays, its literally 120x faster then searching through the arrays for intersects.

Also, it would be slightly faster to make an array with the max possible size first, so you're not resizing the array (and thus possibly moving it to a new location in memory constantly.)

PHP Code:


		
			
  temp.intersect = new[smallerarray.size()];

  for(e: temp.largerarray)
   temp.b.("v"@e) = true;

  for(e: smallerarray)
   if(temp.b.("v"@e)) {
     temp.intersect[temp.j] = e;
     temp.j++;
   }

This does in fact improve performance, although it's not terribly noticeable.

I'll optimize finding the sets from the intersects later. Lets let this soak in first.

Tolnaftate2004

11-29-2007 08:53 AM

The maximum size of the intersect should be the size of the small array as it cannot possibly have more elements in common than there are in the set.

All times are GMT +2. The time now is 11:41 AM.

Page 2 of 4

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