// WHICH ASSERTION HERE FAILS IF THE ANSWER IS SIMPLY WRONG?
// Assertions 3 and 9 compare the shipped TSPLIB tours with their externally published costs.
// Assertions 5 and 11 fail if the produced lower bound exceeds those published optima. Assertions
// 17 through 26 doctor one value in the visible certificate and require the real shipped checker
// to fail on the line that names the damaged property. Assertion 16 is the plausible wrong-answer
// null control, and assertion 27 is the truncation control.

import assert from 'node:assert/strict';
import { createHash } from 'node:crypto';
import { readFileSync } from 'node:fs';
import vm from 'node:vm';
import {
  bestNearestNeighbour,
  exactGapPercent,
  firstAsymmetry,
  heldKarpExact,
  makeBoundData,
  makeFeasibilityData,
  optimisePotentials,
  parseCoordinates,
  parseMatrix,
  parseTsplib,
  parseTsplibTour,
  rationalText,
  registerCertificates,
  scaleMatrix,
  tourCostInt,
  twoOptLocal,
  minimumOneTree,
} from '../../public/tools/tour-check/engine.mjs';

const kitSource = readFileSync(new URL('../../public/_kit/certificate.js', import.meta.url), 'utf8');
const sandbox = { window: {} };
vm.runInContext(kitSource, vm.createContext(sandbox));
const C = sandbox.window.AW.certificate;
registerCertificates(C);

let passed = 0, failed = 0, number = 0;
function test(name, fn) {
  number++;
  try {
    fn();
    passed++;
    console.log(`${number}. PASS ${name}`);
  } catch (error) {
    failed++;
    console.log(`${number}. FAIL ${name}: ${String(error.message || error).replace(/\s+/g, ' ')}`);
  }
}

const fixtureMeta = {
  fri26: {
    optimum: 937n,
    hash: 'e5e34713f8e7c58f9bef5f330ae0b973ead3d1792b4202c052bad309aa552c5c',
    tourHash: '6edb83a31beacd6c7c190c7f00274879e8cfa9c05ff3d0c8480ddbc020fcd34d',
    spots: [[0, 1, 83n], [0, 25, 181n], [2, 5, 49n], [7, 8, 37n], [10, 14, 32n], [15, 20, 68n], [24, 25, 90n], [3, 23, 278n]],
  },
  gr24: {
    optimum: 1272n,
    hash: '8e2e08d3cd27f9bbb2fffad1373ee1c9056754b33d728e6e8facaa3b452519be',
    tourHash: '52f723f07391b6e8d58125355fcf6b768c5b742ac47abc045a3ff54eeeb147ba',
    spots: [[0, 1, 257n], [0, 23, 121n], [2, 5, 88n], [7, 8, 225n], [10, 14, 259n], [15, 20, 99n], [22, 23, 169n], [3, 21, 221n]],
  },
};

const fixtures = {};
for (const [name, meta] of Object.entries(fixtureMeta)) {
  const problemText = readFileSync(new URL(`./fixtures/${name}.tsp`, import.meta.url), 'utf8');
  const tourText = readFileSync(new URL(`./fixtures/${name}.opt.tour`, import.meta.url), 'utf8');
  const parsed = parseTsplib(problemText);
  const tour = parseTsplibTour(tourText, parsed.dimension);
  const independentCost = tour.reduce((sum, at, i) => sum + parsed.matrix[at][tour[(i + 1) % tour.length]], 0n);
  const witness = optimisePotentials(parsed.matrix, meta.optimum);
  const labels = Array.from({ length: parsed.dimension }, (_, i) => String(i + 1));
  const matrixText = parsed.matrix.map((row) => row.map(String));
  const cert = C.make('tour-bound-v1', makeBoundData(labels, matrixText, tour, independentCost, witness, 1n));
  fixtures[name] = { ...parsed, tour, independentCost, witness, cert, problemText, tourText, meta };
}

