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

#1
06-13-2008, 09:46 PM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Programming Exercise #4: Super fun edition

 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. 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...)
 __________________ ◕‿‿◕ · 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 Kristi; 06-16-2008 at 07:29 PM..
#2
06-14-2008, 12:47 AM
 DrakilorP2P Registered User Join Date: Apr 2006 Posts: 755
 Only primes are incompatible to other numbers? There's only 61 primes below 400. Isn't this easily solvable by including everyone who isn't a prime until you run out of space?
#3
06-14-2008, 01:10 AM
 cbk1994 the fake one Join Date: Mar 2003 Location: San Francisco Posts: 10,718
Quote:
 Originally Posted by DrakilorP2P Only primes are incompatible to other numbers? There's only 61 primes below 400. Isn't this easily solvable by including everyone who isn't a prime until you run out of space?
I guess the problem is figuring out who is a prime and who isn't ... but if I recall that's quite easy.
 __________________
#4
06-14-2008, 03:01 AM
 DrakilorP2P Registered User Join Date: Apr 2006 Posts: 755
Quote:
 Originally Posted by cbk1994 I guess the problem is figuring out who is a prime and who isn't ... but if I recall that's quite easy.
It's basic level programming.
#5
06-14-2008, 03:15 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
 It doesn't matter who is included. Make it include only 100 people, I don't care... Finding primes is trivial. I'm sure I could go online and find a list of them, this is not the point of the exercise. I have done this for you: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397
 __________________ ◕‿‿◕ · 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 :/
#6
06-14-2008, 04:25 AM
 cbk1994 the fake one Join Date: Mar 2003 Location: San Francisco Posts: 10,718
Quote:
 Originally Posted by Tolnaftate2004 It doesn't matter who is included. Make it include only 100 people, I don't care... Finding primes is trivial. I'm sure I could go online and find a list of them, this is not the point of the exercise. I have done this for you: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397
Easiest way has GOT to be to loop through every possible combination of two numbers that could possibly be a prime. Most efficient, too!
 __________________
#7
06-14-2008, 04:39 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by cbk1994 Easiest way has GOT to be to loop through every possible combination of two numbers that could possibly be a prime. Most efficient, too!
I updated the exercise. So, primes are no longer involved.
 __________________ ◕‿‿◕ · 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 :/
