leetcode/course_to_take.cpp at master · Mayank-Parasar/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//
// Created by Mayank Parasar on 2019-12-18.
//

/*
 * You are given a hash table where the key is a course code, and the value is a list of all the course codes
 * that are prerequisites for the key. Return a valid ordering in which we can complete the courses.
 * If no such ordering exists, return NULL.

Example:
{
  'CSC300': ['CSC100', 'CSC200'],
  'CSC200': ['CSC100'],
  'CSC100': []
}

This input should return the order that we need to take these courses:
 ['CSC100', 'CSC200', 'CSCS300']
 */

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <assert.h>

using namespace std;

// elementals are the courses that do not have any pre-requisite.

void course_order(map<string, vector<string>>& database,
                vector<string>& course_order) {
    // populate the vector with elementals
    for(auto entry: database) {
        if(entry.second.size() == 0) {
            course_order.push_back(entry.first);
        }
    }
    // if there are no elementals present then it will not possible

    map<string, vector<string>>::iterator itr;
    repeat:
    for(itr=database.begin(); itr != database.end(); itr++) {
        if(find(course_order.begin(), course_order.end(), itr->first) == course_order.end()) {
            // the course is not present in the course order.. check if its pre-requisite are met
            // if yes, add it to the course order and goto repeat
            vector<string> requirements = itr->second;
            int ii = 0;
            for(ii=0; ii < requirements.size(); ii++) {
                int kk =0;
                for(kk = 0; kk < course_order.size(); kk++) {
                    if (course_order[kk] == requirements[ii]) {
                        break;
                    }
                    else {

                    }
                }
                if(kk < course_order.size()) {
                    // this course prerequisite is present
                    continue;
                }
                else if( kk == course_order.size()) {
                    // this course is not present therefore pre-requisite have not meet
                    break;
                } else {
                    assert(0);
                }
                // if(ii == -1)
                    // break; // this makes
            }
            if(ii == requirements.size()) {
                // all the pre-requiste for this course has meet
                // add this course to the course order
                // only if not already present and repeat
                course_order.push_back(itr->first);
                goto repeat;
            }

        }
        else {
            continue; // found the course in the course_order
        }
    }
    return;
}

int main() {

    vector<string> course_order_;
    map<string, vector<string>> database;

    // initialize the database
    database["CSC300"] = {"CSC100", "CSC200"};
    database["CSC200"] = {"CSC100"};
    database["CSC100"] = {};

    course_order(database, course_order_);

    for(auto ii : course_order_ ) {
        cout << ii << " ";
    }

    return 0;
}