Game Theory: Nim, Grundy Numbers, and Sprague-Grundy

def nim_winner(piles):
    xor = 0
    for p in piles:
        xor ^= p
    return xor != 0  # True = current player wins

# Optimal move: make XOR = 0
def nim_optimal_move(piles):
    xor = 0
    for p in piles: xor ^= p
    if xor == 0: return None  # losing position
    for i, p in enumerate(piles):
        new_p = p ^ xor
        if new_p < p:
            return i, new_p  # take from pile i, leave new_p
    return None

# Grundy / Nimber values
def grundy(state, memo={}):
    if state in memo: return memo[state]
    reachable = set()
    # Add all states reachable in one move
    # Example: state = pile size, can remove 1,2,3
    for take in range(1, min(3, state) + 1):
        reachable.add(grundy(state - take, memo))
    # MEX (minimum excludant)
    mex = 0
    while mex in reachable: mex += 1
    memo[state] = mex
    return mex

# Composite games: XOR grundy values of independent sub-games
def composite_game_winner(sub_states, grundy_fn):
    total_xor = 0
    for s in sub_states:
        total_xor ^= grundy_fn(s)
    return total_xor != 0

#include <bits/stdc++.h>
using namespace std;

// LeetCode 292: Nim Game (remove 1,2,3 from pile)
bool canWinNim(int n) {
    return n % 4 != 0;
}

// LeetCode 294: Flip Game II
bool canWin(string s) {
    unordered_map<string, bool> memo;
    function<bool(string)> solve = [&](string s) -> bool {
        if (memo.count(s)) return memo[s];
        for (int i = 0; i + 1 < (int)s.size(); i++) {
            if (s[i] == '+' && s[i+1] == '+') {
                s[i] = s[i+1] = '-';
                bool wins = !solve(s);
                s[i] = s[i+1] = '+';
                if (wins) return memo[s] = true;
            }
        }
        return memo[s] = false;
    };
    return solve(s);
}

// Grundy for subtraction game {1,2,...,k}
// Pattern: grundy(n) = n % (k+1)
int grundySubtraction(int n, int k) {
    return n % (k + 1);
}

public class GameTheory {
    // Sprague-Grundy with memoization
    private Map<Integer, Integer> memo = new HashMap<>();

    int grundy(int state) {
        if (memo.containsKey(state)) return memo.get(state);
        Set<Integer> reachable = new HashSet<>();
        // Define moves here: example remove 1,2,3
        for (int take = 1; take <= Math.min(3, state); take++)
            reachable.add(grundy(state - take));
        int mex = 0;
        while (reachable.contains(mex)) mex++;
        memo.put(state, mex);
        return mex;
    }

    // LeetCode 877: Stone Game — always first player wins
    public boolean stoneGame(int[] piles) { return true; }

    // LeetCode 1140: Stone Game II
    public int stoneGameII(int[] piles) {
        int n = piles.length;
        int[] suffix = new int[n + 1];
        for (int i = n-1; i >= 0; i--) suffix[i] = suffix[i+1] + piles[i];
        int[][] dp = new int[n][n+1];
        for (int i = n-1; i >= 0; i--) {
            for (int M = 1; M <= n; M++) {
                for (int x = 1; x <= 2*M && i+x <= n; x++)
                    dp[i][M] = Math.max(dp[i][M], suffix[i] - (i+x < n ? dp[i+x][Math.max(M,x)] : 0));
            }
        }
        return dp[0][1];
    }
}