1908. Game of Nim
Problem Description
In this game-themed problem, we have two players, Alice and Bob, who are playing a turn-based game involving piles of stones. There are n
piles of stones, and on each player's turn, that player must remove any positive number of stones from any one pile. If a player can't make a move (which happens when all piles are empty), they lose. The twist in the problem comes from the assumption that both players will make the best possible move at any point in the game, meaning they play optimally. The task is to determine if Alice, who always goes first, will win the game given the initial number of stones in each pile represented by an integer array piles
, where piles[i]
specifies the number of stones in the ith pile.
Intuition
The problem is a variant of the classical game theory problem known as Nim. The key to solving this sort of problem lies in understanding the optimal strategies that players can employ and the winning positions in such a game.
A fundamental concept in playing Nim optimally is the Nim-sum, or the bitwise XOR sum of the number of stones in each pile. If the Nim-sum is 0 at the beginning of a player's turn, that player is in a losing position (assuming both players play perfectly). This is because no matter what move they make, the opponent can always return the game to a state where the Nim-sum is 0, putting the initial player back into a losing position on their next turn.
Therefore, if the Nim-sum of all the pile sizes is not 0 when it's Alice's turn (which is the case at the start of the game since she goes first), then Alice can make a move that forces a 0 Nim-sum on Bob's turn, putting her in a winning position from the start.
As the problem assumes optimal play from both Alice and Bob, we can deduce the winner by calculating the Nim-sum of all the pile sizes.
Although the provided solution code uses a depth-first search (DFS) approach, which can handle variations of the problem where the rules of play diverge from classical Nim, for this specific problem, a simplified solution would compute the Nim-sum, like so:
class Solution:
def nimGame(self, piles: List[int]) -> bool:
xor_sum = 0
for pile in piles:
xor_sum ^= pile
return xor_sum != 0
This code simply iterates over the piles and computes the cumulative XOR. If the result is non-zero, Alice wins, since she can always make a move to set the Nim-sum to 0 for Bob; if it is zero, Bob wins by maintaining the 0 Nim-sum position through each of his turns.
Learn more about Math and Dynamic Programming patterns.
Solution Approach
The reference solution provided uses a recursive DFS approach to simulate every possible state of the game. Although for the specific game rules provided, there is a more efficient solution as explained earlier, this approach can handle a wider variety of game rules where the winning strategy might not be straightforward.
Here's a walk-through of the provided DFS solution:
-
The
dfs
function is defined within the context of thenimGame
method. It is decorated with@cache
, which is a Python decorator that automatically memoizes the results of the function calls. Memoization ensures that repeated states of the game are not re-evaluated, which optimizes the solution by reducing the number of recursive calls. -
The
dfs
function is intended to be called with a tuplest
representing the current state of the game, i.e., the number of stones in each pile. It convertsst
into a listlst
for easier manipulation since tuples are immutable. -
The
dfs
function then iterates over every pilelst[i]
and for each pile tries removing every possible positive number of stonesj
(from 1 to the pile's size inclusive). This simulates all potential moves a player could make. -
After simulating the move (removing
j
stones from pilei
),dfs
recursively checks whether this state leads to a losing state for the opponent by callingnot dfs(tuple(lst))
. If a losing state for the opponent is found, then the current state is winning, hence it returnsTrue
. -
If no move leads to an immediate winning state, the
dfs
function returnsFalse
, indicating that any opponent's response to the current state can at most prolong the game, but eventually the current player will lose. -
nimGame
callsdfs
using the initial statetuple(piles)
and returns the result. If the result isTrue
, it means Alice can win starting from the initial state; otherwise, if it'sFalse
, Bob will win.
The beauty of this approach is that it considers the entire space of possible moves and outcomes, and it ensures that we do not overlook any strategy that could lead to a win. However, as mentioned, the specific problem of Nim has a well-known mathematical solution, which is more efficient than the general DFS approach.
Nonetheless, the DFS approach is a powerful technique when dealing with complex decision-making problems in games or situations where optimal strategies are not known in advance. It provides a methodical way to explore all possible outcomes and determine the best sequence of actions when players are acting optimally.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example where there are 3 piles of stones with the following number of stones in each pile: piles = [1, 3, 5]
. We will use this example to illustrate the solution approach.
-
At the beginning of the game, the Nim-sum is calculated by performing a bitwise XOR operation of the numbers of stones in each pile:
1 ^ 3 ^ 5
. -
Performing the calculation gives us
1 ^ 3 = 2
and then2 ^ 5 = 7
. Since 7 is not equal to 0, Alice can make a move to leave the Nim-sum at 0 for Bob. -
To find Alice's optimal move, we can look at the binary representation of the pile sizes and compare it with the Nim-sum. Let's do this:
- The binary representation of the piles:
1 -> 001
,3 -> 011
,5 -> 101
- The binary representation of the Nim-sum
7
:111
- The binary representation of the piles:
-
Alice will try to make a move that results in a new state with a Nim-sum of 0. She can do this by choosing a pile and removing enough stones to turn the current Nim-sum (
111
) to000
. For example, Alice can remove 4 stones from the third pile (5 stones), which gives us a new state of[1, 3, 1]
. -
The new Nim-sum after Alice's move is
1 ^ 3 ^ 1
, which equals0
, since1 ^ 1 = 0
and0 ^ 3 = 3
and finally3 ^ 0 = 3,
and in binary,3
is011
, which will result back to0
once XOR'ed with itself during Bob's turn. -
Now it is Bob's turn, and since the Nim-sum is
0
, any move he makes will leave a non-zero Nim-sum for Alice to exploit. -
If Bob removes 1 stone from any pile, the piles may look like
[1, 2, 1]
. Alice can then remove 2 stones from the second pile, leaving a single stone in two piles:[1, 1, 1]
, which has a Nim-sum of0
again. -
Ultimately, no matter how Bob plays, if Alice starts with a non-zero Nim-sum and both play optimally henceforth, Alice will always be able to return the game to a state where the Nim-sum is
0
at Bob's turn.
Using this example, we can see that the decision on the first move is crucial: given a non-zero Nim-sum, there is always a winning strategy for the player making the first move. Alice wins this game if she follows the strategy of always making a move to return the game to a state with a Nim-sum of 0
at the end of her turn.
Solution Implementation
1from typing import List
2from functools import lru_cache
3
4class Solution:
5 def nimGame(self, piles: List[int]) -> bool:
6 # Apply memoization to avoid recomputation of the same game states
7 @lru_cache(maxsize=None)
8 def can_win(st):
9 # Convert tuple to list to modify the piles
10 piles_list = list(st)
11 # Iterate over each pile
12 for i, pile in enumerate(piles_list):
13 # Try removing 1 to pile stones from the current pile
14 for stones_removed in range(1, pile + 1):
15 # Remove the stones for the current move
16 piles_list[i] -= stones_removed
17 # Check if opponent would lose from this state
18 if not can_win(tuple(piles_list)):
19 return True # If opponent loses, current player wins
20 # Undo the move
21 piles_list[i] += stones_removed
22 # If no winning move, return False
23 return False
24
25 # Start the game with the initial piles configuration
26 return can_win(tuple(piles))
27
28# Example usage:
29# sol = Solution()
30# result = sol.nimGame([1, 2, 3]) # Pass the initial piles as a list
31# print(result) # Outputs True or False depending on whether you can win the Nim game
32
1import java.util.Map;
2import java.util.HashMap;
3
4class Solution {
5 // Initialize a memoization map to store computed game states
6 private Map<Integer, Boolean> memoization = new HashMap<>();
7 // 'powersOfEight' array will store the powers of 8 (1, 8, 64, ...) for encoding the game state
8 private int[] powersOfEight = new int[8];
9
10 public Solution() {
11 // Precompute the powers of 8 up to 8^7
12 powersOfEight[0] = 1;
13 for (int i = 1; i < 8; ++i) {
14 powersOfEight[i] = powersOfEight[i - 1] * 8;
15 }
16 }
17
18 // Method to determine if the current player can win the nim game given the piles
19 public boolean nimGame(int[] piles) {
20 return depthFirstSearch(piles);
21 }
22
23 // Private method for a recursive depth-first search to simulate all possible moves
24 private boolean depthFirstSearch(int[] piles) {
25 // Calculate a unique state hash for the current state of the piles
26 int stateHash = computeStateHash(piles);
27 // If this state has been encountered before, return the stored result
28 if (memoization.containsKey(stateHash)) {
29 return memoization.get(stateHash);
30 }
31
32 // Try reducing each pile by a number of stones and perform DFS on the new state
33 for (int i = 0; i < piles.length; ++i) {
34 for (int stonesToRemove = 1; stonesToRemove <= piles[i]; ++stonesToRemove) {
35 piles[i] -= stonesToRemove;
36 // If the opponent cannot win after our move, we found a winning move
37 if (!depthFirstSearch(piles)) {
38 piles[i] += stonesToRemove; // Undo the move
39 memoization.put(stateHash, true); // Memoize the winning result
40 return true;
41 }
42 piles[i] += stonesToRemove; // Undo the move before trying next move
43 }
44 }
45
46 // If no winning move is found, this is a losing state
47 memoization.put(stateHash, false);
48 return false;
49 }
50
51 // Computes a unique hash for the current state of the piles using powers of 8
52 private int computeStateHash(int[] piles) {
53 int stateHash = 0;
54 // Encode the piles' state into a single integer using base 8 representation
55 for (int i = 0; i < piles.length; ++i) {
56 stateHash += piles[i] * powersOfEight[i];
57 }
58 return stateHash;
59 }
60}
61
1#include <vector>
2#include <unordered_map>
3#include <functional>
4
5using namespace std;
6
7class Solution {
8public:
9 bool nimGame(vector<int>& piles) {
10 unordered_map<int, int> memo; // Store calculated game results to avoid recomputation.
11 int powerOfEight[8] = {1}; // Precomputed powers of 8 for state encoding.
12 for (int i = 1; i < 8; ++i) {
13 powerOfEight[i] = powerOfEight[i - 1] * 8;
14 }
15
16 // Function to encode the current state of piles as a single integer.
17 auto encodeState = [&](vector<int>& piles) {
18 int state = 0;
19 for (int i = 0; i < piles.size(); ++i) {
20 state += piles[i] * powerOfEight[i];
21 }
22 return state;
23 };
24
25 // Depth-First Search (DFS) algorithm to determine if current player can win.
26 function<bool(vector<int>&)> dfs = [&](vector<int>& piles) {
27 int currentState = encodeState(piles);
28 if (memo.count(currentState)) {
29 return memo[currentState]; // Return precomputed result if available.
30 }
31 for (int i = 0; i < piles.size(); ++i) { // Try each pile.
32 for (int j = 1; j <= piles[i]; ++j) { // Try removing 1 to all stones from pile.
33 piles[i] -= j; // Remove stones from the current pile.
34 if (!dfs(piles)) { // If opponent loses from the resulting state...
35 piles[i] += j; // Backtrack to restore pile size.
36 return memo[currentState] = true; // Current player can win.
37 }
38 piles[i] += j; // Backtrack to restore pile size.
39 }
40 }
41 return memo[currentState] = false; // If no winning move found, current player loses.
42 };
43
44 return dfs(piles); // Start the game with the initial piles.
45 }
46};
47
48int main() {
49 vector<int> piles = {3, 4, 5};
50 Solution solution;
51 bool canWin = solution.nimGame(piles);
52 // canWin will be true or false depending on whether the player can win or not.
53 return 0;
54}
55
1// Represents the Nim game initial state
2function nimGame(piles: number[]): boolean {
3 // Base for representing the state
4 const base: number[] = Array(8).fill(1);
5 for (let i = 1; i < base.length; ++i) {
6 base[i] = base[i - 1] * 8;
7 }
8
9 // Converts a pile array into a unique state representation
10 const toState = (piles: number[]): number => {
11 let state = 0;
12 for (let i = 0; i < piles.length; ++i) {
13 state += piles[i] * base[i];
14 }
15 return state;
16 };
17
18 // Memoization cache to store known game states
19 const memo: Map<number, boolean> = new Map();
20
21 // Recursive function to determine if the current player can win from the given pile configuration
22 const canWin = (piles: number[]): boolean => {
23 const currentState = toState(piles);
24 if (memo.has(currentState)) {
25 return memo.get(currentState)!;
26 }
27 for (let i = 0; i < piles.length; ++i) {
28 for (let j = 1; j <= piles[i]; ++j) {
29 piles[i] -= j; // Try reducing the current pile by 'j'
30 if (!canWin(piles)) { // If the opponent can't win from here, current player wins
31 piles[i] += j; // Restore the pile before memoizing and returning
32 memo.set(currentState, true);
33 return true;
34 }
35 piles[i] += j; // Restore the pile for the next iteration
36 }
37 }
38 memo.set(currentState, false); // Current player can't win from this state
39 return false;
40 };
41
42 // Start the game by calling the recursive function with the initial piles configuration
43 return canWin(piles);
44}
45
Time and Space Complexity
The provided Python code implements a recursive solution to the Nim Game problem with memoization using the cache
decorator, which caches results of subproblems to avoid repetitive calculations.
Time Complexity
The time complexity of the recursive solution is determined by the number of possible states and the transitions between these states. Since the state is represented by the st
tuple, which is essentially the current configuration of piles
, the number of distinct states can be vast. For each state, the dfs
function iterates over each pile and attempts to reduce the number of stones in each pile by every possible number from 1
to x
(the size of the pile).
Let's suppose:
n
is the number of piles.m
is the maximum size of a single pile.
In the worst case, each pile can be reduced to zero in m
different ways, which gives us m^n
possible states (assuming piles can have different maximum sizes, in practice it's less due to combining identical pile sizes). The dfs
function is called once for each transition between these states, and because of memoization, each state is computed only once. Hence, the time complexity is O(m^n)
but in practice, it can be significantly less due to memoization and the fact that not all transitions occur due to pruning (when a winning state is found, further exploration of that branch is stopped).
Space Complexity
The space complexity is determined by the maximum size of the recursion stack and the space required to store the memoization cache. The recursion depth can go as deep as the number of possible transitions m^n
, in the worst case. The cache will need to store a result for each unique state of the piles
, thus requiring O(m^n)
space as well. Therefore, the total space complexity is O(m^n)
.
In summary:
- Time Complexity:
O(m^n)
- Space Complexity:
O(m^n)
Please note that in practice, the actual complexities may be lower due to memoization and pruning as explained above.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!