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.