Grundy Numbers, also recognized as Nimbers, play a vital role in addressing problems related to combinatorial game theory in C++. They signify the smallest excluded (mex) value for game positions, which in turn decides whether a player is in a winning or losing position. Through the computation of Grundy Numbers, individuals can anticipate the most advantageous moves and evaluate the results of the game.
Example:
Input: Starting with 5 items.
Output:
Grundy Number for 5 is: 1
Starting with 5 items is a winning position.
Explanation:
For a stack of 5 objects, the Grundy Number is 1, signifying a position advantageous for winning. This implies that the player has the ability to execute a move that puts the opponent at a disadvantage (Grundy Number 0). Through strategic removal of 1, 2, or 3 items, the player in the current turn dictates the result of the game.
Approach 1: Dynamic Programming with Memoization.
Algorithm:
Step 1: Establish the Objective: The goal is to assess whether the initial pile size n represents a winning or losing scenario. This will involve computing Grundy Numbers for every pile size from 1 to n. A Grundy Number of 0 denotes a losing position, meaning there is no possible winning move, whereas any different number indicates a winning situation.
Base Scenario: In the case of a stack with zero items, the Grundy Number is determined as 0 since there are no further moves to make. Consequently, the player faces defeat, leading to this being categorized as a losing state.
Step 3: Iterative Computation for Every Location: When dealing with a pile of size n, analyze the available actions: eliminating 1, 2, or 3 objects. Calculate the Grundy Number for each action on the resulting pile size (for example, if one item is removed, determine the Grundy Number for n-1). Save these calculated Grundy Numbers in a set. This phase comprehensively encompasses all potential results stemming from the existing pile size.
Calculate the Minimum Excludant (mex): After determining the Grundy Numbers, the subsequent task involves identifying the smallest non-negative integer that is absent from this set. Referred to as the "minimum excludant" or mex, this value signifies the lowest Grundy Number that cannot be reached from the present state, thus serving as the optimal choice for the player taking the opposing side.
Implementing Step 5 involves employing memoization as a strategy for enhancing efficiency. By storing precomputed Grundy Numbers in a memoization table (represented as an array), we can bypass redundant recalculations. This way, if the Grundy Number for a particular pile size has already been computed, we can retrieve it from the table instead of recomputing it.
Step 6: Conclusion: Based on the calculated Grundy Number for the initial pile size n: If the number is 0, it represents an unfavorable position (as no move exists that would result in a disadvantage for the opponent). If the number is greater than 0, it signifies a favorable position (indicating that the player can make a move that puts the opponent in a disadvantageous position).
Program:
#include <iostream>
#include <vector>
#include <unordered_set>
int calculateGrundy(int n, std::vector<int>& grundy) {
if (n == 0) return 0; // Base case
if (grundy[n] != -1) return grundy[n]; // Use memoized result if available
std::unordered_set<int> nextGrundy;
if (n >= 1) nextGrundy.insert(calculateGrundy(n - 1, grundy));
if (n >= 2) nextGrundy.insert(calculateGrundy(n - 2, grundy));
if (n >= 3) nextGrundy.insert(calculateGrundy(n - 3, grundy));
int mex = 0;
while (nextGrundy.count(mex)) mex++; // Find the minimum excluded value
grundy[n] = mex; // Memoize the result
return grundy[n];
}
int main() {
int n = 5; // Starting with a pile of 5 items
std::vector<int> grundy(n + 1, -1); // Memoization table
int result = calculateGrundy(n, grundy);
std::cout << "Grundy Number for " << n << " is: " << result << "\n";
if (result == 0)
std::cout << "Starting with " << n << " items is a losing position.\n";
else
std::cout << "Starting with " << n << " items is a winning position.\n";
return 0;
}
Output:
Grundy Number for 5 is: 1
Starting with 5 items is a winning position.
Complexity Analysis:
Time Complexity:
The time complexity of the algorithm is O(n) because of the utilization of memoization. Every Grundy Number ranging from 0 to n is calculated just once, leveraging previously stored outcomes. The evaluation of potential moves (such as eliminating 1, 2, or 3 items) is constant at O(1), which enhances the efficiency of the method, particularly for higher n values.
Space Complexity:
The space complexity is O(n) as we save Grundy Numbers for every pile size from 0 to n in an array. This caching table prevents unnecessary recalculations. The extra space needed is minimal since only a fixed collection is necessary to monitor potential Grundy values for each location.
Approach 2: Bottom-Up Dynamic Programming
The Bottom-Up Dynamic Programming strategy offers a powerful and resourceful method for calculating Grundy Numbers across different pile sizes, eliminating the necessity for recursive function calls. Rather than initiating the process from the final pile size and recursively reducing it, this method commences from the smallest conceivable pile (0 items) and progressively constructs upwards.
Program:
#include <iostream>
#include <vector>
#include <unordered_set>
int main() {
int n = 5; // Starting with a pile of 5 items
std::vector<int> grundy(n + 1, 0); // Memoization table for Grundy Numbers
for (int i = 1; i <= n; ++i) {
std::unordered_set<int> nextGrundy;
if (i >= 1) nextGrundy.insert(grundy[i - 1]);
if (i >= 2) nextGrundy.insert(grundy[i - 2]);
if (i >= 3) nextGrundy.insert(grundy[i - 3]);
// Calculate mex (minimum excluded value)
int mex = 0;
while (nextGrundy.count(mex)) mex++;
grundy[i] = mex; // Store the computed Grundy Number
}
int result = grundy[n];
std::cout << "Grundy Number for " << n << " is: " << result << "\n";
if (result == 0)
std::cout << "Starting with " << n << " items is a losing position.\n";
else
std::cout << "Starting with " << n << " items is a winning position.\n";
return 0;
}
Output:
Grundy Number for 5 is: 1
Starting with 5 items is a winning position.
Explanation:
To begin, we establish the initial pile size, denoted as n, indicating the quantity of items in the starting pile (in this instance, it's 5).
Following that, we set up a vector called grundy with a capacity of n+1. Each entry in this vector will hold the Grundy Number corresponding to a particular pile size. The vector is set to zero initially, with grundy[0] = 0. This starting scenario indicates that a pile containing zero items is considered a losing position due to the absence of available moves.
Iterative Computation of Grundy Numbers:
We implement an iterative process starting from 1 and continuing up to n. Each iteration, denoted by i representing the current size of the pile, involves determining the Grundy Number by considering various moves (such as removing 1, 2, or 3 items).
For monitoring the potential outcomes, we maintain an unordered set named nextGrundy to store the Grundy Numbers of all feasible positions reachable from the current pile size i. This collection facilitates the identification of the smallest non-negative integer absent in nextGrundy, referred to as the minimum excludant or "mex."
Exploring Possible Moves:
For each pile size i, the player can remove 1, 2, or 3 items, as long as i is large enough to allow that move:
- If i >= 1, we consider the state reached by removing 1 item, which is grundy[i - 1].
- If i >= 2, we consider removing 2 items, resulting in the state grundy[i - 2].
- If i >= 3, we consider removing 3 items, leading to grundy[i - 3].
- We insert the Grundy Numbers of these reachable states into the nextGrundy set, ensuring we have a collection of possible outcomes from the current pile size.
Calculating the Smallest Excluded Value (SEV):
- The SEV, also known as the minimum excludant (mex), refers to the tiniest non-negative integer absent in the nextGrundy set. Initially set to 0, we iterate through increments until encountering a value not within nextGrundy.
- This determined SEV serves as the Grundy Number for the ongoing pile size i, denoted by grundy[i] = mex. The rationale behind selecting this value lies in its status as the smallest Grundy Number unattainable through any feasible move, strategically positioning the player by preventing the opponent from reaching it.
Upon evaluating Grundy Numbers for all pile sizes up to n, the Grundy Number assigned to the initial pile size, grundy[n], provides insight into whether it represents a winning or losing scenario. In cases where grundy[n] equals zero, the starting position is considered a losing one since there are no available moves that would result in the opponent being in a losing position. Conversely, if grundy[n] is non-zero, it signifies a winning position as there is a move available that leads to a situation where the opponent is left with no winning choices.
Complexity analysis:
Time Complexity
The time complexity of this bottom-up dynamic programming method is O(n).
Iterating Once Through n Values:
When iterating from 1 to n, we compute the Grundy Number for each pile size i in a single pass.
Fixed Operations Per Pile Size:
When considering each pile size i, we specifically evaluate three potential actions: eliminating 1, 2, or 3 items. The effort required for each of these actions remains consistent.
Determining the minimum excluded value (mex) is also an operation with a fixed time complexity, as the available moves (1, 2, or 3 items) are fixed and not dependent on the size n.
In general, as we carry out a consistent level of effort for every stack size up to n, the total time complexity remains O(n).
Space Complexity
The space complexity is O(n).
Grundy Array:
To store Grundy Numbers for each pile size ranging from 0 to n, we initialize an array called grundy with a size of n+1. This array requires O(n) space allocation.
Temporary Assign nextGrundy:
- The unsorted collection nextGrundy is employed to hold potential results for every stack size i. Nevertheless, as we're solely examining three potential actions (1, 2, or 3 items), the utmost size of nextGrundy remains consistent, i.e., O(1), no matter the value of n.
- Consequently, the memory allocation of nextGrundy is minimal and has no impact on expanding space intricacy.
Consequently, the overall space complexity is primarily determined by the grundy array, leading to a space complexity of O(n).
