// Erdos-Straus DSS Greedy Sequence — Core Engine
// Computes the greedy sequence and provides DSS oracle operations.

export function isDSS(set) {
  const n = set.length;
  const sumsByCard = new Map();
  const subsets = allSubsets(set);
  for (const sub of subsets) {
    const s = sub.reduce((a, b) => a + b, 0);
    const card = sub.length;
    if (!sumsByCard.has(s)) {
      sumsByCard.set(s, card);
    } else if (sumsByCard.get(s) !== card) {
      return false;
    }
  }
  return true;
}

function allSubsets(arr) {
  const result = [];
  const n = arr.length;
  for (let mask = 1; mask < (1 << n); mask++) {
    const sub = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) sub.push(arr[i]);
    }
    result.push(sub);
  }
  return result;
}

export function computeGreedySequence(k) {
  const seq = [1];
  for (let i = 1; i < k; i++) {
    let x = seq[seq.length - 1] + 1;
    while (true) {
      const candidate = [...seq, x];
      if (isDSS(candidate)) {
        seq.push(x);
        break;
      }
      x++;
    }
  }
  return seq;
}

export function verifyQuadraticBound(seq) {
  const results = [];
  for (let k = 0; k < seq.length; k++) {
    const kk = k + 1; // 1-indexed
    const bound = Math.floor((kk * kk + 1) / 2);
    const actual = seq[k];
    results.push({
      k: kk,
      greedy: actual,
      bound,
      holds: actual >= bound,
      ratio: (actual / bound).toFixed(3)
    });
  }
  return results;
}

export function sumToCardinality(weights, observedSum) {
  const n = weights.length;
  for (let mask = 1; mask < (1 << n); mask++) {
    let s = 0;
    let card = 0;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        s += weights[i];
        card++;
      }
    }
    if (s === observedSum) return card;
  }
  return -1;
}

export function cardinalityFromSum(weights, observedSum) {
  // DSS guarantees: from the sum alone, determine how many elements contributed.
  // This is O(1) lookup after precomputation.
  const table = buildCardinalityTable(weights);
  return table.get(observedSum) ?? -1;
}

export function buildCardinalityTable(weights) {
  const table = new Map();
  const n = weights.length;
  for (let mask = 1; mask < (1 << n); mask++) {
    let s = 0;
    let card = 0;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        s += weights[i];
        card++;
      }
    }
    table.set(s, card);
  }
  return table;
}