Course schedule and alien dictionary

Why it matters

A university lists prerequisites: you must pass Programming 1 before Data Structures, and Data Structures before Algorithms. A build tool must compile a library before the program that links it. A package manager must install a dependency before the package that needs it. Each of these is a list of "this must come before that", and the question is whether an order exists that respects all of them.

Two common interview problems ask this in different forms. The first is called Course Schedule. Given courses and their prerequisites, can you finish all of them, and if so, in what order? The second is called Alien Dictionary. You are given words sorted in a language you do not know, and you must work out the order of its letters. Both problems are topological sorting problems. The topological sort lesson earlier in this module explains the method, called Kahn's algorithm, in full. This lesson applies it to two new inputs, and it adds the cycle check and the rules for turning words into constraints.

Terms used in this lesson

A prerequisite is an item that must be done before another. We draw it as a directed edge, an arrow from the earlier item to the later one. A directed edge is written a -> b in this lesson, meaning a comes before b.

The waiting count of an item is the number of prerequisites it still needs. An item with a waiting count of 0 can be done now.

A cycle is a loop of arrows that you can follow from a vertex back to itself. If a cycle exists, no item on it can be done first, so no valid order exists.

A topological order is a list of all the items in which every prerequisite appears before the item it unlocks.

A queue is a line where items leave in the order they joined. Programmers call this first in, first out, or FIFO.

Part 1: Course schedule

The input is a number of courses, numbered from 0, and a list of pairs. A pair {course, before} means that before must be taken before course. Notice that the pair is written with the later course first. This matches the common form of the problem, and the code below uses the same order.

Take four courses and these four pairs: {1, 0}, {2, 0}, {3, 1} and {3, 2}. Read them as rules. Course 1 needs course 0. Course 2 needs course 0. Course 3 needs both 1 and 2.

Start with the courses that need nothing. Course 0 is the only one. Take it. It unlocks courses 1 and 2, and each of them now has no waiting prerequisites. Take course 1. Course 3 still waits for course 2. Take course 2. Now course 3 has no waiting prerequisites, so take it. The order is 0, 1, 2, 3. Every course was taken and every rule was obeyed.

Now take two courses with the pairs {0, 1} and {1, 0}. Course 0 needs course 1, and course 1 needs course 0. Neither has a waiting count of 0. Nothing can start, so the order is empty. The number of courses finished, 0, is less than the number of courses, 2. That mismatch is the cycle check. Any course that is never taken is either on a cycle or waiting for a course on a cycle.

The method has four steps:

1. For each course, count how many prerequisites it has. This is its waiting count.
2. Put every course with a waiting count of 0 into a queue.
3. Take a course from the front of the queue and add it to the order. For each course it unlocks, lower that course's waiting count by 1. If the count reaches 0, put it in the queue.
4. When the queue is empty, compare the length of the order with the number of courses. If they match, the order is valid. If not, a cycle blocked some courses.

The code below does this. It returns an optional list. An optional value either holds a list or holds nothing, and here nothing means a cycle was found.

#include <cstddef>
#include <iostream>
#include <optional>
#include <queue>
#include <utility>
#include <vector>
 
// Each pair {course, before} means "take before before course first".
std::optional<std::vector<int>> findOrder(int numCourses,
                                          const std::vector<std::pair<int, int>>& prereqs) {
    std::vector<std::vector<int>> unlocks(numCourses);
    std::vector<int> waitingFor(numCourses, 0);
    for (const auto& [course, before] : prereqs) {
        unlocks[before].push_back(course);
        ++waitingFor[course];
    }
    std::queue<int> ready;
    for (int c = 0; c < numCourses; ++c) {
        if (waitingFor[c] == 0) ready.push(c);
    }
    std::vector<int> order;
    while (!ready.empty()) {
        int c = ready.front();
        ready.pop();
        order.push_back(c);
        for (int next : unlocks[c]) {
            if (--waitingFor[next] == 0) ready.push(next);
        }
    }
    if (order.size() != static_cast<std::size_t>(numCourses)) return std::nullopt;
    return order;
}
 
