Graal Forums Programming Exercise #4: Super fun edition
 FAQ Members List Calendar Search Today's Posts Mark Forums Read

#16
06-14-2008, 08:46 AM
 cbk1994 the fake one Join Date: Mar 2003 Location: San Francisco Posts: 10,718
Quote:
 Originally Posted by Programmer Time: 0.001927852
Aww, mine was 0.008700847 seconds.

Of course, I was trying to make mine inefficient, for some reason ...
 __________________
#17
06-14-2008, 03:14 PM
 Programmer Coder Join Date: Jan 2008 Location: -78.464422, 106.837328 Posts: 449
Quote:
 Originally Posted by cbk1994 Aww, mine was 0.008700847 seconds. Of course, I was trying to make mine inefficient, for some reason ...
Perhaps too many nested loops?
 __________________ - Iᴀɴ Zɪᴍᴍᴇʀᴍᴀɴ
#18
06-14-2008, 07:50 PM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by Programmer 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).
 __________________ ◕‿‿◕ · 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 :/
#19
06-14-2008, 08:03 PM
 Dan Daniel Join Date: Oct 2007 Posts: 383
Quote:
 Originally Posted by Tolnaftate2004 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
 __________________ Email: [email protected]
#20
06-14-2008, 08:20 PM
 cbk1994 the fake one Join Date: Mar 2003 Location: San Francisco Posts: 10,718
Quote:
 Originally Posted by Dan 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?
 __________________
#21
06-15-2008, 04:49 PM
 Dan Daniel Join Date: Oct 2007 Posts: 383
 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
 __________________ Email: [email protected]

Last edited by Dan; 06-15-2008 at 05:07 PM.. Reason: Added time.
#22
06-15-2008, 05:39 PM
 Chompy Ż\(ş_o)/Ż Join Date: Sep 2006 Location: Norway Posts: 2,815
 Uhm, Dan, suppose to be discussion :o
 __________________
#23
06-15-2008, 06:33 PM
 Dan Daniel Join Date: Oct 2007 Posts: 383
Quote:
 Originally Posted by Chompy Uhm, Dan, suppose to be discussion :o
Well then this is how I'd make the groups, lol.
 __________________ Email: [email protected]
#24
06-15-2008, 06:35 PM
 Chompy Ż\(ş_o)/Ż Join Date: Sep 2006 Location: Norway Posts: 2,815
Quote:
 Originally Posted by Dan Well then this is how I'd make the groups, lol.
Try explain it with words instead of code
 __________________
#25
06-15-2008, 09:17 PM
 Dan Daniel Join Date: Oct 2007 Posts: 383
Quote:
 Originally Posted by Chompy Try explain it with words instead of code
I want to know if it does what it should do tho (if I did what was needed).
 __________________ Email: [email protected]
#26
06-16-2008, 07:36 PM
 Kristi Bowie's Deciple Join Date: Dec 2003 Location: Boston, MA Posts: 748
 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
 __________________
#27
06-16-2008, 10:41 PM
 cbk1994 the fake one Join Date: Mar 2003 Location: San Francisco Posts: 10,718
Quote:
 Originally Posted by Kristi 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
 __________________
#28
06-16-2008, 10:48 PM
 Kristi Bowie's Deciple Join Date: Dec 2003 Location: Boston, MA Posts: 748
Quote:
 Originally Posted by cbk1994 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).
 __________________
#29
06-16-2008, 11:03 PM
 Dan Daniel Join Date: Oct 2007 Posts: 383
Quote:
 Originally Posted by Kristi 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 .
 __________________ Email: [email protected]
#30
06-18-2008, 10:46 PM
 Stryke Scripter Join Date: Apr 2008 Posts: 157
 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

 Tags programming-exercise