"""Reproducible, finite exact checks of the report's tree witness and constants.

Free-group words are reduced exactly. Axis windows are finite: the accompanying
review supplies the tree-geodesic argument extending the overlap calculation.
This script neither checks the probabilistic theorem nor repairs its proof.
"""
from fractions import Fraction
import hashlib
import json
import math
from pathlib import Path


def reduce(word):
    stack = []
    for c in word:
        if stack and stack[-1] == c.swapcase():
            stack.pop()
        else:
            stack.append(c)
    return ''.join(stack)


def inverse(word):
    return word.swapcase()[::-1]


def multiply(left, right):
    return reduce(left + right)


def distance(left, right):
    return len(multiply(inverse(left), right))


def axis_vertex(g, t):
    period, residue = divmod(t, len(g))
    whole = g * period if period >= 0 else inverse(g) * (-period)
    return multiply(whole, g[:residue])


def witness(m, n):
    g = 'a' * m + 'b' * (3 * m)
    ell = len(g)
    # Nonperiodicity of a cyclically reduced word rules out a proper power.
    assert all(g != g[:k] * (ell // k)
               for k in range(1, ell) if ell % k == 0)
    axis = {t: axis_vertex(g, t) for t in range(-ell, 2 * ell + 1)}
    translated = {t: multiply('a', v) for t, v in axis.items()}
    overlap = set(axis.values()) & set(translated.values())
    assert overlap == {'a' * k for k in range(1, m + 1)}
    s = [axis[t] for t in range(m + 2)]
    companion = ['a' * k for k in range(1, m + 1)]
    assert distance(s[0], companion[0]) == 1
    assert distance(s[-1], companion[-1]) == 1
    # Distance profiles include the first excluded vertex at each endpoint.
    ds = {t: min(distance(axis[t], x) for x in translated.values())
          for t in range(-1, m + 3)}
    assert ds[-1] == ds[m + 2] == 2
    assert all(ds[t] <= 1 for t in range(m + 2))
    h = multiply('a', g * n)
    pulled = [multiply(inverse(h), v) for v in companion]
    assert pulled == [axis_vertex(g, -n * ell + t) for t in range(m)]
    assert not set(s) & set(pulled)
    # Projection to the parameter circle is the axis coordinate modulo ell.
    projected = {(-n * ell + t) % ell for t in range(m)}
    assert projected == set(range(m))
    assert projected <= set(range(m + 2))
    assert m > 2 and m <= Fraction(ell, 3) and m + 1 < Fraction(ell, 2)
    return dict(m=m, N=n, ell=ell, J=1, d=m, piece_length=m + 1,
                companion_length=m - 1, lifted_overlap_vertices=0,
                projected_overlap_edge_length=m - 1,
                endpoint_distances=[1, 1], next_vertex_distances=[2, 2],
                proper_power=False)


def cosh_rational_bounds(x, terms=20):
    """Positive Taylor sum with a geometric majorant for its remaining tail."""
    term = Fraction(1)
    total = term
    for k in range(1, terms + 1):
        term *= x * x / ((2 * k - 1) * (2 * k))
        total += term
    ratio = x * x / ((2 * terms + 1) * (2 * terms + 2))
    assert 0 <= ratio < 1
    return total, total + term * ratio / (1 - ratio)


def certify_rounding():
    # cos(2*pi/5) = (sqrt(5)-1)/4. The following bounds are exact rationals.
    klo = Fraction(3090169943749474, 10**16)
    khi = Fraction(3090169943749475, 10**16)
    assert (4 * klo + 1)**2 < 5 < (4 * khi + 1)**2
    c_hint = math.acosh(float(klo) + 1)
    d_hint = math.acosh(float(2 * khi * khi + 2 * khi + 1))
    # Floating point proposes endpoints only; the inequalities below certify them.
    clo = Fraction(math.floor(c_hint * 10**8), 10**8)
    dhi = Fraction(math.ceil(d_hint * 10**8), 10**8)
    _, cosh_c_upper = cosh_rational_bounds(clo)
    cosh_d_lower, _ = cosh_rational_bounds(dhi)
    assert cosh_c_upper < klo + 1
    assert cosh_d_lower > 2 * khi * khi + 2 * khi + 1
    lambda_upper = dhi / clo
    denominator_upper = 40 * lambda_upper + 1
    assert denominator_upper < Fraction(6351, 100)
    return dict(K_lower=str(klo), K_upper=str(khi), c_lower=str(clo),
                d_upper=str(dhi), lambda_upper=str(lambda_upper),
                denominator_upper=str(denominator_upper),
                strict_margin_lower=str(Fraction(6351, 100) - denominator_upper),
                method='Exact rational Taylor bounds for cosh with a geometric tail; monotonicity of cosh on positive reals.',
                taylor_terms=20)


def main():
    cases = [witness(m, n) for m in [4, 5, 7, 16, 32]
             for n in [2, 3, 7]]
    alpha = Fraction(1, 20)
    q_limit = alpha / (alpha + 2)
    assert q_limit == Fraction(1, 41)
    assert 2 * q_limit == alpha * (1 - q_limit)
    K = math.cos(2 * math.pi / 5)
    lam = math.acosh(2 * K * K + 2 * K + 1) / math.acosh(K + 1)
    denominator = 40 * lam + 1
    assert denominator < 63.51
    out = dict(
        scope='Finite exact free-group checks and independent arithmetic; not a full proof or a theorem counterexample.',
        tree_cases=cases,
        density=dict(q_limit=str(q_limit), endpoint_requires_strict_slack=True,
                     lambda_double=lam, denominator_double=denominator,
                     rounding_margin_double=63.51 - denominator,
                     rounding_certificate=certify_rounding()),
        delta_correction=dict(before_coefficients={'eta': -4, 'lambda2_Kplus1': -2,
                              'epsilon': -2, 'psi': -2, 'delta': -4},
                              printed_delta_coefficient=-2),
        script_sha256=hashlib.sha256(Path(__file__).read_bytes()).hexdigest(),
    )
    output = Path(__file__).with_name('report-check-results.json')
    output.write_text(json.dumps(out, indent=2) + '\n')
    print(json.dumps({'exact_tree_cases_passed': len(cases),
                      'density': out['density'], 'output': str(output)}, indent=2))


if __name__ == '__main__':
    main()
