5
\$\begingroup\$

Introduction

You are the computer science teacher in a large high school and have been tasked to create a system to generate the student timetables. You must, given a JSON dictionary of student names and the subjects they are taking, you must generate a timetable for each of the students.

Specifications

Each student takes seven subjects (English Literature, English Language and Maths are compulsory but don't count towards the seven subjects):

Subject name - Abbreviation

Art - Ar
Biology - Bi
Business Studies - Bu
Chemistry - Ch
Computer Science - CS
French - Fr
Geography - Gg
History - Hi
IT - IT
Mandarin - Cn
Music - Mu
PE - PE
Physics - Ph
Spanish - Sp

Compulsory:

English Language - La
English Literature - Li
Maths - Ma

Other:

Tutor - Tu
Free - Ac

All abbreviations must be in the same case as above.

Each day has ten periods of lessons. A lesson can either span a single period or a double period. There must be three lessons of each subject with each having one double lesson (double period length) and two single lessons. The only exception to this rule is English Language which only occurs once a week and is a double.

There must be only one lesson of the same subject a day.

A school day is Monday to Friday.

Between periods 3 and 4 and between periods 5 and 6, there is a break. Lessons must not be placed over a break. From period six inclusive on a Wednesday to the end of the day, there are free periods. Period 1 on a Tuesday is Tutor period. Period 10 on a Friday is also Tutor. Period 10 on a Thursday is a free period.

Lessons must not be split into multiple groups meaning that people studying the same subject must be together in those subjects. Students may have any number of frees.

You must use the subject's abbbreviation in the timetable.

Data input

The JSON data must either be read from a local file or placed as a string variable in your code. The file will be a list of students with their names and a list of subjects. For example:

[ 
{"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"]}
]

Your program should then generate a timetable for each of the students, fitting all of the subjects in.

If there are multiple solutions, choose the first.

Note: The JSON file above has not been tested to see if it has a valid answer, it was just created to describe the formatting.

Output

The output must be a JSON file or CSV with the format detailed in your answer. You can either make a file for each of the students or have the timetables for all students in the same file.

Winning

The winning code is the shortest that successfully creates working timetables.

\$\endgroup\$
15
  • 2
    \$\begingroup\$ Congrats on posting question no. 2,500. ;) \$\endgroup\$ Sep 19, 2014 at 18:20
  • \$\begingroup\$ @Martin Nice! ;) \$\endgroup\$
    – Beta Decay
    Sep 19, 2014 at 18:21
  • 1
    \$\begingroup\$ 1. "three lessons including one double". Is that exactly one double, plus two singles? Is two doubles of an equivalent time not valid? what about 2 doubles plus a single? 2. Are all students studying the same subject expected to attend lessons in that subject at the same time? I assume so, but it is not explicitly stated. 3. If the answer to 2 is yes, is there an exception to this rule for free periods? (I haven't calculated whether a student will have any additional free periods other than the ones you have mentioned explicitly.) \$\endgroup\$ Sep 19, 2014 at 18:28
  • \$\begingroup\$ I propose the required output is just an ASCII table, maybe a CSV file. Drawing an image is a trivial task if there is a nice image library available for your language. The drawing of an image is not the hardest part of a challenge like this, but the requirement rules some languages out. PNG output could be a bonus. \$\endgroup\$
    – britishtea
    Sep 20, 2014 at 14:55
  • 1
    \$\begingroup\$ One question: "Between periods 3 and 4 and between periods 5 and 6, there is a break. Lessons must not be placed over a break" means there is neither a double lesson 3+4 nor 5+6? \$\endgroup\$
    – Wikunia
    Sep 28, 2014 at 8:48

1 Answer 1

0
+50
\$\begingroup\$

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)!");
    }
}); 
\$\endgroup\$
1
  • \$\begingroup\$ I've implemented your suggested example in the question \$\endgroup\$
    – Beta Decay
    Oct 1, 2014 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.