{"challengeId":"ramsey-r55-color","entry":"verifier.mjs","sha256":"5beb2d28a310d197be6d41f3c4ffed75e8d2df7fd90e15b862e02be431ed8c6c","scoreDirection":"maximize","scoreLabel":"vertices","seedPolicy":{"mode":"fixed","testCount":1},"source":"// Frozen verifier for ramsey-r55-color. Self-contained (no imports, no external\n// data). The \"instance\" here is not a fixed graph but a RULE: the solver supplies\n// an N-vertex 2-coloring of the complete graph K_N (each of the C(N,2) edges is\n// colored 0 or 1), and the verifier asserts the coloring contains NO monochromatic\n// K5 — no 5 vertices whose 10 induced edges are all color-0 or all color-1.\n//\n// This is the Ramsey-number frontier R(5,5): a K5-free 2-coloring exists at N\n// exactly when N < R(5,5). R(5,5) is known only to lie in 43..46 (Exoo 1989 gave\n// a coloring at N=42; the exact value has been open for ~36 years). Score = N,\n// the number of vertices. MAXIMIZE.\n//\n// Pure integer / bitwise arithmetic only — deterministic; seedPolicy \"fixed\".\n// Bounded N<=60 so the worst case C(60,5) ~ 5.46M five-subsets stays well under\n// the timeout.\n\nconst MAX_N = 60;\nconst MIN_N = 1;\n\nfunction gate(name, pass, detail) { return { name, pass, detail }; }\nfunction bad(name, detail) { return { ok: false, score: null, gates: [gate(name, false, detail)], behavior: {}, logs: [] }; }\n\n// Build a symmetric N x N color matrix (flat Int8Array, color[i*N+j]) from the\n// artifact. Accepts either { n, edges:\"<bitstring>\" } where the bitstring lists\n// the upper triangle in row-major order (pairs (0,1),(0,2),...,(0,N-1),(1,2),...)\n// or { n, edges:[int,...] } an adjacency-style int array of the same triangle.\nfunction buildMatrix(n, edges) {\n  const need = (n * (n - 1)) / 2;\n  let triangle;\n  if (typeof edges === 'string') {\n    if (edges.length !== need) return { err: `edges bitstring length ${edges.length}, expected C(${n},2)=${need}` };\n    triangle = new Int8Array(need);\n    for (let k = 0; k < need; k++) {\n      const ch = edges.charCodeAt(k);\n      if (ch === 48) triangle[k] = 0;        // '0'\n      else if (ch === 49) triangle[k] = 1;   // '1'\n      else return { err: `edges[${k}] must be '0' or '1', got ${JSON.stringify(edges[k])}` };\n    }\n  } else if (Array.isArray(edges)) {\n    if (edges.length !== need) return { err: `edges array length ${edges.length}, expected C(${n},2)=${need}` };\n    triangle = new Int8Array(need);\n    for (let k = 0; k < need; k++) {\n      const v = edges[k];\n      if (v !== 0 && v !== 1) return { err: `edges[${k}] must be 0 or 1, got ${String(v)}` };\n      triangle[k] = v;\n    }\n  } else {\n    return { err: 'edges must be a bitstring or an int[] of the upper triangle' };\n  }\n  const color = new Int8Array(n * n);\n  let k = 0;\n  for (let i = 0; i < n; i++) {\n    for (let j = i + 1; j < n; j++) {\n      const c = triangle[k++];\n      color[i * n + j] = c;\n      color[j * n + i] = c;\n    }\n  }\n  return { color };\n}\n\n// Return true if vertices i<j<k<l<m form a monochromatic K5 under `color`.\nfunction isMono(color, n, a, b, c, d, e) {\n  const c0 = color[a * n + b];\n  // all 10 edges must equal c0\n  return (\n    color[a * n + c] === c0 && color[a * n + d] === c0 && color[a * n + e] === c0 &&\n    color[b * n + c] === c0 && color[b * n + d] === c0 && color[b * n + e] === c0 &&\n    color[c * n + d] === c0 && color[c * n + e] === c0 &&\n    color[d * n + e] === c0\n  );\n}\n\nexport function verify(ctx) {\n  const sol = ctx && ctx.solution;\n  if (!sol || typeof sol !== 'object' || Array.isArray(sol)) {\n    return bad('structure', 'expected { n: <int>, edges: <bitstring|int[]> }');\n  }\n  const n = sol.n;\n  if (typeof n !== 'number' || !Number.isInteger(n)) {\n    return bad('structure', `n must be an integer, got ${String(n)}`);\n  }\n  if (n < MIN_N || n > MAX_N) {\n    return bad('bounds', `n must be in [${MIN_N}, ${MAX_N}]; got ${n}`);\n  }\n  if (sol.edges === undefined || sol.edges === null) {\n    return bad('structure', 'missing edges (bitstring or int[] of the upper triangle)');\n  }\n  const built = buildMatrix(n, sol.edges);\n  if (built.err) return bad('structure', built.err);\n  const color = built.color;\n\n  // Scan every 5-subset for a monochromatic K5. C(n,5) with n<=60 is bounded.\n  for (let a = 0; a < n; a++) {\n    for (let b = a + 1; b < n; b++) {\n      for (let c = b + 1; c < n; c++) {\n        for (let d = c + 1; d < n; d++) {\n          for (let e = d + 1; e < n; e++) {\n            if (isMono(color, n, a, b, c, d, e)) {\n              const col = color[a * n + b];\n              return {\n                ok: false,\n                score: null,\n                gates: [gate('k5-free', false, `monochromatic K5 (color ${col}) on vertices {${a},${b},${c},${d},${e}}`)],\n                behavior: {},\n                logs: [`mono K5 found at {${a},${b},${c},${d},${e}}`],\n              };\n            }\n          }\n        }\n      }\n    }\n  }\n\n  return {\n    ok: true,\n    score: n,\n    gates: [gate('k5-free', true, `valid K5-free 2-coloring on ${n} vertices (${(n * (n - 1)) / 2} edges checked, no monochromatic K5)`)],\n    behavior: { vertices: n },\n    logs: [`K5-free 2-coloring on n=${n} vertices`],\n  };\n}\n"}