init.py

"""
Initial TSP solver for OpenEvolve.

REQUIRED: solve_tsp(coords: List[Tuple[float, float]]) -> List[int]
Heuristic: Nearest Neighbor + 2-opt with restarts and a time limit.
- Использует евклид для построения/улучшения; эвалюатор считает истинную длину (включая GEO/ATT/матрицы).
- Возвращает перестановку 0..n-1. Защитный постпроцесс делает результат валидным даже при мутациях.
"""

from typing import List, Tuple
import math
import random
import time

Coord = Tuple[float, float]

# -------------------- distances --------------------

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

# -------------------- construction --------------------

def _nearest_neighbor_tour(coords: List[Coord], start: int = 0) -> List[int]:
    n = len(coords)
    if n <= 1:
        return list(range(n))
    unvisited = set(range(n))
    unvisited.remove(start)
    tour = [start]
    cur = start
    while unvisited:
        nxt = min(unvisited, key=lambda j: _dist_xy(coords[cur], coords[j]))
        tour.append(nxt)
        unvisited.remove(nxt)
        cur = nxt
    return tour

# -------------------- 2-opt with delta --------------------

def _two_opt_improve(coords: List[Coord],
                     tour: List[int],
                     time_limit: float,
                     start_time: float,
                     max_iterations: int = 2000) -> List[int]:
    """Standard 2-opt with O(1) delta; circular tour; безопасные индексы."""
    n = len(tour)
    if n <= 3:
        return tour[:]

    def edge_len(i: int, j: int) -> float:
        return _dist_xy(coords[tour[i]], coords[tour[j]])

    improved = True
    it = 0
    best = tour[:]

    while improved and it < max_iterations:
        improved = False
        for i in range(0, n - 1):
            if time.time() - start_time >= time_limit:
                return best
            i_next = (i + 1) % n
            # избегаем ребра (0, n-1), чтобы не разрывать одну и ту же грань
            for j in range(i + 2, n if i > 0 else n - 1):
                j_next = (j + 1) % n
                old = edge_len(i, i_next) + edge_len(j, j_next)
                new = edge_len(i, j) + edge_len(i_next, j_next)
                if new + 1e-12 < old:
                    best[i_next:j + 1] = reversed(best[i_next:j + 1])
                    improved = True
                    break
            if improved:
                break
        it += 1
    return best

# -------------------- helpers --------------------

def _avg_dist_per_city(coords: List[Coord]) -> List[float]:
    n = len(coords)
    if n <= 1:
        return [0.0] * n
    av = []
    for i in range(n):
        ci = coords[i]
        s = 0.0
        for j in range(n):
            if i == j:
                continue
            s += _dist_xy(ci, coords[j])
        av.append(s / (n - 1))
    return av

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

def _to_permutation(tour_like, n: int) -> List[int]:
    """Defensive: привести к перестановке 0..n-1."""
    try:
        lst = list(tour_like)
    except Exception:
        return list(range(n))
    lst = [int(x) for x in lst if isinstance(x, int) and 0 <= x < n]
    seen = set()
    out = []
    for v in lst:
        if v not in seen:
            seen.add(v)
            out.append(v)
    for v in range(n):
        if v not in seen:
            out.append(v)
    return out[:n]

# -------------------- REQUIRED entrypoint --------------------

def solve_tsp(coords: List[Coord]) -> List[int]:
    """
    Возвращает перестановку 0..n-1 (Гамильт. тур).
    Стратегия: NN + 2-opt, рестарты, лимит времени.
    """
    n = len(coords)
    if n <= 1:
        return list(range(n))

    params = {
        "restarts": 10,
        "time_limit": 10.0,     # seconds
        "random_seed": 42,
        "max_iterations": 5000, # upper bound for improvement
    }

    random.seed(params["random_seed"])
    start_time = time.time()
    time_limit = params["time_limit"]

    # 1) базовый тур
    best = _nearest_neighbor_tour(coords, start=0)
    best = _two_opt_improve(coords, best, time_limit, start_time, max_iterations=params["max_iterations"])
    best_len = _tour_len(coords, best)

    # 2) рестарты: приоритет более «центральным» вершинам (низкая средняя дистанция)
    av = _avg_dist_per_city(coords)
    num_priority = max(1, int(params["restarts"] * 0.3))
    priority_starts = sorted(range(n), key=lambda i: av[i])[:num_priority]
    random_starts = [random.randrange(n) for _ in range(max(0, params["restarts"] - num_priority))]
    starts = priority_starts + random_starts

    for s in starts:
        if time.time() - start_time >= time_limit:
            break
        t = _nearest_neighbor_tour(coords, start=s)
        t = _two_opt_improve(coords, t, time_limit, start_time, max_iterations=params["max_iterations"])
        l = _tour_len(coords, t)
        if l + 1e-12 < best_len:
            best, best_len = t, l

    # 3) гарантированно валидная перестановка
    return _to_permutation(best, n)