Programming Exercise #1

[Skyld]

Originally Posted by zokemon

PHP Code:

temp.list = {}; 


PHP Code:

temp.list = new [0]; 


[napo_p2p]

Originally Posted by Skyld

PHP Code:

temp.list = new [0]; 


Does it really matter? I saw in some documentation on the graal wiki somewhere that temp.list = {}; is alright too.

[coreys]

Originally Posted by Skyld

PHP Code:

temp.list = new [0]; 


<3
Someone agrees with me. :3

[Inverness]

Originally Posted by Skyld

PHP Code:

temp.list = new [0]; 


Originally Posted by Graal v5.006 Info

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

...

[zokemon]

Originally Posted by Skyld

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 .

Originally Posted by Kristi

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.

[Kristi]

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

[Tolnaftate2004]

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]

Originally Posted by Tolnaftate2004

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]

Originally Posted by Kristi

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.

[Kristi]

Originally Posted by Tolnaftate2004

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.

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.

[Novo]

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]

Originally Posted by Novo

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]

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]

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

[Tolnaftate2004]

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.