Graal Forums - Programming Exercise #1

Page 1 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)

Kristi

11-19-2007 08:04 AM

Programming Exercise #1

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

11-19-2007 09:16 AM

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

11-19-2007 09:55 AM

interesting *waits for novo

Googi

11-19-2007 09:57 AM

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

11-19-2007 02:45 PM

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

Crono

11-19-2007 10:30 PM

I never knew Googi could script. :)

xAndrewx

11-19-2007 11:05 PM

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

Inverness

11-19-2007 11:08 PM

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

11-20-2007 12:35 AM

Posted a sample to clarify for you tards.

zokemon

11-20-2007 12:49 AM

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

11-20-2007 12:56 AM

Quote:

Originally Posted by zokemon (Post 1359400)

PHP Code:


		
			
temp.list = {};

PHP Code:


		
			
temp.list = new [0];

napo_p2p

11-20-2007 01:03 AM

Quote:

Originally Posted by Skyld (Post 1359404)

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

11-20-2007 01:03 AM

Quote:

Originally Posted by Skyld (Post 1359404)

PHP Code:


		
			
temp.list = new [0];

<3
Someone agrees with me. :3

Kristi

11-20-2007 01:17 AM

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

Googi

11-20-2007 01:30 AM

Quote:

Originally Posted by Gerami (Post 1359326)

I never knew Googi could script. :)

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

Quote:

Originally Posted by xAndrewx (Post 1359342)

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

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

All times are GMT +2. The time now is 07:46 AM.

Page 1 of 4

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