void show(const char* label, int numCourses, const std::vector<std::pair<int, int>>& prereqs) {
    std::cout << label << ": ";
    auto order = findOrder(numCourses, prereqs);
    if (!order) {
        std::cout << "impossible, the prerequisites form a cycle\n";
        return;
    }
    for (std::size_t i = 0; i < order->size(); ++i) {
        std::cout << (i ? " " : "") << (*order)[i];
    }
    std::cout << '\n';
}
 
int main() {
    show("four courses", 4, {{1, 0}, {2, 0}, {3, 1}, {3, 2}});
    show("two courses in a loop", 2, {{0, 1}, {1, 0}});
    show("no prerequisites", 3, {});
    show("course 2 waits on itself", 3, {{2, 2}});
}

Compile and run it with g++ -std=c++20 -Wall -o course course.cpp && ./course. The output is:

four courses: 0 1 2 3
two courses in a loop: impossible, the prerequisites form a cycle
no prerequisites: 0 1 2
course 2 waits on itself: impossible, the prerequisites form a cycle

The "no prerequisites" case shows that every course with a waiting count of 0 enters the queue at the start, in number order. The last case is a cycle of length one. Course 2 lists itself as a prerequisite, so its waiting count can never reach 0. This is the same failure as a cycle of two courses, and the same check catches it.

The function returns an empty list, not an absent value, when there are zero courses. That is correct, because a school with no courses has a valid (empty) order. The absent value is reserved for a real cycle.

The queue is first in, first out, so the order depends on the order of the input. Any order that obeys every rule is accepted for this problem, so the answer does not have to match a particular one.

Part 2: Alien dictionary

An alien language uses letters in some order that we do not know. Someone gives us a list of words, and the list is sorted in the alien dictionary order. The task is to find the letter order.

Start with the rule that makes this work. In an ordinary dictionary, two words are compared letter by letter. At the first position where they differ, the word with the earlier letter comes first. Those two letters are the only facts we learn from a pair of words. Between the words wrt and wrf, the first two letters match. At position 2, the letters are t and f. Since wrt comes before wrf, the alien alphabet must have t before f.

Each such fact is an edge in a graph, from the earlier letter to the later letter. Use the adjacent pairs of words only. A pair that is not next to each other adds no new rule. Any letter order that puts each adjacent pair in order also puts the words further apart in order, because alphabetical order is transitive: if a comes before b, and b before c, then a comes before c.

Here is a worked example with five words: wrt, wrf, er, ett and rftt. Compare each neighbouring pair.

• wrt and wrf: the first difference is at position 2, t and f. So t before f.
• wrf and er: the first difference is at position 0, w and e. So w before e.
• er and ett: the first difference is at position 1, r and t. So r before t.
• ett and rftt: the first difference is at position 0, e and r. So e before r.

The four edges form a chain: w before e, e before r, r before t, and t before f. The only letter order is wertf. Every letter appears in the chain, so nothing is left out.

The method is the same as Kahn's algorithm, with letters as the items. The waiting count of a letter is the number of letters that must come before it. Each distinct edge should be counted once. The algorithm then works through the letters that have a waiting count of 0.

Three special cases need care.

First, a letter that is in the words but has no edges still belongs in the answer. For the words ab and ca, the first letters are a and c, so a comes before c. The letter b has no constraint, but it must still appear in the answer. The answer is abc, and the letter b is placed where its position is free.

Second, a prefix problem makes the input impossible. The word ab is a prefix of abc, because its letters match the start of abc. In any dictionary, a prefix comes before the longer word. So if abc appears before ab in the input, no alphabet can make the list sorted. The answer is an empty string.

