"""Checks and a report for Part 6: the walls of a box.

Run from this folder: python test_box.py
"""
import random
import statistics
from collections import Counter

import box
import route_exact
import unfold
from group_dsu import SHIFTS, TURNS, GroupDSU, turn_across
from surface import (angle_defects, corner_counts, depth_first, euler_characteristic,
                     frames_reachable, move, simulate)
from surface import box as box_surface
from surface import torus as torus_surface
from two_colour import is_odd_loop, two_colour


def reach(s, start):
    return {f for f, _ in frames_reachable(s, start)}


def random_box(rng):
    a, b, c = rng.randint(1, 6), rng.randint(1, 6), rng.randint(1, 6)
    open_top = rng.random() < 0.5
    s = box_surface(a, b, c, open_top)
    blocked = [n for n in s.names if rng.random() < rng.random() * 0.4]
    s = box_surface(a, b, c, open_top, blocked)
    return s


def test_walk(rng):
    for _ in range(400):
        s = random_box(rng)
        if not s.floor:
            continue
        start = rng.choice(s.floor)
        cmds = depth_first(s, start)
        cleaned, _, _ = simulate(s, start, cmds)
        assert cleaned == reach(s, start) and len(cmds) == 2 * (len(cleaned) - 1)
    print('walk .................... ok (400 boxes and pools with furniture)')


def test_square_loops():
    """Round a corner of the box, three stretches close the loop and the robot comes home a
    quarter turn round; everywhere else it takes four and the robot comes home as it left."""
    for n in (2, 3, 4, 6):
        s = box_surface(n, n, n)
        closes = Counter()
        for f in s.floor:
            for h in '^>v<':
                result = box.square_loop(s, f, 1, h)
                closes[result] += 1
        assert closes == Counter({(4, (0, False)): 24 * n * n - 24, (3, (3, False)): 24})
        for k in range(2, n + 1):
            stretches = Counter()
            for f in s.floor:
                for h in '^>v<':
                    result = box.square_loop(s, f, k, h, most=60)
                    stretches[result[0]] += 1
                    if result[0] == 3:
                        assert result[1] == (3, False)
            # Centred on a corner (odd k), three stretches; passing a corner off centre, twelve.
            assert set(stretches) <= {3, 4, 12}
            assert stretches[3] == (24 if k % 2 else 0)
    print('square loops ............ ok (every loop closes after 3, 4 or 12 stretches; 3 only '
          'round a corner)')


def test_twelve():
    """Four stretches past a corner off centre carry the start to its image under the corner's
    three-fold symmetry (the three faces take turns), so twelve close the loop."""
    n = 6
    s = box_surface(n, n, n)
    corners = [(x, y, z) for x in (0, n) for y in (0, n) for z in (0, n)]

    def centre(f):
        return tuple(sum(p[k] for p in s.corners[f]) / 4 for k in range(3))
    checked = 0
    for f in s.floor:
        for h in '^>v<':
            result = box.square_loop(s, f, 2, h, most=12)
            if not result or result[0] != 12:
                continue
            field, frame, head, seen = f, (0, False), h, []
            for stretch in range(12):
                for _ in range(2):
                    field, frame = move(s, field, frame, head)
                head = box.LEFT_OF[head]
                if stretch in (3, 7):
                    seen.append(field)
            c = centre(f)
            k = min(corners, key=lambda q: sum((c[i] - q[i]) ** 2 for i in range(3)))
            rel = [tuple(abs(centre(x)[i] - k[i]) for i in range(3)) for x in [f] + seen]
            a, b, d = rel[0]
            assert {rel[1], rel[2]} == {(d, a, b), (b, d, a)}   # the two cyclic turns
            checked += 1
    assert checked > 0
    print(f'twelve stretches ........ ok ({checked} loops: each round of four turns the start '
          'round the corner)')


