initial_program.py

from typing import List, Tuple, Optional
import math, itertools

Coord = Tuple[float, float]

def _dist(a: Coord, b: Coord) -> float:
    return math.hypot(a[0] - b[0], a[1] - b[1])

def _tour_len(coords: List[Coord], tour: List[int]) -> float:
    s = 0.0; n = len(tour)
    for i in range(n):
        a, b = tour[i], tour[(i+1)%n]
        s += _dist(coords[a], coords[b])
    return s

# --- fallback exact (HK) на случай, если n неожиданно больше ---
def _held_karp_exact(coords: List[Coord]) -> List[int]:
    n = len(coords)
    if n <= 1: return list(range(n))
    D = [[0.0]*n for _ in range(n)]
    for i in range(n):
        xi, yi = coords[i]
        for j in range(i+1, n):
            d = math.hypot(xi - coords[j][0], yi - coords[j][1])
            D[i][j] = D[j][i] = d
    FULL = (1 << n) - 1
    INF = float("inf")
    dp = [[INF]*n for _ in range(1 << n)]
    parent = [[-1]*n for _ in range(1 << n)]
    dp[1][0] = 0.0
    for mask in range(1 << n):
        if (mask & 1) == 0: continue
        for j in range(n):
            if (mask >> j) & 1 == 0: continue
            cj = dp[mask][j]
            if cj == INF: continue
            rem = (~mask) & FULL
            m = rem
            while m:
                k = (m & -m).bit_length() - 1
                m ^= (1 << k)
                nm = mask | (1 << k)
                val = cj + D[j][k]
                if val < dp[nm][k]:
                    dp[nm][k] = val
                    parent[nm][k] = j
    best_end, best = -1, INF
    for j in range(1, n):
        c = dp[FULL][j] + D[j][0]
        if c < best:
            best, best_end = c, j
    # reconstruct
    tour = [0]*n
    mask = FULL; j = best_end
    for t in range(n-1, 0, -1):
        tour[t] = j
        pj = parent[mask][j]; mask ^= (1 << j); j = pj
    tour[0] = 0
    return tour

def solve_tsp(coords: List[Coord]) -> List[int]:
    n = len(coords)
    if n <= 1: return list(range(n))
    if n > 9:
        # Защита: если эвалюатор расширят диапазон, не зависаем.
        return _held_karp_exact(coords)

    # Наивный перебор: фиксируем старт = 0, перебираем перестановки остальных
    best_len = float("inf")
    best_tour: List[int] = []
    cities = list(range(n))
    for perm in itertools.permutations(cities[1:], n-1):
        tour = [0] + list(perm)
        L = _tour_len(coords, tour)
        if L < best_len:
            best_len = L
            best_tour = tour
    return best_tour

# опционально:
def run_program(params: Optional[dict] = None) -> dict:
    import random, time
    params = params or {}
    n = int(params.get("n", 9))
    seed = int(params.get("seed", 42))
    rng = random.Random(seed)
    coords = [(rng.random(), rng.random()) for _ in range(n)]
    t0 = time.time(); tour = solve_tsp(coords); dt = time.time() - t0
    return {"tour": tour, "tour_length": _tour_len(coords, tour), "runtime": dt}

if __name__ == "__main__":
    print(run_program())