Graal Forums  

Go Back   Graal Forums > Development Forums > NPC Scripting
FAQ Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
Thread Tools Search this Thread Display Modes
  #1  
Old 11-19-2007, 08:04 AM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
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}
__________________

Last edited by Kristi; 11-21-2007 at 03:47 PM..
Reply With Quote
  #2  
Old 11-19-2007, 09:16 AM
napo_p2p napo_p2p is offline
oh snaps
napo_p2p's Avatar
Join Date: Sep 2003
Location: Pismo Beach, California
Posts: 2,118
napo_p2p has a spectacular aura aboutnapo_p2p has a spectacular aura about
Send a message via AIM to napo_p2p Send a message via MSN to 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(arr1arr2) {
  
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) < && searchArr(temp.arr2temp.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(arrsubarr) {
  
temp.found 0;
  for (
temp.etemp.arr) {
    if (
temp.== temp.subarr[temp.found]) {
      
temp.found++;
      if (
temp.found == temp.subarr.size()) {
        return 
true;
      }
    }
    else {
      
temp.found 0;
    }
  }
  return 
false;

__________________
Scito hoc super omnia.
Haec vita est tua una sola.
Dum vita superest, utere maxime quoque puncto, momento, et hora quae habes.
Tempus neminem non manet.
Noli manere tempus.
Carpe Diem

Seize the Day.
Reply With Quote
  #3  
Old 11-19-2007, 09:55 AM
xAndrewx xAndrewx is offline
Registered User
xAndrewx's Avatar
Join Date: Sep 2004
Posts: 5,260
xAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud of
interesting *waits for novo
__________________
Reply With Quote
  #4  
Old 11-19-2007, 09:57 AM
Googi Googi is offline
A Serious Epidemic
Googi's Avatar
Join Date: Oct 2001
Location: Canada
Posts: 18,866
Googi has much to be proud ofGoogi has much to be proud ofGoogi has much to be proud ofGoogi has much to be proud ofGoogi has much to be proud ofGoogi has much to be proud of
Send a message via AIM to Googi
I get the feeling I'm being manipulated, but...

PHP Code:
function ArrayComp(array1,array2) {
  if (
temp.array1.size || 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.0temp.temp.array1.size 3temp.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.1] == temp.array2[temp.var + 1]) {
              if (
temp.array1[temp.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;

__________________

Last edited by Googi; 11-20-2007 at 02:22 AM..
Reply With Quote
  #5  
Old 11-19-2007, 02:45 PM
Darklux Darklux is offline
Petrification of a Newbie
Darklux's Avatar
Join Date: Dec 2002
Location: Dortmund, Germany
Posts: 1,375
Darklux is a jewel in the roughDarklux is a jewel in the rough
Send a message via ICQ to Darklux Send a message via AIM to Darklux Send a message via Yahoo to Darklux
Hmm I never coded gscript, but whats about quicksorting both sets and find the common ones, then?
Reply With Quote
  #6  
Old 11-19-2007, 10:30 PM
Crono Crono is offline
:pluffy:
Join Date: Feb 2002
Location: Sweden
Posts: 20,000
Crono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond reputeCrono has a reputation beyond repute
I never knew Googi could script.
__________________
Reply With Quote
  #7  
Old 11-19-2007, 11:05 PM
xAndrewx xAndrewx is offline
Registered User
xAndrewx's Avatar
Join Date: Sep 2004
Posts: 5,260
xAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud of
What Googi posted doesn't make logical sense, at all.
__________________
Reply With Quote
  #8  
Old 11-19-2007, 11:08 PM
Inverness Inverness is offline
Incubator
Inverness's Avatar
Join Date: Aug 2004
Location: Houston, Texas
Posts: 3,613
Inverness is a jewel in the roughInverness is a jewel in the rough
PHP Code:
function ex1(a1a2) {
  
temp.out = {};
  
temp.0;
  for (
0a1.size() - 2++) {
    if (
a2.pos(("" a1.subarray(i3))) > -1) {
      
out.add(a1.subarray(i3));
    }
  }
  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(a1a2) {
  
temp.out = {};
  
temp.0;
  
temp.sub 0;
  
  for (
0a1.size() - 2++) {
    
sub = ("" a1.subarray(i3));
    if (
a2.pos(sub) > -1) {
      if (
out.index(sub) < 0) {
        
out.add(sub);
        
+= 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
__________________

Last edited by Inverness; 11-19-2007 at 11:22 PM..
Reply With Quote
  #9  
Old 11-20-2007, 12:35 AM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
Posted a sample to clarify for you tards.
__________________
Reply With Quote
  #10  
Old 11-20-2007, 12:49 AM
zokemon zokemon is offline
That one guy...
zokemon's Avatar
Join Date: Mar 2001
Location: Sonoma County, California
Posts: 2,925
zokemon is a jewel in the roughzokemon is a jewel in the rough
Send a message via ICQ to zokemon Send a message via AIM to zokemon Send a message via MSN to zokemon Send a message via Yahoo to zokemon
PHP Code:
function getSets(ab) {
  
temp.list = {};
  for (
temp.0a.size() - 2i++) {
    if (!(
a[iin b)) continue;
    for (
temp.1a.size() - 1j++) {
      if (!(
a[jin b)) continue;
      for (
temp.1a.size(); k++) {
        if (
a[kin 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(foobar));

__________________
Do it with a DON!
Reply With Quote
  #11  
Old 11-20-2007, 12:56 AM
Skyld Skyld is offline
Script-fu
Skyld's Avatar
Join Date: Jan 2002
Location: United Kingdom
Posts: 3,914
Skyld has much to be proud ofSkyld has much to be proud ofSkyld has much to be proud ofSkyld has much to be proud ofSkyld has much to be proud ofSkyld has much to be proud of
Send a message via AIM to Skyld
Quote:
Originally Posted by zokemon View Post
PHP Code:
temp.list = {}; 
PHP Code:
temp.list = new [0]; 
Reply With Quote
  #12  
Old 11-20-2007, 01:03 AM
napo_p2p napo_p2p is offline
oh snaps
napo_p2p's Avatar
Join Date: Sep 2003
Location: Pismo Beach, California
Posts: 2,118
napo_p2p has a spectacular aura aboutnapo_p2p has a spectacular aura about
Send a message via AIM to napo_p2p Send a message via MSN to napo_p2p
Quote:
Originally Posted by Skyld View Post
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.
__________________
Scito hoc super omnia.
Haec vita est tua una sola.
Dum vita superest, utere maxime quoque puncto, momento, et hora quae habes.
Tempus neminem non manet.
Noli manere tempus.
Carpe Diem

Seize the Day.
Reply With Quote
  #13  
Old 11-20-2007, 01:03 AM
coreys coreys is offline
N-Pulse Assistant Manager
coreys's Avatar
Join Date: Mar 2005
Posts: 2,180
coreys has a spectacular aura about
Send a message via AIM to coreys Send a message via MSN to coreys Send a message via Yahoo to coreys
Quote:
Originally Posted by Skyld View Post
PHP Code:
temp.list = new [0]; 
<3
Someone agrees with me. :3
__________________

Quote:
*SlikRick: so should I even ask about your aim status?
*Xor: well if you want to
*Xor: but i am LARPING
*SlikRick: While on a computer?
*Xor: yes
*Xor: in my living room
*SlikRick: ahh
*Xor: i have a fort setup to hide from beasts
Reply With Quote
  #14  
Old 11-20-2007, 01:17 AM
Kristi Kristi is offline
Bowie's Deciple
Kristi's Avatar
Join Date: Dec 2003
Location: Boston, MA
Posts: 748
Kristi has a spectacular aura aboutKristi has a spectacular aura about
Send a message via AIM to Kristi Send a message via MSN to Kristi
Zero, that is incredibly inefficient. We want something better then the naive algorithm
__________________
Reply With Quote
  #15  
Old 11-20-2007, 01:30 AM
Googi Googi is offline
A Serious Epidemic
Googi's Avatar
Join Date: Oct 2001
Location: Canada
Posts: 18,866
Googi has much to be proud ofGoogi has much to be proud ofGoogi has much to be proud ofGoogi has much to be proud ofGoogi has much to be proud ofGoogi has much to be proud of
Send a message via AIM to Googi
Quote:
Originally Posted by Gerami View Post
I never knew Googi could script.
I'm pretty seriously fourth or fifth rate at scripting.

Quote:
Originally Posted by xAndrewx View Post
What Googi posted doesn't make logical sense, at all.
If there's a problem, I want to know about it.
__________________
Reply With Quote
Reply

Tags
programming-exercise

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 05:29 AM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.