"""
p97 — Text Justification (LC 68)

INVARIANT (line-packing): line_len = sum(word_len) + (count - 1) for mandatory
  single spaces. Adding word w requires line_len + 1 + len(w) <= maxWidth.

INVARIANT (spacing): for k words on a non-last line, distribute
  (maxWidth - total_word_chars) spaces across (k - 1) gaps via divmod.
  Leftover goes to the LEFTMOST gaps (left-leaning).

INVARIANT (last line + single-word line): always left-justified — words
  joined by single spaces, then trailing-space padded to maxWidth.
"""
from __future__ import annotations

import random
from typing import List


def _format_line(words: List[str], maxWidth: int, is_last: bool) -> str:
    k = len(words)
    total_word_chars = sum(len(w) for w in words)
    if k == 1 or is_last:
        # Left-justify: single spaces between, pad trailing.
        line = " ".join(words)
        return line + " " * (maxWidth - len(line))
    # Full-justify: distribute (maxWidth - total_word_chars) across (k - 1) gaps.
    total_spaces = maxWidth - total_word_chars
    gaps = k - 1
    base, extra = divmod(total_spaces, gaps)
    parts: List[str] = []
    for i, w in enumerate(words):
        parts.append(w)
        if i < gaps:
            # Leftmost `extra` gaps get one extra space.
            parts.append(" " * (base + (1 if i < extra else 0)))
    return "".join(parts)


def full_justify(words: List[str], maxWidth: int) -> List[str]:
    """Greedy line-packing + per-line formatting. O(total chars)."""
    out: List[str] = []
    i = 0
    n = len(words)
    while i < n:
        # Greedy: pack words into the current line.
        j = i
        line_len = len(words[j])
        j += 1
        while j < n and line_len + 1 + len(words[j]) <= maxWidth:
            line_len += 1 + len(words[j])
            j += 1
        is_last = j == n
        out.append(_format_line(words[i:j], maxWidth, is_last))
        i = j
    return out


def _verify(words: List[str], maxWidth: int, lines: List[str]) -> bool:
    """Property check: every line is exactly maxWidth; concatenated visible words match input."""
    for line in lines:
        if len(line) != maxWidth:
            return False
    rebuilt = []
    for line in lines:
        rebuilt.extend(line.split())
    return rebuilt == words


def edge_cases() -> None:
    # Canonical LC examples.
    r = full_justify(
        ["This", "is", "an", "example", "of", "text", "justification."], 16
    )
    assert r == ["This    is    an", "example  of text", "justification.  "], r

    r = full_justify(["What", "must", "be", "acknowledgment", "shall", "be"], 16)
    assert r == ["What   must   be", "acknowledgment  ", "shall be        "], r

    r = full_justify(
        [
            "Science", "is", "what", "we", "understand", "well", "enough", "to",
            "explain", "to", "a", "computer.", "Art", "is", "everything", "else",
            "we", "do",
        ],
        20,
    )
    assert r == [
        "Science  is  what we",
        "understand      well",
        "enough to explain to",
        "a  computer.  Art is",
        "everything  else  we",
        "do                  ",
    ], r

    # Single word, fits exactly.
    r = full_justify(["a"], 1)
    assert r == ["a"], r

    # Single word, line of width 5.
    r = full_justify(["hi"], 5)
    assert r == ["hi   "], r

    # Word exactly equal to maxWidth.
    r = full_justify(["abc", "defgh"], 5)
    assert r == ["abc  ", "defgh"], r


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(200):
        n = rng.randint(1, 12)
        maxWidth = rng.randint(1, 12)
        words = []
        for _ in range(n):
            w_len = rng.randint(1, maxWidth)  # ensure each word fits
            words.append("a" * w_len)
        lines = full_justify(words, maxWidth)
        assert _verify(words, maxWidth, lines), (words, maxWidth, lines)


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