Stone Game Series — Minimax DP & Optimal Play

// Option 1: Pick from LEFT (piles[i])
//   - I get piles[i] stones NOW
//   - Opponent faces subarray piles[i+1..j]
//   - Opponent's optimal score = dp[i+1][j]
//   - My net = piles[i] - dp[i+1][j]

// Option 2: Pick from RIGHT (piles[j])
//   - I get piles[j] stones NOW
//   - Opponent faces subarray piles[i..j-1]
//   - Opponent's optimal score = dp[i][j-1]
//   - My net = piles[j] - dp[i][j-1]

// I choose the MAXIMUM of these two:
// dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])

function stoneGameI(piles) {
  const n = piles.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  // Base case: single stone
  for (let i = 0; i < n; i++) dp[i][i] = piles[i];

  // Fill DP table by subarray length
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      const pickLeft = piles[i] - dp[i + 1][j];
      const pickRight = piles[j] - dp[i][j - 1];
      dp[i][j] = Math.max(pickLeft, pickRight);
    }
  }

  // Alice wins if dp[0][n-1] > 0
  return dp[0][n - 1] > 0;
}

// Alternative: Space-optimized O(n) using 1D array
function stoneGameIOptimized(piles) {
  const n = piles.length;
  const dp = [...piles];  // dp[i] = dp[i][i] initial state

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      // dp[i] currently holds dp[i+1][j-1] from previous iteration
      // We need dp[i+1][j] (current dp[i+1]) and dp[i][j-1] (current dp[i])
      const pickLeft = piles[i] - dp[i + 1];
      const pickRight = piles[j] - dp[i];
      dp[i] = Math.max(pickLeft, pickRight);
    }
  }

  return dp[0] > 0;
}

function stoneGameII(piles) {
  const n = piles.length;
  const suffix = Array(n + 1).fill(0);
  for (let i = n - 1; i >= 0; i--) {
    suffix[i] = suffix[i + 1] + piles[i];
  }

  // dp[i][M] = max stones current player can get from piles[i:] with multiplier M
  const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));

  function solve(i, M) {
    if (i >= n) return 0;
    if (dp[i][M] !== 0) return dp[i][M];

    let maxStones = 0;
    // Try taking X = 1 to 2M stones
    for (let X = 1; X <= 2 * M && i + X <= n; X++) {
      const taken = suffix[i] - suffix[i + X];
      const opponent = solve(i + X, Math.max(M, X));
      const myTotal = taken + (suffix[i + X] - opponent);
      maxStones = Math.max(maxStones, myTotal);
    }

    dp[i][M] = maxStones;
    return maxStones;
  }

  const aliceScore = solve(0, 1);
  const total = suffix[0];
  return aliceScore > total - aliceScore;
}

// Iterative bottom-up version:
function stoneGameIIBottomUp(piles) {
  const n = piles.length;
  const suffix = Array(n + 1).fill(0);
  for (let i = n - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + piles[i];

  const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));

  for (let i = n - 1; i >= 0; i--) {
    for (let M = 1; M <= n; M++) {
      for (let X = 1; X <= 2 * M && i + X <= n; X++) {
        const opponent = dp[i + X][Math.max(M, X)];
        dp[i][M] = Math.max(dp[i][M], suffix[i] - opponent);
      }
    }
  }

  return dp[0][1] > suffix[0] - dp[0][1];
}

