NodeJS
Edit
The algorthim is much faster now!
There is definitely no solution for the given example!
I tried some algorithms to generate a time table and I am pretty sure that your example has no solution.
So I changed the example to
students.json:
[
{"name":"Sarah","subjects":["physics","it","biology","history","art","business studies","french"]},
{"name":"Jim","subjects":["history","business studies","biology","computer science","geography","chemistry"]},
{"name":"Mary","subjects":["it","computer science","biology","physics","chemistry","art"]},
{"name":"Chris","subjects":["biology","chemistry","physics","french","computer science","geography"]}
]
(I only deleted the pe)
which generates this timeTable.json
{
"mon":
[["Bi"],["Bi"],["Ar","Gg"],["La"],["La"],["Ch"],["Ch"],["CS"],["CS"],["Ph"]],
"tue":
[["Tu"],["Bi"],["Ar","Gg"],["Ma"],["Ma"],["Ch"],["CS"],["Ph"],["Ph"],["Bu"]],
"wed":
[["Bi"],["Ar","Gg"],["Ar","Gg"],["Li"],["Li"],["Fr"],["Fr"],["IT"],["IT"],["Hi"]],
"thu":
[["Li"],["Ma"],["Ch"],["CS"],["Bu"],["Ph"],["Fr"],["IT"],["Hi"],["Ac"]],
"fri":
[["Li"],["Ma"],["Fr"],["Bu"],["Bu"],["IT"],["Hi"],["Hi"],[],["Tu"]]
}
And yes my programm is very long but I think code which is shortened afterwards makes it really hard to read and nowadays it isn't important to save bytes but time!
If you have any suggestions or you found a bug => comment!
You can start the file (timeTable.js) with node timeTable.js students.js
var fs = require('fs');
console.log('Timetable');
var json = JSON.parse(fs.readFileSync(process.argv[2], 'utf8'));
var backTracks = 0;
var lessons =
["art","biology","business studies","chemistry","computer science","french","geography","history","it","mandarin","music","pe","physics","spanish"];
var abbr = ["Ar","Bi","Bu","Ch","CS","Fr","Gg","Hi","IT","Cn","Mu","PE","Ph","Sp"];
var single = [2,2,2,2,2,2,2,2,2,2,2,2,2,2];
var double = [1,1,1,1,1,1,1,1,1,1,1,1,1,1];
var days = ["mon","tue","wed","thu","fri"];
var nrOfStudents = json.length;
var q = 0;
// convert json into correct position
for (var i = 0; i < json.length; i++) {
var subjects = json[i].subjects;
for (var s = 0; s < subjects.length; s++) {
var pos = lessons.indexOf(subjects[s].toLowerCase());
if (pos >= 0) {
subjects[s] = pos;
}
}
}
// Special lessons
var timeTable = {"mon":[],"tue":[],"wed":[],"thu":[],"fri":[]};
timeTable.tue[0] = ["Tu"];
timeTable.fri[9] = ["Tu"];
timeTable.thu[9] = ["Ac"];
// one english double (Monday 4-5)
timeTable.mon[3] = ["La"];
timeTable.mon[4] = ["La"];
// one double two single for math and literature (Tue 4-5,Wed 4-5,Thu 1,2,Fri 1,2)
timeTable.tue[3] = ["Ma"];
timeTable.tue[4] = ["Ma"];
timeTable.wed[3] = ["Li"];
timeTable.wed[4] = ["Li"];
timeTable.thu[0] = ["Li"];
timeTable.thu[1] = ["Ma"];
timeTable.fri[0] = ["Li"];
timeTable.fri[1] = ["Ma"];
var timeTableBackup = {0:[],1:[],2:[],3:[],4:[]};
for (var i = 0; i < 5; i++) {
var day = timeTable[days[i]];
for (var j = 0; j < 10; j++) {
if (!(j in day) || !Array.isArray(day[j])) {
day[j] = [];
}
}
}
// sort subjects
var sortedSubs = [];
// 14 subjects
for (var i = 0; i < 14; i++) {
sortedSubs[i] = {t:0,students:[],n:i};
}
for (var i = 0; i < json.length; i++) {
var subjects = json[i].subjects;
var student = json[i].name;
for (var s = 0; s < subjects.length; s++) {
sortedSubs[subjects[s]].t ++;
sortedSubs[subjects[s]].n = subjects[s];
sortedSubs[subjects[s]].students.push(student);
}
}
console.log(sortedSubs);
sortedSubs = sortByKey(sortedSubs,"t");
var k = sortedSubs.length-1;
// remove all subs that weren't choosen by anyone
while(sortedSubs[k].t == 0) {
var sub = sortedSubs.pop();
single[sub.n] = 0;
double[sub.n] = 0;
k--;
}
var goBack = false;
var start = false;
var d = 0;
while (d < 5) {
// 10 lessons per day
var l = 0;
while(l < 10) {
var day = timeTable[days[d]];
// if there is no subject
if (day[l].length == 0) {
var next = false;
var s = start === false ? 0 : start;
var firstChoice = false;
while (!next && s < sortedSubs.length) {
if (possibleToAdd(day,l,s)) { // different lessons on one day and possiblity to add lesson
goBack = false;
next = true;
if (!firstChoice) firstChoice = s;
// get the number of students that don't have this lesson
var except = nrOfStudents - sortedSubs[s].t;
if (except > 0) {
// get the first lesson which none of the students have
var breaked = false;
var tempL;
for (var ss = s+1; ss < sortedSubs.length; ss++) {
if (sortedSubs[ss].t <= except && possibleToAdd(day,l,ss)) {
var intersection = arrIntersect(sortedSubs[s].students,sortedSubs[ss].students);
// no student has both classes
if (intersection.length == 0) {
if (!breaked) { // fill the current lesson (s) only once
tempL = addLesson(day,l,s);
}
tempL = addLesson(day,l,ss);
breaked = true;
}
}
}
if (breaked) {
l = tempL;
} else { // it wasn't possible to have two classes at this time
next = false;
var found = false;
// maybe there are other lessons which can be added => found = true
for (var z = s+1; z < sortedSubs.length; z++) {
if (possibleToAdd(day,l,z)) {
found = true;
break;
}
}
// otherwise fill this lesson with the first choice
if (!found) {
l = addLesson(day,l,firstChoice);
}
}
} else {
// everyone has this lesson :)
// on day lesson no. l: subject no. s
l = addLesson(day,l,s);
}
} else {
if (start) goBack = true;
}
s++;
}
start = false;
}
// Friday last lesson
if ((d == 4 && l == 9) || goBack) {
// how many lessons are missing?
var sum = double.reduce(function(pv, cv) { return pv + cv; }, 0)*2 + single.reduce(function(pv, cv) { return pv + cv; }, 0);
if (sum > 0) {
remove = removeLesson(d,l);
if (remove) {
backTracks++;
if (backTracks % 50000 == 0) {
console.log('backTracks: '+backTracks+'...');
}
d = remove.back.day;
l = remove.back.lesson;
start = remove.start;
} else {
console.log('I could not find a solution for this problem :( ');
console.log('backtracks: '+backTracks);
process.exit();
l = 10;
d = 5;
}
} else {
l = 10;
d = 5;
}
} else {
l++;
}
}
d++;
}
function removeLesson(d,l) {
var day = timeTable[days[d]];
var back = true;
// what is the latest subject
var latestSub = sortedSubs[sortedSubs.length-1].n;
// backtrack
while(back) {
// if there is no lesson before => back to the last lesson the day before
if (l == -1) {
if (d == 0) {
return false; // not possible at all
}
d--;
day = timeTable[days[d]];
l = day.length-1;
}
// if there is a non default lesson
if (day[l].length > 0 && parseInt(day[l][0]) == day[l][0]) {
// if the latestSub isn't part of this lesson we don't need to backtrack more
if (day[l].indexOf(latestSub) < 0) { back = false; }
var intersection = [];
// if we are not in the first lesson => get double lessons
if (l > 0) {
intersection = arrIntersect(day[l],day[l-1]);
}
// if there are double lessons
if (intersection.length > 0) {
for (var i = 0; i < day[l].length; i++) {
// check if current lesson is a double lesson
if (intersection.indexOf(day[l][i]) >= 0) {
double[day[l][i]]++;
} else {
single[day[l][i]]++;
}
}
// remove all single lessons the lesson before
for (var i = 0; i < day[l-1].length; i++) {
if (intersection.indexOf(day[l-1][i]) < 0) {
single[day[l-1][i]]++;
}
}
day[l] = [];
l--;
} else {
for (var i = 0; i < day[l].length; i++) {
single[day[l][i]]++;
}
}
// delete the day if the current lesson was the least possible solution
if (back) {
day[l] = [];
}
} else {
l--;
}
}
var start = false;
// get start subject for this lesson d,l
for (var s = 0; s < sortedSubs.length-1; s++) {
if (day[l].indexOf(sortedSubs[s].n) >= 0) {
start = ++s;
day[l] = [];
break;
}
}
if (!start) {
console.log('there is a bug');
process.exit();
}
return {back:{day:d,lesson:l},start:start};
}
function addLesson(day,l,s) {
// is a double lesson possible?
if (double[sortedSubs[s].n] > 0 && l != 2 && l != 4 && l+1 < 10 && (day[l+1].length == 0 || parseInt(day[l+1][0]) == day[l+1][0])) {
double[sortedSubs[s].n]--;
for (var i = l; i <= l+1; i++) {
if (Array.isArray(day[i])) {
day[i].push(sortedSubs[s].n);
} else {
day[i] = [sortedSubs[s].n];
}
}
l++;
} else if (single[sortedSubs[s].n] > 0) { // put it into a single lesson
single[sortedSubs[s].n]--;
if (Array.isArray(day[l])) {
day[l].push(sortedSubs[s].n);
} else {
day[l] = [sortedSubs[s].n];
}
} else {
console.log('ERROR');
process.exit();
}
return l;
}
function possibleToAdd(day,l,s) {
// it is not allowed to have the same lesson twice on a day
var notSet = true;
for (var i = 0; i < l; i++) {
if (day[i].indexOf(sortedSubs[s].n) >= 0) {
notSet = false;
break;
}
}
if (!notSet) return false;
// no double lesson 3+4 and (starting with 1)
if (double[sortedSubs[s].n] > 0 && l != 2 && l != 4 && l+1 < 10 && (day[l+1].length == 0 || parseInt(day[l+1][0]) == day[l+1][0])) {
return true;
} else if (single[sortedSubs[s].n] > 0) {
return true;
} else {
return false;
}
}
function arrIntersect(array1,array2) {
return array1.filter(function(n) {
return array2.indexOf(n) != -1
});
}
function sortByKey(array, key) {
return array.sort(function(a, b) {
var x = a[key];
var y = b[key];
return ((x < y) ? 1 : -1);
});
}
// convert lesson numbers into abbr
for (var d = 0; d < 5; d++) {
var day = timeTable[days[d]];
// 10 lessons per day
for (var l = 0; l < 10; l++) {
for (var ll = 0; ll < day[l].length; ll++) {
if (parseInt(day[l][ll]) == day[l][ll]) {
day[l][ll] = abbr[day[l][ll]];
}
}
}
}
console.log(timeTable);
console.log('Backtracks: '+backTracks);
fs.writeFile("timeTable.json", JSON.stringify(timeTable), function(err) {
if(err) {
console.log(err);
} else {
console.log("The file was saved (timeTable.json)!");
}
});
