"""
p69 — Alien Dictionary (LeetCode 269, HARD, Premium).

Given words sorted in an unknown alphabet, derive that alphabet order.

Strategy:
1. Build directed graph over chars: edge a -> b means "a precedes b."
2. For each adjacent pair of words, find first differing char -> one edge.
3. Check prefix violation: if word2 is a proper prefix of word1 with len(word1) > len(word2), return "".
4. Topo sort. Cycle -> "".

Returns ANY valid ordering ("" if invalid).
"""
from __future__ import annotations
import random
from collections import defaultdict, deque
from itertools import permutations
from typing import List, Set


def _build_graph(words: List[str]):
    """Returns (adj, indeg, all_chars) or (None, None, None) on prefix violation."""
    all_chars: Set[str] = set()
    for w in words:
        all_chars.update(w)
    adj = defaultdict(set)
    indeg = {c: 0 for c in all_chars}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        found_diff = False
        for j in range(min_len):
            if w1[j] != w2[j]:
                # INVARIANT: only the FIRST differing char yields an edge; later chars give no info.
                if w2[j] not in adj[w1[j]]:
                    adj[w1[j]].add(w2[j])
                    indeg[w2[j]] += 1
                found_diff = True
                break
        if not found_diff and len(w1) > len(w2):
            # Prefix violation: "abc" appearing before "ab" is impossible in dictionary order.
            return None, None, None

    return adj, indeg, all_chars


def alien_order_kahn(words: List[str]) -> str:
    adj, indeg, all_chars = _build_graph(words)
    if all_chars is None:
        return ""

    # INVARIANT: every char with indeg 0 starts in the queue (including isolated chars).
    q = deque(c for c in all_chars if indeg[c] == 0)
    out = []
    while q:
        c = q.popleft()
        out.append(c)
        for nb in adj[c]:
            indeg[nb] -= 1
            if indeg[nb] == 0:
                q.append(nb)

    if len(out) != len(all_chars):
        return ""  # cycle
    return "".join(out)


def alien_order_dfs(words: List[str]) -> str:
    adj, indeg, all_chars = _build_graph(words)
    if all_chars is None:
        return ""

    WHITE, GRAY, BLACK = 0, 1, 2
    color = {c: WHITE for c in all_chars}
    order: List[str] = []

    for start in all_chars:
        if color[start] != WHITE:
            continue
        # Iterative DFS with three-color
        stack = [(start, iter(sorted(adj[start])))]
        color[start] = GRAY
        while stack:
            u, it = stack[-1]
            advanced = False
            for v in it:
                if color[v] == GRAY:
                    return ""  # cycle
                if color[v] == WHITE:
                    color[v] = GRAY
                    stack.append((v, iter(sorted(adj[v]))))
                    advanced = True
                    break
            if not advanced:
                color[u] = BLACK
                order.append(u)
                stack.pop()

    return "".join(reversed(order))


def _is_consistent(order: str, words: List[str]) -> bool:
    rank = {c: i for i, c in enumerate(order)}
    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        ok = False
        for j in range(min_len):
            if w1[j] != w2[j]:
                if rank[w1[j]] >= rank[w2[j]]:
                    return False
                ok = True
                break
        if not ok and len(w1) > len(w2):
            return False
    return True


def alien_order_brute(words: List[str]) -> str:
    chars = sorted({c for w in words for c in w})
    if len(chars) > 7:
        raise ValueError("brute only for small alphabets")
    for perm in permutations(chars):
        s = "".join(perm)
        if _is_consistent(s, words):
            return s
    return ""


def _equiv(a: str, b: str, words: List[str]) -> bool:
    """Two outputs are 'equivalent' if both are empty or both are valid orderings using same char set."""
    if (a == "") != (b == ""):
        return False
    if a == "":
        return True
    if sorted(a) != sorted(b):
        return False
    return _is_consistent(a, words) and _is_consistent(b, words)


def edge_cases() -> None:
    assert alien_order_kahn(["wrt", "wrf", "er", "ett", "rftt"]) == "wertf"
    # Prefix violation
    assert alien_order_kahn(["abc", "ab"]) == ""
    # Cycle: z->x then x->z
    assert alien_order_kahn(["z", "x", "z"]) == ""
    # Single word
    assert sorted(alien_order_kahn(["abc"])) == ["a", "b", "c"]
    # Two equal words — no info, no violation
    assert sorted(alien_order_kahn(["abc", "abc"])) == ["a", "b", "c"]
    # Empty words list yields empty string
    assert alien_order_kahn([]) == ""
    print("edge_cases: PASS")


def _random_words(rng: random.Random, alphabet: str, n_words: int, max_len: int) -> List[str]:
    return ["".join(rng.choice(alphabet) for _ in range(rng.randint(1, max_len))) for _ in range(n_words)]


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(300):
        alphabet = "abcde"[: rng.randint(2, 5)]
        n_words = rng.randint(1, 6)
        max_len = rng.randint(1, 4)
        words = _random_words(rng, alphabet, n_words, max_len)
        a = alien_order_kahn(words)
        b = alien_order_dfs(words)
        c = alien_order_brute(words)

        # All must agree on FEASIBILITY:
        assert (a == "") == (c == ""), f"trial {trial}: kahn={a!r} brute={c!r} words={words}"
        assert (b == "") == (c == ""), f"trial {trial}: dfs={b!r} brute={c!r} words={words}"
        # Both algorithms must produce VALID orderings when one exists:
        if a != "":
            assert _is_consistent(a, words), f"trial {trial}: kahn order {a!r} not consistent with {words}"
            assert sorted(a) == sorted({c for w in words for c in w})
        if b != "":
            assert _is_consistent(b, words), f"trial {trial}: dfs order {b!r} not consistent with {words}"
    print("stress_test: 300 trials — Kahn, DFS, brute (permutation verifier) all agree on feasibility and orderings.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")