// Exact minimum-size covering designs invariant under a cyclic group action.
//   --group=cyclic: Z_v acts regularly by translation mod v
//   --group=rot1:   Z_{v-1} cycles points 0..v-2, point v-1 fixed (1-rotational)
// C_G(v,k,t) = min block count over G-invariant coverings, exact via B&B.
//
// Usage: node cyclic_exact.mjs v k t [maxSeconds] [resFile] [--group=cyclic|rot1]
import { schoenheim } from "./lib.mjs";

const argvRaw = process.argv.slice(2);
const positionalRaw = argvRaw.filter(a => !/^--/.test(a));
const positional = positionalRaw.map(Number);
const [v, k, t] = positional.slice(0, 3);
const maxSeconds = Number(positional[3] || 600);
const resFile = /^\.\.?|^[/\\]|[A-Za-z]:/.test(positionalRaw[4] || "") ? positionalRaw[4] : undefined;
const groupArg = argvRaw.find(a => /^--group=/.test(a)) || "--group=cyclic";
const GROUP = groupArg.split("=")[1];
const L = schoenheim(v, k, t);

// Group rotation: apply the generator r times (r in 0..CYC_LEN-1)
const CYC_LEN = GROUP === "rot1" ? v - 1 : v;
console.log(`C_G(${v},${k},${t}) group=${GROUP} cycle=${CYC_LEN}: Schoenheim L=${L}`);

const FULLMASK = (1n << BigInt(v)) - 1n;
function genStep(m) {
  if (GROUP === "rot1") {
    const hiBit = m & (1n << BigInt(v - 1));
    const lowMask = FULLMASK ^ (1n << BigInt(v - 1));
    const low = m & lowMask;
    // rotate low CYC_LEN bits left by 1: bit i -> bit i+1 mod CYC_LEN
    const top = (low >> BigInt(CYC_LEN - 1)) & 1n;          // bit CYC_LEN-1 wraps to 0
    const moved = ((low << 1n) & lowMask) | top;
    return hiBit | moved;
  }
  return ((m << 1n) & FULLMASK) | (m >> BigInt(v - 1));
}
function pow(m, r) {
  let out = m;
  for (let i = 0; i < r; i++) out = genStep(out);
  return out;
}

function popcountBig(x) { let c = 0; while (x) { c += Number(x & 1n); x >>= 1n; } return c; }

// ---- enumerate k-subsets and group into rotation orbits ----
const kSubsets = [];
for (let m = 0n; m < (1n << BigInt(v)); m++) {
  if (popcountBig(m) === k) kSubsets.push(m);
}
console.log(`k-subsets: ${kSubsets.length} (C(${v},${k})=${kSubsets.length ? kSubsets.length : ""})`);

const seen = new Set();
const orbits = [];
for (const m of kSubsets) {
  if (seen.has(m)) continue;
  const fam = [];
  for (let r = 0; r < CYC_LEN; r++) {
    const cur = pow(m, r);
    if (!fam.includes(cur)) fam.push(cur);
  }
  for (const f of fam) seen.add(f);
  orbits.push({ size: fam.length, blocks: [...fam].sort((a, b) => (a < b ? -1 : 1)), cov: 0n, pc: 0 });
}
const totBlocks = orbits.reduce((a, o) => a + o.size, 0);
console.log(`orbits: ${orbits.length}, distinct blocks covered: ${totBlocks}`);
if (totBlocks !== kSubsets.length) { console.error("ORBIT ENUMERATION BROKEN"); process.exit(1); }

// ---- t-subset indexing ----
const tsubs = [];
{
  const cur = [];
  (function rec(start, need) { if (need === 0) { tsubs.push([...cur]); return; }
    for (let i = start; i <= v - need; i++) { cur.push(i); rec(i + 1, need - 1); cur.pop(); } })(0, t);
}
const T = tsubs.length;
console.log(`t-subsets: ${T}`);
const tIndex = new Map(tsubs.map((s, i) => [s.join(","), i]));

function tmaskOf(blockMask) {
  const pts = [];
  for (let i = 0; i < v; i++) if ((blockMask >> BigInt(i)) & 1n) pts.push(i);
  let m = 0n;
  (function rec(start, need, acc) {
    if (need === 0) { m |= 1n << BigInt(tIndex.get(acc.join(","))); return; }
    for (let i = start; i < pts.length; i++) { acc.push(pts[i]); rec(i + 1, need - 1, acc); acc.pop(); }
  })(0, t, []);
  return m;
}