function stoneGameIII(stoneValue) {
  const n = stoneValue.length;
  const suffix = Array(n + 1).fill(0);
  for (let i = n - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + stoneValue[i];

  // dp[i] = max score current player can get from piles[i:]
  const dp = Array(n + 1).fill(0);

  for (let i = n - 1; i >= 0; i--) {
    let best = -Infinity;
    for (let X = 1; X <= 3 && i + X <= n; X++) {
      // Current player takes piles[i..i+X-1], opponent gets dp[i+X]
      best = Math.max(best, suffix[i] - dp[i + X]);
    }
    dp[i] = best;
  }

  const alice = dp[0];
  const bob = suffix[0] - alice;
  if (alice > bob) return "Alice";
  if (alice < bob) return "Bob";
  return "Tie";
}

function stoneGameIV(n) {
  // Generate all perfect squares up to n
  const squares = [];
  for (let i = 1; i * i <= n; i++) squares.push(i * i);

  const dp = Array(n + 1).fill(false);
  dp[0] = false;  // No stones → current player loses

  for (let i = 1; i <= n; i++) {
    for (const s of squares) {
      if (s > i) break;
      if (!dp[i - s]) {
        dp[i] = true;  // Found a winning move!
        break;
      }
    }
  }

  return dp[n];
}

// Mathematical shortcut (works for this specific problem):
function stoneGameIVMath(n) {
  // The pattern: Alice wins unless n % (some period) == 0
  // But this is NOT guaranteed — always implement DP first!
  return stoneGameIV(n);  // Stick with DP for safety
}

function stoneGameV(stoneValue) {
  const n = stoneValue.length;
  const prefix = Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stoneValue[i];

  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  // sum[i..j] using prefix
  function sum(i, j) {
    return prefix[j + 1] - prefix[i];
  }

  // Process by increasing subarray length
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      let best = 0;
      for (let k = i; k < j; k++) {
        const left = sum(i, k);
        const right = sum(k + 1, j);
        if (left < right) {
          // Keep left (smaller), opponent plays right
          best = Math.max(best, left + dp[i][k]);
        } else if (left > right) {
          // Keep right (smaller), opponent plays left
          best = Math.max(best, right + dp[k + 1][j]);
        } else {
          // Equal — choose either
          best = Math.max(best, left + dp[i][k], right + dp[k + 1][j]);
        }
      }
      dp[i][j] = best;
    }
  }

  return dp[0][n - 1];
}

function stoneGameVI(aliceValues, bobValues) {
  const n = aliceValues.length;

  // Create array of [combinedValue, aliceValue, bobValue, index]
  const stones = [];
  for (let i = 0; i < n; i++) {
    stones.push({
      combined: aliceValues[i] + bobValues[i],
      alice: aliceValues[i],
      bob: bobValues[i],
    });
  }

  // Sort by combined value DESCENDING
  stones.sort((a, b) => b.combined - a.combined);

  let aliceScore = 0;
  let bobScore = 0;

  for (let i = 0; i < n; i++) {
    if (i % 2 === 0) {
      aliceScore += stones[i].alice;  // Alice' turn
    } else {
      bobScore += stones[i].bob;      // Bob's turn
    }
  }

  if (aliceScore > bobScore) return 1;
  if (aliceScore < bobScore) return -1;
  return 0;
}

// Why sorting by combined value works:
// When Alice picks stone i, the net gain over Bob is:
//   aliceValues[i] - (what Bob would have gotten if Alice didn't pick it)
// If Alice doesn't pick stone i, Bob might pick it and get bobValues[i].
// So Alice's pick prevents Bob from getting bobValues[i].
// Net advantage = aliceValues[i] - (-bobValues[i]) = aliceValues[i] + bobValues[i]
// Alice wants to MAXIMIZE this advantage → pick highest combined value!

function stoneGameVII(stones) {
  const n = stones.length;
  const prefix = Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stones[i];

  function sum(i, j) {
    return prefix[j + 1] - prefix[i];
  }

  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      // Pick left: get sum[i+1..j], then opponent advantage = dp[i+1][j]
      const pickLeft = sum(i + 1, j) - dp[i + 1][j];
      // Pick right: get sum[i..j-1], then opponent advantage = dp[i][j-1]
      const pickRight = sum(i, j - 1) - dp[i][j - 1];
      dp[i][j] = Math.max(pickLeft, pickRight);
    }
  }

  return dp[0][n - 1];  // Alice's max advantage over Bob
}

function stoneGameVIII(stones) {
  const n = stones.length;
  const prefix = Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stones[i];

  // dp[i] = max advantage current player can get from suffix starting at i
  const dp = Array(n + 1).fill(0);
  let maxDiff = prefix[n] - dp[n];  // Best difference seen so far

  // Process from right to left
  for (let i = n - 1; i >= 0; i--) {
    // If we take prefix up to i, opponent gets dp[i+1] from remaining
    // Our advantage = sum[0..i] - dp[i+1]
    dp[i] = maxDiff;
    // Update maxDiff for next iteration
    // At position i, taking prefix [0..i] gives sum[0..i] - dp[i+1]
    maxDiff = Math.max(maxDiff, prefix[i + 1] - dp[i + 1]);
  }

  return dp[0];
}