for (const name of ['fri26', 'gr24']) {
  const f = fixtures[name];
  test(`${name} shipped files have the recorded SHA-256 hashes`, () => {
    assert.equal(createHash('sha256').update(f.problemText).digest('hex'), f.meta.hash);
    assert.equal(createHash('sha256').update(f.tourText).digest('hex'), f.meta.tourHash);
  });
  test(`${name} parser matches 8 entries read directly from the published lower triangle`, () => {
    for (const [i, j, expected] of f.meta.spots) assert.equal(f.matrix[i][j], expected, `entry ${i},${j}`);
  });
  test(`${name} published optimal tour independently sums to the published optimum`, () => {
    assert.equal(f.independentCost, f.meta.optimum);
  });
  test(`${name} published tour passes the unmodified shipped certificate checker`, () => {
    const result = C.check(C.readback(C.serialise(f.cert)));
    assert.equal(result.ok, true, result.lines.filter((line) => !line.ok).map((line) => line.text).join(', '));
  });
  test(`${name} node-potential 1-tree bound does not exceed the published optimum`, () => {
    assert.ok(f.witness.bound <= f.meta.optimum, `bound ${f.witness.bound} exceeds optimum ${f.meta.optimum}`);
  });
  test(`${name} bound does not exceed any supplied tour cost`, () => {
    const nearest = bestNearestNeighbour(f.matrix);
    assert.ok(f.witness.bound <= f.independentCost);
    assert.ok(f.witness.bound <= nearest.cost);
  });
  // ⚠ THE TWO ASSERTIONS ABOVE ARE ONE-SIDED, AND ON THEIR OWN THEY CANNOT FAIL ON THE
  // DEFECT THIS FILE IS MOST LIKELY TO SHIP. Every bound that is too SMALL is still
  // "valid": a spanning tree used in place of a 1-tree, an ascent that never runs, or a
  // sign error in the subgradient step all produce a bound far below the truth, and all of
  // them satisfy bound <= optimum and bound <= tour cost on every instance. A blinded
  // re-derivation built three such implementations tonight and every one passed both
  // assertions while reporting "at most 51% longer" about a published OPTIMAL tour.
  //
  // So the bound is pinned from BELOW as well. The floor is the published optimum less two,
  // which the honest ascent clears on both fixtures (it lands exactly one short), and which
  // no broken version comes close to. The control underneath proves the floor bites.
  test(`${name} bound is pinned from BELOW as well, so a too-weak bound is red`, () => {
    assert.ok(f.witness.bound >= f.meta.optimum - 2n,
      `bound ${f.witness.bound} is more than two below the published optimum ${f.meta.optimum}; a weak bound is still a valid bound, which is why this assertion exists`);
  });
  test(`${name} control on that floor: a zero-potential 1-tree is far too weak and fails it`, () => {
    const zeros = Array.from({ length: f.dimension }, () => 0n);
    const naive = minimumOneTree(f.matrix, zeros);
    assert.ok(naive.bound <= f.meta.optimum, 'the naive bound is still a VALID bound, which is the whole problem');
    assert.ok(naive.bound < f.meta.optimum - 2n,
      `the ascent-free bound is ${naive.bound} against an optimum of ${f.meta.optimum}, so the floor above is what separates them`);
  });
}

const defaultMatrix = parseMatrix(`0 12 10 19 8 14
12 0 3 7 6 11
10 3 0 6 20 9
19 7 6 0 4 13
8 6 20 4 0 5
14 11 9 13 5 0`);
const defaultScaled = scaleMatrix(defaultMatrix);
const defaultLabels = ['A', 'B', 'C', 'D', 'E', 'F'];
const defaultTour = [0, 1, 2, 3, 4, 5];
const defaultCost = tourCostInt(defaultScaled.matrix, defaultTour);
const defaultNearest = bestNearestNeighbour(defaultScaled.matrix);
const defaultLocal = twoOptLocal(defaultScaled.matrix, defaultNearest.tour);
const defaultWitness = optimisePotentials(defaultScaled.matrix, defaultLocal.cost);
const defaultExact = heldKarpExact(defaultScaled.matrix);
const defaultCert = C.make('tour-bound-v1', makeBoundData(defaultLabels, defaultMatrix, defaultTour, defaultCost, defaultWitness, defaultScaled.scale));
const defaultText = C.serialise(defaultCert);

