Author Topic: Thanks & Congrats  (Read 1159 times)

0 Members and 1 Guest are viewing this topic.

Devrim Altınkurt

  • Level 1
  • *
  • Posts: 26
  • MCPD, MCT, ICT Teacher.
    • View Profile
    • daltinkurt.com
Thanks & Congrats
« on: May 12, 2016, 03:55:34 PM »
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

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 5162
  • FET author and forum moderator
    • View Profile
    • Homepage
Re: Thanks & Congrats
« Reply #1 on: May 12, 2016, 11:30:54 PM »
Thank you for your report and appreciation! :)
« Last Edit: May 12, 2016, 11:51:14 PM by Liviu Lalescu »

Liviu Lalescu

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 5162
  • FET author and forum moderator
    • View Profile
    • Homepage
Re: Thanks & Congrats
« Reply #2 on: May 12, 2016, 11:53:49 PM »
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

  • Level 1
  • *
  • Posts: 26
  • MCPD, MCT, ICT Teacher.
    • View Profile
    • daltinkurt.com
Re: Thanks & Congrats
« Reply #3 on: May 15, 2016, 02:02:29 PM »
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

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 5162
  • FET author and forum moderator
    • View Profile
    • Homepage
Re: Thanks & Congrats
« Reply #4 on: May 16, 2016, 02:48:45 AM »
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.

Quote

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.

Quote

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.

Quote

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.

Quote

best regards..

Devrim Altınkurt

  • Level 1
  • *
  • Posts: 26
  • MCPD, MCT, ICT Teacher.
    • View Profile
    • daltinkurt.com
Re: Thanks & Congrats
« Reply #5 on: May 16, 2016, 08:37:24 AM »
Quote
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]
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]
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

  • Forum Administrator
  • Level 5
  • *****
  • Posts: 5162
  • FET author and forum moderator
    • View Profile
    • Homepage
Re: Thanks & Congrats
« Reply #6 on: May 16, 2016, 08:44:31 AM »
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.