https://www.hackerrank.com/challenges/game-of-stones-1/problem
Game Of Stones.
Two players called P1 and P2 are playing a game with a starting number of stones. Player 1 always plays first, and the two players move in alternating turns. The game's rules are as follows:
In a single move, a player can remove either 2, 3, or 5 stones from the game board.
If a player is unable to make a move, that player loses the game.
Given the starting number of stones, find and print the name of the winner. P1 is named First and P2 is named Second. Each player plays optimally, meaning they will not make a move that causes them to lose the game if a winning move exists.
For example, if n = 4, P1 can make the following moves:
P1 removes 2 stones leaving 2. P2 will then remove 2 stones and win.
P1 removes 3 stones leaving 1. P2 cannot move and loses.
P1 would make the second play and win the game.
Function Description
Complete the gameOfStones function in the editor below. It should return a string, either First or Second.
gameOfStones has the following parameter(s):
n: an integer that represents the starting number of stones
Input Format
The first line contains an integer , the number of test cases. Each of the next lines contains an integer , the number of stones in a test case.
Constraints
1<= n,t <= 100
Output Format
On a new line for each test case, print First if the first player is the winner. Otherwise print Second.
My question
In this Document from link, Players can take 2, 3 or 5 stones each turn.
But, if the number of stones and the number of conditions are different for each cases, how do i write the code?
For example. Case 1, players can take 2, 3 or 5 stones, and Case 2, players can take 2, 4, 7, 9 stones.
and Code will pass both case.
Input Case 1:
3 //total conditions of stones can take
2 3 5 //player can take 2, 3 or 5 stones
8 // Number of cases of number of starting stones
1
2
3
4
5
6
7
10
Case 2:
4 //total conditions of stones can take
2 3 7 9 //players can take 2, 3,7 or 9 stones
5 // Number of cases of number of starting stones
5
6
7
10
15
And Code will pass both cases. How should I write the coding that satisfies this case?
I wrote my solution to your new problem in Swift. If you're not familiar with it, hopefully it is similar enough to languages you use to be useful.
This is a solution to the general case.
// This is an internal function that also takes a dictionary of results so that
// it can remember solutions it has already found
func game(n: Int, conditions: [Int], result: inout [Int : String]) -> String {
// Have we seen this answer before? If so, just return it
if let answer = result[n] {
return answer
}
if n < conditions.min()! {
// I can't move because the number of stones left is fewer than
// I'm allowed to take
result[n] = "Second" // to speed up the solution, remember this result
return "Second"
} else if conditions.contains(n) {
// I can take all of the stones, so I win
result[n] = "First" // to speed up the solution, remember this result
return "First"
} else {
// Try taking each of the stones I'm allowed to take, and see
// if that causes my opponent to lose
for take in conditions {
let leave = n - take
// If the number of stones I leave causes the opponent to lose, I win
if leave > 0 && game(n: leave, conditions: conditions, result: &result) == "Second" {
result[n] = "First" // to speed up the solution, remember this result
return "First"
}
}
}
// No way for me to win, so I come in second.
result[n] = "Second" // to speed up the solution, remember this result
return "Second"
}
// Generate a dictionary to store already generated answers, and call the
// internal recursive routine
func gameOfStones(n: Int, conditions: [Int]) -> String {
var result = [Int : String]()
return game(n: n, conditions: conditions, result: &result)
}
print(gameOfStones(n: 4, conditions: [2, 3, 5])) // "First"
print(gameOfStones(n: 6, conditions: [3, 7, 13])) // "Second"