#!/usr/bin/env python3
"""Bounded exact replay of a specified parity-prefix/first-hit comparison.

No imports from the second implementation; no network or third-party packages.
A resource limit never yields a negative mathematical conclusion.
"""
import json
from pathlib import Path
import re
import sys

MAX_INPUT_BYTES = 65536


def integer_field(value, name, low, high):
    if type(value) is not int or not low <= value <= high:
        raise ValueError(f'{name} must be an integer in [{low}, {high}]')
    return value


def validate(spec):
    if type(spec) is not dict or set(spec) != {'schema','starts','prefix_length','max_steps','max_bits'}:
        raise ValueError('Expected exactly the documented input fields')
    if type(spec['schema']) is not int or spec['schema'] != 1:
        raise ValueError('Unsupported schema')
    integer_field(spec['prefix_length'], 'prefix_length', 1, 64)
    integer_field(spec['max_steps'], 'max_steps', 0, 10000)
    integer_field(spec['max_bits'], 'max_bits', 1, 4096)
    starts = spec['starts']
    if type(starts) is not list or not 2 <= len(starts) <= 16:
        raise ValueError('starts must contain between 2 and 16 decimal strings')
    if any(type(n) is not str or len(n) > 1234 or not re.fullmatch(r'[1-9][0-9]*',n) for n in starts):
        raise ValueError('Each start must be a canonical positive decimal string of at most 1234 digits')
    return spec


def step(n):
    return n // 2 if n % 2 == 0 else (3 * n + 1) // 2


def replay(start, prefix_length, max_steps, max_bits):
    value = int(start)
    orbit, parity = [], []
    first_hit = None
    reason = None
    for index in range(max_steps + 1):
        if value.bit_length() > max_bits:
            reason = 'bit-cap'
            break
        orbit.append(str(value))
        if len(parity) < prefix_length:
            parity.append(str(value % 2))
        if value == 1 and first_hit is None:
            first_hit = index
        if first_hit is not None and len(parity) == prefix_length:
            break
        if index == max_steps:
            reason = 'step-cap'
            break
        value = step(value)
    return {'start':start,'orbit':orbit,'parity_prefix':''.join(parity),'first_hit':first_hit,
            'status':'resource-limit' if reason else 'reached-one','limit':reason}


def run(spec):
    validate(spec)
    records = [replay(n,spec['prefix_length'],spec['max_steps'],spec['max_bits']) for n in spec['starts']]
    complete = [r for r in records if r['status'] == 'reached-one']
    witnesses = [[a['start'],b['start']] for i,a in enumerate(complete) for b in complete[i+1:]
                 if a['parity_prefix'] == b['parity_prefix'] and a['first_hit'] != b['first_hit']]
    # A complete witness remains a counterexample even if another input hits a cap.
    disposition = 'counterexample' if witnesses else 'unknown' if len(complete) != len(records) else 'no-counterexample-in-supplied-inputs'
    return {'schema':1,'map':'T(n)=n/2 if even; (3*n+1)/2 if odd','prefix_length':spec['prefix_length'],
            'records':records,'counterexample_pairs':witnesses,'disposition':disposition}


def no_duplicates(pairs):
    result = {}
    for key,value in pairs:
        if key in result: raise ValueError('Duplicate input field')
        result[key] = value
    return result


def load(path):
    with Path(path).open('rb') as stream:
        raw = stream.read(MAX_INPUT_BYTES + 1)
    if len(raw) > MAX_INPUT_BYTES: raise ValueError('Input exceeds 65536 bytes')
    return json.loads(raw, object_pairs_hook=no_duplicates)


def main():
    try:
        if len(sys.argv) != 2: raise ValueError('Usage: python3 check.py input.json')
        result = run(load(sys.argv[1]))
    except (ValueError, OSError) as error:
        print(json.dumps({'error':str(error)},sort_keys=True),file=sys.stderr)
        return 2
    print(json.dumps(result,sort_keys=True,separators=(',',':')))
    return 0


if __name__ == '__main__':
    raise SystemExit(main())
