Game in Space

#### Ninja is in space with his super spaceship having unlimited fuel. Ninja initially has a health level ‘H’ and his spaceship has an armour ‘A’. He decides to play a game, where at any instant he can be only on one of the 3 planets: VENUS, MARS or SATURN. At every unit of time, he has to change his location and you can assume he can change his location instantly. Each planet has different effects on health and armour which are :

``````Venus: Decreases health by 4, decreases armour by 8.
Mars: Increases health by 3, increases armour by 2.
Saturn: Decreases health by 10, increases armour by 5.
``````

#### Note :

``````You can choose any of the 3 planets during your first move.
``````
##### Input format :
``````The first line of input contains a single integer T, representing the number of test cases.

Then the T test cases follow.

The first line of every test case contains 2 single space-separated integers representing initial health and initial armour respectively.
``````
##### Output format :
``````For every test case, print a single integer representing the maximum time Ninja can survive.

The output of each test case is printed in a separate line.
``````

#### Note :

``````You don’t have to print anything, it has already been taken care of. Just implement the given function.
``````
###### Constraints :
``````1 <= T <= 10
1 <= H, A <= 10^3

Where ‘T’ denotes the number of test cases,  ‘H’ is the initial health and ‘A’ is the initial armour.

Time Limit: 1sec
``````
#TataConsultancyServices(Tcs)#AssistantSystemEngineer CodingNinjas
Answered Mar 08, 2022
Recursive

The idea is simple, we will check all the possible ways of choosing planets with the help of recursion and find out which combination gives maximum time.

Along with this, we will prefer to move Mars whenever possible as it is always beneficial to make a move to Mars.

• So we will make a recursive function named SOLVE which will receive 3 parameters ‘H’, ‘A’ and ‘MOVE_MARS’.
• Initialize a bool variable ‘MOVE_MARS’ = 0 ,where ‘MOVE_MARS’ == 0 indicates we can move to Mars .
• Base Case :
• When ‘A’ <= 0 or ‘H’ <= 0 then we will return -1 as we can’t move to any other planet now and we have already added 1 in time for this move.
• Check the value of the ‘MOVE_MARS’:
• If it is equal to 0, it means we are moving to Mars.
• Then increase ‘H’ by 3, ‘A’ by 2 and set ‘MOVE_MARS’ = 1. We then make a recursive call.
• Return 1 + the result received in above call.
• If the ‘MOVE_MARS’ is equal to 1, it means we have to move either to Saturn or Venus.
• Make two calls, one to Venus and other to Saturn by changing variables according to their effect and setting ‘MOVE_MARS’ = 0.
• Return 1+ the results received in the above call.
• Return the value returned by SOLVE.
Space Complexity: O(n)Explanation:

