Thanks & Congrats

[Devrim Altınkurt]

first of all, really thank you for this perfect algorithm.

I am working a time tabling for an university.
it is web based so i tried to convert your algorithm to javascript.
before that, i was using genetic algorithm, but it was so slow.

here are 2 videos:
1)
first video is about comparison between GA and "recursive swap"
left side is GA, right one is yours.

https://www.youtube.com/watch?v=D0PyFRD8Hfk

it is in Turkish but i think you can understand what is going on.

2)
second video is about scheduling 133 activities.
i tried to enforce the algorithm.
and the result is unbelievable:

https://www.youtube.com/watch?v=yI-CB3rrQXg

it took about 30 seconds.


thank you again for this algorithm.
best regards...

[Liviu Lalescu]

Thank you for your report and appreciation!

[Liviu Lalescu]

So, did you manage to translate the algorithm part into Javascript or you worked with the fet command-line executable? Write us any details you consider interesting.

[Devrim Altınkurt]

So, did you manage to translate the algorithm part into Javascript or you worked with the fet command-line executable? Write us any details you consider interesting.

i translated algorithm part directly to javascript. didn't worked with command-line executable.

and I didn't use all constraints & features in fet.

I used theese:
- basic constraints,
- teacher not available times,
- rooms capacities,
- break time contraints,
- and manually placed activities before by school manager.

(i am sure that I can also implement other parts when needed)

***
the things i considered interesting:

1) js doesn't have a "goto" command. and you use too many "goto"

example for "again_if_impossible_activity" in randomswap function:

//again_if_impossible_activity:
for (; ; ) {
...
...
...
if (...){
   //goto again_if_impossible_activity;
   continue;
   }
break;
} // for;;


2) i implemented Qt objects (QList, QSet, Matrix1D, Matrix2D, Matrix3D, QHash)

example:

var QList = function () {
    var obj = [];

    this.count = function () {
        return obj.length;
    }
    this.size = function () {
        return this.count();
    }
    this.indexOf = function (x) {
        return obj.indexOf(x);
    }
    this.contains = function (x) {
        return obj.indexOf(x) > -1;
    }
    this.clear = function () {
        obj = [];
    }
    this.removeAll = function (x) {
        var i = 0;
        var s = 0;
        for (var i = obj.length - 1; i >= 0; i--) {
            if (obj === x) {
                s++;
                obj.splice(i, 1);
            }
        }
        return s;
    }

    this.append = function (x) {
        obj.push(x);
    }

    this.get = function (x) {
        return obj

• ;
      }
      this.set = function (x, val) {
          obj
• = val;
      }
      this.all = function () { return obj; }
  }
  
  3) javascript doesn't have "#define"
  
  #define nMinDaysBroken         (nMinDaysBrokenL[level])
  #define selectedRoom         (selectedRoomL[level])
  #define perm               (permL[level])
  #define conflActivities         (conflActivitiesL[level])
  #define nConflActivities      (nConflActivitiesL[level])
  #define roomSlots            (roomSlotsL[level])
  
  4) in javascript, the functions doesn't support passing parameters by reference for primitive types.
  example:
  
  void Generate::generate(int maxSeconds, bool& impossible, bool& timeExceeded, bool threaded, QTextStream* maxPlacedActivityStream)
  
  I implemented as follows:
  this.generate = function (pars) {
  ...
  }
  
  var pars = {
              maxSeconds: 1000000,
              impossible: false,
              timeExceeded: false
          };
  gen.generate(pars);
  
  5)
  javascript doesn't support "operator overloading" and "indexers"
  
  template <typename T> inline T* Matrix2D<T>::operator[](int i)
  {
     return a;
  }
  
  6) i really liked your "randomly sorting 1D array" code.
  
  best regards..

[Liviu Lalescu]

So, did you manage to translate the algorithm part into Javascript or you worked with the fet command-line executable? Write us any details you consider interesting.

i translated algorithm part directly to javascript. didn't worked with command-line executable.

This is a tough job you did. If you want to show your work, I could add a link to your page in the Tools/Links section of FET. Just let me know.

and I didn't use all constraints & features in fet.

I used theese:
- basic constraints,
- teacher not available times,
- rooms capacities,
- break time contraints,
- and manually placed activities before by school manager.

(i am sure that I can also implement other parts when needed)

***
the things i considered interesting:

1) js doesn't have a "goto" command. and you use too many "goto"

example for "again_if_impossible_activity" in randomswap function:

//again_if_impossible_activity:
for (; ; ) {
...
...
...
if (...){
   //goto again_if_impossible_activity;
   continue;
   }
break;
} // for;;

