"""Part 6: the shortest way across the walls of a box, by unfolding it.

A real robot doesn't drive in grid steps: it drives straight. On a flat floor the shortest way
between two points is the straight line; on the walls of a box it is a straight line on some
unfolding of the box. Cut the box open along its edges, lay a chain of faces out flat, one after
another, draw the straight line from the start to the goal on that flat chain, and it is a path
on the box. Every shortest path appears on some chain, so trying every chain of faces (none
twice) and keeping the shortest straight line that really stays inside its chain gives the
answer.

This is Henry Dudeney's spider and fly puzzle (1903): in a room 30 feet long and 12 wide and
high, a spider in the middle of one end wall, a foot below the ceiling, wants a fly in the middle
of the other end wall, a foot above the floor. The obvious way, up, across the ceiling and down,
is 42 feet. The shortest is 40, and it crosses five of the six faces.

The check at the bottom does it a second way, without unfolding anything: for each chain it
slides the crossing points along the shared edges to make the path as short as possible in three
dimensions ("pulling the string tight"), and keeps the best.
"""
from itertools import product
from math import hypot


def faces(L, W, H):
    """The six faces of the box [0, L] x [0, W] x [0, H], as (name, origin, u, v, a, b):
    points origin + s u + t v with 0 <= s <= a, 0 <= t <= b."""
    return [
        ('floor', (0, 0, 0), (1, 0, 0), (0, 1, 0), L, W),
        ('ceiling', (0, 0, H), (1, 0, 0), (0, 1, 0), L, W),
        ('near end', (0, 0, 0), (0, 1, 0), (0, 0, 1), W, H),
        ('far end', (L, 0, 0), (0, 1, 0), (0, 0, 1), W, H),
        ('left side', (0, 0, 0), (1, 0, 0), (0, 0, 1), L, H),
        ('right side', (0, W, 0), (1, 0, 0), (0, 0, 1), L, H),
    ]


def local(face, p):
    """Point p (on the face) in the face's own coordinates, as a complex number s + it."""
    _, o, u, v, _, _ = face
    d = [p[k] - o[k] for k in range(3)]
    return complex(sum(d[k] * u[k] for k in range(3)), sum(d[k] * v[k] for k in range(3)))


def on_face(face, p, eps=1e-9):
    _, o, u, v, a, b = face
    n = (u[1] * v[2] - u[2] * v[1], u[2] * v[0] - u[0] * v[2], u[0] * v[1] - u[1] * v[0])
    if abs(sum((p[k] - o[k]) * n[k] for k in range(3))) > eps:
        return False
    w = local(face, p)
    return -eps <= w.real <= a + eps and -eps <= w.imag <= b + eps


def shared_edges(L, W, H):
    """For every pair of faces that meet, the two corners of the edge between them."""
    fs = faces(L, W, H)
    corners = list(product((0, L), (0, W), (0, H)))
    edges = {}
    for p, q in ((p, q) for p in corners for q in corners if p < q):
        if sum(p[k] != q[k] for k in range(3)) != 1:
            continue
        both = [i for i, f in enumerate(fs) if on_face(f, p) and on_face(f, q)]
        i, j = both
        edges[i, j] = edges[j, i] = (p, q)
    return fs, edges


def place(pos):
    """A placement is (alpha, beta, mirror): local point w goes to alpha w + beta, or
    alpha conj(w) + beta when mirrored."""
    alpha, beta, mirror = pos
    return lambda w: alpha * (w.conjugate() if mirror else w) + beta


def unfold_next(fs, edges, i, pos, j):
    """Lay face j flat next to face i (already placed at pos), across their shared edge, on
    the far side of it."""
    p3, q3 = edges[i, j]
    f = place(pos)
    p, q = f(local(fs[i], p3)), f(local(fs[i], q3))
    wp, wq = local(fs[j], p3), local(fs[j], q3)
    ci = f(complex(fs[i][4], fs[i][5]) / 2)                     # face i's centre, placed
    side_i = ((q - p).conjugate() * (ci - p)).imag
    for mirror in (False, True):
        a, b = (wp.conjugate(), wq.conjugate()) if mirror else (wp, wq)
        alpha = (q - p) / (b - a)
        beta = p - alpha * a
        g = place((alpha, beta, mirror))
        cj = g(complex(fs[j][4], fs[j][5]) / 2)
        if ((q - p).conjugate() * (cj - p)).imag * side_i < 0:  # opposite sides of the edge
            return alpha, beta, mirror
    raise AssertionError('no way to lay the face flat')