O(min(H, A) where ‘H’ is the initial health and ‘A’ is the initial armour.

The maximum depth of recursion stack space can be O(min(H, A)).

Time Complexity: O(2^n)Explanation:

O(2^min(H, A)) where ‘H’ is the initial health and ‘A’ is the initial armour.

As in each recursive call, we are making further at most 2 recursive calls till the value of ‘A’ or ‘H‘ is greater than 0.

Report CodingNinjas
Answered Mar 08, 2022
Recursion + Memoization

Our last approach was very simple and easy, but its time complexity was of exponential order. We can improve our solution by taking care of the overlapping subproblems. Thus, we will eliminate the need for solving the same subproblems again and again by storing them in a lookup table. This approach is known as Memoization

• So we will make a recursive function named SOLVE which will receive 3 parameters ‘H’, ‘A’ and ‘MOVE_MARS’.
• We will initialize a 2-D array, say ‘MEMO’ with -1. Where MEMO[i][j] equal to -1 means the current state is not explored. Otherwise, it will store the maximum time Ninja can survive with health = ’i’ and armour = ’j’.
• Initialize a bool variable ‘MOVE_MARS’ = 0 ,where ‘MOVE_MARS’ == 0 indicates we can move to Mars .
• Base Case :
• When ‘A’ <= 0 or ‘H’ <= 0 then we will return -1 as we can’t move to any other planet now and we have already added 1 in time for this move.
• We will check the value of ‘MEMO[H][A]’ :
• If it is not equal to -1, then we can say we have already explored the result for the current state, so return ‘MEMO[H][A]’.
• Check the value of the ‘MOVE_MARS’:
• If it is equal to 0, it means we are moving to Mars.
• Then increase ‘H’ by 3, ‘A’ by 2 and set ‘MOVE_MARS’ = 1. We then make a recursive call.
• Set ‘MEMO[H][A]’ = 1+result received in above call and return ‘MEMO[H][A]’.
• If the ‘MOVE_MARS’ is equal to 1, it means we have to move either to Saturn or Venus.
• Make two calls, one to Venus and other to Saturn by changing variables according to their effect and setting ‘MOVE_MARS’ = 0.
• Set ‘MEMO[H][A]’ = 1+maximum of results received in above call and return ‘MEMO[H][A]’.
• Return ‘MEMO[H][A]’.
Space Complexity: O(1)Explanation:

O(1).

We are using a 2-D array of size 2000*2000 in each case as the maximum value of H+A can be 2000.

Time Complexity: OtherExplanation:

O(min(H, A)), where  ‘H’ is the initial health and ‘A’ is initial armour.

We make at most 2 recursive calls till the value of ‘A’ or ‘H‘ is greater than 0 and are storing the already calculated results in ‘memo’. Hence the overall time complexity will be O(min(H, A)).

Java (SE 1.8)
``````/*
Time Complexity: O(min(H, A))
Space Complexity: O(1)
Where H is the initial health and A is initial armour.
*/
import java.util.Arrays;
public class Solution {
static int solve(int h, int a, int moveMars, int[][] memo) {
// Base Case
if (h <= 0 || a <= 0) {
return -1;
}
// If we have already explored the current state
if (memo[h][a] != -1) {
return memo[h][a];
}
// Recursive calls
if (moveMars == 0) {
// Moving to Mars
return memo[h][a] = 1 + solve(h + 3, a + 2, 1, memo);
} else {
// Moving to Venus
int venus = 1 + solve(h - 4, a - 8, 0, memo);
// Moving to saturn
int saturn = 1 + solve(h - 10, a + 5, 0, memo);
// Return the maximum of Venus and Saturn
return memo[h][a] = Math.max(venus, saturn);
}
}
public static Integer gameSpace(Integer h, Integer a) {
int[][] memo = new int;
for (int i = 0; i < 2000; i++) {
Arrays.fill(memo[i], -1);
}
int ans = solve(h, a, 0, memo);
return ans;
}
}
``````

Python (3.5)
``````'''
Time Complexity: O(min(H, A))
Space Complexity: O(1)
Where H is the initial health and A is initial armour.
'''
def solve(h, a, moveMars, memo):
# Base Case
if (h <= 0 or a <= 0):
return -1
# If we have already explored the current state
if (memo[h][a] != -1):
return memo[h][a]
# Recursive calls
if (moveMars == 0):
# Moving to Mars
memo[h][a] = 1 + solve(h + 3, a + 2, 1, memo)
return memo[h][a]
else:
# Moving to Venus
venus = 1 + solve(h - 4, a - 8, 0, memo);
# Moving to saturn
saturn = 1 + solve(h - 10, a + 5, 0, memo);
# Return the maximum of Venus and Saturn
memo[h][a] = max(venus, saturn)
return memo[h][a]
def gameSpace(h, a):
# Intializing the memo table
memo = [[-1 for j in range(2000)] for i in range(2000)]
solve(h, a, 0, memo)
return memo[h][a]
``````

C++ (g++ 5.4)
``````/*
Time Complexity: O(min(H, A))
Space Complexity: O(1)
Where H is the initial health and A is initial armour.
*/
int solve(int h, int a, bool moveMars, vector>& memo) {
// Base Case
if (h <= 0 || a <= 0) {
return -1;
}
// If we have already explored the current state
if (memo[h][a] != -1) {
return memo[h][a];
}
// Recursive calls
if (moveMars == 0) {
// Moving to Mars
return memo[h][a] = 1 + solve(h + 3, a + 2, 1, memo);
} else {
// Moving to Venus
int venus = 1 + solve(h - 4, a - 8, 0, memo);
// Moving to saturn
int saturn = 1 + solve(h - 10, a + 5, 0, memo);
// Return the maximum of Venus and Saturn
return memo[h][a] = max(venus, saturn);
}
}
int gameSpace(int h, int a) {
// Intializing the memo table
vector> memo = vector> (2000, vector  (2000, -1));
solve(h, a, 0, memo);
return memo[h][a];
}``````
Report CodingNinjas
Answered Mar 08, 2022
Greedy Approach

In the earlier approach, we tried to find all the possible solutions and select the one with maximum survival time, but we really do not need to find all the possible solutions. Instead, we will use some greedy approach. We can see that it is always beneficial to go to Mars so for every odd second, we will go to Mars. Now for even seconds, we are left with Venus and Saturn. So we will choose Venus if possible else we will choose Saturn, as Venus decreases health less than Saturn.

• Initialize an integer variable ‘TURN’ = 0.
• Run an infinite while loop:
• If ‘TURN’ is even (we can go to Mars) then do:
• Increase ‘H’ by 3 and ‘A’ by 2.
• Increase ‘TURN’ by 1.
• If ‘TURN’ is odd, it means we have to choose between Saturn or Venus.  So, do:
• If ‘H’ > 4 and ‘A’ > 8 (we can go to Venus):
• Decrease ‘H’ by 4 and ‘A’ by 8.
• Increase ‘TURN’ by 1.
• Else if ‘H’ > 10 (we can go to Saturn):
• Decrease ‘H’ by 10 and increase ‘A’ by 5.
• Increase ‘TURN’ by 1.
• If none of the above two conditions is met :
• We can not make a move, so break the loop.
• Return ‘TURN’.
Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra memory.

Time Complexity: O(n)Explanation:

O(min(H, A)), where  ‘H’ is the initial health and ‘A’ is the initial armour.

As we will keep on iterating till either of ‘A’ or ‘H’ is greater than 0.

Java (SE 1.8)
``````/*
Time Complexity: O(min(H, A))
Space Complexity: O(1)
Where H is the intial health and A is the initial armour.
*/
public class Solution {
public static Integer gameSpace(Integer h, Integer a) {
int turn = 0;
// Running a loop while h > 0 and a > 0
while (h > 0 && a > 0) {
// We can move to Mars
if (turn % 2 == 0) {
h += 3;
a += 2;
}
// We can not move to Mars
else {
// If we can move to Venus, we will go to Venus
if (h > 4 && a > 8) {
h -= 4;
a -= 8;
}
// If we can go to Saturn
else if (h > 10) {
h -= 10;
a += 5;
}
// If we can not make a move
else {
break;
}
}
// Increase turn by 1
turn++;
}
return turn;
}
}
``````

Python (3.5)
``````'''
Time Complexity: O(min(H, A))
Space Complexity: O(1)
Where H is the intial health and A is the initial armour.
'''
def gameSpace(h, a):
turn = 0
# Running a loop while h > 0 and a > 0
while (h and a):
# We can move to Mars
if (turn % 2 == 0):
h += 3
a += 2
# We can not move to Mars
else:
# If we can move to Venus, we will go to Venus
if (h > 4 and a > 8):
h -= 4
a -= 8
# If we can go to Saturn
elif (h > 10):
h -= 10
a += 5
# If we can not make a move
else:
break
# Increase turn by 1
turn += 1
return turn``````

C++ (g++ 5.4)
``````/*
Time Complexity: O(min(H, A))
Space Complexity: O(1)
Where H is the intial health and A is the initial armour.
*/
int gameSpace(int h, int a) {
int turn = 0;
// Running a loop while h > 0 and a > 0
while (h and a) {
// We can move to Mars
if (turn % 2 == 0) {
h += 3;
a += 2;
}
// We can not move to Mars
else {
// If we can move to Venus, we will go to Venus
if (h > 4 and a > 8) {
h -= 4;
a -= 8;
}
// If we can go to Saturn
else if (h > 10) {
h -= 10;
a += 5;
}
// If we can not make a move
else {
break;
}
}
// Increase turn by 1
turn++;
}
return turn;
}``````
Report