Course schedule and alien dictionary in Python

Why this matters

A university lists a prerequisite for many courses. Data Structures needs Programming first. Compilers needs Data Structures first. If the list of prerequisites loops, for example Course A needs B, B needs C, and C needs A, then no student can ever start, and the registrar's software has to say so. A build system faces the same question with source files: it must compile each file after the files it depends on, and it must report a circular dependency instead of looping forever.

A second problem looks different on the surface but uses the same tool. Suppose you find a book written in an alphabet you do not know, and the words in the book are sorted by the alien alphabet's order. The order of the letters can be worked out from the sorted words alone, and the method is a topological sort.

This lesson uses the topological sort from lesson 3 of this module, which explains Kahn's algorithm in full. Kahn's algorithm keeps a queue (a line where items leave in the order they joined) of vertices with no unmet prerequisites, removes them one by one, and checks whether every vertex was removed. This lesson applies that loop to two problems, and adds the details that the problems need.

Words used in this lesson

A prerequisite is a task that must be finished before another task can start. In a graph, each prerequisite is a directed edge from the prerequisite to the task that depends on it.

A cycle is a path that follows the arrows and returns to where it began. A cycle means there is no valid order, because each task in the loop waits for another one in the loop.

A topological order is a list of all the vertices in which every edge goes from an earlier item to a later one.

The indegree of a vertex is the number of edges pointing into it. In this lesson it means the number of prerequisites that are still unfinished.

Problem one: can all the courses be finished?

The first problem is usually called Course Schedule. You are given a number of courses, numbered from 0 to n - 1, and a list of pairs. Each pair [course, prereq] means that prereq must be taken before course. The question is whether there is an order that takes every course.

The direction of the edge matters, and it is the most common source of errors. The pair [1, 0] says that course 0 comes before course 1. So the edge goes from 0 to 1, from the prerequisite to the course that needs it. The code below reads the pair in this way: adj[prereq].append(course) adds an edge from the prerequisite prereq to the course course.

A small example

Take four courses and these pairs: [1, 0], [2, 0], [3, 1], and [3, 2]. Course 0 has no prerequisite. Courses 1 and 2 need course 0. Course 3 needs both 1 and 2.

The indegrees are 0 for course 0, 1 for courses 1 and 2, and 2 for course 3. The queue starts with course 0 alone. Here is the trace.

Taking course 0 unlocked courses 1 and 2. Taking 1 and 2 together unlocked course 3. The order is [0, 1, 2, 3]. Every course was taken, so the answer is yes.

The Python code

The function returns the order when one exists. If some course is never taken, it returns an empty list, which is the signal that no order exists.

Run it and the output is:

course 4, prereqs [[1, 0], [2, 0], [3, 1], [3, 2]]: [0, 1, 2, 3]

Several Python features are at work here.

• [[] for _ in range(num_courses)] builds one empty list for each course. A list comprehension is a loop written on one line.
• for course, prereq in prereqs takes each two-item list and unpacks it into two names.
• deque is a queue from the collections module. popleft() removes the first item in constant time. Removing the first item of a plain list with pop(0) shifts every other item, so it gets slower as the list grows.
• An empty deque is false in an if or while, so while queue: runs until the queue is empty.
• return order if len(order) == num_courses else [] is a conditional expression. It reads as: return order when its length equals the number of courses, otherwise return an empty list.

Readers who know Java will see the same queue loop. The differences are the list comprehension and deque, which replace ArrayList and ArrayDeque.

The key line is the return. len(order) counts how many courses the loop took. If the count equals the number of courses, the order is complete. If a cycle exists, the courses on the cycle never reach indegree 0, so they never enter the queue, and the count comes out short.

Detecting a cycle

Take two courses that need each other: [0, 1] and [1, 0]. Course 0 needs 1, and course 1 needs 0. Both indegrees are 1, so the queue starts empty. The loop does not run at all, the order stays empty, and the function returns an empty list.

show(2, [[0, 1], [1, 0]])

course 2, prereqs [[0, 1], [1, 0]]: []

A cycle does not have to cover every course. Take four courses with these pairs: [1, 0], [2, 1], [1, 2], and [3, 0]. Course 0 is free to start. Courses 1 and 2 need each other, so neither can start. Course 3 needs 0, so it can be taken after course 0.

show(4, [[1, 0], [2, 1], [1, 2], [3, 0]])

course 4, prereqs [[1, 0], [2, 1], [1, 2], [3, 0]]: []

The trace shows the problem. Course 0 is taken first. That releases course 3, which is taken next. The queue is then empty, but only 2 of the 4 courses were taken. The cycle between 1 and 2 blocked them. The function sees the order has length 2, not 4, and returns the empty list.

The rule is that one cycle, anywhere in the graph, is enough to make the whole schedule impossible. The courses that are not on the cycle may still be takeable, but the full list cannot be finished, so the answer is an empty list.

