"""Part 6: union-find with labels from any group.

Part 5's union-find stored one bit per field: whether it was mirrored relative to its parent.
Nothing in the structure cared that the labels were bits. It combined two labels (xor), undid
one (xor again) and started from nothing (0). Any group supplies those three things, so the same
code keeps any kind of relation between fields:

- quarter turns, {0, 1, 2, 3} under addition mod 4: how much the robot's frame has turned
  (this part, on the box);
- shifts, pairs of integers under addition: where a field sits on the unrolled plane (Part 4's
  periods, found incrementally);
- parity, {0, 1} under xor: Part 4's colours and Part 5's mirrorings.

Each field x stores rel[x], its label relative to its parent, meaning
    value(x) = value(parent) * rel[x],
and value(root) is the identity. `union(a, b, g)` records value(b) = value(a) * g. When a and b
are already joined, the claim is checked instead, and what is left over when it fails,
value(a) * g * value(b)^-1, is what the loop through that edge does to the robot: its holonomy.
"""


class GroupDSU:
    def __init__(self, compose, inverse, identity):
        self.compose, self.inverse, self.identity = compose, inverse, identity
        self.parent, self.rel, self.size = {}, {}, {}

    def add(self, x):
        if x not in self.parent:
            self.parent[x], self.rel[x], self.size[x] = x, self.identity, 1

    def find(self, x):
        """(root, value of x relative to the root), compressing the path."""
        path = []
        while self.parent[x] != x:
            path.append(x)
            x = self.parent[x]
        root, acc = x, self.identity
        for y in reversed(path):                    # nearest the root first
            acc = self.compose(acc, self.rel[y])
            self.parent[y], self.rel[y] = root, acc
        return root, (self.rel[path[0]] if path else self.identity)

    def union(self, a, b, g):
        """Record value(b) = value(a) * g. Returns ('joined', None), or ('loop', h) when a and b
        were already joined, with h the loop's leftover: the identity if the claim agrees."""
        ra, va = self.find(a)
        rb, vb = self.find(b)
        through = self.compose(va, g)               # value(b) by way of this edge
        if ra == rb:
            return 'loop', self.compose(through, self.inverse(vb))
        if self.size[ra] >= self.size[rb]:
            self.parent[rb], self.rel[rb] = ra, self.compose(through, self.inverse(vb))
            self.size[ra] += self.size[rb]
        else:
            # value(a) = value(b) * g^-1, so hang ra under rb the other way round.
            self.parent[ra] = rb
            self.rel[ra] = self.compose(self.compose(vb, self.inverse(g)), self.inverse(va))
            self.size[rb] += self.size[ra]
        return 'joined', None


# Three groups, as (compose, inverse, identity).
PARITY = (lambda a, b: a ^ b, lambda a: a, 0)
TURNS = (lambda a, b: (a + b) % 4, lambda a: -a % 4, 0)
SHIFTS = (lambda a, b: (a[0] + b[0], a[1] + b[1]), lambda a: (-a[0], -a[1]), (0, 0))


def turn_across(surface, f, side):
    """How many quarter turns the robot's frame makes crossing from f through side, on a
    surface without twists: its up moves from side u of f to side u + t + 2 - side of g."""
    _, t, flipped = surface.glue[f][side]
    assert not flipped, 'a twist is a mirror image, not a turn'
    return (t + 2 - side) % 4