Greedy edge construction with 2-opt

// Candidate: greedy edge construction (shortest edges first, degree <= 2, no premature
// cycles, closed at the end) followed by first-improvement 2-opt. Deterministic: ties in
// edge length break by edge index.
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);
  };

  const tour = greedyEdgeTour(xs, ys, n, d);
  twoOpt(tour, d);
  return tour;
}

function greedyEdgeTour(xs, ys, n, d) {
  if (n < 3) return Array.from({ length: n }, (_, i) => i);
  const m = (n * (n - 1)) / 2;
  const eu = new Int32Array(m);
  const ev = new Int32Array(m);
  const len = new Float64Array(m);
  let t = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      eu[t] = i;
      ev[t] = j;
      len[t] = d(i, j);
      t++;
    }
  }
  const order = new Array(m);
  for (let i = 0; i < m; i++) order[i] = i;
  order.sort((a, b) => len[a] - len[b] || a - b);

  const parent = new Int32Array(n);
  for (let i = 0; i < n; i++) parent[i] = i;
  const find = (x) => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  };
  const degree = new Uint8Array(n);
  const adjacentA = new Int32Array(n).fill(-1);
  const adjacentB = new Int32Array(n).fill(-1);
  const link = (u, v) => {
    if (adjacentA[u] === -1) adjacentA[u] = v;
    else adjacentB[u] = v;
    if (adjacentA[v] === -1) adjacentA[v] = u;
    else adjacentB[v] = u;
    degree[u]++;
    degree[v]++;
  };
  let added = 0;
  for (let k = 0; k < m && added < n - 1; k++) {
    const e = order[k];
    const u = eu[e];
    const v = ev[e];
    if (degree[u] >= 2 || degree[v] >= 2) continue;
    const ru = find(u);
    const rv = find(v);
    if (ru === rv) continue;
    parent[ru] = rv;
    link(u, v);
    added++;
  }
  // Close the Hamiltonian path: exactly two vertices have degree 1.
  const ends = [];
  for (let i = 0; i < n; i++) if (degree[i] === 1) ends.push(i);
  if (ends.length === 2) link(ends[0], ends[1]);

  // Walk the cycle.
  const tour = new Array(n);
  let previous = -1;
  let current = 0;
  for (let k = 0; k < n; k++) {
    tour[k] = current;
    const next = adjacentA[current] !== previous ? adjacentA[current] : adjacentB[current];
    previous = current;
    current = next;
  }
  return tour;
}

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;
  }
}