1075 Advanced

1075-stone-game — Stone Game (Minimax DP)

Functional Programming

Tutorial

The Problem

Two players alternate taking stones from either end of a row. Each player plays optimally to maximize their own stones. Does the first player always win when the number of piles is even?

The stone game is a minimax problem — both players are rational and play to their best advantage. Interval DP captures the optimal play for any sub-interval. Interestingly, when piles.len() is even, the first player can always win by a parity argument (but proving it requires the DP to show the margin, not just the winner).

🎯 Learning Outcomes

• Model two-player optimal play as interval DP

• Use dp[i][j] = score difference (current player minus opponent) for piles i..j

• Understand the minimax recurrence: take max of (pile[i] - dp[i+1][j]) and (pile[j] - dp[i][j-1])

• Recognize that the "difference" state avoids tracking both players' scores separately

• Connect to game theory and alpha-beta pruning

Code Example

#![allow(clippy::all)]
// 1075: Stone Game — Minimax DP

use std::collections::HashMap;

// Approach 1: Bottom-up interval DP
fn stone_game_dp(piles: &[i32]) -> bool {
    let n = piles.len();
    // dp[i][j] = max score difference (current player - opponent) for piles[i..=j]
    let mut dp = vec![vec![0i32; n]; n];
    for i in 0..n {
        dp[i][i] = piles[i];
    }
    for len in 2..=n {
        for i in 0..=n - len {
            let j = i + len - 1;
            dp[i][j] = (piles[i] - dp[i + 1][j]).max(piles[j] - dp[i][j - 1]);
        }
    }
    dp[0][n - 1] > 0
}

// Approach 2: Recursive with memoization
fn stone_game_memo(piles: &[i32]) -> bool {
    fn solve(i: usize, j: usize, piles: &[i32], cache: &mut HashMap<(usize, usize), i32>) -> i32 {
        if i > j {
            return 0;
        }
        if i == j {
            return piles[i];
        }
        if let Some(&v) = cache.get(&(i, j)) {
            return v;
        }
        let v = (piles[i] - solve(i + 1, j, piles, cache))
            .max(piles[j] - solve(i, j - 1, piles, cache));
        cache.insert((i, j), v);
        v
    }
    let mut cache = HashMap::new();
    solve(0, piles.len() - 1, piles, &mut cache) > 0
}

// Approach 3: Mathematical — first player always wins with even piles
fn stone_game_math(_piles: &[i32]) -> bool {
    // With even number of piles, first player can always choose
    // all odd-indexed or all even-indexed piles (by choosing first/last).
    // One of those sums is strictly greater, so first player always wins.
    true
}

// Bonus: compute actual scores
fn stone_game_scores(piles: &[i32]) -> (i32, i32) {
    let n = piles.len();
    let total: i32 = piles.iter().sum();
    let mut dp = vec![vec![0i32; n]; n];
    for i in 0..n {
        dp[i][i] = piles[i];
    }
    for len in 2..=n {
        for i in 0..=n - len {
            let j = i + len - 1;
            dp[i][j] = (piles[i] - dp[i + 1][j]).max(piles[j] - dp[i][j - 1]);
        }
    }
    let diff = dp[0][n - 1];
    let p1 = (total + diff) / 2;
    let p2 = total - p1;
    (p1, p2)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dp() {
        assert!(stone_game_dp(&[5, 3, 4, 5]));
        assert!(stone_game_dp(&[3, 7, 2, 3]));
    }

    #[test]
    fn test_memo() {
        assert!(stone_game_memo(&[5, 3, 4, 5]));
        assert!(stone_game_memo(&[3, 7, 2, 3]));
    }

    #[test]
    fn test_math() {
        assert!(stone_game_math(&[5, 3, 4, 5]));
    }

    #[test]
    fn test_scores() {
        let (p1, p2) = stone_game_scores(&[5, 3, 4, 5]);
        assert!(p1 > p2);
        assert_eq!(p1 + p2, 17);
    }
}

