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
  #1  
Old 06-13-2008, 09:46 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
Programming Exercise #4: Super fun edition

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.
  2. 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..
Reply With Quote
  #2  
Old 06-14-2008, 12:47 AM
DrakilorP2P DrakilorP2P is offline
Registered User
DrakilorP2P's Avatar
Join Date: Apr 2006
Posts: 755
DrakilorP2P is just really niceDrakilorP2P is just really nice
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?
Reply With Quote
  #3  
Old 06-14-2008, 01:10 AM
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 DrakilorP2P View Post
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.
__________________
Reply With Quote
  #4  
Old 06-14-2008, 03:01 AM
DrakilorP2P DrakilorP2P is offline
Registered User
DrakilorP2P's Avatar
Join Date: Apr 2006
Posts: 755
DrakilorP2P is just really niceDrakilorP2P is just really nice
Quote:
Originally Posted by cbk1994 View Post
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.
Reply With Quote
  #5  
Old 06-14-2008, 03:15 AM
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
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 :/
Reply With Quote
  #6  
Old 06-14-2008, 04:25 AM
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 Tolnaftate2004 View Post
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!
__________________
Reply With Quote
  #7  
Old 06-14-2008, 04:39 AM
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
Quote:
Originally Posted by cbk1994 View Post
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 :/
Reply With Quote
  #8  
Old 06-14-2008, 04:53 AM
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
PHP Code:
function onCreated()
{
  
temp.start timevar2;
  
  
temp.incompatible = {
                        { 
1},
                        { 
3},
                        { 
5},
                        { 
6}
                      };
  
  
temp.chosen null;
  
temp.sets null;
  
  for ( 
temp.0100++ )
  {
    
temp.moveOn false;
    
    while ( ! 
moveOn )
    {
      
temp.person1 intrandom0400 ) );
      
temp.person2 intrandom0400 ) );
      
      if ( 
chosen.index( @ person1 ) != -|| chosen.index( @ person2 ) != -|| person1 == person2 )
      {
        continue;
      }
      
      for ( 
temp.incompatible )
      {
        if ( ( 
a[0] == person1 && a[1] == person2 ) || ( a[0] == person2 || a[1] == person1 ) )
        {
          
// Incompatible
          
continue;
        }
      }
      
      
chosen.addperson1 );
      
