Stone Game In C++

In this tutorial, we will explore the Stone game implementation using C++.

Problem Statement:

Bob and Alice participate in a game involving a row of stone piles. The row consists of an even number of piles, each containing a positive integer number of stones. The objective of the game is to end up with the highest total number of stones. Since all piles have an odd number of stones, there will always be a definitive winner. Alice starts the game, and Bob takes his turn after her. In each turn, a player can opt to take all the stones from either the beginning or the end of the row. The game continues until there are no more piles left to be taken, and the player with the most stones at that point is declared the winner.

It evaluates as true in the event of Alice emerging as the victor in the game, and false if Bob emerges as the winner, under the assumption that both players employ optimal strategies.

Let stones piles in a row be like:

Example 1:

Piles: {5, 3, 4, 5}

Player A:

• ✅ A will start the game.
• ✅ They can choose either pile 1 or pile 4.
• ✅ If A chooses pile 1: Stones = 5.
• ✅ Stones = 5.

Player B:

• ✅ If A chooses pile 1, the options for B are pile 2 or pile 4.
• ✅ If B chooses pile 2: Stones = 3. Otherwise, if B chooses pile 4, stones = 5.
• ✅ If B chooses pile 4, A will choose pile 3 and win with a total of 9 stones and B with 8 stones.
• ✅ Else A will choose pile 4 and win with a total of 10 stones and B will have 7 stones.
• ✅ Stones = 3.
• ✅ Otherwise, if B chooses pile 4, stones = 5.

Example 2:

Piles: {6,2,4,6}

• ✅ The winner is A.

Constraints:

• ✅ 2 <= p.length <= 500
• ✅ length is even.
• ✅ 1 <= p[i] <= 500
• ✅ sum(p[i]) is odd.

1. Dynamic Programming Method:

Algorithm:

• ✅ First, create a list with piles of stones in it.
• ✅ Make a 2D-DP array and fill it with zero values.
• ✅ When the remaining piles are p[i], p[i+1],... p[j], each player has two options; as a result, the player's probability can be computed by comparing j-i to n modulo 2.
• ✅ Player A chooses p[i] or p[j] to get the most stones possible.
• ✅ To reduce the number of stones, Player B selects p[i] or p[j].
• ✅ In case A has more stones, it return true.

Pseudo code:

n = piles array size 
construct an array called p with a size of n + 1 and a matrix called dyp with a size of n x n. 
for i from 0 to n - 1. 
p[i + 1] := p[i] + piles[i] 
for l in the interval 2 to n − 
Increase i and j by 1, for i=0; j:= l - 1, j < n. 
dyp[i, j] := max of piles[j] + p[j] - p[i] - dyp[i, j - 1] and piles[i] + p[i + 2] - p[j] + dyp[i + 1, j] 
when dyp[0, n - 1] > dyp[0, n - 1] - pre[n], return true.

Example 1:

Let's consider an example to demonstrate the stone game using C++ programming language.

#include<bits/stdc++.h>
using namespace std;
class StoneGame{
public:
    bool stoneGame(vector<int>& stones) {
        int n = stones.size();
        int dp[n+2][n+2];
        memset(dp, 0, sizeof(dp));
        for(int span = 1; span <= n; ++span) {
            for(int start = 0, end = span - 1; end < n; ++start, ++end) {
                int parity = (end + start) % 2; 
                if(parity == 0) 
                    dp[start+1][end+1] = max(stones[start] + dp[start+2][end+1], stones[end] + dp[start+1][end]);
                else
                    dp[start+1][end+1] = min(stones[start] + dp[start+2][end+1], stones[end] + dp[start+1][end]); 
            }
        }
        return dp[1][n] > 0;
    }
};

int main(){
    StoneGame game;
    vector<int> stones = {6, 2, 4, 6};
    if(game.stoneGame(stones)){
        cout<<"True";
    }
    else{
        cout<<"False";
    }
}

Output:

Complexity Analysis:

Time Complexity:

• ✅ O(n^2)

Space Complexity:

• ✅ O(n^2)

2. Observed Method:

When Player A chooses the initial stone pile in a scenario where there are an even number of heaps, it's crucial to understand that Player A has the flexibility to opt for either odd or even piles consistently.

Assume:

Player B can choose between piles[1] or piles[n-1] if Player A opts for selecting piles at even indices and picks the initial pile at index 0. Player B is restricted to choosing piles at odd positions, while Player A consistently has the choice to select piles at even positions in every round.

Algorithm:

• ✅ It initializes a list or array that contains piles of stones.
• ✅ Return True.

Example 2:

#include<bits/stdc++.h>
using namespace std;
class Rock{
public:
    bool rockMatch(vector<int>& rocks) {
        return true;
    }
};
int main(){
    Rock r;
    vector<int> rocks = {5, 3, 4, 5};
    if(r.rockMatch(rocks)){
        cout<<"True";
    }
    else{
        cout<<"False";
    }
}

Output:

Complexity Analysis:

Time Complexity:

Space Complexity:

Conclusion:

In summary, determining the victor of the stone game played by two individuals can be successfully achieved by utilizing either of the two tactics detailed earlier. These represent distinct methods for resolving the stone game challenge.