Iterated local search with double-bridge kicks

// Candidate: iterated local search on top of 05. Greedy edge construction, then a local
// search made of neighbour-list 2-opt (don't-look bits) and Or-opt; afterwards a fixed
// number of double-bridge kicks drawn from the harness-provided seeded generator
// (ctx.random), each followed by the same local search, keeping the best tour. The
// generator is seeded per instance by the harness, so replications reproduce exactly.
const K = 8;
/** Kicks per instance, scaled by size so the largest instances stay well inside the 3 s limit. */
const kicksFor = (n) => (n <= 100 ? 60 : n <= 200 ? 30 : 15);

export function solve(instance, ctx) {
  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 random = ctx && typeof ctx.random === "function" ? ctx.random : mulberry32(0x9e3779b9);

  const neighbors = neighborLists(n, d, Math.min(K, n - 1));
  const localSearch = (tour) => {
    for (let round = 0; round < 20; round++) {
      const before = tourLength(tour, d);
      neighborListTwoOpt(tour, d, neighbors);
      tour = orOpt(tour, d);
      if (tourLength(tour, d) > before - 1e-9) break;
    }
    return tour;
  };

  let best = localSearch(greedyEdgeTour(n, d));
  let bestLength = tourLength(best, d);
  if (n < 8) return best;
  const kicks = kicksFor(n);
  for (let kick = 0; kick < kicks; kick++) {
    const candidate = localSearch(doubleBridge(best, random));
    const length = tourLength(candidate, d);
    if (length < bestLength - 1e-9) {
      best = candidate;
      bestLength = length;
    }
  }
  return best;
}

// Double bridge: A B C D -> A C B D with three random cut points.
function doubleBridge(tour, random) {
  const n = tour.length;
  const cuts = [1 + Math.floor(random() * (n - 1)), 1 + Math.floor(random() * (n - 1)), 1 + Math.floor(random() * (n - 1))].sort((a, b) => a - b);
  const [p1, p2, p3] = cuts;
  return tour.slice(0, p1).concat(tour.slice(p2, p3), tour.slice(p1, p2), tour.slice(p3));
}

function mulberry32(seed) {
  let state = seed >>> 0;
  return () => {
    state = (state + 0x6d2b79f5) >>> 0;
    let z = state;
    z = Math.imul(z ^ (z >>> 15), z | 1) >>> 0;
    z ^= z + Math.imul(z ^ (z >>> 7), z | 61);
    return ((z ^ (z >>> 14)) >>> 0) / 4294967296;
  };
}

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 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 greedyEdgeTour(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++;
  }
  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]);
  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 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];
  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;
      {
        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;
      {
        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;
          }
        }
      }
    }
  }
}

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++) {
          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;
}