chosen.addperson2 );
      
      
sets.add( { person1person2 } );
      
      
moveOn true;
    }
  }
  
  for ( 
temp.set sets )
  {
    echo( 
"Set:" SPC set[0SPC "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:
Set59 and 119
Set
166 and 136
Set
279 and 156
Set
131 and 142
Set
195 and 397
Set
364 and 340
Set
314 and 382
Set
326 and 216
Set
352 and 140
Set
366 and 139
Set
12 and 32
Set
104 and 21
Set
92 and 75
Set
307 and 68
Set
271 and 367
Set
187 and 38
Set
103 and 66
Set
194 and 235
Set
209 and 390
Set
232 and 174
Set
331 and 147
Set
363 and 109
Set
398 and 329
Set
249 and 11
Set
362 and 354
Set
29 and 312
Set
170 and 337
Set
380 and 42
Set
304 and 167
Set
80 and 8
Set
234 and 275
Set
244 and 44
Set
265 and 76
Set
218 and 197
Set
224 and 375
Set
55 and 188
Set
84 and 54
Set
118 and 334
Set
288 and 98
Set
135 and 318
Set
10 and 305
Set
347 and 160
Set
158 and 28
Set
169 and 393
Set
303 and 13
Set
90 and 255
Set
230 and 22
Set
302 and 138
Set
240 and 37
Set
57 and 251
Set
343 and 313
Set
242 and 291
Set
73 and 0
Set
319 and 243
Set
394 and 223
Set
256 and 31
Set
392 and 346
Set
287 and 359
Set
261 and 117
Set
33 and 58
Set
186 and 283
Set
201 and 88
Set
126 and 78
Set
293 and 69
Set
360 and 65
Set
309 and 130
Set
162 and 95
Set
112 and 49
Set
339 and 200
Set
214 and 106
Set
184 and 231
Set
47 and 105
Set
15 and 237
Set
133 and 282
Set
205 and 72
Set
207 and 61
Set
146 and 125
Set
381 and 257
Set
64 and 149
Set
128 and 268
Set
324 and 322
Set
and 122
Set
226 and 46
Set
306 and 51
Set
178 and 35
Set
248 and 185
Set
369 and 155
Set
43 and 145
Set
183 and 311
Set
91 and 353
Set
14 and 115
Set
157 and 358
Set
213 and 171
Set
289 and 350
Set
290 and 286
Set
87 and 388
Set
217 and 159
Set
294 and 357
Set
148 and 24
Set
374 and 1
Time taken
0.008700847 seconds
__________________
Reply With Quote
  #9  
Old 06-14-2008, 05:11 AM
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
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 :/
Reply With Quote
  #10  
Old 06-14-2008, 05:15 AM
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 Tolnaftate2004 View Post
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
__________________
Reply With Quote
  #11  
Old 06-14-2008, 05:57 AM
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
Quote:
Originally Posted by cbk1994 View Post
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 :/
Reply With Quote
  #12  
Old 06-14-2008, 06:12 AM
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 Tolnaftate2004 View Post
Well I changed the incompatibilities so that any person would only match up with one other person.
o

Probably hit a max loop limit.
__________________
Reply With Quote
  #13  
Old 06-14-2008, 07:26 AM
Programmer Programmer is offline
Coder
Programmer's Avatar
Join Date: Jan 2008
Location: -78.464422, 106.837328
Posts: 449
Programmer has a spectacular aura aboutProgrammer has a spectacular aura about
Send a message via AIM to Programmer Send a message via MSN to Programmer Send a message via Yahoo to Programmer
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 = {
    {
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)
    {
      
this.studentsSelected.add(f);
    } else
    {
      
i--; continue;
    }
  }
  
  
// Group them
  
for (0this.studentsSelected.size(); += 2)
  {
    
this.studentGroups.add({this.studentsSelected[i], this.studentsSelected[i+1]});
  }
  
  
// 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.end timevar2;
  
  echo(
this.end this.start);
  
  for (
050i++)
  {
    echo(
"Group " @ (i+1) @ ": {" this.studentGroups[i][0] @ ", " this.studentGroups[i][1] @ "}");
  }

Time taken: 0.002021789

Example Output:
PHP Code:
0.002021789
Group 1
: {137114}
Group 2: {282284}
Group 3: {47288}
Group 4: {26753}
Group 5: {19329}
Group 6: {345299}
Group 7: {141228}
Group 8: {9350}
Group 9: {347390}
Group 10: {166207}
Group 11: {13941}
Group 12: {130336}
Group 13: {140376}
Group 14: {262238}
Group 15: {1960}
Group 16: {35279}
Group 17: {368151}
Group 18: {54387}
Group 19: {81108}
Group 20: {332380}
Group 21: {249160}
Group 22: {73300}
Group 23: {6466}
Group 24: {316204}
Group 25: {24824}
Group 26: {8111}
Group 27: {215396}
Group 28: {252148}
Group 29: {270240}
Group 30: {229378}
Group 31: {172209}
Group 32: {227333}
Group 33: {283127}
Group 34: {42194}
Group 35: {359302}
Group 36: {6292}
Group 37: {30293}
Group 38: {105374}
Group 39: {371324}
Group 40: {242119}
Group 41: {83348}
Group 42: {256158}
Group 43: {189128}
Group 44: {232389}
Group 45: {322191}
Group 46: {225197}
Group 47: {33334}
Group 48: {239121}
Group 49: {39213}
Group 50: {23029
Probably not very efficient, but it works. I couldn't find any incompatibilities! XD
__________________
- Iᴀɴ Zɪᴍᴍᴇʀᴍᴀɴ
Reply With Quote
  #14  
Old 06-14-2008, 07:36 AM
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
Quote:
Originally Posted by Programmer View Post
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 :/
Reply With Quote
  #15  
Old 06-14-2008, 07:44 AM
Programmer Programmer is offline
Coder
Programmer's Avatar
Join Date: Jan 2008
Location: -78.464422, 106.837328
Posts: 449
Programmer has a spectacular aura aboutProgrammer has a spectacular aura about
Send a message via AIM to Programmer Send a message via MSN to Programmer Send a message via Yahoo to Programmer
Quote:
Originally Posted by Tolnaftate2004 View Post
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)
    {
      
this.studentsSelected.add(f);
    } else
    {
      
i--; continue;
    }
  }
  
  
// Group them
  
for (0this.studentsSelected.size(); += 2)
  {
    
this.studentGroups.add({this.studentsSelected[i], this.studentsSelected[i+1]});
  }
  
  
// 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ɪᴍᴍᴇʀᴍᴀɴ
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 08:41 AM.


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