test('the matrix worked example headlines rederive to tour 44, bound 43, and exact gap 100/43 percent', () => {
  assert.equal(defaultCost, 44n);
  assert.equal(defaultWitness.bound, 43n);
  assert.equal(rationalText(exactGapPercent(defaultCost, defaultWitness.bound).n, exactGapPercent(defaultCost, defaultWitness.bound).d), '100/43');
});
test('the matrix worked example baselines and exhaustive audit rederive independently of display code', () => {
  assert.equal(defaultNearest.cost, 44n);
  assert.equal(defaultNearest.start, 1);
  assert.equal(defaultLocal.cost, 43n);
  assert.equal(defaultLocal.passes, 1);
  assert.equal(defaultExact.cost, 43n);
  assert.equal(defaultExact.states, 80);
});

const coordinateInput = `drill-1 0 0
drill-2 12 1
drill-3 18 9
drill-4 9 15
drill-5 1 11
drill-6 7 7`;
test('the coordinate example rederives its rounded matrix and all numeric result claims', () => {
  const parsed = parseCoordinates(coordinateInput), scaled = scaleMatrix(parsed.matrix), tour = [0, 1, 2, 3, 4, 5];
  const cost = tourCostInt(scaled.matrix, tour), nearest = bestNearestNeighbour(scaled.matrix), local = twoOptLocal(scaled.matrix, nearest.tour);
  const witness = optimisePotentials(scaled.matrix, local.cost), exact = heldKarpExact(scaled.matrix);
  assert.deepEqual(parsed.matrix[0], ['0', '12', '20', '17', '11', '10']);
  assert.equal(cost, 59n); assert.equal(nearest.cost, 59n); assert.equal(local.cost, 59n);
  assert.equal(witness.bound, 58n); assert.equal(exact.cost, 59n);
  assert.equal(rationalText((cost - witness.bound) * 100n, witness.bound), '50/29');
});

test('null control: a plausible but wrong displayed total fails on the named edge-sum line', () => {
  const bad = defaultText.replace('tourCost: 44', 'tourCost: 45');
  const result = C.check(C.readback(bad));
  assert.equal(result.ok, false);
  assert.ok(result.lines.some((line) => !line.ok && line.text === 'the displayed tour cost equals the edge-by-edge sum'));
});

const faults = [
  ['duplicate label', 'labels: A | B | C | D | E | F', 'labels: A | A | C | D | E | F', 'point labels are non-empty and unique'],
  ['nonzero diagonal', 'matrix[0]: 0 12 10 19 8 14', 'matrix[0]: 1 12 10 19 8 14', 'the matrix diagonal is zero'],
  ['negative cost', 'matrix[4]: 8 6 20 4 0 5', 'matrix[4]: 8 6 -20 4 0 5', 'every matrix cost is non-negative'],
  ['one asymmetric entry', 'matrix[0]: 0 12 10 19 8 14', 'matrix[0]: 0 13 10 19 8 14', 'the cost matrix is symmetric'],
  ['duplicate tour point', 'tour: 0 1 2 3 4 5', 'tour: 0 1 2 3 4 4', 'the proposed tour visits every point exactly once'],
  ['wrong tour total', 'tourCost: 44', 'tourCost: 45', 'the displayed tour cost equals the edge-by-edge sum'],
  ['valid but nonminimum tree edge', 'treeEdge[1]: 1 3', 'treeEdge[1]: 1 4', 'the listed non-root tree has minimum transformed cost'],
  ['repeated root edge', 'rootMate: 2 5', 'rootMate: 2 2', 'the 1-tree uses two distinct edges at the root'],
  ['nonminimum root edge', 'rootMate: 2 5', 'rootMate: 1 5', 'the two root edges have the minimum possible transformed sum'],
  ['wrong lower-bound arithmetic', 'bound: 43', 'bound: 42', 'the displayed lower bound equals the 1-tree total minus twice the potentials'],
];

for (const [fault, before, after, namedLine] of faults) test(`fault table: ${fault} breaks “${namedLine}”`, () => {
  assert.equal(defaultText.split(before).length - 1, 1, 'fault target is not unique');
  const doctored = defaultText.replace(before, after);
  const result = C.check(C.readback(doctored));
  assert.equal(result.ok, false);
  assert.ok(result.lines.some((line) => !line.ok && line.text === namedLine), `named line stayed green: ${namedLine}`);
});

