{"challengeId":"snake-in-the-box-13","entry":"verifier.mjs","sha256":"b6fc2174d4a26ce005cd43aa448a4e2262ad155ba30382bc8092c2c37886cfad","scoreDirection":"maximize","scoreLabel":"edges","seedPolicy":{"mode":"fixed","testCount":1},"source":"// Frozen verifier for snake-in-the-box-13. Self-contained (no imports): it reads\n// the candidate's path artifact and returns a Verdict. It never executes agent\n// code — build() already ran in the sandbox and handed us plain data. This file is\n// part of the challenge's PROTECTED surface.\n//\n// THE INSTANCE is the 13-dimensional hypercube graph Q13: its 2^13 = 8192 vertices\n// are the integers 0..8191, and two vertices are adjacent iff they differ in\n// exactly one bit (popcount(a XOR b) == 1). The whole graph is defined by that\n// rule — there is no external data file and nothing to overfit.\n//\n// A SNAKE-IN-THE-BOX is an INDUCED PATH in Q13: a sequence of distinct vertices\n// where\n//   (1) consecutive vertices differ in exactly one bit (a real cube edge), and\n//   (2) NO two non-consecutive path vertices are adjacent in the cube (no chord).\n// Condition (2) is what makes it \"induced\" — the path, taken as a subgraph, has\n// exactly its path edges and no others. Score = number of edges = path length - 1.\n//\n// The chord check is done in O(13 * L) by looking up each of a vertex's 13\n// neighbors in a vertex->position map: every neighbor that is on the path must be\n// the immediate predecessor or successor. Pure integer / bitwise arithmetic —\n// deterministic across runtimes, so seedPolicy.mode is \"fixed\".\n\nconst D = 13;\nconst N = 1 << D; // 8192 vertices, ids 0..8191\nconst MAX_LEN = 3000; // bound L so the O(13*L) check stays far under timeoutMs\n\nfunction gate(name, pass, detail) {\n  return { name, pass, detail };\n}\nfunction bad(name, detail) {\n  return { ok: false, score: null, gates: [gate(name, false, detail)], behavior: {}, logs: [] };\n}\n\n// popcount of a 13-bit integer via repeated lowest-bit clear (Kernighan).\nfunction popcount(x) {\n  let c = 0;\n  while (x) {\n    x &= x - 1;\n    c++;\n  }\n  return c;\n}\n\nexport function verify(ctx) {\n  const sol = ctx && ctx.solution;\n  if (!sol || typeof sol !== 'object' || !Array.isArray(sol.path)) {\n    return bad('structure', 'expected { path: [v0, v1, ...] } of hypercube vertex ids');\n  }\n  const path = sol.path;\n  const L = path.length;\n  if (L < 1) {\n    return bad('structure', 'path must contain at least one vertex');\n  }\n  if (L > MAX_LEN) {\n    return bad('structure', `path length ${L} exceeds the bound ${MAX_LEN}`);\n  }\n\n  // Every entry must be an integer vertex id in range, and all distinct.\n  const pos = new Map();\n  for (let i = 0; i < L; i++) {\n    const v = path[i];\n    if (!Number.isInteger(v) || v < 0 || v >= N) {\n      return bad('structure', `vertex at index ${i} must be an integer in 0..${N - 1}; got ${String(v)}`);\n    }\n    if (pos.has(v)) {\n      return bad('distinct', `vertex ${v} repeats (indices ${pos.get(v)} and ${i})`);\n    }\n    pos.set(v, i);\n  }\n\n  // (1) Each consecutive pair must differ in exactly one bit (a real cube edge).\n  for (let i = 0; i + 1 < L; i++) {\n    const d = popcount(path[i] ^ path[i + 1]);\n    if (d !== 1) {\n      return bad('unit-step', `step ${i}->${i + 1} changes ${d} bits, not exactly 1`);\n    }\n  }\n\n  // (2) Induced (no chord): for every vertex, each of its 13 cube neighbors that\n  // also lies on the path must be the immediate predecessor or successor. Any other\n  // on-path neighbor is a chord and disqualifies the snake.\n  for (let i = 0; i < L; i++) {\n    const v = path[i];\n    for (let b = 0; b < D; b++) {\n      const w = v ^ (1 << b);\n      const j = pos.get(w);\n      if (j === undefined) continue;\n      if (j !== i - 1 && j !== i + 1) {\n        return bad('induced', `chord: path vertices ${v} (index ${i}) and ${w} (index ${j}) are cube-adjacent but not consecutive`);\n      }\n    }\n  }\n\n  const edges = L - 1;\n  const gates = [\n    gate('valid-snake', true, `induced path of ${L} distinct vertices, ${edges} edges, no chords`),\n  ];\n  return {\n    ok: true,\n    score: edges,\n    gates,\n    behavior: { edges, vertices: L },\n    logs: [`edges=${edges} vertices=${L}`],\n  };\n}\n"}