for (const o of orbits) {
  let m = 0n;
  for (const b of o.blocks) m |= tmaskOf(b);
  o.cov = m; o.pc = popcountBig(m);
}

// sanity: union of all coverage = everything
let allCov = 0n;
for (const o of orbits) allCov |= o.cov;
if (allCov !== (1n << BigInt(T)) - 1n) { console.error("COVERAGE HOLE — enumeration error"); process.exit(1); }

// covering orbits per t-subset
const coveringOfT = new Array(T);
for (let oi = 0; oi < orbits.length; oi++) {
  for (let x = 0; x < T; x++) {
    if ((orbits[oi].cov >> BigInt(x)) & 1n) (coveringOfT[x] ??= []).push(oi);
  }
}

// ---- greedy incumbent ----
const FULL = (1n << BigInt(T)) - 1n;
let bestW, bestSol;
{
  let unc = FULL, w = 0; const chosen = [];
  while (unc !== 0n) {
    let bi = -1, bpRatio = -1;
    for (let oi = 0; oi < orbits.length; oi++) {
      if (chosen.includes(oi)) continue;
      const ratio = popcountBig(orbits[oi].cov & unc) / orbits[oi].size;
      if (ratio > bpRatio) { bpRatio = ratio; bi = oi; }
    }
    chosen.push(bi); w += orbits[bi].size; unc &= ~orbits[bi].cov;
  }
  bestW = w; bestSol = chosen.slice();
  console.log(`greedy incumbent: ${w} blocks in ${chosen.length} orbits`);
}

// ---- exact B&B ----
// admissible lower bound: weight + ceil(uncovered / maxRatio), maxRatio = max over orbits of pc/size
const maxRatio = Math.max(...orbits.map(o => o.pc / o.size));
const t0 = Date.now();
let nodes = 0, timeLimitHit = false;

function dfs(unc, weight, chosen) {
  nodes++;
  if ((nodes & 4095) === 0 && (Date.now() - t0) / 1000 > maxSeconds) { timeLimitHit = true; throw new Error("TIME_LIMIT"); }
  if (unc === 0n) {
    if (weight < bestW) {
      bestW = weight; bestSol = chosen.slice();
      console.log(`NEW BEST: ${bestW} blocks in ${bestSol.length} orbits (nodes=${nodes})`);
    }
    return;
  }
  const lb = weight + Math.ceil(popcountBig(unc) / maxRatio);
  if (lb >= bestW) return;
  // most-constrained uncovered t-subset
  let bx = -1, bc = Infinity;
  for (let x = 0; x < T; x++) {
    if ((unc >> BigInt(x)) & 1n) {
      const cl = coveringOfT[x].length;
      if (cl < bc) { bc = cl; bx = x; if (bc <= 1) break; }
    }
  }
  const cands = coveringOfT[bx]
    .filter(oi => weight + orbits[oi].size < bestW)
    .map(oi => ({ oi, g: popcountBig(orbits[oi].cov & unc) / orbits[oi].size }))
    .sort((a, b) => b.g - a.g);
  for (const { oi } of cands) {
    dfs(unc & ~orbits[oi].cov, weight + orbits[oi].size, [...chosen, oi]);
    if (timeLimitHit) throw new Error("TIME_LIMIT");
  }
}

try {
  dfs(FULL, 0, []);
  console.log(`\nEXACT RESULT: C_G(${v},${k},${t}) [${GROUP}] = ${bestW} (Schoenheim L=${L}, nodes=${nodes})`);
  console.log(bestW === L ? "*** G-INVARIANT DESIGN ATTAINS THE SCHOENHEIM BOUND ***"
    : `no G-invariant covering attains L; excess = ${bestW - L} blocks`);
  console.log("orbit indices:", JSON.stringify(bestSol));
  if (resFile) {
    const { writeFileSync } = await import("node:fs");
    writeFileSync(resFile.replace(/\.json$/, `_${GROUP}.json`), JSON.stringify({ v, k, t, group: GROUP, L, status: "EXACT", c_g: bestW, excess: bestW - L, nodes, orbitIndices: bestSol }) + "\n");
  }
} catch (e) {
  if (timeLimitHit) {
    console.log(`\nTIME LIMIT after ${nodes} nodes; best found: ${bestW} (not proven optimal)`);
    if (resFile) {
      const { writeFileSync } = await import("node:fs");
      writeFileSync(resFile.replace(/\.json$/, `_${GROUP}.json`), JSON.stringify({ v, k, t, group: GROUP, L, status: "TIME_LIMIT", ub_g: bestW, nodes }) + "\n");
    }
  } else throw e;
}