test('truncation control: removing the final matrix row is refused by readback', () => {
  const truncated = defaultText.split('\n').filter((line) => !line.startsWith('matrix[5]:')).join('\n');
  assert.throws(() => C.readback(truncated), /shape row says 6/);
});

test('the same unmodified checker still passes the untouched control after every fault', () => {
  assert.equal(C.check(C.readback(defaultText)).ok, true);
});

test('asymmetry is detected without blocking the separate feasibility certificate', () => {
  const matrix = parseMatrix('0 2 3\n4 0 5\n3 5 0'), scaled = scaleMatrix(matrix), labels = ['A', 'B', 'C'], tour = [0, 1, 2];
  assert.deepEqual(firstAsymmetry(scaled.matrix), { i: 0, j: 1, forward: 2n, backward: 4n });
  const cost = tourCostInt(scaled.matrix, tour);
  const cert = C.make('tour-feasibility-v1', makeFeasibilityData(labels, matrix, tour, cost, scaled.scale));
  assert.equal(C.check(cert).ok, true);
});

test('triangle-inequality violations remain accepted by the symmetric checker', () => {
  const matrix = parseMatrix('0 2 9 2\n2 0 2 9\n9 2 0 2\n2 9 2 0'), scaled = scaleMatrix(matrix), tour = [0, 1, 2, 3];
  const cost = tourCostInt(scaled.matrix, tour), witness = optimisePotentials(scaled.matrix, cost);
  const cert = C.make('tour-bound-v1', makeBoundData(['A', 'B', 'C', 'D'], matrix, tour, cost, witness, scaled.scale));
  assert.equal(C.check(cert).ok, true);
});

test('EUC_2D half distances round up using integer comparisons, without floating point', () => {
  const parsed = parseCoordinates('A 0 0\nB 0.5 0\nC 0 2');
  assert.equal(parsed.matrix[0][1], '1');
  assert.equal(parsed.matrix[0][2], '2');
});

test('the documented 200-point bound limit completes with a passing certificate', () => {
  const n = 200;
  const matrix = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => BigInt(Math.min(Math.abs(i - j), n - Math.abs(i - j)))));
  const tour = Array.from({ length: n }, (_, i) => i), cost = tourCostInt(matrix, tour), witness = optimisePotentials(matrix, cost);
  const labels = tour.map((i) => String(i + 1)), textMatrix = matrix.map((row) => row.map(String));
  const cert = C.make('tour-bound-v1', makeBoundData(labels, textMatrix, tour, cost, witness, 1n));
  assert.equal(cost, 200n);
  assert.equal(C.check(cert).ok, true);
});

test('exact DP and every 1-tree bound agree with independent brute force on 40 seeded small matrices', () => {
  let seed = 0x51f15e;
  const random = () => { seed = (1664525 * seed + 1013904223) >>> 0; return seed; };
  function brute(matrix) {
    const rest = Array.from({ length: matrix.length - 1 }, (_, i) => i + 1);
    let best = null;
    function visit(at) {
      if (at === rest.length) {
        const cost = tourCostInt(matrix, [0, ...rest]);
        if (best === null || cost < best) best = cost;
        return;
      }
      for (let i = at; i < rest.length; i++) {
        [rest[at], rest[i]] = [rest[i], rest[at]];
        visit(at + 1);
        [rest[at], rest[i]] = [rest[i], rest[at]];
      }
    }
    visit(0);
    return best;
  }
  for (let caseNo = 0; caseNo < 40; caseNo++) {
    const n = 3 + random() % 6;
    const matrix = Array.from({ length: n }, () => Array(n).fill(0n));
    for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) matrix[i][j] = matrix[j][i] = 1n + BigInt(random() % 50);
    const optimum = brute(matrix), exact = heldKarpExact(matrix), witness = optimisePotentials(matrix, optimum);
    assert.equal(exact.cost, optimum, `exact mismatch on seeded case ${caseNo}`);
    assert.ok(witness.bound <= optimum, `bound exceeded optimum on seeded case ${caseNo}`);
  }
});

console.log(`\n${passed} passed, ${failed} failed`);
process.exitCode = failed ? 1 : 0;