2) i implemented Qt objects (QList, QSet, Matrix1D, Matrix2D, Matrix3D, QHash)

example:

var QList = function () {
    var obj = [];

    this.count = function () {
        return obj.length;
    }
    this.size = function () {
        return this.count();
    }
    this.indexOf = function (x) {
        return obj.indexOf(x);
    }
    this.contains = function (x) {
        return obj.indexOf(x) > -1;
    }
    this.clear = function () {
        obj = [];
    }
    this.removeAll = function (x) {
        var i = 0;
        var s = 0;
        for (var i = obj.length - 1; i >= 0; i--) {
            if (obj === x) {
                s++;
                obj.splice(i, 1);
            }
        }
        return s;
    }

    this.append = function (x) {
        obj.push(x);
    }

    this.get = function (x) {
        return obj

• ;
      }
      this.set = function (x, val) {
          obj
• = val;
      }
      this.all = function () { return obj; }
  }
  
  

Matrix1D, 2D, and 3D are actually my simple tricks to obtain a good speed for generation. They were added after the initial code was written, when I needed to convert the code from static matrices to dynamically allocated arrays.

3) javascript doesn't have "#define"

#define nMinDaysBroken         (nMinDaysBrokenL[level])
#define selectedRoom         (selectedRoomL[level])
#define perm               (permL[level])
#define conflActivities         (conflActivitiesL[level])
#define nConflActivities      (nConflActivitiesL[level])
#define roomSlots            (roomSlotsL[level])

These are again some simple tricks for a better generation speed.

4) in javascript, the functions doesn't support passing parameters by reference for primitive types.
example:

void Generate::generate(int maxSeconds, bool& impossible, bool& timeExceeded, bool threaded, QTextStream* maxPlacedActivityStream)

I implemented as follows:
this.generate = function (pars) {
...
}

var pars = {
            maxSeconds: 1000000,
            impossible: false,
            timeExceeded: false
        };
gen.generate(pars);

5)
javascript doesn't support "operator overloading" and "indexers"

template <typename T> inline T* Matrix2D<T>::operator[](int i)
{
   return a;
}

6) i really liked your "randomly sorting 1D array" code.

Thanks! Do you mean randomizing a 1D array, or sorting the perm[] array by the number of conflicts, after computing the number of conflicts for each perm?

Actually, randomizing the 1D array in O(n) I got it from Cormen, Leiserson and Rivest. Before that, I used a bad O(n^2) approximate procedure, to swap n^2 random pairs.

best regards..

[Devrim Altınkurt]

Do you mean randomizing a 1D array, or sorting the perm[] array by the number of conflicts, after computing the number of conflicts for each perm?

I wrote about theese parts:

(getPreferredRoom)

Code Select Expand

for (var i = 0; i < allowedRoomsList.count(); i++) {
var t = allowedRoomsList.get(i); // at
var r = randomKnuth(allowedRoomsList.count() - i);
allowedRoomsList.set(i, allowedRoomsList.get(i + r));
allowedRoomsList.set(i + r, t);
}

or

(randomswap)

Code Select Expand

for (var i = 0; i < gt.rules.nHoursPerWeek; i++) {
var t = perm[level][i];
var r = randomKnuth(gt.rules.nHoursPerWeek - i);
perm[level][i] = perm[level][i + r];
perm[level][i + r] = t;
}

I'm going to create a subdomain (fet.daltinkurt.com) at my personal website about this.
I will write to you again when i completed.

[Liviu Lalescu]

Oh, then you mean randomizing a 1D array. This is taken from CLR, as I wrote, but anyway it is nice.

I'll wait for your link to be up.

[ap6709]

I have used your software last year to generate an optimum timetable at my high school comprising of about 1060 activities. It all started by seeing our Principal ma'am in tears over drafting a good, error free time table and me being the computer teacher could not stand it any longer. Other  teachers used to mock and ridicule at her created timetable and numerous silly and few major mistakes. She was so happy last year that she gifted me a nice T-Shirt for my service. This year too, I was able to make a fantastic (I keeping my fingers crossed as our Principal ma'am just posted all the individual teachers timetable just a couple of hours ago in Whatsapp and till now I am receiving all positive responses) timetable in a matter of just about 10-12 man hours. I shall be in service for coming 28 years from now and definitely shall be using your software and even reporting about bugs/features to make it more and more user friendly. I thank you from the bottom of my heart for this wonderful piece of software, which saves so many countless man hours correcting the manually made timetable. Cheers from me, our Prinicipal ma'am and the entire staff for having created this timetable software and made available to all as a freeware.

[Liviu Lalescu]

Thank you for your flattering and encouraging review!