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
  #16  
Old 11-20-2007, 01:52 AM
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
Quote:
Originally Posted by Skyld View Post
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)
...
__________________
Reply With Quote
  #17  
Old 11-20-2007, 02:33 AM
Twinny Twinny is offline
My empire of dirt
Twinny's Avatar
Join Date: Mar 2006
Location: Australia
Posts: 2,422
Twinny is just really niceTwinny is just really nice
Send a message via AIM to Twinny
Quote:
Originally Posted by Googi View Post
I'm pretty seriously fourth or fifth rate at scripting.
Where did this rank come from?
Reply With Quote
  #18  
Old 11-20-2007, 03:09 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 Twinny View Post
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.
__________________
Reply With Quote
  #19  
Old 11-20-2007, 05:25 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
Quote:
Originally Posted by Skyld View Post
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 View Post
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.
__________________
Do it with a DON!
Reply With Quote
  #20  
Old 11-20-2007, 07:52 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
Quote:
Originally Posted by Googi View Post
PHP Code:
  if (temp.array1.size || temp.array2.size 2) { 

PHP Code:
for (temp.0temp.temp.array1.size 3temp.i++) { 
wouldn't work at all
__________________
Reply With Quote
  #21  
Old 11-20-2007, 08:05 AM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
PHP Code:
function S3(arrA,arrB) {
  
temp.intersect.clear();
  
temp.sets.clear();
  if (
arrA.size() > arrB.size()) temp.= {arrB,arrA};
  else                           
temp.= {arrA,arrB};

  for (
elmttemp.c[0]) {
    if (
elmt in temp.c[1])
      
temp.intersect.add(elmt);
  }

  
temp.len temp.intersect.size();
  for (
temp.i=0temp.i<temp.len-2temp.i++) {
    for (
temp.j=temp.i+1temp.j<temp.len-1temp.j++) {
      for (
temp.k=temp.j+1temp.ktemp.lentemp.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()}.
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/

Last edited by Tolnaftate2004; 11-21-2007 at 03:34 AM..
Reply With Quote
  #22  
Old 11-20-2007, 11:46 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
Quote:
Originally Posted by Tolnaftate2004 View Post
PHP Code:
function S3(arrA,arrB) {
  
temp.intersect.clear();
  
temp.sets.clear();
  if (
arrA.size() > arrB.size()) temp.= {arrB,arrA};
  else                           
temp.= {arrA,arrB};

  for (
elmttemp.c[0]) {
    if (
elmt in temp.c[0])
      
temp.intersect.add(elmt);
  }

  
temp.len temp.intersect.size();
  for (
temp.i=0temp.i<temp.len-2temp.i++) {
    for (
temp.j=temp.i+1temp.j<temp.len-1temp.j++) {
      for (
temp.k=temp.j+1temp.ktemp.lentemp.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.
__________________

Last edited by Kristi; 11-20-2007 at 12:00 PM..
Reply With Quote
  #23  
Old 11-20-2007, 10:42 PM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Kristi View Post
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 (elmttemp.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.
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/

Last edited by Tolnaftate2004; 11-21-2007 at 03:34 AM..
Reply With Quote
  #24  
Old 11-21-2007, 12:41 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 xAndrewx View Post
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.
__________________
Reply With Quote
  #25  
Old 11-21-2007, 02:52 AM
Novo Novo is offline
[TServerDeveloper]
Join Date: Jun 2006
Posts: 448
Novo will become famous soon enough
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.
Reply With Quote
  #26  
Old 11-21-2007, 02:53 AM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Novo View Post
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.
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
Reply With Quote
  #27  
Old 11-21-2007, 03:14 AM
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
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(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;
}

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

function 
ex1(a1a2) {
  
temp.out = {};
  
temp.0;
  
temp.sub 0;

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

function 
S3(arrA,arrB) {
  
temp.intersect.clear();
  
temp.sets.clear();
  if (
arrA.size() > arrB.size()) temp.= {arrB,arrA};
  else                           
temp.= {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
__________________
Reply With Quote
  #28  
Old 11-21-2007, 04:22 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
Rather long, don't you think? XD
But I don't even have the competence to try.
__________________

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
  #29  
Old 11-29-2007, 08:47 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
Quote:
Originally Posted by Tolnaftate2004 View Post
A good point: O(N1*N2 + N!/((N-3)!*3!))

I had originally intended to do something along these lines:
PHP Code:
  for (elmttemp.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(etemp.array1)
   
temp.b.("v"@e) = true;

for(
etemp.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(
etemp.largerarray)
   
temp.b.("v"@e) = true;

  for(
esmallerarray)
   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.
__________________

Last edited by Kristi; 11-29-2007 at 09:08 PM..
Reply With Quote
  #30  
Old 11-29-2007, 08:53 AM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to 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.
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
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 04:43 PM.


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