The course we want to avoid is guaranteed somewhere in the list of courses and prerequisites. There will be no untakeable courses. There may be multiple courses with no prerequisites. The prompt is to create a function which takes in a course to avoid, and a list of courses and prerequisites. Returns how many courses we can take before the course we want to avoid. The disliked course should be in the list of the courses and prerequisites, guaranteed. The function returns how many courses we can take before the course we want to avoid.
I have wrote this algorithm by hand without any efficiencies. I was hoping someone could help me optimize it or guide me in modern javascript algorithmic best practices as it took me longer than usual to form a solution. In addition, if someone could help me calculate the Big O time complexity of what I have, in explaining why another solution is better, it would be much appreciated.
var disliked = "Linear Algebra";
var prereqs = [
["Calculus 1", "Calculus 2"],
["Calculus 2", "Linear Algebra"],
["Linear Algebra", "Discrete Math"],
["Discrete Math", "Analysis of Algorithms"],
["Algorithms", "Analysis of Algorithms"],
["Data Structures", "Algorithms"],
["Algorithms", "AI"],
["Calculus 1", "AI"],
["AI", "Computer Vision"],
["Algorithms", "Networks"],
["Algorithms", "Operating Systems"],
["Analysis of Algorithms", "Theory of CS"],
];
function countCourses(disliked, prereqs) {
// [x] 1) Choose dislike: ie, alg
// for each array {
// if current array indice 0 === "alg" (ie, dislike)
// push its indice value 1 to new array, delete current array
// ex, uniques[] = [analysis, AI, NET, OS]
// new array: [calc1, calc2], [calc2, lin alg],[lin alg, d math], [d math, analysis], [d. struct, alg]
// [calc1, AI], [AI, comp], [analysis, theory]
//
// O(N)
let next_classes = [];
for (let i = 0; i < prereqs.length; i++) {
if (prereqs[i][0] === disliked) {
next_classes.push(prereqs[i][1]);
prereqs.splice(i, 1);
i = i - 1;
}
}
console.table(next_classes);
console.table(prereqs);
// For each next class requirement in the sequence (after disliked class)
// Remove, add to impossible_classes as we cannot take them
// impossible_courses[]: [analysis, AI, net, OS]
for(let i = 0; i < prereqs.length; i++) {
for(let j = 0; j < next_classes.length; j++) {
if (prereqs[i][0] === next_classes[j]) {
next_classes.push(prereqs[i][1]);
//prereqs.splice(i, 1);
//j = i - 1;
}
}
}
console.table(next_classes);
// 2) for each array {
// if current array indice 0 === [a unique value] (ie, value from [analysis, AI, net, OS])
// delete current array
// Effectively deletes classes after unique [analysis, AI, net, OS] in the sequence,
// which cannot also be taken
// ie, theory, comp
for (let i = 0; i < prereqs.length; i++) {
for (let j = 0; j < next_classes.length; j++) {
if (prereqs[i][0] === next_classes[j]) {
prereqs.splice(i, 1);
i = 0;
}
}
}
// if nothing inside impossible_courses --> that means,
// the course you dislike is a "final course", nothing comes after it
// it contains only pre-requisites.
if (next_classes.length === 0) {
for (let i = 0; i < prereqs.length; i++) {
// find the disliked final course
if (prereqs[i][1] === disliked) {
// delete disliked course array from prereqs
prereqs.splice(i, 1);
// return the size of prereqs -
console.table(prereqs);
return prereqs.length;
}
}
} else {
console.table(prereqs);
// use concat() to merge all prereqs into one
const flattenedPrereqs = [].concat(...prereqs);
const distinctCourses = [...new Set(flattenedPrereqs)];
// remove all occurences of 'disliked' course and impossible courses
// from the flattened array
for(let i = 0; i < distinctCourses.length; i++) {
if(distinctCourses[i] === disliked) {
distinctCourses.splice(i, 1);
}
for (let j = 0; j < next_classes.length; j++) {
if (distinctCourses[i] === next_classes[j]) {
distinctCourses.splice(i, 1);
i = i - 1;
}
}
}
console.table(distinctCourses);
return distinctCourses.length;
}
// NOTE: You may use print statements for debugging purposes, but you may
// need to remove them for the tests to pass.
}
console.log(countCourses(disliked, prereqs));
This is a sample for output using “linear algebra” as disliked course:
$ node disliked_courses.js
┌─────────┬─────────────────┐
│ (index) │ Values │
├─────────┼─────────────────┤
│ 0 │ 'Discrete Math' │
└─────────┴─────────────────┘
┌─────────┬──────────────────────────┬──────────────────────────┐
│ (index) │ 0 │ 1 │
├─────────┼──────────────────────────┼──────────────────────────┤
│ 0 │ 'Calculus 1' │ 'Calculus 2' │
│ 1 │ 'Calculus 2' │ 'Linear Algebra' │
│ 2 │ 'Discrete Math' │ 'Analysis of Algorithms' │
│ 3 │ 'Algorithms' │ 'Analysis of Algorithms' │
│ 4 │ 'Data Structures' │ 'Algorithms' │
│ 5 │ 'Algorithms' │ 'AI' │
│ 6 │ 'Calculus 1' │ 'AI' │
│ 7 │ 'AI' │ 'Computer Vision' │
│ 8 │ 'Algorithms' │ 'Networks' │
│ 9 │ 'Algorithms' │ 'Operating Systems' │
│ 10 │ 'Analysis of Algorithms' │ 'Theory of CS' │
└─────────┴──────────────────────────┴──────────────────────────┘
┌─────────┬──────────────────────────┐
│ (index) │ Values │
├─────────┼──────────────────────────┤
│ 0 │ 'Discrete Math' │
│ 1 │ 'Analysis of Algorithms' │
│ 2 │ 'Theory of CS' │
└─────────┴──────────────────────────┘
┌─────────┬───────────────────┬──────────────────────────┐
│ (index) │ 0 │ 1 │
├─────────┼───────────────────┼──────────────────────────┤
│ 0 │ 'Calculus 1' │ 'Calculus 2' │
│ 1 │ 'Calculus 2' │ 'Linear Algebra' │
│ 2 │ 'Algorithms' │ 'Analysis of Algorithms' │
│ 3 │ 'Data Structures' │ 'Algorithms' │
│ 4 │ 'Algorithms' │ 'AI' │
│ 5 │ 'Calculus 1' │ 'AI' │
│ 6 │ 'AI' │ 'Computer Vision' │
│ 7 │ 'Algorithms' │ 'Networks' │
│ 8 │ 'Algorithms' │ 'Operating Systems' │
└─────────┴───────────────────┴──────────────────────────┘
┌─────────┬─────────────────────┐
│ (index) │ Values │
├─────────┼─────────────────────┤
│ 0 │ 'Calculus 1' │
│ 1 │ 'Calculus 2' │
│ 2 │ 'Algorithms' │
│ 3 │ 'Data Structures' │
│ 4 │ 'AI' │
│ 5 │ 'Computer Vision' │
│ 6 │ 'Networks' │
│ 7 │ 'Operating Systems' │
└─────────┴─────────────────────┘
8