def crosses(s, t, p, q, eps=1e-12):
    """Where segment s-t crosses segment p-q: the fraction along s-t, or None."""
    d, e = t - s, q - p
    den = (d.conjugate() * e).imag
    if abs(den) < eps:
        return None
    lam = ((p - s).conjugate() * e).imag / den
    mu = ((p - s).conjugate() * d).imag / den
    if -eps <= lam <= 1 + eps and eps < mu < 1 - eps:          # through the edge, not a corner
        return lam
    return None


def chains(fs, edges, start, goal):
    """Every chain of faces from start to goal with no face twice."""
    out, path = [], [start]

    def grow():
        if path[-1] == goal:
            out.append(list(path))
            return
        for j in range(len(fs)):
            if j not in path and (path[-1], j) in edges:
                path.append(j)
                grow()
                path.pop()
    grow()
    return out


def routes(L, W, H, a, b):
    """Every chain of faces on which the straight line from a to b stays inside the chain,
    crossing each shared edge in order: [(length, chain of face names)], in the order found."""
    fs, edges = shared_edges(L, W, H)
    fa = next(i for i, f in enumerate(fs) if on_face(f, a))
    fb = [i for i, f in enumerate(fs) if on_face(f, b)]
    out = []
    for goal in fb:
        for chain in chains(fs, edges, fa, goal):
            pos = [(1, 0, False)]
            for i, j in zip(chain, chain[1:]):
                pos.append(unfold_next(fs, edges, i, pos[-1], j))
            s = place(pos[0])(local(fs[fa], a))
            t = place(pos[-1])(local(fs[goal], b))
            lams = []
            for k, (i, j) in enumerate(zip(chain, chain[1:])):
                p3, q3 = edges[i, j]
                f = place(pos[k])
                lam = crosses(s, t, f(local(fs[i], p3)), f(local(fs[i], q3)))
                if lam is None:
                    break
                lams.append(lam)
            else:
                if lams == sorted(lams):
                    out.append((abs(t - s), [fs[i][0] for i in chain]))
    return out


def shortest(L, W, H, a, b):
    """The shortest path over the walls from point a to point b (both on the box's surface).
    Returns (length, chain of face names), trying every unfolding."""
    best = None
    for length, chain in routes(L, W, H, a, b):
        if best is None or length < best[0] - 1e-9:
            best = (length, chain)
    return best


# ---- The check: pull the string tight, in three dimensions --------------------------------

def dist(p, q):
    return hypot(p[0] - q[0], p[1] - q[1], p[2] - q[2])


def tight(L, W, H, a, b, sweeps=200):
    """For every chain, put one point on each shared edge and slide them one at a time to the
    spot that makes the path shortest (golden-section search: the length is convex in each
    point). Returns (length, chain) for the best chain. No unfolding involved."""
    fs, edges = shared_edges(L, W, H)
    fa = next(i for i, f in enumerate(fs) if on_face(f, a))
    best = None
    for goal in [i for i, f in enumerate(fs) if on_face(f, b)]:
        for chain in chains(fs, edges, fa, goal):
            segs = [edges[i, j] for i, j in zip(chain, chain[1:])]
            mus = [0.5] * len(segs)

            def point(k, mu):
                p, q = segs[k]
                return tuple(p[c] + mu * (q[c] - p[c]) for c in range(3))

            def length():
                pts = [a] + [point(k, m) for k, m in enumerate(mus)] + [b]
                return sum(dist(pts[k], pts[k + 1]) for k in range(len(pts) - 1))
            for _ in range(sweeps if segs else 0):
                for k in range(len(segs)):
                    lo, hi = 0.0, 1.0
                    for _ in range(60):
                        m1, m2 = lo + (hi - lo) * 0.382, lo + (hi - lo) * 0.618
                        mus[k] = m1
                        f1 = length()
                        mus[k] = m2
                        f2 = length()
                        lo, hi = (lo, m2) if f1 < f2 else (m1, hi)
                    mus[k] = (lo + hi) / 2
            total = length()
            if best is None or total < best[0] - 1e-9:
                best = (total, [fs[i][0] for i in chain])
    return best