// Simplified:
function stoneGameVIII(stones) {
  const n = stones.length;
  let suffixSum = stones.reduce((a, b) => a + b, 0);
  let best = suffixSum;  // Take all stones on last possible turn

  for (let i = n - 1; i > 0; i--) {
    suffixSum -= stones[i];
    // Current player takes prefix [0..i-1], opponent gets dp from position i
    // dp[i] = max score from position i onward
    best = Math.max(best, suffixSum - best);
  }

  return best;
}

function stoneGameIX(stones) {
  // Count stones by their value modulo 3
  let count0 = 0, count1 = 0, count2 = 0;
  for (const s of stones) {
    if (s % 3 === 0) count0++;
    else if (s % 3 === 1) count1++;
    else count2++;
  }

  // If count1 and count2 are both 0, all stones are divisible by 3
  // Alice MUST pick one → sum % 3 = 0 → Alice LOSES immediately
  if (count1 === 0 && count2 === 0) return false;

  // If count0 is even:
  //   Alice wins if min(count1, count2) > 0
  // If count0 is odd:
  //   Alice wins if abs(count1 - count2) > 2
  if (count0 % 2 === 0) {
    return Math.min(count1, count2) > 0;
  } else {
    return Math.abs(count1 - count2) > 2;
  }
}

// Detailed logic explanation:
// The game is about using 1s and 2s to AVOID making the sum % 3 = 0
// Stones with value % 3 == 0 just change turn order (neutral)
// If count0 is even, 0s don't affect turn parity
// If count0 is odd, 0s flip turn parity
// To avoid losing: Alice needs to ensure she never creates sum % 3 == 0
// while forcing Bob into that situation

function stoneDivision(n) {
  const grundy = Array(n + 1).fill(0);

  for (let i = 2; i <= n; i++) {
    const reachable = new Set();

    // Find all divisors d of i where d > 0 and d < i
    for (let d = 1; d * d <= i; d++) {
      if (i % d === 0) {
        const d1 = d;
        const d2 = i / d;

        // For divisor d1: split into d1 piles of size i/d1
        if (d1 < i) {
          const g = grundy[i / d1];
          const xorVal = (d1 % 2 === 0) ? 0 : g;
          reachable.add(xorVal);
        }

        // For divisor d2 (different from d1)
        if (d2 !== d1 && d2 < i) {
          const g = grundy[i / d2];
          const xorVal = (d2 % 2 === 0) ? 0 : g;
          reachable.add(xorVal);
        }
      }
    }

    // mex — find smallest non-negative integer not in reachable
    let g = 0;
    while (reachable.has(g)) g++;
    grundy[i] = g;
  }

  return grundy[n] !== 0;
}

// Pattern detection for large n (up to 10^12):
// Grundy(n) = 0 only for n = 1 or n = 2
// For n >= 3, Grundy(n) > 0 → First player wins
// But verify with DP for small n, then generalize

function predictTheWinner(nums) {
  const n = nums.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  for (let i = 0; i < n; i++) dp[i][i] = nums[i];

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      dp[i][j] = Math.max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
    }
  }

  return dp[0][n - 1] >= 0;
}

// Space-optimized version
function predictTheWinnerOpt(nums) {
  const n = nums.length;
  const dp = [...nums];  // dp[i] initially = dp[i][i]

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      dp[i] = Math.max(nums[i] - dp[i + 1], nums[j] - dp[i]);
    }
  }

  return dp[0] >= 0;
}

// Universal Minimax DP Template for Two-Player Games

function solve(values) {
  const n = values.length;

  // Step 1: Precompute prefix/suffix sums if needed
  const prefix = Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + values[i];
  function sum(i, j) { return prefix[j + 1] - prefix[i]; }

  // Step 2: Initialize DP
  // dp[i][j] = maximum NET advantage for current player on subarray i..j
  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  // Step 3: Base case — single element
  for (let i = 0; i < n; i++) dp[i][i] = values[i];

  // Step 4: Fill DP — increase subarray length
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;

      // For each possible move at this state
      // "At this position, I CHOOSE to pick left, pick right, or some other action"
      // dp[i][j] = max over all valid moves of (myGain - opponentAdvantage)

      // Example: pick from ends (Stone Game I, VII)
      const pickLeft = values[i] - dp[i + 1][j];     // or sum(i+1,j) - dp[i+1][j] for SG VII
      const pickRight = values[j] - dp[i][j - 1];   // or sum(i,j-1) - dp[i][j-1] for SG VII
      dp[i][j] = Math.max(pickLeft, pickRight);
    }
  }

  // Step 5: Answer
  return dp[0][n - 1];  // Positive → first player wins
}