Third, a cycle makes the input impossible. The words z, x, z require z before x from the first pair, and x before z from the second pair. A cycle means no order, so the answer is an empty string.

When there are several valid answers, the code below always takes the smallest available letter first. The std::set used as the ready list, a container that keeps its items in sorted order, gives the smallest letter, so the output is the same on every run.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
 
// Returns the letter order, or "" when the words cannot be in any order.
std::string alienOrder(const std::vector<std::string>& words) {
    std::map<char, std::set<char>> unlocks;  // letter -> letters that must come after it
    std::map<char, int> waitingFor;          // letter -> how many letters must come before it
    for (const std::string& w : words) {
        for (char ch : w) waitingFor.try_emplace(ch, 0);
    }
 
    for (std::size_t i = 0; i + 1 < words.size(); ++i) {
        const std::string& a = words[i];
        const std::string& b = words[i + 1];
        std::size_t len = std::min(a.size(), b.size());
        std::size_t j = 0;
        while (j < len && a[j] == b[j]) ++j;
        if (j == len) {
            if (a.size() > b.size()) return "";
            continue;
        }
        if (unlocks[a[j]].insert(b[j]).second) ++waitingFor[b[j]];
    }
 
    std::set<char> ready;
    for (const auto& [ch, count] : waitingFor) {
        if (count == 0) ready.insert(ch);
    }
    std::string order;
    while (!ready.empty()) {
        char ch = *ready.begin();
        ready.erase(ready.begin());
        order += ch;
        for (char next : unlocks[ch]) {
            if (--waitingFor[next] == 0) ready.insert(next);
        }
    }
    if (order.size() != waitingFor.size()) return "";
    return order;
}
 
void show(const std::vector<std::string>& words) {
    std::string order = alienOrder(words);
    std::cout << (order.empty() ? std::string("(invalid)") : order) << '\n';
}
 
int main() {
    show({"wrt", "wrf", "er", "ett", "rftt"});
    show({"z", "x"});
    show({"ab", "ac"});
    show({"abc", "ab"});
    show({"z", "x", "z"});
}

Compile and run it with g++ -std=c++20 -Wall -o alien alien.cpp && ./alien. The output is:

wertf
zx
abc
(invalid)
(invalid)

The (invalid) text is printed by show, not by alienOrder. The function returns an empty string, and show turns that into readable text.

The {"ab", "ac"} case returns abc. The first difference is at position 1, b and c, so b comes before c. The letter a appears in both words but has no constraint, so it is placed first because it is the smallest letter with a waiting count of 0.

The {"z", "x"} case gives zx, because z is the only edge. The {"abc", "ab"} case should give (invalid), and the mistakes section shows what happens when the prefix check is missing.

The set also prevents double counting. The call unlocks[a[j]].insert(b[j]).second returns true only the first time a pair is added. The waiting count goes up only then. If the same pair appeared again in the input, the count and the list of unlocks would stay consistent.

Common mistakes

Missing the prefix case

A version of the alien dictionary program without the prefix check still compiles. The line if (a.size() > b.size()) return ""; is the check, and removing it changes the output for the impossible input {"abc", "ab"}. That version prints:

wertf
zx
abc
abc
(invalid)

The fourth line should be (invalid), but the program prints abc. No letter constraint was found, so the algorithm accepts the words. The fix is the prefix check, which runs when one word is a prefix of the other and returns an empty string when the longer word comes first.

Letters with no constraints left out

If the program only registers letters that appear in a comparison, a letter like b in {"ab", "ca"} is missing from the answer. The fix is the first loop in alienOrder, which registers every letter in every word before any edges are added.

Keeping the count and the list out of step

The waiting count and the unlock list must describe the same edges. If one of them adds an edge that the other does not, the count will never reach 0, or it will reach 0 too early. The code uses the .second value from set::insert for both, so they stay in step.

Passing a bad course number to operator bracket

