Advanced Nim & Grundy Numbers — The Sprague–Grundy Theorem

Grundy(state) = mex({ Grundy(s') | s' is a valid move from state })

Where mex(S) = Minimum EXcluded non-negative integer in set S

Example: S = {[0, 1, 3]} → mex(S) = 2
         S = {[0, 1, 2, 4]} → mex(S) = 3
         S = {} → mex(S) = 0 (terminal state)

THEOREM: Any impartial game G composed of independent sub-games
G1, G2, ..., Gk can be analyzed as follows:

1. Compute Grundy(Gi) for each sub-game
2. Nim-sum = Grundy(G1) ⊕ Grundy(G2) ⊕ ... ⊕ Grundy(Gk)
3. If Nim-sum ≠ 0 → N-position (winning for current player)
4. If Nim-sum = 0 → P-position (losing for current player)

In other words: G ≅ Nim heap of size Grundy(G)

The XOR rule from standard Nim GENERALIZES to any impartial game!

// Nim Game II — CSES (moves allowed = {[1, 2, 3]})
function nimGameII(piles, moves = [1, 2, 3]) {
  // Precompute Grundy numbers up to max pile size
  const maxPile = Math.max(...piles);
  const grundy = new Array(maxPile + 1).fill(0);

  for (let i = 1; i <= maxPile; i++) {
    const reachable = new Set();
    for (const m of moves) {
      if (i - m >= 0) reachable.add(grundy[i - m]);
    }
    // mex: find smallest non-negative not in reachable
    let g = 0;
    while (reachable.has(g)) g++;
    grundy[i] = g;
  }

  // XOR all Grundy numbers
  const xorSum = piles.reduce((acc, p) => acc ^ grundy[p], 0);
  return xorSum !== 0 ? "First" : "Second";
}

// Pattern: Grundy[n] = n mod (moves.length + 1) for consecutive moves {1..k}
// But for arbitrary move sets, compute DP mex as above

// Standard Nim pile of size n:
// Reachable states: {0, 1, 2, ..., n-1}
// Grundy(0) = 0, Grundy(1) = 1, ..., Grundy(n-1) = n-1
// mex{0, 1, 2, ..., n-1} = n
// ∴ Grundy(n) = n for standard Nim

// Nim-sum = Grundy(p1) ⊕ Grundy(p2) ⊕ ... ⊕ Grundy(pk)
//         = p1 ⊕ p2 ⊕ ... ⊕ pk (same as before!)

// Staircase Nim — Grundy Proof
//
// Each stair i is a sub-game. What's Grundy(i)?
// From stair i, you move stones to stair i-1.
// This is equivalent to: Grundy(i) = i XOR Grundy(i-1)? No...
//
// Key insight: Moving stones from i → i-1 changes the parity of
// stones on BOTH stairs. The "real" game is on odd stairs.
//
// For stair i:
//   - If i is ODD: moving stones here is like reducing a Nim pile
//     of size equal to the stone count (they will reach ground)
//   - If i is EVEN: opponent can "mirror" any move you make here
//
// ∴ Grundy(i) = stones[i] if i is odd, 0 if i is even
// Final XOR = XOR of stones on odd-indexed stairs

function misereNim(piles) {
  const maxPile = Math.max(...piles);
  const allOnes = maxPile <= 1; // All piles are 0 or 1

  if (allOnes) {
    // FLIP: Normal XOR logic is inverted
    // Normal: odd count of 1s → First wins
    // Misère: odd count of 1s → First LOSES
    const xorAll = piles.reduce((a, b) => a ^ b, 0);
    return xorAll === 0 ? "First" : "Second";
  } else {
    // Any pile > 1 → Same as normal Nim!
    const nimSum = piles.reduce((a, b) => a ^ b, 0);
    return nimSum !== 0 ? "First" : "Second";
  }
}

// Why? The winning player can force a state where:
// 1. They leave exactly one pile with > 1 stone
// 2. All other piles are 0 or 1
// 3. The opponent is forced to take from the >1 pile
// 4. The opponent ends up taking the LAST stone = LOSS

// Poker Nim — Solution
function pokerNim(piles, passes) {
  // Standard Nim-sum first
  const nimSum = piles.reduce((a, b) => a ^ b, 0);

  if (nimSum !== 0) {
    // Already winning — no need to pass
    return "First";
  }

  // Nim-sum = 0 — losing position NORMALLY
  // But if we have a pass token AND opponent doesn't...
  // Actually in standard Poker Nim BOTH players have same passes
  // So if total passes > 0, first player wins by passing!
  if (passes > 0) {
    return "First"; // Pass once, opponent faces losing position
  }

  return "Second"; // No passes, stuck in losing position
}

// Simplified: If ANY player has a pass, first player wins.
// Because the first player can always use a pass from a losing
// position to flip the parity. This works as long as passes > 0.

// Nimble Game — Solution
function nimbleGame(squares) {
  // squares[i] = number of coins on square i
  // Each coin on square i contributes Grundy = i
  // Pairs of coins on same square cancel (i ⊕ i = 0)

  let xorSum = 0;
  for (let i = 0; i < squares.length; i++) {
    if (squares[i] % 2 === 1) {
      xorSum ^= i;  // Odd coins on square i → include i in XOR
    }
    // Even coins → cancel out (i ⊕ i = 0)
  }

  return xorSum !== 0 ? "First" : "Second";
}

// Intuition:
// - Each coin is a Nim pile of size = square index
// - Two coins on same square = two equal piles → cancel
// - Only need to track parity of coins per square

// Industrial Nim — Solution
// Key: XOR of range [L, R] efficiently using prefix XOR pattern

// Helper: XOR of all numbers from 0 to n
function xor0toN(n) {
  const mod = n % 4;
  if (mod === 0) return n;
  if (mod === 1) return 1;
  if (mod === 2) return n + 1;
  return 0;
}

// XOR of range [L, R] = xor0toN(R) ⊕ xor0toN(L-1)
function xorRange(L, R) {
  if (L === 0) return xor0toN(R);
  return xor0toN(R) ^ xor0toN(L - 1);
}

function industrialNim(groups) {
  // groups: [{start, count}, ...]
  let xorSum = 0;
  for (const {start, count} of groups) {
    xorSum ^= xorRange(start, start + count - 1);
  }
  return xorSum !== 0 ? "First" : "Second";
}

// XOR 0..n pattern:
// n % 4 == 0 → n
// n % 4 == 1 → 1
// n % 4 == 2 → n + 1
// n % 4 == 3 → 0