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
  #31  
Old 06-18-2008, 11:00 PM
cbk1994 cbk1994 is offline
the fake one
cbk1994's Avatar
Join Date: Mar 2003
Location: San Francisco
Posts: 10,718
cbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond repute
Send a message via AIM to cbk1994
Quote:
Originally Posted by Stryke View Post
Would this work?

PHP Code:
function onCreated()
{
  
this.start timevar2;
  
this.incompatability = {
                         {
23,46},
                         {
29,44},
                         {
45,96},
                         {
11,77},
                         {
2,32},
                         {
1,12},
                         {
13,69},
                         };
  
this.houselist NULL;
  for(
temp.i=0temp.i<100temp.i++)
  {
    
this.intA 0;
    
this.intB 0;
    while(!
this.intA && !this.intB)
    {
      
this.intA int(random(0,400));
      
this.intB int(random(0,400));
      for(
temp.j=0temp.j<100temp.j++)
      {
        if(
this.intA == this.houselist[temp.j][0])
          
this.int 0;
        else if(
this.intA == this.houselist[temp.j][1])
          
this.int 0;
        else if(
this.intB == this.houselist[temp.j][0])
          
this.int 0;
        else if(
this.intB == this.houselist[temp.j][1])
          
this.int 0;
        if(
this.intA == this.incompatibility[temp.j])
          if(
this.intB == this.incompatibility[temp.j])
            
this.int 0;
        else if(
this.intB == this.incompatibility[temp.j])
          if(
this.intA == this.incompatibility[temp.j])
            
this.int 0;
      }
      if(
this.intA == this.intB)
        
this.int 0;
    }
    
this.houselist.add({this.intA,this.intB});
  }
  
this.end timevar2;
}
savelog2("houseList.txt",this.houselist);
echo(
"Time: " this.end this.start); 
Time: 0.026829004

Damn that's slow compared to others lol
I didn't try it, but, like said, anything using random will not work well with larger numbers.
__________________
Reply With Quote
  #32  
Old 06-18-2008, 11:00 PM
Dan Dan is offline
Daniel
Join Date: Oct 2007
Posts: 383
Dan is an unknown quantity at this point
Send a message via MSN to Dan
I think it's slow because of the logging you're doing. But yeah, quite some loops also.
__________________
Reply With Quote
  #33  
Old 06-21-2008, 06:36 AM
Stryke Stryke is offline
Scripter
Join Date: Apr 2008
Posts: 157
Stryke is an unknown quantity at this point
Oh it's only 50? :P

Time remaining: 0.007151126

Still crappy. :P I took out the log too.
Reply With Quote
  #34  
Old 06-21-2008, 06:52 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
We can assume that the algorithm would eventually need to be used to find an appropriate room assignment for a group of students for which there is only one solution (i.e. worst case scenario). Because of this, the algorithm would need to "know" that student A needs to pair with student B rather than student C. Hence why random is a horrible idea.
__________________
◕‿‿◕ · 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
  #35  
Old 07-19-2008, 09:26 PM
WhiteDragon WhiteDragon is offline
Banned
Join Date: Feb 2007
Posts: 1,002
WhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to behold
PHP Code:
//#CLIENTSIDE
function onWeaponFired() {
  
// Bad match array
  
temp.bad = {
             {
91,50},
             {
60,230},
             {
132,399},
             {
52,293},
             {
22,25},
             {
83,293},
             {
83,82}
             };
  
// Generate students array
  
temp.students = new[400];
  for (
temp.0temp.400temp.i++)
    
temp.students[temp.i] = temp.i;



  
// START of exercise
  
temp.start timevar2;

  
// Shuffle students array
  
temp.temp.students.size();
  for (
temp.0temp.temp.1temp.i++) {
    
temp.temp.random(0,32767) / (32767 / (temp.temp.i) + 1);
    
temp.temp.students[temp.j];
    
temp.students[temp.j] = temp.students[temp.i];
    
temp.students[temp.i] = temp.t;
  }
  
  
// Heapsort the bad match array
  
temp.bad.sortascending();
  
  
temp.pairs = new[50];
  
temp.0;
  while (
temp.50) {
    
temp.pair = {temp.students[temp.x], temp.students[temp.x+1]};

    
// Binary search for the current pair in the bad pairs
    
if (binarysearcharray(temp.badtemp.pair) == -1) {
      
temp.pairs[temp.i] = temp.pair;
      
temp.x++;
    }
    
temp.x++;
    
temp.i++;
  }
  
  
  
// END of exercise
  
temp.time timevar2 temp.start;
    
  
player.chat temp.pairs;
  echo (
temp.time);
}

