Or-opt segment moves after 2-opt

// Candidate: nearest-neighbor construction, then 2-opt and Or-opt alternated until
// neither finds an improving move. Or-opt relocates segments of one to three consecutive
// vertices to the best position, in either orientation. Deterministic.
export function solve(instance) {
  const points = instance.points;
  const n = points.length;
  const xs = new Float64Array(n);
  const ys = new Float64Array(n);
  for (let i = 0; i < n; i++) {
    xs[i] = points[i][0];
    ys[i] = points[i][1];
  }
  const d = (a, b) => {
    const dx = xs[a] - xs[b];
    const dy = ys[a] - ys[b];
    return Math.sqrt(dx * dx + dy * dy);
  };

  let tour = nearestNeighbor(xs, ys, n);
  for (let round = 0; round < 40; round++) {
    const before = tourLength(tour, d);
    twoOpt(tour, d);
    tour = orOpt(tour, d);
    if (tourLength(tour, d) > before - 1e-9) break;
  }
  return tour;
}

function nearestNeighbor(xs, ys, n) {
  const visited = new Uint8Array(n);
  const tour = new Array(n);
  tour[0] = 0;
  visited[0] = 1;
  let current = 0;
  for (let k = 1; k < n; k++) {
    let best = -1;
    let bestDistance = Infinity;
    for (let j = 0; j < n; j++) {
      if (visited[j]) continue;
      const dx = xs[current] - xs[j];
      const dy = ys[current] - ys[j];
      const distance = dx * dx + dy * dy;
      if (distance < bestDistance) {
        bestDistance = distance;
        best = j;
      }
    }
    visited[best] = 1;
    tour[k] = best;
    current = best;
  }
  return tour;
}

function tourLength(tour, d) {
  let total = 0;
  for (let i = 0; i < tour.length; i++) total += d(tour[i], tour[(i + 1) % tour.length]);
  return total;
}

function twoOpt(tour, d) {
  const n = tour.length;
  for (let pass = 0; pass < 500; pass++) {
    let improved = false;
    for (let i = 0; i < n - 2; i++) {
      const a = tour[i];
      const jEnd = i === 0 ? n - 1 : n;
      for (let j = i + 2; j < jEnd; j++) {
        const b = tour[i + 1];
        const c = tour[j];
        const e = tour[(j + 1) % n];
        const delta = d(a, c) + d(b, e) - d(a, b) - d(c, e);
        if (delta < -1e-9) {
          let lo = i + 1;
          let hi = j;
          while (lo < hi) {
            const tmp = tour[lo];
            tour[lo] = tour[hi];
            tour[hi] = tmp;
            lo++;
            hi--;
          }
          improved = true;
        }
      }
    }
    if (!improved) break;
  }
}

// Or-opt: for each segment of length 1..3, find the best insertion edge outside the segment.
function orOpt(tour, d) {
  const n = tour.length;
  if (n < 8) return tour;
  for (let pass = 0; pass < 100; pass++) {
    let improved = false;
    for (let len = 1; len <= 3; len++) {
      for (let i = 0; i + len <= n; i++) {
        const prev = tour[(i - 1 + n) % n];
        const first = tour[i];
        const last = tour[i + len - 1];
        const next = tour[(i + len) % n];
        const removeGain = d(prev, first) + d(last, next) - d(prev, next);
        if (removeGain <= 1e-9) continue;
        let best = 1e-9;
        let bestK = -1;
        let bestReversed = false;
        for (let k = 0; k < n; k++) {
          // Skip the edges touching or inside the segment: (prev,first) ... (last,next).
          if ((((k - (i - 1)) % n) + n) % n <= len) continue;
          const u = tour[k];
          const v = tour[(k + 1) % n];
          const base = d(u, v);
          const gainForward = removeGain - (d(u, first) + d(last, v) - base);
          if (gainForward > best) {
            best = gainForward;
            bestK = k;
            bestReversed = false;
          }
          const gainReversed = removeGain - (d(u, last) + d(first, v) - base);
          if (gainReversed > best) {
            best = gainReversed;
            bestK = k;
            bestReversed = true;
          }
        }
        if (bestK >= 0) {
          const segment = tour.slice(i, i + len);
          if (bestReversed) segment.reverse();
          const anchor = tour[bestK];
          const rest = tour.slice(0, i).concat(tour.slice(i + len));
          const at = rest.indexOf(anchor);
          tour = rest.slice(0, at + 1).concat(segment, rest.slice(at + 1));
          improved = true;
        }
      }
    }
    if (!improved) break;
  }
  return tour;
}