Graal Forums - Programming Exercise #4: Super fun edition

Page 2 of 3

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 #4: Super fun edition (https://forums.graalonline.com/forums/showthread.php?t=80068)

cbk1994

06-14-2008 08:46 AM

Quote:

Originally Posted by Programmer (Post 1397001)

Time: 0.001927852

Aww, mine was 0.008700847 seconds.

Of course, I was trying to make mine inefficient, for some reason ...

Programmer

06-14-2008 03:14 PM

Quote:

Originally Posted by cbk1994 (Post 1397004)

Aww, mine was 0.008700847 seconds.

Of course, I was trying to make mine inefficient, for some reason ...

Perhaps too many nested loops?

Tolnaftate2004

06-14-2008 07:50 PM

Quote:

Originally Posted by Programmer (Post 1397001)

Picky, Picky.

PHP Code:


		
			
function onCreated()
{
  this.start = timevar2;
  
  this.incompatability = {
    {102, 284},
    {392, 126},
    {1, 2},
    {3, 4},
    {5, 6},
    {7, 8}
  };
  
  
  this.studentsSelected.clear();
  this.studentGroups.clear();
  
  numStudentsSelected = 0;
  // Select students at random
  for (i = 0; i < 100; i++)
  {
    f = int(random(0, 400));
    
    if (this.studentsSelected.index(f) == -1)
    {
      this.studentsSelected.add(f);
    } else
    {
      i--; continue;
    }
  }
  
  // Group them
  for (i = 0; i < this.studentsSelected.size(); i += 2)
  {
    this.studentGroups.add({this.studentsSelected[i], this.studentsSelected[i+1]});
  }
  
  // Remove incompatabilities
  for (i = 0; i < 50; i++)
  {
    sGroup = this.studentGroups[i];
    
    for (a = 0; a < this.incompatability.size(); a++)
    {
      if ((sGroup[0] == this.incompatability[a][0] || sGroup[0] == this.incompatability[a][1]) && (sGroup[1] == this.incompatability[a][0] || sGroup[1] == this.incompatability[a][1]))
      {
        echo("INCOMPATABILITY: " @ sGroup);
        
        // we've found an incompatability, so lets flip this student with the next group
        sGroup2 = this.studentGroups[i+1];
        
        sGroup[0] = sGroup2[0];
        
        this.studentGroups[i] = sGroup;
        this.studentGroups[i+1] = sGroup2;
        
        i--;
        continue;
      }
    }
  }
  
  this.end = timevar2;
  
  echo(this.end - this.start);
  
  for (i = 0; i < 50; i++)
  {
    echo("Group " @ (i+1) @ ": {" @ this.studentGroups[i][0] @ ", " @ this.studentGroups[i][1] @ "}");
  }
}

Time: 0.001927852

Once again, this failed to perform the task.
Again, let's discuss what we ought to be doing to solve this problem. This is a very difficult problem to solve (HRs idea, don't blame me).

Dan	06-14-2008 08:03 PM

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.
easy Solve this problem.

Is it possible for you to write in a little more simple English for me? :) I don't understand the task quite well, though I'd like to give it a go ;)

cbk1994

06-14-2008 08:20 PM

Quote:

Originally Posted by Dan (Post 1397049)

Is it possible for you to write in a little more simple English for me? :) I don't understand the task quite well, though I'd like to give it a go ;)

1. hard You are putting 400 people in houses. Only 100 people will be able to have a house. You have a list of people that can not be in the same house. 2 people must be in each house. Talk about it, don't script it unless you want to.

Is that a bit better?

Dan	06-15-2008 04:49 PM

Not sure if I entirely understood the task, but I suppose this should work?

PHP Code:


		
			
function onCreated() {
  temp.students_incompatible = {{1,2},{3,49}};
  temp.students_total = new[400];
  temp.house_list = {};
  
  while (temp.house_list.size() < 100) {
    temp.i = 0;
    while (temp.students_total[temp.i] == 1)
      temp.i ++;
    temp.students_total[temp.i] = 1;
    temp.j = temp.i;
    
    temp.go = false;
    while (temp.students_total[temp.j] == 1 || !temp.go) {
      if ((@ {temp.i + 1,temp.j + 1}) in temp.students_incompatible) {
        temp.go = false;
        temp.j ++;
      }
      else if ((@ {temp.j + 1,temp.i + 1}) in temp.students_incompatible) {
        temp.go = false;
        temp.j ++;
      }
      else if (temp.students_total[temp.j] == 1)
        temp.j ++;
      else
        temp.go = true;
    }
    temp.students_total[temp.j] = 1;
    temp.house_list.add({temp.i + 1,temp.j + 1});
  }
  echo(temp.house_list);
}

Time: 0.008579015

Chompy

06-15-2008 05:39 PM

Uhm, Dan, suppose to be discussion :o

Dan	06-15-2008 06:33 PM

Quote:

Originally Posted by Chompy (Post 1397216)

Uhm, Dan, suppose to be discussion :o

Well then this is how I'd make the groups, lol.

Chompy

06-15-2008 06:35 PM

Quote:

Originally Posted by Dan (Post 1397233)

Well then this is how I'd make the groups, lol.

Try explain it with words instead of code :p

Dan	06-15-2008 09:17 PM

Quote:

Originally Posted by Chompy (Post 1397237)

Try explain it with words instead of code :p

I want to know if it does what it should do tho (if I did what was needed).

Kristi

06-16-2008 07:36 PM

You are using very small lists :) Your algorithms are based on the fact that the list is small. If you took your basic ideas and applied them to more complex or impossible lists, they would run much longer then any of our lifetimes.

By impossible, suppose you were given a list of incompatible students that makes it impossible to come up with 100 students.

Your work is cut out for you ;)

cbk1994

06-16-2008 10:41 PM

Quote:

Originally Posted by Kristi (Post 1397490)

If you took your basic ideas and applied them to more complex or impossible lists, they would run much longer then any of our lifetimes.

No, that's why we have a max loop limit ^^

Kristi

06-16-2008 10:48 PM

Quote:

Originally Posted by cbk1994 (Post 1397552)

No, that's why we have a max loop limit ^^

You are supposed to assume a limit doesn't exist (in graal this can be achieved with a scheduleevent).

Dan	06-16-2008 11:03 PM

Quote:

Originally Posted by Kristi (Post 1397560)

You are supposed to assume a limit doesn't exist (in graal this can be achieved with a scheduleevent).

OK. Good luck to anyone trying, Dan's not going to invest any more time in this Programming Exercise because there's more work to do >_<.

Stryke

06-18-2008 10:46 PM

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

All times are GMT +2. The time now is 09:36 AM.

Page 2 of 3

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