Deriving the graph from the input

The hardest part is not the algorithm. It is working out what the nodes and edges are.

Why it works

Adjacent items give one constraint each

When an ordering must be inferred from a sorted list of items, each adjacent pair yields exactly one piece of information: the position of their first difference tells you which symbol comes before which.

Only the first difference matters. Everything after it is unconstrained, because the earlier position already decided the order. Comparing every pair rather than adjacent ones, or reading past the first difference, both invent constraints that are not there.

1def constraints_from(words):2    pairs = []3    for first, second in zip(words, words[1:]):4        for a, b in zip(first, second):5            if a != b:6                pairs.append((a, b))        # a comes before b7                break                       # nothing after this is implied8    return pairs9 10print(constraints_from(["wrt", "wrf", "er", "ett", "rftt"]))

Write these down first

What is a node? What does an edge mean, and which direction does it point? Which inputs produce edges, and which produce nothing? What input is impossible, and how would I detect it?

Four sentences. For the problem below they take five minutes and turn it from a hard problem into a derivation followed by an algorithm you have already written.

Find the bug· 5 min

Find the invented constraint

This extracts ordering constraints from adjacent words. It produces constraints that the input does not actually imply. Click the line that is wrong.

Click the line you think is wrong

Complexity· 5 min

Cost of the derivation

Extracting constraints from n words of average length L, then topologically ordering the resulting graph over an alphabet of size a. Give the total time and the space for the graph.

Python

1for first, second in zip(words, words[1:]):2    for a, b in zip(first, second):3        if a != b:4            pairs.append((a, b))5            break

Problem· 38 min

Alien Dictionary

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

CodeGround