Programming Exercise #1

[Kristi]

So, there is a lot of help around here dealing with syntax of scripting, but I don't see much discussion on best algorithms. Be this the case, I am going to every so often (when I feel like it) post some mathematically cool problem for you all to help each other solve and break some mental barriers.

Problem 1.
Given 2 arrays of numbers, find all the sets of 3 numbers that both arrays have in common.

Remember, the goal is to make this as efficient as possible with graal script.

Edit: For clarification, this is a sample
If you have the following two sets
{2,3,5,6,8,10}
{1,5,3,10,6,9,2}

All of the sets of 3 would be
{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}

New Edit: Let's do unique sets. If you have two sets of {1,1,2,3}, then the answer is {1,2,3}, not {1,2,3} {1,2,3}

[napo_p2p]

I have something I put together real quick, but it searches linearly, so someone could most certainly come up with something more efficient.

Also, I assumed that if both arrays are (for example):
{1, 2, 3, 4, 5, 6}

Then they would just have the two sets {1, 2, 3} and {4, 5, 6}.
Instead of {1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 6}.

Also, there is a high chance that there is a case where the algorithm fails, as I haven't really tested it... so feel free to find a case that doesn't work :P.

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;
}

//True if subarr is in arr.
function searchArr(arr, subarr) {
  temp.found = 0;
  for (temp.e: temp.arr) {
    if (temp.e == temp.subarr[temp.found]) {
      temp.found++;
      if (temp.found == temp.subarr.size()) {
        return true;
      }
    }
    else {
      temp.found = 0;
    }
  }
  return false;
} 


[xAndrewx]

interesting *waits for novo

[Googi]

I get the feeling I'm being manipulated, but...

PHP Code:

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;
} 


[Darklux]

Hmm I never coded gscript, but whats about quicksorting both sets and find the common ones, then?

[Crono]

I never knew Googi could script.

[xAndrewx]

What Googi posted doesn't make logical sense, at all.

[Inverness]

PHP Code:

function ex1(a1, a2) {
  temp.out = {};
  temp.i = 0;
  for (i = 0; i < a1.size() - 2; i ++) {
    if (a2.pos(("" @ a1.subarray(i, 3))) > -1) {
      out.add(a1.subarray(i, 3));
    }
  }
  return out;
} 


Am I doing it right?

That doesn't check if all the sets are exactly different, I'll do that next I guess.

You need to give examples of input and output >

PHP Code:

function ex1(a1, a2) {
  temp.out = {};
  temp.i = 0;
  temp.sub = 0;
  
  for (i = 0; i < a1.size() - 2; i ++) {
    sub = ("" @ a1.subarray(i, 3));
    if (a2.pos(sub) > -1) {
      if (out.index(sub) < 0) {
        out.add(sub);
        i += 2;
      }
    }
  }
  return out;
} 


It would be nice to have a variable.add2() function that only adds if the input isn't already in the array :o

[Kristi]

Posted a sample to clarify for you tards.

[zokemon]

PHP Code:

function getSets(a, b) {
  temp.list = {};
  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]});
      }
    }
  }
  return list;
} 


Just slap this into the script to try it:

PHP Code:

function onCreated() {
  temp.foo = {2,3,5,6,8,10};
  echo(foo);
  temp.bar = {1,5,3,10,6,9,2};
  echo(bar);
  echo(getSets(foo, bar));
} 


[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

[Kristi]

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

[Googi]

Originally Posted by Gerami

I never knew Googi could script.

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

Originally Posted by xAndrewx

What Googi posted doesn't make logical sense, at all.

If there's a problem, I want to know about it.

[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)

...

[Twinny]

Originally Posted by Googi

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

Where did this rank come from?

[Googi]

Originally Posted by Twinny

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]

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.

[xAndrewx]

Originally Posted by Googi

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]

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.

[Googi]

Originally Posted by xAndrewx

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]

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.

[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.

[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.

[Kristi]

Originally Posted by 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.

I was half asleep, good point xD
I actually read my post before yours and was about to correct that (does so)

[Tolnaftate2004]

Also, the method you proposed for determining the intersection gives duplicates.

[Kristi]

Originally Posted by Tolnaftate2004

Also, the method you proposed for determining the intersection gives duplicates.

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.b.("v"@e) = false;
     temp.j++;
   } 


I should also point out that its O(n+m)

[Tolnaftate2004]

Originally Posted by Kristi

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.c.("v"@e))) {
     temp.intersect[temp.j] = e;
     temp.c.("v"@e) = true;
     temp.j++;
   } 


Okay, so why the temp.intersect array now? We can just do:

PHP Code:

  for(e: smallerarray)
   if(temp.b.("v"@e)) 
     temp.c.("v"@e) = true;

  temp.intersect = temp.c.getdynamicvarnames(); 


I think O(getdynamicvarnames) ~ O(temp.intersect[temp.j++] =), at worst. I suppose the only issue here would be getting the size to optimize the set-making and the eventual substrings. Just some thoughts...

[Kristi]

Originally Posted by Tolnaftate2004

Okay, so why the temp.intersect array now?

I changed it to falsify b instead, i guess while you were typing this up.
However, im not sure which would work faster. when i get home and have access to my rc ill find out by averaging the run times :P

creating temp.c set means creating and moving a lot of pointers. it might be faster to assign the intersects directly to the array instead of getting dynamic variable names because of it. Ill report back tonight

[xAndrewx]

whats the use in this? I wouldn't use this in a script... lol

Make a exercise that'll come in handy !!!!

[Tolnaftate2004]

Originally Posted by xAndrewx

I wouldn't use this in a script... lol

That's not really the point of the thread. We're trying to solve problems as efficiently as possible, which is a skill that will come in handy.

[xAndrewx]

why if you're not intending to use it? i'm asking for you to base your exercises on something that'll come in handy

[Tolnaftate2004]

Originally Posted by xAndrewx

why if you're not intending to use it?

It's good practice.

[Kristi]

Originally Posted by xAndrewx

why if you're not intending to use it? i'm asking for you to base your exercises on something that'll come in handy

Mathematical and computational efficiency is the basis of programming