Course numbers must be between 0 and numCourses minus 1. The unlocks[before] line uses the bracket operator, and that operator does not check the index. A bad index reads memory outside the vector, and the program may crash or give wrong results. While debugging, .at() checks the index and throws an error that names the problem. This small test file shows the message:

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v{1, 2, 3};
    std::cout << v.at(7) << "\n";
}

The program prints:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 7) >= this->size() (which is 3)

The message gives the bad index, 7, and the size of the vector, 3. Once the fix is in place, switch back to the bracket operator if speed matters, or keep .at() in code that reads input from outside the program.

Comparing a signed number with an unsigned size

The course program casts numCourses to std::size_t before comparing it with order.size(). Without the cast, the compiler gives a warning. This small test file shows the message:

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v{1, 2, 3};
    int n = 3;
    if (v.size() != n) std::cout << "different\n";
}

With -Wall, the compiler reports:

mistakes_sign.cpp: In function ‘int main()’:
mistakes_sign.cpp:7:18: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
    7 |     if (v.size() != n) std::cout << "different\n";
      |         ~~~~~~~~~^~~~

The warning is safe to fix by casting, as the course program does. The comparison is correct either way here, because the count is never negative. The warning matters when a negative number could be compared with a size, because the negative number is turned into a very large unsigned number.

Practice

Exercise 1. Five courses have these pairs: {1, 0}, {2, 1}, {3, 2}, {4, 2} and {4, 3}. Find a valid order.

Show the answer

The only valid order is 0 1 2 3 4. Course 0 has no prerequisites, so it comes first. Course 1 needs 0, course 2 needs 1, and course 3 needs 2. Course 4 needs both 2 and 3, so it comes last. Running the program gives 0 1 2 3 4.

Exercise 2. Three courses have these pairs: {0, 1}, {1, 2} and {2, 1}. Say whether the list can be finished, and explain which courses are stuck.

Show the answer

It cannot be finished. Courses 1 and 2 need each other, so neither can start. Course 0 needs course 1, so it is stuck too. The program prints impossible, the prerequisites form a cycle, because only zero courses are finished out of three.

Exercise 3. The alien dictionary input is {"xy", "xz", "zz"}. Find the letter order by comparing neighbouring words. Write the edges you find, then the answer.

Show the answer

The first pair xy and xz differs at position 1, so y comes before z. The second pair xz and zz differs at position 0, so x comes before z. The edges are y to z and x to z. Both x and y have no prerequisites and z comes last. The answer is xyz, because the smallest letter goes first when two letters are ready.

Exercise 4. The alien dictionary input is {"ab", "ac", "ab"}. Explain why no valid order exists.

Show the answer

The first pair ab and ac gives an edge from b to c, meaning b comes before c. The second pair ac and ab differs at position 1, c and b, so the edge is from c to b, meaning c comes before b. The two edges form a cycle, so no order exists. The program returns an empty string, and show prints (invalid).

Exercise 5. The alien dictionary input is {"ab", "ca"}. Find the letter order and explain why b is in the answer even though it has no edges.

Show the answer

The first letters differ, a and c, so a comes before c. The letter b has no edge at all. It starts with a waiting count of 0, so it can be placed. Both a and b are ready at the start, and the program takes the smallest first. The answer is abc. The letter b must appear, because every letter in the words belongs to the alphabet, even when no word comparison fixes its place.

Summary

• Course Schedule is topological sorting. Count each course's waiting prerequisites, take the ready courses in a queue, and compare the finished count with the total to detect a cycle.
• The answer to a cycle check is in the count: if fewer courses finish than exist, a cycle blocks the rest.
• For alien dictionary, compare each pair of neighbouring words. The first differing letters give one edge.
• A prefix that comes after its longer word makes the input impossible, and a cycle of letter edges does too.
• Every letter in the words must appear in the answer, including letters with no edges.
• Keep the waiting count and the unlock list in step, and use .at() while debugging an index that might be bad.