Graal Forums - Programming Exercise #1

Page 1 of 2

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.

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.

Kristi

11-29-2007 09:07 PM

Quote:

Originally Posted by Tolnaftate2004 (Post 1361203)

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

11-29-2007 10:37 PM

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

Kristi

11-29-2007 10:54 PM

Quote:

Originally Posted by Tolnaftate2004 (Post 1361302)

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

11-29-2007 11:08 PM

Quote:

Originally Posted by Kristi (Post 1361308)

>_<

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

11-29-2007 11:11 PM

Quote:

Originally Posted by Tolnaftate2004 (Post 1361311)

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

11-30-2007 12:00 AM

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

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

Tolnaftate2004

11-30-2007 12:04 AM

Quote:

Originally Posted by xAndrewx (Post 1361321)

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

11-30-2007 12:06 AM

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

11-30-2007 12:13 AM

Quote:

Originally Posted by xAndrewx (Post 1361323)

why if you're not intending to use it?

It's good practice.

Kristi

11-30-2007 12:53 AM

Quote:

Originally Posted by xAndrewx (Post 1361323)

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

All times are GMT +2. The time now is 06:55 PM.

Page 1 of 2

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