"""Part 5: the blind robot on a floor that may have a twist.

Part 4's robot learned the room's periods from where on its counted map the dock turned up. On a
Mobius strip that isn't enough: after going round once, the robot is back on the dock but
mirrored, so the copy of the room it has walked into is a mirror image, not a shifted copy.
Folding the map by a shift would glue the wrong fields together.

So the dock carries an arrow, a mark that looks different in a mirror, and robot.on_dock() now
returns how the arrow looks from the robot, or None off the dock. From that and the counted
position, the robot knows the whole symmetry that carries its starting copy of the room onto the
one it is standing in: a shift, possibly combined with a mirror image or a turn. It collects
those symmetries, and names every field by the smallest position in its orbit under them.

The symmetries form a group. Its shifts form a lattice, handled exactly as in Part 4 (Hermite
normal form), and the rest is finite: every symmetry is a shift followed by one of the eight ways
to turn or mirror a square. So the group is stored as one representative for each of those it
uses, plus the lattice of shifts, and Schreier's lemma says which shifts to add: for every
representative r and every symmetry s found so far, s after r lands on some representative r',
and the leftover shift between them is in the group.
"""
import blind_torus
from periods import hermite, reduce

UNIT = [(-1, 0), (0, 1), (1, 0), (0, -1)]           # '^ > v <' as (row, column) steps
IDENTITY = ((1, 0), (0, 1))


def matrix(perm):
    """The 2 x 2 matrix that sends each of the robot's direction vectors to the one perm says:
    perm[d] is the direction that direction d becomes."""
    up, right = UNIT[perm[0]], UNIT[perm[1]]        # images of (-1, 0) and (0, 1)
    return ((-up[0], right[0]), (-up[1], right[1]))


def apply(m, v):
    return m[0][0] * v[0] + m[0][1] * v[1], m[1][0] * v[0] + m[1][1] * v[1]


def mul(m, n):
    return tuple(tuple(sum(m[i][k] * n[k][j] for k in range(2)) for j in range(2)) for i in range(2))


def compose(g, h):
    """g after h, for symmetries (matrix, shift) acting as v -> matrix v + shift."""
    (m, s), (n, t) = g, h
    mt = apply(m, t)
    return mul(m, n), (mt[0] + s[0], mt[1] + s[1])


def inverse(g):
    m, s = g
    mi = ((m[0][0], m[1][0]), (m[0][1], m[1][1]))   # turns and mirrors: the inverse is the transpose
    t = apply(mi, s)
    return mi, (-t[0], -t[1])


class Isometries:
    """The symmetries found so far. `first` is how the dock's arrow looked at the start: for
    each of the robot's directions, the dock side it pointed through."""

    def __init__(self, first):
        self.first = first
        self.found = []
        self.reps = {IDENTITY: (IDENTITY, (0, 0))}
        self.basis = ()

    def symmetry(self, p, reading):
        """The symmetry that carries the start onto counted position p with the arrow looking
        like `reading`: direction d at the start matches the direction that now points through
        the same dock side."""
        now = {side: d for d, side in enumerate(reading)}
        return matrix([now[self.first[d]] for d in range(4)]), p

    def contains(self, g):
        m, _ = g
        if m not in self.reps:
            return False
        shift = compose(g, inverse(self.reps[m]))[1]
        return reduce(shift, self.basis) == (0, 0)

    def learn(self, p, reading):
        g = self.symmetry(p, reading)
        if self.contains(g):
            return False
        self.found.append(g)
        gens = self.found + [inverse(x) for x in self.found]
        reps, shifts, todo = {IDENTITY: (IDENTITY, (0, 0))}, [], [IDENTITY]
        while todo:                                 # Schreier: close up the representatives
            r = reps[todo.pop()]
            for s in gens:
                sr = compose(s, r)
                if sr[0] not in reps:
                    reps[sr[0]] = sr
                    todo.append(sr[0])
                else:
                    shifts.append(compose(sr, inverse(reps[sr[0]]))[1])
        self.reps, self.basis = reps, hermite(shifts)
        return True

    def canon(self, p):
        return min(reduce(compose(r, (IDENTITY, p))[1], self.basis) for r in self.reps.values())

    def mirrored(self):
        """Has the robot found a way round that mirrors it?"""
        return any(m[0][0] * m[1][1] - m[0][1] * m[1][0] < 0 for m in self.reps)


def solution(robot, growth=2, radius=1):
    """Part 4's frontier explorer, naming fields by their orbits under the symmetries found."""
    group = Isometries(robot.on_dock())
    count, stats = blind_torus.solution(robot, group, growth, radius)
    stats['group'] = group
    return count, stats