"""Contrast a short exact description with compressor proxies; never compute true K."""
from __future__ import annotations
import random
import zlib


def gamma(n):
    """Pre: positive integer. Post: self-delimiting Elias gamma bit string."""
    if not isinstance(n, int) or n <= 0:
        raise ValueError("n must be a positive integer")
    binary = format(n, "b")
    return "0"*(len(binary)-1)+binary


def gamma_decode(stream):
    """Pre: complete binary gamma stream. Post: decoded positive integers or ValueError."""
    if set(stream) - {"0", "1"}:
        raise ValueError("stream must be binary")
    output, i = [], 0
    # Invariant: output decodes exactly stream[:i]. Bound: len(stream)-i.
    while i < len(stream):
        zeros = 0
        while i+zeros < len(stream) and stream[i+zeros] == "0":
            zeros += 1
        end = i+2*zeros+1
        if end > len(stream):
            raise ValueError("truncated gamma code")
        output.append(int(stream[i+zeros:end], 2))
        i = end
    return output


def compressor_ncd(x: bytes, y: bytes):
    """Pre: bytes. Post: raw NCD heuristic; compressors need not stay in [0,1]."""
    a, b = len(zlib.compress(x)), len(zlib.compress(y))
    return (len(zlib.compress(x+y))-min(a, b))/max(a, b)


def demo():
    pattern = b"0110"*2000
    rng = random.Random(7)
    noise = bytes(rng.randrange(256) for _ in range(len(pattern)))
    for name, data in (("repeated", pattern), ("random", noise)):
        print(name, "raw bytes:", len(data), "zlib bytes:", len(zlib.compress(data)))
    print("A short exact program for the repeated string is: b'0110' * 2000")
    print("Compressed lengths include headers; they are not Kolmogorov complexity.")
    stream = "".join(gamma(n) for n in (5, 2, 3, 1))
    print("Gamma stream:", stream, "decoded:", gamma_decode(stream))
    print("NCD repeated vs itself:", round(compressor_ncd(pattern, pattern), 4))
    print("Decoder/program/framing cost must be included in theoretical description bounds.")


def self_test():
    count = 0
    # Invariant: prior integers round-trip through gamma. Bound: remaining 999 integers.
    for n in range(1, 1000):
        check(gamma_decode(gamma(n)), [n])
        count += 1
    values = [1, 2, 3, 13, 1000]
    check(gamma_decode("".join(gamma(n) for n in values)), values)
    check(gamma(13), "0001101")
    for value in (b"", b"a", b"01"*100, bytes(range(256))):
        check(zlib.decompress(zlib.compress(value)), value)
        count += 1
    return count + 2

def check(actual, expected):
    """Require an expected result; this check also runs under python -O."""
    if actual != expected:
        raise AssertionError(f"expected {expected!r}, got {actual!r}")


if __name__ == "__main__":
    import argparse
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument("--self-test", action="store_true")
    args = parser.parse_args()
    if args.self_test:
        print(f"{self_test()} checks passed")
    else:
        demo()