guess_mapping_full.py

def topological_sort(graph: Dict[Any, Iterable[Any]]) -> List[Any]:
    ordered = []
    discovered = set()

    def dfs(node):
        for children in graph.get(node, []):
            if children not in discovered:
                discovered.add(children)
                dfs(children)
        ordered.append(node)

    for start_node in graph.keys():
        if start_node not in discovered:
            discovered.add(start_node)
            dfs(start_node)
    return list(reversed(ordered))


def find_constraints(words: List[str]) -> Dict[str, Set[str]]:
    ordering_constraints = {c: set() for word in words for c in word}

    n = len(words)
    for i in range(n):
        for j in range(i+1, n):
            w1 = words[i]
            w2 = words[j]
            m = min(len(w1), len(w2))
            for k in range(m):
                if w1[k] != w2[k]:
                    ordering_constraints[w1[k]].add(w2[k])
                    break

            # Quick optimization to let transitivity in the graph do its work (could be done for letter 2, etc.)
            if w1[0] != w2[0]:
                break

    return ordering_constraints


def guess_mapping(words: List[str]) -> Dict[str, str]:
    ordering_constraints = find_constraints(words)
    ordered_letters = topological_sort(ordering_constraints)
    return {dst: src for src, dst in zip(string.ascii_lowercase, ordered_letters)}