// Modified binary search
function binarysearcharray(temp.atemp.v) {
  
temp.low 0;
  
temp.high temp.a.size()-1;
  while (
temp.low <= temp.high) {
    
temp.mid = (temp.low temp.high) /2;
    if (
temp.a[temp.mid][0] > temp.v[0] || temp.a[temp.mid][0] == temp.v[0] && temp.a[temp.mid][1] > temp.v[1]) 
      
temp.high temp.mid 1;
    else if (
temp.a[temp.mid][0] < temp.v[0] || temp.a[temp.mid][0] == temp.v[0] && temp.a[temp.mid][1] < temp.v[1])
      
temp.low temp.mid +1;
    else
      return 
temp.mid;
  }
  return -
1;

Average running time of 0.00326736083, but it's a rather small "bad pair" set.

Should run in O(n log n log m) where n is the number of pairs and m is the number of bad pairs.

Last edited by WhiteDragon; 07-20-2008 at 09:20 PM.. Reason: Slight mistake
Reply With Quote
  #36  
Old 07-21-2008, 07:47 AM
WhiteDragon WhiteDragon is offline
Banned
Join Date: Feb 2007
Posts: 1,002
WhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to behold
I realized I made an error, but it wouldn't let me edit it... so here is another giant block of code:

PHP Code:
//#CLIENTSIDE
function onWeaponFired() {
  
// Bad match array
  
temp.bad = {
             {
91,50},
             {
60,230},
             {
132,399},
             {
52,293},
             {
22,25},
             {
83,293},
             {
83,82}
             };
  
// Generate students array
  
temp.students = new[400];
  for (
temp.0temp.400temp.i++)
    
temp.students[temp.i] = temp.i;



  
// START of exercise
  
temp.start timevar2;

  
// Shuffle students array
  
temp.temp.students.size();
  for (
temp.0temp.temp.1temp.i++) {
    
temp.temp.random(0,32767) / (32767 / (temp.temp.i) + 1);
    
temp.temp.students[temp.j];
    
temp.students[temp.j] = temp.students[temp.i];
    
temp.students[temp.i] = temp.t;
  }
  
  
// Heapsort the bad match array
  
temp.bad.sortascending();
  
  
temp.pairs = new[50];
  
temp.0;
  while (
temp.50) {
    
temp.pair = {temp.students[temp.x], temp.students[temp.x+1]};

    
// Binary search for the current pair in the bad pairs
    
if (binarysearcharray(temp.badtemp.pair) == -1) {
      
// Add it
      
temp.pairs[temp.i] = temp.pair;
      
temp.students.remove(temp.students[temp.x]);
      
temp.students.remove(temp.students[temp.y]);
      
temp.i++;
      
temp.0;
      
temp.0;
    } else {
      
// Look more
      
if (temp.== temp.students.size()) {
        
temp.x++;
        
temp.0;
      } else {
        
temp.y++;
      }
    }
  }
  
  
  
// END of exercise
  
temp.time timevar2 temp.start;
    
  
player.chat temp.pairs;
  echo (
temp.time);
}

// Modified binary search
function binarysearcharray(temp.atemp.v) {
  
temp.low 0;
  
temp.high temp.a.size()-1;
  while (
temp.low <= temp.high) {
    
temp.mid = (temp.low temp.high) /2;
    if (
temp.a[temp.mid][0] > temp.v[0] || temp.a[temp.mid][0] == temp.v[0] && temp.a[temp.mid][1] > temp.v[1]) 
      
temp.high temp.mid 1;
    else if (
temp.a[temp.mid][0] < temp.v[0] || temp.a[temp.mid][0] == temp.v[0] && temp.a[temp.mid][1] < temp.v[1])
      
temp.low temp.mid +1;
    else
      return 
temp.mid;
  }
  return -
1;

Worst case is actually O(n**2 log n log m), but it uses Randomization and Restriction, so it's considerably fast than the worst case.
Reply With Quote
  #37  
Old 08-02-2008, 11:24 AM
_Z3phyr_ _Z3phyr_ is offline
Banned
Join Date: Sep 2003
Location: Louisiane
Posts: 390
_Z3phyr_ is an unknown quantity at this point
Quote:
Originally Posted by Tolnaftate2004 View Post
Today's challenge will include 2 problems:
  1. hard Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice.
    The point of this exercise is to GENERATE DISCUSSION. We are not asking you to WRITE the code, merely speculate as to how you might do it. BUT IF YOU FEEL COMPELLED, write the code to accomodate arbitrary lists from the Dean.

Note From Hell Raven: the 100 students are rooming in pairs of 2. So that is 50 pairs (I do not believe this was clear...)

answer:





proof:

N and B are disjoint sets. (see above picture)

---

this is an abstract problem. idk what you guys have been doing with all of that prime number crap.

Last edited by _Z3phyr_; 08-02-2008 at 01:40 PM..
Reply With Quote
  #38  
Old 08-02-2008, 10:35 PM
WhiteDragon WhiteDragon is offline
Banned
Join Date: Feb 2007
Posts: 1,002
WhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to beholdWhiteDragon is a splendid one to behold
This problem is NP-complete, so it's impossible to do it in polynomial time.
The runtime is actually O(n**m) if you check all conditions. The best way to attack the problem would most likely be dynamic programming.
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 11:53 PM.


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