Problem two: returning the order

Course Schedule II asks for the order itself rather than a yes or no. The same code answers it. When the order exists, the function returns it. When a cycle exists, it returns the empty list. The question that remains is which order is returned when several are valid. The queue gives the courses in the order they became ready, and courses that were ready at the same time come out in the order they were added. A different insertion order gives a different valid answer, and both are correct. A problem that asks for one specific order, such as the smallest by number, needs a heap (a structure that always gives back its smallest item first) instead of a plain queue. Python provides one in the heapq module.

Checking an order

When a function returns an order, a second check is cheap and catches many bugs. Store the position of each course in the order, then test every pair: the prerequisite must sit at a smaller position than the course that needs it. The check runs in time proportional to the number of pairs, so it costs little compared with the search itself.

The output is:

order [0, 1, 2, 3] respects: True
order [3, 2, 1, 0] respects: False
empty list respects: False

The second order is a list of all four courses, so the length test passes, but course 3 is taken first, before its prerequisites. The pair check catches that. The empty list fails the length test, so a cycle is reported as a failed check too.

enumerate(order) gives each item together with its index, so i is the position and course is the item.

Problem three: the alien dictionary

Now the second problem. A set of words is sorted in an alphabet that you do not know. The alphabet has some letters, for example w, e, r, t, f, in an order you must find. The words are given in the order the dictionary sorts them.

Take these words: wrt, wrf, er, ett, rftt. The answer is wertf.

Each neighbouring pair teaches one rule

A dictionary sorts words by comparing their first letters. If the first letters are equal, it compares the second letters, and so on. So when two neighbouring words differ, the first position where they differ tells you the order of two letters. Letter x comes before letter y in the alien alphabet, and we write this as an edge from x to y.

Compare each neighbouring pair:

• wrt and wrf first differ at position 2, where the letters are t and f. So t comes before f. Edge t to f.
• wrf and er first differ at position 0, with w and e. Edge w to e.
• er and ett first differ at position 1, with r and t. Edge r to t.
• ett and rftt first differ at position 0, with e and r. Edge e to r.

The four edges are t to f, w to e, r to t, and e to r. These form a chain: w before e, e before r, r before t, t before f. The order is w, e, r, t, f.

Only the first difference in each pair matters. The letters after that point say nothing about the alien alphabet. For example, wrt and wrf differ at position 2, and the letters after position 2 do not exist in either word, so nothing more can be learned from that pair.

The code walks through the pairs with zip(words, words[1:]). words[1:] is the list without its first word, and zip pairs each word with the word after it: ("wrt", "wrf"), ("wrf", "er"), and so on.

Two special cases

There are two cases where a pair teaches nothing or proves the answer impossible.

If one word is a prefix of the other, the words are equal up to the length of the shorter one. For example, ab is a prefix of abc. In a dictionary, the shorter word comes first, so ab must come before abc, and this is true in any alphabet. If the input puts the longer word first, as in abc then ab, no alphabet can make that order correct. The answer is the empty string.

If two words are identical, they teach nothing, and the code skips the pair.

Letters that have no rule

Some letters may appear in the words but never be compared with another letter at the first difference. Take the words ab and adc. The first difference is at position 1, with b and d. So the only edge is b to d. The letters a and c appear in the words, but no rule puts c anywhere in particular. They still belong in the answer. The code includes every letter that appears in any word, so the answer is abcd, with a and c placed by the queue.

The Python code

The first loop registers every letter that appears in any word, with indegree 0. This is how letters with no rule still reach the answer. The second loop compares each neighbouring pair. The while loop finds the first difference. Its condition checks j < n first, so the code never reads a letter past the end of a word. The if j == n block handles the prefix case.

to not in adj[frm] checks whether the edge already exists before it is added, so an edge seen twice counts once in the indegree.

sorted(indeg) and sorted(adj[c]) put the letters in alphabetical order. The reason is explained in the common mistakes below.

The last line compares the length of the answer with the number of letters. If a cycle exists, some letters never reach indegree 0, and the answer is shorter, so the function returns the empty string.

The program prints the results for six test inputs. The repr function shows the empty string as '', so it does not look like a blank line.

['wrt', 'wrf', 'er', 'ett', 'rftt'] 'wertf'
['z', 'x'] 'zx'
['z', 'x', 'z'] ''
['abc', 'ab'] ''
['ab', 'adc'] 'abcd'
['ab', 'ab'] 'ab'

The words z, x, z produce a cycle. The pair z and x gives z before x, and the pair x and z gives x before z. Neither letter reaches indegree 0, so the queue is empty from the start, the answer is shorter than the letter count, and the function returns the empty string.

The prefix case, abc then ab, also returns the empty string, because the function returns as soon as it sees the rule break.

Tracing the example by hand

The edges are t to f, w to e, r to t, and e to r. The indegrees are e 1, f 1, r 1, t 1, and w 0. The queue starts with w.