#8
06-14-2008, 04:53 AM
 cbk1994 the fake one Join Date: Mar 2003 Location: San Francisco Posts: 10,718
 PHP Code: function onCreated(){  temp.start = timevar2;    temp.incompatible = {                        { 1, 2 },                        { 3, 4 },                        { 5, 6 },                        { 6, 7 }                      };    temp.chosen = null;  temp.sets = null;    for ( temp.i = 0; i < 100; i ++ )  {    temp.moveOn = false;        while ( ! moveOn )    {      temp.person1 = int( random( 0, 400 ) );      temp.person2 = int( random( 0, 400 ) );            if ( chosen.index( @ person1 ) != -1 || chosen.index( @ person2 ) != -1 || person1 == person2 )      {        continue;      }            for ( temp.a : incompatible )      {        if ( ( a[0] == person1 && a[1] == person2 ) || ( a[0] == person2 || a[1] == person1 ) )        {          // Incompatible          continue;        }      }            chosen.add( person1 );      chosen.add( person2 );            sets.add( { person1, person2 } );            moveOn = true;    }  }    for ( temp.set : sets )  {    echo( "Set:" SPC set[0] SPC "and" SPC set[1] );  }    echo( "Time taken:" SPC timevar2 - start SPC "seconds." );}  I made it as inefficient as possible. It's rather fun to make inefficient code . I don't know why. PHP Code: Set: 59 and 119Set: 166 and 136Set: 279 and 156Set: 131 and 142Set: 195 and 397Set: 364 and 340Set: 314 and 382Set: 326 and 216Set: 352 and 140Set: 366 and 139Set: 12 and 32Set: 104 and 21Set: 92 and 75Set: 307 and 68Set: 271 and 367Set: 187 and 38Set: 103 and 66Set: 194 and 235Set: 209 and 390Set: 232 and 174Set: 331 and 147Set: 363 and 109Set: 398 and 329Set: 249 and 11Set: 362 and 354Set: 29 and 312Set: 170 and 337Set: 380 and 42Set: 304 and 167Set: 80 and 8Set: 234 and 275Set: 244 and 44Set: 265 and 76Set: 218 and 197Set: 224 and 375Set: 55 and 188Set: 84 and 54Set: 118 and 334Set: 288 and 98Set: 135 and 318Set: 10 and 305Set: 347 and 160Set: 158 and 28Set: 169 and 393Set: 303 and 13Set: 90 and 255Set: 230 and 22Set: 302 and 138Set: 240 and 37Set: 57 and 251Set: 343 and 313Set: 242 and 291Set: 73 and 0Set: 319 and 243Set: 394 and 223Set: 256 and 31Set: 392 and 346Set: 287 and 359Set: 261 and 117Set: 33 and 58Set: 186 and 283Set: 201 and 88Set: 126 and 78Set: 293 and 69Set: 360 and 65Set: 309 and 130Set: 162 and 95Set: 112 and 49Set: 339 and 200Set: 214 and 106Set: 184 and 231Set: 47 and 105Set: 15 and 237Set: 133 and 282Set: 205 and 72Set: 207 and 61Set: 146 and 125Set: 381 and 257Set: 64 and 149Set: 128 and 268Set: 324 and 322Set: 2 and 122Set: 226 and 46Set: 306 and 51Set: 178 and 35Set: 248 and 185Set: 369 and 155Set: 43 and 145Set: 183 and 311Set: 91 and 353Set: 14 and 115Set: 157 and 358Set: 213 and 171Set: 289 and 350Set: 290 and 286Set: 87 and 388Set: 217 and 159Set: 294 and 357Set: 148 and 24Set: 374 and 1Time taken: 0.008700847 seconds.
 __________________
#9
06-14-2008, 05:11 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
 I tried your code and it failed to perform the task. Leaving this to chance is probably a bad idea, seeing as it could lead to an infinite loop.
 __________________ ◕‿‿◕ · 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 :/
#10
06-14-2008, 05:15 AM
 cbk1994 the fake one Join Date: Mar 2003 Location: San Francisco Posts: 10,718
Quote:
 Originally Posted by Tolnaftate2004 I tried your code and it failed to perform the task. Leaving this to chance is probably a bad idea, seeing as it could lead to an infinite loop.
Worked fine for me ;o

The whole goal was inefficiency
 __________________
#11
06-14-2008, 05:57 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by cbk1994 Worked fine for me ;o The whole goal was inefficiency
Well I changed the incompatibilities so that any person would only match up with one other person.
 __________________ ◕‿‿◕ · 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 :/
#12
06-14-2008, 06:12 AM
 cbk1994 the fake one Join Date: Mar 2003 Location: San Francisco Posts: 10,718
Quote:
 Originally Posted by Tolnaftate2004 Well I changed the incompatibilities so that any person would only match up with one other person.
o

Probably hit a max loop limit.
 __________________
#13
06-14-2008, 07:26 AM
 Programmer Coder Join Date: Jan 2008 Location: -78.464422, 106.837328 Posts: 449
 I suppose what you would have to do is this: Starting with 400 students, loop through and select 100 students at random. Then go through those 100 students and group then until you have 50 groups. If you have 2 students who are together on the incompatibility list, flip them with another set at random, as described below: 1 & 2 v ^ 3 & 4 3 & 2 1 & 4 If any of those 2 are on the incompatibility list, then repeat the process. Once everything is OK, then you've got your list. Here's the script I made to accompany this concept: 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.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 taken: 0.002021789 Example Output: PHP Code: 0.002021789 Group 1: {137, 114} Group 2: {282, 284} Group 3: {47, 288} Group 4: {267, 53} Group 5: {19, 329} Group 6: {345, 299} Group 7: {141, 228} Group 8: {93, 50} Group 9: {347, 390} Group 10: {166, 207} Group 11: {139, 41} Group 12: {130, 336} Group 13: {140, 376} Group 14: {262, 238} Group 15: {196, 0} Group 16: {352, 79} Group 17: {368, 151} Group 18: {54, 387} Group 19: {81, 108} Group 20: {332, 380} Group 21: {249, 160} Group 22: {73, 300} Group 23: {64, 66} Group 24: {316, 204} Group 25: {248, 24} Group 26: {8, 111} Group 27: {215, 396} Group 28: {252, 148} Group 29: {270, 240} Group 30: {229, 378} Group 31: {172, 209} Group 32: {227, 333} Group 33: {283, 127} Group 34: {42, 194} Group 35: {359, 302} Group 36: {6, 292} Group 37: {30, 293} Group 38: {105, 374} Group 39: {371, 324} Group 40: {242, 119} Group 41: {83, 348} Group 42: {256, 158} Group 43: {189, 128} Group 44: {232, 389} Group 45: {322, 191} Group 46: {225, 197} Group 47: {33, 334} Group 48: {239, 121} Group 49: {39, 213} Group 50: {230, 29}  Probably not very efficient, but it works. I couldn't find any incompatibilities! XD
 __________________ - Iᴀɴ Zɪᴍᴍᴇʀᴍᴀɴ
#14
06-14-2008, 07:36 AM
 Tolnaftate2004 penguin. Join Date: Jul 2004 Location: Berkeley, CA Posts: 534
Quote:
 Originally Posted by Programmer Probably not very efficient, but it works. I couldn't find any incompatibilities! XD
This does not test if switching 2 people forms compatibility...
 __________________ ◕‿‿◕ · 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 :/
#15
06-14-2008, 07:44 AM
 Programmer Coder Join Date: Jan 2008 Location: -78.464422, 106.837328 Posts: 449
Quote:
 Originally Posted by Tolnaftate2004 This does not test if switching 2 people forms compatibility...
Picky, Picky.

PHP Code:
function onCreated()
{

this.start timevar2;

this.incompatability = {
{
102284},
{
392126},
{
12},
{
34},
{
56},
{
78}
};

this.studentsSelected.clear();

this.studentGroups.clear();

numStudentsSelected 0;

// Select students at random

for (0100i++)
{

int(random(0400));

if (
this.studentsSelected.index(f) == -1)
{

} else
{

i--; continue;
}
}

// Group them

for (0this.studentsSelected.size(); += 2)
{

}

// Remove incompatabilities

for (050i++)
{

sGroup this.studentGroups[i];

for (
0this.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 (
050i++)
{
echo(
"Group " @ (i+1) @ ": {" this.studentGroups[i][0] @ ", " this.studentGroups[i][1] @ "}");
}

Time: 0.001927852
 __________________ - Iᴀɴ Zɪᴍᴍᴇʀᴍᴀɴ

 Tags programming-exercise