(* 1075: Stone Game — Minimax DP *)

(* Approach 1: Bottom-up interval DP *)
let stone_game_dp piles =
  let n = Array.length piles in
  (* dp.(i).(j) = max score difference (current player - opponent) for piles[i..j] *)
  let dp = Array.init n (fun i -> Array.init n (fun j ->
    if i = j then piles.(i) else 0
  )) in
  for len = 2 to n do
    for i = 0 to n - len do
      let j = i + len - 1 in
      dp.(i).(j) <- max
        (piles.(i) - dp.(i + 1).(j))
        (piles.(j) - dp.(i).(j - 1))
    done
  done;
  dp.(0).(n - 1) > 0

(* Approach 2: Recursive with memoization *)
let stone_game_memo piles =
  let n = Array.length piles in
  let cache = Hashtbl.create 64 in
  let rec solve i j =
    if i > j then 0
    else if i = j then piles.(i)
    else
      match Hashtbl.find_opt cache (i, j) with
      | Some v -> v
      | None ->
        let v = max
          (piles.(i) - solve (i + 1) j)
          (piles.(j) - solve i (j - 1))
        in
        Hashtbl.add cache (i, j) v;
        v
  in
  solve 0 (n - 1) > 0

(* Approach 3: Mathematical insight — first player always wins with even piles *)
let stone_game_math _piles =
  (* With even number of piles, first player can always choose
     all odd-indexed or all even-indexed piles. One of those sums
     is strictly greater. So first player always wins. *)
  true

(* Generalized: compute actual scores *)
let stone_game_scores piles =
  let n = Array.length piles in
  let total = Array.fold_left ( + ) 0 piles in
  let dp = Array.init n (fun i -> Array.init n (fun j ->
    if i = j then piles.(i) else 0
  )) in
  for len = 2 to n do
    for i = 0 to n - len do
      let j = i + len - 1 in
      dp.(i).(j) <- max
        (piles.(i) - dp.(i + 1).(j))
        (piles.(j) - dp.(i).(j - 1))
    done
  done;
  let diff = dp.(0).(n - 1) in
  let p1 = (total + diff) / 2 in
  let p2 = total - p1 in
  (p1, p2)

let () =
  assert (stone_game_dp [|5; 3; 4; 5|] = true);
  assert (stone_game_dp [|3; 7; 2; 3|] = true);

  assert (stone_game_memo [|5; 3; 4; 5|] = true);
  assert (stone_game_memo [|3; 7; 2; 3|] = true);

  assert (stone_game_math [|5; 3; 4; 5|] = true);

  let (p1, p2) = stone_game_scores [|5; 3; 4; 5|] in
  assert (p1 > p2);
  assert (p1 + p2 = 17);

  Printf.printf "✓ All tests passed\n"

Key Differences

Score difference encoding: Both encode current_player_score - opponent_score in one cell; this is the key insight that simplifies the state.

Interval filling order: Both fill by increasing len — the same constraint as all interval DP problems.

Parity argument: For even n, the first player can always guarantee a win by parity (take all even-indexed or all odd-indexed piles); the DP proves this by showing the margin.

Alpha-beta pruning: For deeper game trees, alpha-beta pruning reduces the branching factor; the stone game is small enough that full minimax DP is practical.

OCaml Approach

let stone_game piles =
  let n = Array.length piles in
  let dp = Array.make_matrix n n 0 in
  for i = 0 to n - 1 do dp.(i).(i) <- piles.(i) done;
  for len = 2 to n do
    for i = 0 to n - len do
      let j = i + len - 1 in
      dp.(i).(j) <- max
        (piles.(i) - dp.(i+1).(j))
        (piles.(j) - dp.(i).(j-1))
    done
  done;
  dp.(0).(n-1) > 0

Identical structure. The score-difference encoding is a mathematical insight independent of language.

Full Source

#![allow(clippy::all)]
// 1075: Stone Game — Minimax DP

