#!/usr/bin/env python3
"""Check maps.json using Python 3's standard library. No network calls.

Download this script and maps.json into one directory, then run:
    python3 reproduce.py
Checks every assignment with fewer colors and one witness at the minimum.
This verifies six finite examples, not the four color theorem.
"""
import itertools
import json
from pathlib import Path


def area(points):
    return abs(sum(a[0]*b[1]-a[1]*b[0] for a, b in zip(points, points[1:]+points[:1])))/2


def cross(a, b, c):
    return (b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0])


def hull(points):
    points = sorted(set(map(tuple, points)))
    lo, hi = [], []
    for chain, seq in [(lo, points), (hi, points[::-1])]:
        for p in seq:
            while len(chain) >= 2 and cross(chain[-2], chain[-1], p) <= 0:
                chain.pop()
            chain.append(p)
    return lo[:-1]+hi[:-1]


def intersection(subject, clip):
    # Convex clipping checks that the worksheet interiors do not overlap.
    clip = hull(clip)
    for a, b in zip(clip, clip[1:]+clip[:1]):
        result = []
        for s, e in zip(subject, subject[1:]+subject[:1]):
            cs, ce = cross(a, b, s), cross(a, b, e)
            if (cs >= -1e-8) != (ce >= -1e-8):
                ratio = cs/(cs-ce)
                result.append([s[0]+ratio*(e[0]-s[0]), s[1]+ratio*(e[1]-s[1])])
            if ce >= -1e-8:
                result.append(e)
        subject = result
        if not subject:
            break
    return subject


def adjacency(regions):
    # Derive neighbors from endpoint-identical shared sides, independently of
    # the generator's collinear-overlap implementation. All shared sides in
    # this set use the same two endpoints; no partial-side junctions exist.
    by_side = {}
    for r in regions:
        p = r['vertices']
        assert area(p) > 0
        assert abs(area(hull(p))-area(p)) < .001, 'Expected convex region'
        for a, b in zip(p, p[1:]+p[:1]):
            key = tuple(sorted((tuple(a), tuple(b))))
            by_side.setdefault(key, []).append(r['id'])
    assert all(len(owners) <= 2 for owners in by_side.values())
    return sorted(sorted(owners) for owners in by_side.values() if len(owners) == 2)


def verify(data):
    results = []
    for m in data['maps']:
        regions = m['regions']
        ids = [r['id'] for r in regions]
        assert len(set(ids)) == len(ids)
        edges = adjacency(regions)
        assert edges == sorted(sorted(e) for e in m['edges']), (m['id'], 'adjacency mismatch')
        for a, b in itertools.combinations(regions, 2):
            assert area(intersection(a['vertices'], b['vertices'])) < .001, (m['id'], 'overlap')
        total = sum(area(r['vertices']) for r in regions)
        boundary = hull([p for r in regions for p in r['vertices']])
        assert abs(total-area(boundary)) < .01, (m['id'], 'gap or duplicate area')
        assert all(m['solution'][a] != m['solution'][b] for a, b in edges)
        assert len(set(m['solution'].values())) == m['minimumColors']
        indices = [(ids.index(a), ids.index(b)) for a, b in edges]
        for k in range(1, m['minimumColors']+1):
            found = next((colors for colors in itertools.product(range(k), repeat=len(ids))
                          if all(colors[a] != colors[b] for a, b in indices)), None)
            assert (found is not None) == (k == m['minimumColors']), (m['id'], k)
        results.append({'map': m['id'], 'regions': len(regions), 'borders': len(edges),
                        'minimumColors': m['minimumColors'], 'geometry': 'pass'})
    return results


if __name__ == '__main__':
    data = json.loads(Path(__file__).with_name('maps.json').read_text())
    print(json.dumps({'version': data['version'], 'verified': verify(data)}, indent=2))