Stone Game in Java
In this tutorial, we will learn to design a stone game in Java. First of all, we will understand what is this game all about. We will grasp it through various examples.
This game is all about choosing the stone with the highest value. The stones are located in a row for which an input array is provided. The task of choosing the stones of the maximum values is assigned to two players. The player who collects stones of the maximum value is the winner of the game. Player 1 will play first, followed by player 2, and so on. A player can choose either 1 or 2, or 3 stones at once. The stones have to be selected from the left side only. The player must pick at least one stone. Our job is to choose which player will win the game if both players play optimally.
Example 1:
int arr1[] = {5, 4, 10, 19}
Output: The Match between player 1 and player2 is a draw
Explanation: Since stones are chosen from the left side and at max, only three stones are chosen, player 1 can only choose stones 1, 2 & 3. Thus, the total values of the stones chosen are5 + 4 + 10 = 19. Now, it is the turn of player 2. Player 2 can choose only stone 4, whose value is 19. Thus, both players getanidentical value. Hence, it is a draw.
Example 2:
int arr2[] = {10, -2, -2, 8}
Output: Player 1 is the winner of the game.
Explanation: Player 1 picks only the first stone from the left and leaves the remaining. Thus, player 1 has anoverall value of 10. Now comes the turn of player 2 to choose the stones. Since players can only choose stones from the left; Hence, player 2 has to pick stones off the values -2, -2, and 8. Thus, the overall value picked by player 2 is -2 + -2 + 8 = 4, which is less than 8. Hence, player 1 is the winner.
Example 3:
int arr3[] = {-8, 3, 4, 4}
Output: Player 2 is the winner of the game.
Explanation: To maximize the value, player 1 picks stones numbered 1, 2, and 3. Thus, collecting the maximum value of -8 + 3 + 4 = -1. Now, only one stone is left that is picked by player 2. The stone is of the value 4, which is more than player 1. Thus, player 2 is the winner of the game.
Example 4:
int arr4[] = {3, 4, 0, 4, 5, 7, 4}
Output: Player 1 is the winner of the game.
Explanation: To gain the maximum value, player 1 chooses the stones numbered 1 and 2 only. Thus, collecting the maximum value of 3 + 4 = 7. Now comes the turn of player 2, and player 2 picks stones of the values 0, 4, and 5. Here the total values 0 + 4 + 5 = 9. Again, the turn of player 1 arrives, and player 1 picks values 7 and 4. Thus, the total values collected by player 1 is 3 + 7 + 4 = 14, which is greater than 9. Hence, player 1 is the winner of the game.
Implementation
Approach 1: Using Recursion
In this approach, every possible case for the player is considered.
The cases can be:
- Only one stone is picked by a player.
- Two stones are picked.
- All three stones are picked by a player.
The final value is the maximum or the highest value collected by the player.
Now, let us see a program for the same.
A Java Program
public class StoneGame
{
private int compute(int i, int[] num)
{
//computing the size of the array
int size = num.length;
// dealing with the base case
if(i>= size)
{
return 0;
}
// if the player picks only one stone
int one = Integer.MIN_VALUE;
// if the player picks two stones
int two = Integer.MIN_VALUE;
// if the player picks three stones
int three = Integer.MIN_VALUE;
// picked one stone and performed the
// further computation
one = num[i] - compute(i + 1, num);
if((i + 1) < size)
{
// picked two stones at a time and performing
// the further computation
two = num[i] + num[i + 1] - compute(i + 2, num);
}
if((i + 2) < size)
{
// picked 3 stones at a time and further calculations are being performed
three = num[i] + num[i + 1] + num[i + 2] - compute(i + 3, num);
}
// picking the stone with maximum values between one, two, and three
return Math.max(one, Math.max(two, three));
}
public int stoneGameSoln(int[] stoneVal)
{
int res = compute(0, stoneVal);
if(res == 0)
{
// if 0 is returned, means its a draw
return 0;
}
if(res > 0)
{
// return value 1 means player 1 is the winner of the game
return 1;
}
// return value 2 means player 2 is the winner of the game
return 2;
}
// beginning of the main method
public static void main(String[] argvs)
{
// creation of an object of the class StoneGame
StoneGameobj = new StoneGame();
int arr1[] = {6, 4, 10, 18};
int size = arr1.length;
System.out.println("Among the stones having the following values: ");
for(int j = 0; j < size; j++)
{
System.out.print(arr1[j] + " ");
}
System.out.println();
int res = obj.stoneGameSoln(arr1);
if(res == 0)
{
System.out.println("The match between Player 1 and Player 2 is a DRAW");
}
else if(res == 1)
{
System.out.println("Player 1 is the winner of the game.");
}
else
{
System.out.println("Player 2 is the winner of the game.");
}
System.out.println();
int arr2[] = {9, -2, -2, 8};
size = arr2.length;
System. out.println("Among the stones having the following values:");
for(int i = 0; i< size; i++)
{
System.out.print(arr2[i] + " ");
}
System.out.println();
res = obj.stoneGameSoln(arr2);
if(res == 0)
{
System. out.println("The match between Player 1 and Player 2 is a DRAW");
}
else if(res == 1)
{
System.out.println("Player 1 is the winner of the game.");
}
else
{
System.out.println("Player 2 is the winner of the game.");
}
System.out.println();
int arr3[] = {-8, 3, 7, 4};
size = arr3.length;
System. out.println("Among the stones having the following values:");
for(int i = 0; i< size; i++)
{
System.out.print(arr3[i] + " ");
}
System.out.println();
res = obj.stoneGameSoln(arr3);
if(res == 0)
{
System. out.println("The match between Player 1 and Player 2 is a DRAW");
}
else if(res == 1)
{
System.out.println("Player 1 is the winner of the game.");
}
else
{
System.out.println("Player 2 is the winner of the game.");
}
System.out.println();
int arr4[] = {11, 22, 0, 33, 66, 77, 44};
size = arr4.length;
System.out.println("Among the stones having the following values: ");
for(int j = 0; j < size; j++)
{
System.out.print(arr4[j] + " ");
}
System.out.println();
res = obj.stoneGameSoln(arr4);
if(res == 0)
{
System.out.println("The match between Player 1 and Player 2 is a DRAW");
}
else if(res == 1)
{
System.out.println("Player 1 is the winner of the game.");
}
else
{
System.out.println("Player 2 is the winner of the game.");
}
}
}
Output:
Explanation: This program has exponential time complexity;thus, it is not practical to use this approach for a larger number of inputs.
Approach 2: Dynamic Programming
public class StoneGame1
{
public int stoneGameSoln(int storeArr[])
{
int size = storeArr.length;
int dp[] = new int[size];
// it contains the sum of the values of
// the stones of the array stoneArr
int sums[] = new int[size + 1];
for (int j = 0; j < size; j++)
{
sums[j + 1] = sums[j] + storeArr[j];
}
dp[size - 1] = storeArr[size - 1];
if (size > 1)
{
dp[size - 2] = storeArr[size - 2] + Math.max(storeArr[size - 1], 0);
for (int j = size - 3; j >= 0; j--)
{
dp[j] = Integer.MIN_VALUE;
for (int k = 1; k <= 3; k++)
{
// total_score contains the sum of the values of the
// stone earned by the player
// for k = 1 only 1 stone is picked
// for k = 2, 2 stones are picked
// for k = 3, 3 stones are picked
int total_score = sums[j + k] - sums[j];
int a1 = j + k + 1 <size ?dp[j + k + 1] : 0;
int a2 = j + k + 2 <size ?dp[j + k + 2] : 0;
int a3 = j + k + 3 <size ?dp[j + k + 3] : 0;
// the players are playing optimally. Thus,
// the minimum between a1, a2, a3 is to be picked
dp[j] = Math.max(dp[j], total_score + Math.min(a1, Math.min(a2, a3)));
}
}
}
if ((2 * dp[0]) > sums[size])
{
return 1;
}
else if ((2 * dp[0]) < sums[size])
{
return 2;
}
else
{
return 0;
}
}
// beginning of the main method
public static void main(String[] argvs)
{
// creation of an object of the class named StoneGame1
StoneGame1 obj = new StoneGame1();
int arr1[] = {6, 4, 10, 18};
int size = arr1.length;
System.out.println("Among the stones having the following values:");
for(int i = 0; i< size; i++)
{
System.out.print(arr1[i] + " ");
}
System.out.println();
int res = obj.stoneGameSoln(arr1);
if(res == 0)
{
System.out.println("There is a tie between player 1 and player 2");
}
else if(res == 1)
{
System.out.println("Player 1 is the winner of the game.");
}
else
{
System.out.println("Player 2 is the winner of the game.");
}
System.out.println();
int arr2[] = {9, -2, -2, 8};
size = arr2.length;
System.out.println("Among the stones having the following values:");
for(int i = 0; i< size; i++)
{
System.out.print(arr2[i] + " ");
}
System.out.println();
res = obj.stoneGameSoln(arr2);
if(res == 0)
{
System.out.println("There is a tie between player 1 and player 2");
}
else if(res == 1)
{
System.out.println("Player 1 is the winner of the game.");
}
else
{
System.out.println("Player 2 is the winner of the game.");
}
System.out.println();
int arr3[] = {-8, 3, 7, 4};
size = arr3.length;
System.out.println("Among the stones having the following values:");
for(int i = 0; i< size; i++)
{
System.out.print(arr3[i] + " ");
}
System.out.println();
res = obj.stoneGameSoln(arr3);
if(res == 0)
{
System.out.println("There is a tie between player 1 and player 2");
}
else if(res == 1)
{
System.out.println("Player 1 is the winner of the game.");
}
else
{
System.out.println("Player 2 is the winner of the game.");
}
System.out.println();
int arr4[] = {11, 22, 0, 33, 66, 77, 44};
size = arr4.length;
System. out.println("Among the stones having the following values:");
for(int i = 0; i< size; i++)
{
System.out.print(arr4[i] + " ");
}
System.out.println();
res = obj.stoneGameSoln(arr4);
if(res == 0)
{
System.out.println("There is a tie between player 1 and player 2");
}
else if(res == 1)
{
System.out.println("Player 1 is the winner of the game.");
}
else
{
System.out.println("Player 2 is the winner of the game.");
}
}
}
Output:
Explanation: The time complexity of the program is O(3 * N). The space complexity here is O(2N). N represents the total number of elements present in the stone array.
The space complexity can be optimized by using variables instead of arrays in a program.
Approach 3: Optimising the space complexity
public class StoneGame
{
public int stoneGameSoln(int storeArr[])
{
// calculating the length of the array
int size = storeArr.length;
int first1 = 0; // contains the result
int second2 = 0;
int third3 = 0;
for(int j = size - 1; j >= 0; j--)
{
// one for picking only 1 stone
int one = Integer.MIN_VALUE;
// two for picking 2 stones
int two = Integer.MIN_VALUE;
// three for picking 3 stones
int three = Integer.MIN_VALUE;
one = storeArr[j]- first1;
if((j + 1) < size)
{
two = storeArr[j] + storeArr[j + 1] - second2;
}
if((j + 2) < size)
{
three = storeArr[j] + storeArr[j + 1] + storeArr[j + 2] - third3;
}
int t = Math.max(one, Math.max(two, three));
third3 = second2;
second2 = first1;
first1 = t;
}
if(first1 == 0)
{
return 0;
}
else if(first1 > 0)
{
return 1;
}
else
{
return 2;
}
}
// beginning of the main method
public static void main(String[] argvs)
{
// creation of an object of the class named StoneGame
StoneGameobj = new StoneGame();
int arr1[] = {6, 4, 10, 18};
int size = arr1.length;
System.out.println("Among the stones having the following values: ");
for(int i = 0; i< size; i++)
{
System.out.print(arr1[i] + " ");
}
System.out.println();
int res = obj.stoneGameSoln(arr1);
if(res == 0)
{
System.out.println("The match between Player 1 and Player 2 is a DRAW");
}
else if(res == 1)
{
System.out.println("Player 1 is the winner of the game.");
}
else
{
System.out.println("Player 2 is the winner of the game.");
}
System.out.println();
int arr2[] = {9, -2, -2, 8};
size = arr2.length;
System.out.println(" Among the stones having the following values:");
for(int i = 0; i< size; i++)
{
System.out.print(arr2[i] + " ");
}
System.out.println();
res = obj.stoneGameSoln(arr2);
if(res == 0)
{
System.out.println("The match between Player 1 and Player 2 is a DRAW");
}
else if(res == 1)
{
System.out.println("Player 1 is the winner of the game.");
}
else
{
System.out.println("Player 2 is the winner of the game.");
}
System.out.println();
int arr3[] = {-8, 3, 7, 4};
size = arr3.length;
System.out.println("Among the stones having the following values: ");
for(int i = 0; i< size; i++)
{
System.out.print(arr3[i] + " ");
}
System.out.println();
res = obj.stoneGameSoln(arr3);
if(res == 0)
{
System.out.println("The match between Player 1 and Player 2 is a DRAW");
}
else if(res == 1)
{
System.out.println("Player 1 is the winner of the game.");
}
else
{
System.out.println("Player 2 is the winner of the game.");
}
System.out.println();
int arr4[] = {11, 22, 0, 33, 66, 77, 44};
size = arr4.length;
System.out.println("Among the stones having the following values: ");
for(int i = 0; i< size; i++)
{
System.out.print(arr4[i] + " ");
}
System.out.println();
res = obj.stoneGameSoln(arr4);
if(res == 0)
{
System.out.println("The match between Player 1 and Player 2 is a DRAW");
}
else if(res == 1)
{
System.out.println("Player 1 is the winner of the game.");
}
else
{
System.out.println("Player 2 is the winner of the game.");
}
}
}
Output:
Explanation: The space complexity of this program is O(1) due to the usage of variables instead of arrays and the time complexity is O(3 * N).