Graal Forums - Programming Exercise #4: Super fun edition

Graal Forums (https://forums.graalonline.com/forums/index.php)

- NPC Scripting (https://forums.graalonline.com/forums/forumdisplay.php?f=8)

- - Programming Exercise #4: Super fun edition (https://forums.graalonline.com/forums/showthread.php?t=80068)

Quote:

Originally Posted by Stryke (Post 1397932)

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=0; temp.i<100; temp.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=0; temp.j<100; temp.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.

I think it's slow because of the logging you're doing. But yeah, quite some loops also.

Oh it's only 50? :P

Time remaining: 0.007151126

Still crappy. :P I took out the log too.

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.

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.i = 0; temp.i < 400; temp.i++)
    temp.students[temp.i] = temp.i;



  // START of exercise
  temp.start = timevar2;

  // Shuffle students array
  temp.n = temp.students.size();
  for (temp.i = 0; temp.i < temp.n - 1; temp.i++) {
    temp.j = temp.i + random(0,32767) / (32767 / (temp.n - temp.i) + 1);
    temp.t = 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.i = 0;
  while (temp.i < 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.bad, temp.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.a, temp.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.

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.i = 0; temp.i < 400; temp.i++)

    temp.students[temp.i] = temp.i;







  // START of exercise

  temp.start = timevar2;



  // Shuffle students array

  temp.n = temp.students.size();

  for (temp.i = 0; temp.i < temp.n - 1; temp.i++) {

    temp.j = temp.i + random(0,32767) / (32767 / (temp.n - temp.i) + 1);

    temp.t = 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.i = 0;

  while (temp.i < 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.bad, temp.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.x = 0;

      temp.y = 0;

    } else {

      // Look more

      if (temp.y == temp.students.size()) {

        temp.x++;

        temp.y = 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.a, temp.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.

Quote:

Originally Posted by Tolnaftate2004 (Post 1396887)

Today's challenge will include 2 problems:

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:

http://img376.imageshack.us/img376/5436/86884629uj9.png
http://img376.imageshack.us/img376/5...101aefdfeb.jpg

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.

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.