Neighbor-list 2-opt with don't-look bits

// Candidate: nearest-neighbor construction followed by 2-opt restricted to the 8 nearest
// neighbours of each vertex, with don't-look bits (Johnson & McGeoch). Trades a little
// search breadth for far fewer move evaluations. Deterministic.
const K = 8;

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 = nearestNeighbor(xs, ys, n);
  const neighbors = neighborLists(n, d, Math.min(K, n - 1));
  neighborListTwoOpt(tour, d, neighbors);
  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;
}

// k nearest neighbours per vertex, sorted by distance (ties by index).
function neighborLists(n, d, k) {
  const lists = new Array(n);
  const candidates = new Array(n - 1);
  for (let i = 0; i < n; i++) {
    let t = 0;
    for (let j = 0; j < n; j++) if (j !== i) candidates[t++] = j;
    const distances = new Float64Array(n);
    for (let j = 0; j < n; j++) distances[j] = d(i, j);
    candidates.sort((a, b) => distances[a] - distances[b] || a - b);
    lists[i] = Int32Array.from(candidates.slice(0, k));
  }
  return lists;
}

function neighborListTwoOpt(tour, d, neighbors) {
  const n = tour.length;
  const pos = new Int32Array(n);
  for (let i = 0; i < n; i++) pos[tour[i]] = i;
  const next = (c) => tour[(pos[c] + 1) % n];
  const prev = (c) => tour[(pos[c] - 1 + n) % n];

  // Reverse the path from position i forward to position j (inclusive, wrapping), by
  // reversing whichever of the path or its complement is shorter; both give the same cycle.
  const reversePath = (i, j) => {
    let length = ((j - i + n) % n) + 1;
    if (length * 2 > n) {
      const ni = (j + 1) % n;
      const nj = (i - 1 + n) % n;
      i = ni;
      j = nj;
      length = n - length;
    }
    for (let s = 0; s < length >> 1; s++) {
      const a = (i + s) % n;
      const b = (j - s + n) % n;
      const tmp = tour[a];
      tour[a] = tour[b];
      tour[b] = tmp;
      pos[tour[a]] = a;
      pos[tour[b]] = b;
    }
  };

  const queue = new Int32Array(n * 4);
  let head = 0;
  let tail = 0;
  const queued = new Uint8Array(n);
  const push = (c) => {
    if (queued[c]) return;
    queued[c] = 1;
    queue[tail] = c;
    tail = (tail + 1) % queue.length;
  };
  for (let i = 0; i < n; i++) push(tour[i]);

  let budget = 50_000_000;
  while (head !== tail && budget-- > 0) {
    const a = queue[head];
    head = (head + 1) % queue.length;
    queued[a] = 0;
    let improved = true;
    while (improved) {
      improved = false;
      // Successor direction: edges (a,b) and (c,dd) become (a,c) and (b,dd).
      {
        const b = next(a);
        const dab = d(a, b);
        const list = neighbors[a];
        for (let t = 0; t < list.length; t++) {
          const c = list[t];
          const dac = d(a, c);
          if (dac >= dab) break;
          const dd = next(c);
          if (c === b || dd === a) continue;
          const delta = dac + d(b, dd) - dab - d(c, dd);
          if (delta < -1e-9) {
            reversePath(pos[b], pos[c]);
            push(a);
            push(b);
            push(c);
            push(dd);
            improved = true;
            break;
          }
        }
      }
      if (improved) continue;
      // Predecessor direction: edges (b,a) and (dd,c) become (c,a) and (dd,b).
      {
        const b = prev(a);
        const dab = d(a, b);
        const list = neighbors[a];
        for (let t = 0; t < list.length; t++) {
          const c = list[t];
          const dac = d(a, c);
          if (dac >= dab) break;
          const dd = prev(c);
          if (c === b || dd === a) continue;
          const delta = dac + d(b, dd) - dab - d(c, dd);
          if (delta < -1e-9) {
            reversePath(pos[c], pos[b]);
            push(a);
            push(b);
            push(c);
            push(dd);
            improved = true;
            break;
          }
        }
      }
    }
  }
}