Programming Exercise #4: Super fun edition

[Kristi]

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]

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

[Kristi]

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).

[Dan]

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 .

[Stryke]

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

[cbk1994]

Originally Posted by Stryke

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.

[Tolnaftate2004]

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.