use std::collections::HashMap;

// Approach 1: Bottom-up interval DP
fn stone_game_dp(piles: &[i32]) -> bool {
    let n = piles.len();
    // dp[i][j] = max score difference (current player - opponent) for piles[i..=j]
    let mut dp = vec![vec![0i32; n]; n];
    for i in 0..n {
        dp[i][i] = piles[i];
    }
    for len in 2..=n {
        for i in 0..=n - len {
            let j = i + len - 1;
            dp[i][j] = (piles[i] - dp[i + 1][j]).max(piles[j] - dp[i][j - 1]);
        }
    }
    dp[0][n - 1] > 0
}

// Approach 2: Recursive with memoization
fn stone_game_memo(piles: &[i32]) -> bool {
    fn solve(i: usize, j: usize, piles: &[i32], cache: &mut HashMap<(usize, usize), i32>) -> i32 {
        if i > j {
            return 0;
        }
        if i == j {
            return piles[i];
        }
        if let Some(&v) = cache.get(&(i, j)) {
            return v;
        }
        let v = (piles[i] - solve(i + 1, j, piles, cache))
            .max(piles[j] - solve(i, j - 1, piles, cache));
        cache.insert((i, j), v);
        v
    }
    let mut cache = HashMap::new();
    solve(0, piles.len() - 1, piles, &mut cache) > 0
}

// Approach 3: Mathematical — first player always wins with even piles
fn stone_game_math(_piles: &[i32]) -> bool {
    // With even number of piles, first player can always choose
    // all odd-indexed or all even-indexed piles (by choosing first/last).
    // One of those sums is strictly greater, so first player always wins.
    true
}

// Bonus: compute actual scores
fn stone_game_scores(piles: &[i32]) -> (i32, i32) {
    let n = piles.len();
    let total: i32 = piles.iter().sum();
    let mut dp = vec![vec![0i32; n]; n];
    for i in 0..n {
        dp[i][i] = piles[i];
    }
    for len in 2..=n {
        for i in 0..=n - len {
            let j = i + len - 1;
            dp[i][j] = (piles[i] - dp[i + 1][j]).max(piles[j] - dp[i][j - 1]);
        }
    }
    let diff = dp[0][n - 1];
    let p1 = (total + diff) / 2;
    let p2 = total - p1;
    (p1, p2)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dp() {
        assert!(stone_game_dp(&[5, 3, 4, 5]));
        assert!(stone_game_dp(&[3, 7, 2, 3]));
    }

    #[test]
    fn test_memo() {
        assert!(stone_game_memo(&[5, 3, 4, 5]));
        assert!(stone_game_memo(&[3, 7, 2, 3]));
    }

    #[test]
    fn test_math() {
        assert!(stone_game_math(&[5, 3, 4, 5]));
    }

    #[test]
    fn test_scores() {
        let (p1, p2) = stone_game_scores(&[5, 3, 4, 5]);
        assert!(p1 > p2);
        assert_eq!(p1 + p2, 17);
    }
}

(* 1075: Stone Game — Minimax DP *)

(* Approach 1: Bottom-up interval DP *)
let stone_game_dp piles =
  let n = Array.length piles in
  (* dp.(i).(j) = max score difference (current player - opponent) for piles[i..j] *)
  let dp = Array.init n (fun i -> Array.init n (fun j ->
    if i = j then piles.(i) else 0
  )) in
  for len = 2 to n do
    for i = 0 to n - len do
      let j = i + len - 1 in
      dp.(i).(j) <- max
        (piles.(i) - dp.(i + 1).(j))
        (piles.(j) - dp.(i).(j - 1))
    done
  done;
  dp.(0).(n - 1) > 0