def test_turns(rng):
    """The turns a loop can leave the robot with, by union-find, match the frames a search
    finds on the start field; a closed box has all four, a belt round the middle none."""
    seen = Counter()
    for _ in range(400):
        s = random_box(rng)
        if not s.floor:
            continue
        start = rng.choice(s.floor)
        turns = box.turns_on_loops(s, start)
        at_start = {u for f, (u, _) in frames_reachable(s, start) if f == start}
        assert turns == at_start
        seen[len(turns)] += 1
    cube = box_surface(3, 3, 3)
    assert box.turns_on_loops(cube, 0) == {0, 1, 2, 3}
    belt = box_surface(3, 3, 3, blocked=[n for n in cube.names if n[0] in ('top', 'bottom')])
    assert box.turns_on_loops(belt, belt.floor[0]) == {0}
    corner = (0, 0, 0)
    only = [n for f, n in enumerate(cube.names) if corner not in cube.corners[f]]
    tri = box_surface(3, 3, 3, blocked=only)       # just the three fields round one corner
    assert len(tri.floor) == 3 and box.turns_on_loops(tri, tri.floor[0]) == {0, 1, 2, 3}
    print(f'turns on loops .......... ok (400 boxes: {seen[1]} with no turns, {seen[2]} with '
          f'half turns only, {seen[4]} with all four)')


def test_descartes():
    """A closed box is 720 degrees short at its corners, a pool 360, whatever their sizes; and
    the three fields at a corner make a loop of three, so no checkerboard colouring exists."""
    for a in range(1, 6):
        for b in range(1, 6):
            for c in range(1, 6):
                s = box_surface(a, b, c)
                assert euler_characteristic(s) == 2 and angle_defects(s) == 720
                short = sorted(360 - 90 * n for n, arcs in corner_counts(s).values() if not arcs)
                assert short.count(90) == 8 and set(short) <= {0, 90}
                p = box_surface(a, b, c, open_top=True)
                assert euler_characteristic(p) == 1 and angle_defects(p) == 360
                kind, loop = two_colour(s, 0)
                assert kind == 'odd loop' and is_odd_loop(s, loop)
    s = box_surface(4, 4, 4)
    kind, loop = two_colour(s, 0)
    print(f'descartes, parity ....... ok (125 boxes, 125 pools; the odd loop found first on a '
          f'4 x 4 x 4 box has {len(loop)} fields)')


def test_exact():
    """Fewest commands on small boxes: the pruned search (no checkerboard: there is none)
    against brute force."""
    rows = []
    for a, b, c, open_top in [(1, 1, 1, False), (1, 1, 2, False), (1, 2, 2, False),
                              (2, 2, 1, True), (2, 3, 1, True), (1, 1, 3, False)]:
        s = box_surface(a, b, c, open_top)
        n = len(s.floor)
        referee = route_exact.fewest(s, 0, prune=False)
        fast = route_exact.fewest(s, 0)
        assert len(fast) == len(referee)
        assert simulate(s, 0, fast)[0] == set(s.floor)
        rows.append((a, b, c, open_top, n, len(referee)))
    print('fewest commands ......... ok (' + ', '.join(
        f'{"pool" if o else "box"} {a}x{b}x{c}: {n} fields, {m}' for a, b, c, o, n, m in rows) + ')')
    return rows


def test_unfold(rng):
    """Dudeney's spider and fly, and random pairs of points: unfolding against pulling the
    string tight."""
    length, chain = unfold.shortest(30, 12, 12, (0, 6, 11), (30, 6, 1))
    assert abs(length - 40) < 1e-9 and len(chain) == 5
    obvious = 1 + 30 + 11                           # up, across the ceiling, down
    assert obvious == 42
    for _ in range(12):
        L, W, H = rng.randint(2, 12), rng.randint(2, 12), rng.randint(2, 12)
        a = random_point(rng, L, W, H)
        b = random_point(rng, L, W, H)
        u = unfold.shortest(L, W, H, a, b)
        t = unfold.tight(L, W, H, a, b, sweeps=40)
        assert abs(u[0] - t[0]) < 1e-6, (L, W, H, a, b, u, t)
    # The same room in one-foot fields, for a robot that drives in steps: the obvious route's 42.
    s = box_surface(30, 12, 12)
    spider, fly = s.index[('left', 11, 5)], s.index[('right', 5, 0)]
    dist, todo = {spider: 0}, [spider]
    for f in todo:                                  # breadth first: todo only grows at the end
        for g in s.glue[f]:
            if g is not None and g[0] not in dist:
                dist[g[0]] = dist[f] + 1
                todo.append(g[0])
    assert dist[fly] == 42
    print('unfolding ............... ok (spider and fly: 40 feet over 5 faces; 12 random pairs '
          'agree with the string pulled tight; 42 grid steps)')


def random_point(rng, L, W, H):
    face = rng.randrange(6)
    x, y, z = rng.uniform(0, L), rng.uniform(0, W), rng.uniform(0, H)
    return [(x, y, 0), (x, y, H), (0, y, z), (L, y, z), (x, 0, z), (x, W, z)][face]


def report_unfold(rng, pairs=2000):
    """Opposite ends of a long room: how many faces does the shortest way cross?"""
    faces = Counter()
    for _ in range(pairs):
        a = (0, rng.uniform(0, 12), rng.uniform(0, 12))
        b = (30, rng.uniform(0, 12), rng.uniform(0, 12))
        faces[len(unfold.shortest(30, 12, 12, a, b)[1])] += 1
    print(f'\nDudeney\'s room, {pairs} random pairs of points on the two end walls: faces crossed '
          + ', '.join(f'{k}: {v}' for k, v in sorted(faces.items())))


def first_wrap(s, order):
    """Newman and Ziff's trick: floor appears field by field; union-find with shifts on the
    unrolled plane. A loop whose leftover shift isn't (0, 0) goes round the torus."""
    dsu, present = GroupDSU(*SHIFTS), set()
    step = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}
    for k, f in enumerate(order, 1):
        dsu.add(f)
        present.add(f)
        for side, g in enumerate(s.glue[f]):
            if g is not None and g[0] in present:
                kind, left = dsu.union(f, g[0], step[side])
                if kind == 'loop' and left != (0, 0):
                    return k, left
    return None


def report_wrap(rng):
    print('\nFloor added one field at a time on an n x n torus: when does a loop first go round?')
    for n in (16, 32, 64, 128, 256):
        s, _ = torus_surface(['*' + '.' * (n - 1)] + ['.' * n] * (n - 1))
        shares, ways = [], Counter()
        for _ in range(400 if n <= 64 else 60):
            order = list(range(n * n))
            rng.shuffle(order)
            k, left = first_wrap(s, order)
            shares.append(k / (n * n))
            ways['across' if left[0] == 0 else 'down' if left[1] == 0 else 'diagonal'] += 1
        print(f'  n = {n:<4} share of floor {statistics.mean(shares):.4f} '
              f'(sd {statistics.stdev(shares):.4f}); ' + ', '.join(f'{k} {v}' for k, v in sorted(ways.items())))


def test_turn_labels():
    """On a flat floor every crossing is a zero turn; on a box, only crossings over an edge of the
    box turn the frame."""
    s = box_surface(3, 3, 3)
    for f in s.floor:
        for side in range(4):
            if s.glue[f][side] is not None:
                g = s.glue[f][side][0]
                same_face = s.names[f][0] == s.names[g][0]
                assert (turn_across(s, f, side) == 0) or not same_face
    dsu = GroupDSU(*TURNS)
    for x in range(10):
        dsu.add(x)
    print('turn labels ............. ok')


if __name__ == '__main__':
    rng = random.Random(6)
    test_walk(rng)
    test_square_loops()
    test_twelve()
    test_turns(rng)
    test_turn_labels()
    test_descartes()
    test_exact()
    test_unfold(rng)
    report_unfold(rng)
    report_wrap(rng)