The answer is wertf.

Common mistakes

Reversing the prerequisite pair. The pair [course, prereq] names the course first. Swap the two numbers and the answer can still look valid, which makes this mistake easy to miss. For the single pair [0, 1], course 0 needs course 1, so the correct order is [1, 0]. Reversing the pair gives [0, 1], which takes course 0 first and breaks the rule:

course 2, prereqs [[0, 1]]: [1, 0]
course 2, prereqs [[1, 0]]: [0, 1]

The first line is correct. The second line is what you get when the pair is written the wrong way round.

Using a course number outside the range. If a pair names course 4 as its first number, but there are only 4 courses, the list is too short and Python stops the program:

IndexError: list index out of range

The message IndexError means an index was past the end of a list, or before its start. The message does not name the list or the index, so check the numbers in the input yourself. Every number must be between 0 and num_courses - 1.

Python does not always stop on a bad number. A negative index counts from the end of the list, so -1 means the last item, not an error. A pair that uses -1 as its prerequisite runs without any error and gives an answer:

print(find_order(2, [[0, -1]]))

[1, 0]

The function treats course 0 as needing course 1, because adj[-1] is the same list as adj[1]. Check for negative numbers as well as numbers that are too large.

Comparing only some of the neighbouring pairs. The loop must compare every pair in the list, not just the first or the last. A rule that appears only in the middle of the list is still a rule.

Comparing past the first difference. For ab and ac, the first difference is at position 1, which gives b before c. Reading position 2 would be past the end of a two-letter word, and Python reports it:

print("ab"[2])

IndexError: string index out of range

Even for words of equal length, the letters after the difference say nothing about the order.

Forgetting the prefix rule. If the longer word comes first, the function must return the empty string. Skipping this check gives an answer for an input that has no valid alphabet.

Missing letters with no rule. A function that builds its graph only from the edges will leave out letters that never appear at a first difference. Register every letter from every word before reading the pairs.

Building a list of lists with *. [[]] * 3 makes three references to one empty list, not three separate lists. Adding to one of them adds to all of them:

adj = [[]] * 3
adj[0].append(1)
print(adj)

[[1], [1], [1]]

A list comprehension makes a new list each time it runs:

adj = [[] for _ in range(3)]
adj[0].append(1)
print(adj)

[[1], [], []]

Trusting the order of a set. A set stores each item once, but the order its items come out in is not fixed. For strings, Python changes the order from one run to the next by default, because it uses a random seed to mix the hashes. The same set can print differently each time the program runs:

PYTHONHASHSEED=1 python3 -c "print(list({'w', 'e', 'r', 't', 'f'}))"
PYTHONHASHSEED=2 python3 -c "print(list({'w', 'e', 'r', 't', 'f'}))"

['w', 'f', 't', 'r', 'e']
['w', 'r', 't', 'f', 'e']

If the queue is filled in set order, the answer can change between runs. That is why the code uses sorted(...) for each set before it reads from it. The output of sorted is the same every time. Your output for the commands above will be different if your Python build uses other hash values.

Practice

Exercise 1. Three courses have the pairs [1, 0], [2, 1], and [0, 2]. Can all courses be taken?

Show the answer

No. Course 1 needs 0, course 2 needs 1, and course 0 needs 2. This is a cycle, so no course can start. The function returns the empty list.

Exercise 2. Three courses have the pairs [2, 0] and [2, 1]. Give a valid order.

Show the answer

The order [0, 1, 2] is valid. Courses 0 and 1 have no prerequisites and are taken first in number order. Course 2 needs both, so it comes last. The function returns exactly this.

Exercise 3. The alien words are ab, ac, and bc. What is the alphabet order?

Show the answer

The pair ab and ac first differs at position 1, with b and c, so b comes before c. The pair ac and bc first differs at position 0, with a and b, so a comes before b. The order is abc.

Exercise 4. The alien words are ab, ba, and ab. What does the function return, and why?

Show the answer

It returns the empty string. The first pair ab and ba gives a before b. The second pair ba and ab gives b before a. The two rules form a cycle, so no order exists.

Exercise 5. The alien words are b, a, and c. What is the alphabet order?

Show the answer

The answer is bac. The pair b and a gives b before a. The pair a and c gives a before c. The chain is b, a, c.

Summary

• A course list with a cycle has no valid order, and Kahn's loop reveals it by taking fewer items than exist.
• For course pairs [course, prereq], the edge goes from prereq to course, and reversing it gives a wrong answer.
• For an alien dictionary, only the first differing letter of each neighbouring word pair gives a rule.
• A longer word followed by its own prefix, such as abc then ab, is an impossible input, and the answer is the empty string.
• Every letter in every word must be registered, or letters with no rules are lost from the answer.
• In Python, a negative index does not raise an error, and a set does not keep a fixed order, so sort before you depend on the order.