(* Approach 2: Recursive with memoization *)
let stone_game_memo piles =
  let n = Array.length piles in
  let cache = Hashtbl.create 64 in
  let rec solve i j =
    if i > j then 0
    else if i = j then piles.(i)
    else
      match Hashtbl.find_opt cache (i, j) with
      | Some v -> v
      | None ->
        let v = max
          (piles.(i) - solve (i + 1) j)
          (piles.(j) - solve i (j - 1))
        in
        Hashtbl.add cache (i, j) v;
        v
  in
  solve 0 (n - 1) > 0

(* Approach 3: Mathematical insight — first player always wins with even piles *)
let stone_game_math _piles =
  (* With even number of piles, first player can always choose
     all odd-indexed or all even-indexed piles. One of those sums
     is strictly greater. So first player always wins. *)
  true

(* Generalized: compute actual scores *)
let stone_game_scores piles =
  let n = Array.length piles in
  let total = Array.fold_left ( + ) 0 piles in
  let dp = Array.init n (fun i -> Array.init n (fun j ->
    if i = j then piles.(i) else 0
  )) in
  for len = 2 to n do
    for i = 0 to n - len do
      let j = i + len - 1 in
      dp.(i).(j) <- max
        (piles.(i) - dp.(i + 1).(j))
        (piles.(j) - dp.(i).(j - 1))
    done
  done;
  let diff = dp.(0).(n - 1) in
  let p1 = (total + diff) / 2 in
  let p2 = total - p1 in
  (p1, p2)

let () =
  assert (stone_game_dp [|5; 3; 4; 5|] = true);
  assert (stone_game_dp [|3; 7; 2; 3|] = true);

  assert (stone_game_memo [|5; 3; 4; 5|] = true);
  assert (stone_game_memo [|3; 7; 2; 3|] = true);

  assert (stone_game_math [|5; 3; 4; 5|] = true);

  let (p1, p2) = stone_game_scores [|5; 3; 4; 5|] in
  assert (p1 > p2);
  assert (p1 + p2 = 17);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dp() {
        assert!(stone_game_dp(&[5, 3, 4, 5]));
        assert!(stone_game_dp(&[3, 7, 2, 3]));
    }

    #[test]
    fn test_memo() {
        assert!(stone_game_memo(&[5, 3, 4, 5]));
        assert!(stone_game_memo(&[3, 7, 2, 3]));
    }

    #[test]
    fn test_math() {
        assert!(stone_game_math(&[5, 3, 4, 5]));
    }

    #[test]
    fn test_scores() {
        let (p1, p2) = stone_game_scores(&[5, 3, 4, 5]);
        assert!(p1 > p2);
        assert_eq!(p1 + p2, 17);
    }
}

Deep Comparison

Stone Game — Comparison

Core Insight

Stone game is minimax DP on intervals. The key trick: store the score difference rather than absolute scores. Taking pile i gives piles[i] - dp[i+1][j] because after taking, your opponent is the "current player" for the remaining interval. The mathematical solution (first player always wins with even piles) bypasses DP entirely.

OCaml Approach

• Array.init n (fun i -> Array.init n ...) for 2D table with diagonal init

• max of two choices (take left vs take right)

• Hashtbl for memoization

• Score reconstruction: (total + diff) / 2

Rust Approach

• vec![vec![0; n]; n] with separate diagonal init loop

• .max() method chaining

• HashMap for memoization

• Same score reconstruction formula

Comparison Table

Aspect	OCaml	Rust
2D init	`Array.init n (fun i -> Array.init n (fun j -> ...))`	Init loop + `vec!`
Minimax	`max (take_left) (take_right)`	`.max()`
Score difference	Subtraction: `piles.(i) - dp.(i+1).(j)`	Same: `piles[i] - dp[i+1][j]`
Math proof	`true` (same insight)	`true` (same insight)
Score split	`(total + diff) / 2`	`(total + diff) / 2`

Exercises

Return the first player's actual score (not just win/lose) from stone_game_dp.

Implement the greedy strategy (always take the larger of the two ends) and demonstrate it is NOT optimal by constructing a counterexample.

Extend to k players (not just 2) taking turns — generalize the DP to track the score difference relative to the leader.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust