Optimize an Algorithm to take in a disliked string and Array of [Prereq, next_class] sub-arrays, outputs number of classes you can take before it

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
``````

Firstly, welcome to the forums.

While we are primarily here to help people with their Free Code Camp progress, we are open to people on other paths, too. Some of what you are asking is pretty trivial in the Free Code Camp context, so you might find that if you’re not getting the instruction and material you need in your current studies, the FCC curriculum will really help you get started. At a modest guess I’d say investing a 4-5 hours working through the curriculum here will really pay off. You can find the curriculum at https://www.freecodecamp.org/learn.

With your current questions, we don’t have enough context to know what you already know or don’t know, so it is impossible to guide you without just telling you the answer (which we won’t do).

It is pretty typical on here for people to share a codepen / repl.it / jsfiddle example of what they have tried so that anyone helping has more of an idea of what help is actually helpful.

Please provide some example of what you’ve tried and I’m sure you’ll get more help.

Happy coding

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.