Pattern visualizer
Alien Dictionary
A sorted dictionary hides its alphabet in the FIRST letter where two neighbouring words diverge — every letter before that point already matched, so it says nothing, and one word being a prefix of the other says nothing either (unless the longer one comes first, which is impossible in any alphabet). Each divergence is one directed edge, letter before -> letter after, and once every adjacent pair has been compared, recovering the full order is exactly Kahn's topological sort: repeatedly take a letter nothing points into, and removing it may free the letters it pointed to. A cycle in these edges — like z before x and x before z — means no alphabet could produce this dictionary, and the letter count coming up short of the full order is how that shows up. Animated on: words = ["wrt", "wrf", "er", "ett", "rftt"], sorted lexicographically by an unknown alien alphabet — derive that alphabet's letter order, or "" if the words are inconsistent with any order..
Derive edges from adjacent words, then Kahn's topological sort
5 words, given already sorted by this alien alphabet's rules: "wrt", "wrf", "er", "ett", "rftt". The only place two neighbouring words reveal a rule is the FIRST letter where they differ — everything before that point is already equal, and everything after is irrelevant to the comparison.
1FUNCTION alienOrder(words):2 SEED indeg[c] <- 0 FOR EVERY CHARACTER IN words3 FOR EACH adjacent pair (w1, w2) IN words4 IF w1 IS PREFIX OF w2 AND LENGTH(w1) > LENGTH(w2)5 RETURN ""6 j <- FIRST INDEX WHERE w1[j] != w2[j]7 IF j EXISTS, ADD EDGE w1[j] -> w2[j] AND indeg[w2[j]] <- indeg[w2[j]] + 18 queue <- ALL c WITH indeg[c] = 09 WHILE queue NOT EMPTY10 c <- REMOVE FRONT OF queue11 APPEND c TO order12 FOR EACH d IN next[c]13 indeg[d] <- indeg[d] - 114 IF indeg[d] = 0, APPEND d TO queue15 RETURN order IF LENGTH(order) = UNIQUE CHAR COUNT ELSE ""
← / → step · space play · Home restart